| 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 |
|
|---|
