zeda_tree.h

Go to the documentation of this file.

/* ZEDA - Elementary Data and Algorithms
 * Copyright (C) 1998 Tomomichi Sugihara (Zhidao)
 */
#ifndef __ZEDA_TREE_H__
#define __ZEDA_TREE_H__

#include <zeda/zeda_misc.h>

__BEGIN_DECLS

/* ********************************************************** *//* ************************************************** */

/* ********************************************************** *//* ******************************************************* */

#define zTreeClass(node_t,data_t) \
typedef struct __##node_t{\
  struct __##node_t *parent;\
  struct __##node_t *child[2];\
  uint size;\
  data_t data;\
} node_t;\
\
__EXPORT node_t *node_t##Init(node_t *node);\
__EXPORT void node_t##Destroy(node_t *tree);\
__EXPORT node_t *node_t##NodeAlloc(data_t *val)

#define zTreeClassMethod(node_t,data_t,init,destroy) \
static data_t *(* _##node_t##DataInit)(data_t *) = init;\
static void (* _##node_t##DataDestroy)(data_t *) = destroy;\
\
node_t *node_t##Init(node_t *node){\
  if( _##node_t##DataInit ) _##node_t##DataInit( &(node)->data );\
  node->parent = node->child[0] = node->child[1] = NULL;\
  node->size = 0;\
  return node;\
}\
\
static void __##node_t##NodeDestroy(node_t *node){\
  if( node->child[0] )\
    __##node_t##NodeDestroy( node->child[0] );\
  if( node->child[1] )\
    __##node_t##NodeDestroy( node->child[1] );\
  if( _##node_t##DataDestroy ) _##node_t##DataDestroy( &(node)->data );\
  free( node );\
}\
\
void node_t##Destroy(node_t *tree){\
  if( tree->child[0] )\
    __##node_t##NodeDestroy( tree->child[0] );\
  node_t##Init( tree );\
}\
\
node_t *node_t##NodeAlloc(data_t *val){\
  node_t *node;\
  if( !( node = zAlloc( node_t, 1 ) ) ){\
    ZALLOCERROR();\
    return NULL;\
  }\
  node_t##Init( node );\
  memcpy( &node->data, val, sizeof(data_t) );\
  return node;\
}

#define zHeapClass(node_t,data_t) \
zTreeClass(node_t,data_t); \
__EXPORT node_t *node_t##AddComplete(node_t *tree, data_t *val);\
__EXPORT node_t *node_t##UpHeap(node_t *tree, node_t *node, int (* cmp)(node_t*,node_t*,void*), void *util);\
__EXPORT node_t *node_t##AddHeap(node_t *tree, data_t *val, int (* cmp)(node_t*,node_t*,void*), void *util);\
__EXPORT node_t *node_t##DownHeap(node_t *node, int (* cmp)(node_t*,node_t*,void*), void *util);\
__EXPORT node_t *node_t##DeleteHeap(node_t *tree, int (* cmp)(node_t*,node_t*,void*), void *util);\
__EXPORT void node_t##Heapify(node_t *tree, int (* cmp)(node_t*,node_t*,void*), void *util)

#define zHeapClassMethod(node_t,data_t,init,destroy) \
zTreeClassMethod(node_t,data_t,init,destroy) \
static void __##node_t##BindParentChild(node_t *parent, int id, node_t *child){\
  if( ( parent->child[id] = child ) ) child->parent = parent;\
}\
\
static void __##node_t##NodeSwapHeap(node_t *node, int cid){\
  node_t *parent, *tmp;\
  int id;\
  parent = node->parent;\
  id = _zTreeParentID( node );\
  __##node_t##BindParentChild( parent, id, node->child[cid] );\
  __##node_t##BindParentChild( node, cid, node->child[cid]->child[cid] );\
  __##node_t##BindParentChild( parent->child[id], cid, node );\
  tmp = node->child[1-cid];\
  __##node_t##BindParentChild( node, 1-cid, parent->child[id]->child[1-cid] );\
  __##node_t##BindParentChild( parent->child[id], 1-cid, tmp );\
}\
\
node_t *node_t##AddComplete(node_t *tree, data_t *val){\
  node_t *node, *np_new;\
  uint mask, cid;\
  if( !( np_new = node_t##NodeAlloc( val ) ) ) return NULL;\
  if( ++tree->size == 1 ){\
    __##node_t##BindParentChild( tree, 0, np_new );\
    return tree->child[0];\
  }\
  _zTreeInitHeapMask( tree, &mask );\
  for( node=tree->child[0]; ; node=node->child[cid], mask>>=1 ){\
    cid = mask & tree->size ? 1 : 0;\
    if( mask == 1 ) break;\
  }\
  __##node_t##BindParentChild( node, cid, np_new );\
  return np_new;\
}\
\
node_t *node_t##UpHeap(node_t *tree, node_t *node, int (* cmp)(node_t*,node_t*,void*), void *util){\
  while( node->parent != tree && !cmp( node->parent, node, util ) )\
    __##node_t##NodeSwapHeap( node->parent, _zTreeParentID( node ) );\
  return node;\
}\
\
node_t *node_t##AddHeap(node_t *tree, data_t *val, int (* cmp)(node_t*,node_t*,void*), void *util){\
  return node_t##UpHeap( tree, node_t##AddComplete( tree, val ), cmp, util );\
}\
\
node_t *node_t##DownHeap(node_t *node, int (* cmp)(node_t*,node_t*,void*), void *util){\
  uint cid;\
  while( node->child[0] ){\
    cid = !node->child[1] ? 0 : ( cmp( node->child[0], node->child[1], util ) ? 0 : 1 );\
    if( cmp( node, node->child[cid], util ) ) break;\
    __##node_t##NodeSwapHeap( node, cid );\
  }\
  return node;\
}\
\
node_t *node_t##DeleteHeap(node_t *tree, int (* cmp)(node_t*,node_t*,void*), void *util){\
  node_t *ret, *np;\
  uint mask, cid;\
  _zTreeInitHeapMask( tree, &mask );\
  for( np=tree->child[0]; np; mask>>=1, np=np->child[cid] ){\
    cid = mask & tree->size ? 1 : 0;\
    if( mask == 1 ) break;\
  }\
  ret = tree->child[0];\
  if( !np ){\
    tree->child[0] = NULL;\
  } else if( np->child[cid] ){\
    __##node_t##BindParentChild( tree, 0, np->child[cid] );\
    np->child[cid] = NULL;\
    __##node_t##BindParentChild( tree->child[0], 0, ret->child[0] );\
    __##node_t##BindParentChild( tree->child[0], 1, ret->child[1] );\
    node_t##DownHeap( tree->child[0], cmp, util );\
  }\
  ret->parent = ret->child[0] = ret->child[1] = NULL;\
  tree->size--;\
  return ret;\
}\
\
static void __##node_t##Heapify(node_t *tree, int (* cmp)(node_t*,node_t*,void*), void *util){\
  if( zTreeIsLeaf( tree ) ) return;\
  if( tree->child[0] ) __##node_t##Heapify( tree->child[0], cmp, util );\
  if( tree->child[1] ) __##node_t##Heapify( tree->child[1], cmp, util );\
  node_t##DownHeap( tree, cmp, util );\
}\
\
void node_t##Heapify(node_t *tree, int (* cmp)(node_t*,node_t*,void*), void *util){\
  if( zTreeIsEmpty( tree ) ) return;\
  __##node_t##Heapify( tree->child[0], cmp, util );\
}

#define zTreeIsEmpty(t) ( (t)->size == 0 )
#define zTreeIsLeaf(t)  ( !(t)->child[0] && !(t)->child[1] )

#define _zTreeParentID(n) ( (n)->parent->child[0] == (n) ? 0 : ( (n)->parent->child[1] == (n) ? 1 : -1 ) )

#define _zTreeInitHeapMask(t,mask) do{\
  *(mask) = 1 << ( sizeof(int)*8 - 2 );\
  while( !( *(mask) & (t)->size ) ) *(mask) >>= 1;\
  *(mask) >>= 1;\
} while(0)

#define zTreeInit(node_t,node)                 node_t##Init( node )
#define zTreeDestroy(node_t,tree)              node_t##Destroy( tree )
#define zTreeNodeAlloc(node_t,val)             node_t##NodeAlloc( val )
#define zTreeAddComplete(node_t,tree,val)      node_t##AddComplete( tree, val )
#define zTreeUpHeap(node_t,tree,node,cmp,util) node_t##UpHeap( tree, node, cmp, util )
#define zTreeAddHeap(node_t,tree,val,cmp,util) node_t##AddHeap( tree, val, cmp, util )
#define zTreeDownHeap(node_t,node,cmp,util)    node_t##DownHeap( node, cmp, util )
#define zTreeDeleteHeap(node_t,tree,cmp,util)  node_t##DeleteHeap( tree, cmp, util )
#define zTreeHeapify(node_t,tree,cmp,util)     node_t##Heapify( tree, cmp, util )

__END_DECLS

#endif /* __ZEDA_TREE_H__ */