HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_SplayTree.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_SplayTree.h (C++)
7  *
8  * COMMENTS:
9  *
10  * This code implements a generic c++ class of splay tress.
11  * It is based on C code written by David Brower, daveb@rtech.uucp 1/88
12  * who based it on pascal code written by Douglas W. Jones who
13  * based it on algorithms originally taken from "Self Adjusting Binary
14  * Trees" by DD Sleator and RE Tarjan (ACM SIGAC TBoston, Apr 1983).
15  *
16  */
17 
18 #ifndef __UT_SplayTree_h__
19 #define __UT_SplayTree_h__
20 
21 
22 #include "UT_API.h"
23 class utSplayNode;
24 
26 
27 public:
28 
29  // Constructors and destructor:
30 
31  explicit UT_SplayTree(int (*fcomp)(const void *, const void *));
32  UT_SplayTree(const UT_SplayTree &tree); // shallow
33  virtual ~UT_SplayTree(void);
34 
35  // Modification methods
36 
37  int add(const void *, unsigned maxDepth = 0);
38 
39  // remove node from tree, deallocate it and return its data
40  // 0 if not found. If passed 0, it removes the root.
41  const void *remove(const void * = 0);
42 
43  // delete every node from the tree
44  void clear(void);
45 
46  // Add a tree to us or remove it:
47  UT_SplayTree &operator+=(const UT_SplayTree &tree);
48  UT_SplayTree &operator-=(const UT_SplayTree &tree);
49 
50  // Assign another tree to us:
51  UT_SplayTree &operator=(const UT_SplayTree &tree);
52 
53  // query methods
54 
55  // apply the function to each node in the tree
56  // terminate if a non-zero result is obtained
57  // Return the result returned from the last node
58  // if no nodes, return 0
59 
60  int traverse(int (*func)(const void *));
61  int traverse(int (*func)(const void *,void *),void *data);
62  int traverseBackward(int (*func)(const void *));
63  int traverseBackward(int (*func)(const void *,void *),
64  void *data);
65 
66  // return the node containing the data, 0 if not found
67  const void *find(const void *data) const;
68 
69  int entries(void) const {return count; }
70 
71 private:
72 
73  // insert a node into the tree. If maxdepth > 0, we do a
74  // splay if we find a branch that exceeds this maximum depth
75  void insertNode(utSplayNode *, unsigned maxDepth);
76  void deleteNode(utSplayNode *);
77  utSplayNode *findNode(const void *data);
78  utSplayNode *removeHead(utSplayNode **);
79  void splay(utSplayNode *);
80  void splayToDepth(unsigned);
81  int splayToDepth(utSplayNode *, unsigned, unsigned);
82 
83  // member data
84  int (*myFcomp)(const void *, const void *);
85  utSplayNode *myRoot; // root of binary tree
86  int count; // size of tree
87  int myNumAdded; // Number added since last splayToDepth
88 };
89 
90 #endif
#define UT_API
Definition: UT_API.h:13
GLboolean * data
Definition: glcorearb.h:130
GLint GLsizei count
Definition: glcorearb.h:404
GLenum func
Definition: glcorearb.h:782
typedef int
Definition: png.h:1175
int entries(void) const
Definition: UT_SplayTree.h:69