home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / xwphescr.zip / XWPH0208.ZIP / include / helpers / tree.h < prev    next >
C/C++ Source or Header  |  2002-06-14  |  2KB  |  100 lines
  1.  
  2. /*
  3.  *@@sourcefile tree.h:
  4.  *      header file for tree.c (red-black balanced binary trees).
  5.  *      See remarks there.
  6.  */
  7.  
  8. #if __cplusplus
  9. extern "C" {
  10. #endif
  11.  
  12. #ifndef XWPTREE_INCLUDED               //  Allow multiple inclusions
  13.     #define XWPTREE_INCLUDED
  14.  
  15.     #include "helpers\simples.h"
  16.             // V0.9.19 (2002-06-13) [umoeller]
  17.  
  18.     typedef enum { BLACK, RED } nodeColor;
  19.  
  20.     /*
  21.      *@@ TREE:
  22.      *      tree node.
  23.      *
  24.      *      To use the tree functions, all your structures
  25.      *      must have a TREE structure as their first member.
  26.      *
  27.      *      Example:
  28.      *
  29.      +      typedef struct _MYTREENODE
  30.      +      {
  31.      +          TREE        tree;
  32.      +          char        acMyData[1000];
  33.      +      } MYTREENODE, *PMYTREENODE;
  34.      *
  35.      *      See tree.c for an introduction to the tree functions.
  36.      */
  37.  
  38.     typedef struct _TREE
  39.     {
  40.         struct _TREE    *left,
  41.                         *right,
  42.                         *parent;
  43.         nodeColor       color;          // the node's color (BLACK, RED)
  44.  
  45.         ULONG           ulKey;          // the node's key (data)
  46.  
  47.     } TREE, *PTREE;
  48.  
  49.     #if defined(__IBMC__) || defined(__IBMCPP__)
  50.         #define TREEENTRY _Optlink
  51.     #else
  52.         // EMX or whatever: doesn't know calling conventions
  53.         #define TREEENTRY
  54.     #endif
  55.  
  56.     #define STATUS_OK                   0
  57.     #define STATUS_DUPLICATE_KEY        -1
  58.     #define STATUS_INVALID_NODE         -2
  59.  
  60.     typedef int TREEENTRY FNTREE_COMPARE(ULONG ul1, ULONG ul2);
  61.  
  62.     //  Function prototypes
  63.     void treeInit(TREE **root,
  64.                   PLONG plCount);
  65.  
  66.     int TREEENTRY treeCompareKeys(ULONG  ul1, ULONG ul2);
  67.  
  68.     int TREEENTRY treeCompareStrings(ULONG  ul1, ULONG ul2);
  69.  
  70.     int treeInsert(TREE **root,
  71.                    PLONG plCount,
  72.                    TREE *x,
  73.                    FNTREE_COMPARE *pfnCompare);
  74.  
  75.     int treeDelete(TREE **root,
  76.                    PLONG plCount,
  77.                    TREE *z);
  78.  
  79.     TREE* treeFind(TREE *root,
  80.                    ULONG key,
  81.                    FNTREE_COMPARE *pfnCompare);
  82.  
  83.     TREE* treeFirst(TREE *r);
  84.  
  85.     TREE* treeLast(TREE *r);
  86.  
  87.     TREE* treeNext(TREE *r);
  88.  
  89.     TREE* treePrev(TREE *r);
  90.  
  91.     TREE** treeBuildArray(TREE* pRoot,
  92.                           PLONG plCount);
  93.  
  94. #endif
  95.  
  96. #if __cplusplus
  97. }
  98. #endif
  99.  
  100.