summaryrefslogtreecommitdiff
path: root/ace/RB_Tree.h
blob: a58a07d540fec84c9f526ef3fd8f38deb78660cb (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
/* -*- C++ -*- */
// $Id$

// ============================================================================
//
// = LIBRARY
//    ace
//
// = FILENAME
//    RB_Tree.h
//
// = AUTHOR
//     Chris Gill
//
// ============================================================================

#ifndef ACE_RB_TREE_H
#define ACE_RB_TREE_H

#include "ace/ACE.h"
#include "ace/Functor.h"

#if !defined (ACE_LACKS_PRAGMA_ONCE)
# pragma once
#endif /* ACE_LACKS_PRAGMA_ONCE */

class ACE_RB_Tree_Node_Base
{
public:
  enum RB_Tree_Node_Color {RED, BLACK};
};

template <class KEY, class T>
class ACE_RB_Tree_Node : public ACE_RB_Tree_Node_Base
{
  // = TITLE
  //   Implements a node in a Red-Black Tree ADT.
public:

  // Initialization and termination methods.

  ACE_RB_Tree_Node (const KEY &k, const T &t);
  // Constructor.

  ~ACE_RB_Tree_Node (void);
  // Destructor.

  KEY &key (void);
  // Key accessor.

  T &item (void);
  // Item accessor.

  void color (RB_Tree_Node_Color c);
  // Set color of the node.

  RB_Tree_Node_Color color (void);
  // Get color of the node.

  ACE_RB_Tree_Node<KEY, T> *parent (void);
  // Accessor for node's parent pointer.

  void parent (ACE_RB_Tree_Node<KEY, T> * p);
  // Mutator for node's parent pointer.

  ACE_RB_Tree_Node<KEY, T> *left (void);
  // Accessor for node's left child pointer.

  void left (ACE_RB_Tree_Node<KEY, T> *l);
  // Mutator for node's left child pointer.

  ACE_RB_Tree_Node<KEY, T> *right (void);
  // Accessor for node's right child pointer.

  void right (ACE_RB_Tree_Node<KEY, T> * r);
  // Mutator for node's right child pointer

private:

  KEY k_;
  // The key.

  T t_;
  // The item.

  RB_Tree_Node_Color color_;
  // Color of the node.

  ACE_RB_Tree_Node<KEY, T> *parent_;
  // Pointer to node's parent.

  ACE_RB_Tree_Node<KEY, T> *left_;
  // Pointer to node's left child.

  ACE_RB_Tree_Node<KEY, T> *right_;
  // Pointer to node's right child.
};

template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>
class ACE_RB_Tree
{
  // = TITLE
  //   Implements a Red-Black Tree ADT, according to T. H. Corman,
  //   C. E. Leiserson, and R. L. Rivest, "Introduction to Algorithms"
  //   1990, MIT, chapter 14.
  //
  // = Description
  //   If an ACE allocator is passed to the RB_Tree constructor, it is used 
  //   for all dynamic allocations done by the tree.
public:
  // = Initialization and termination methods.
  ACE_RB_Tree ();
  // Constructor.

  ACE_RB_Tree (const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &rbt);
  // Copy constructor.

  virtual ~ACE_RB_Tree (void);
  // Destructor.

  void operator= (const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &rbt);
  // Assignment operator.

  virtual int lessthan (const KEY &k1, const KEY &k2);
  // Less than comparison function for keys, using comparison functor.

  T* find (const KEY &k);
  // Returns a pointer to the item corresponding to the
  // given key, or 0 if it cannot find the key in the tree.

  T* insert (const KEY &k, const T &t);
  // Inserts a *copy* of the key and the item into the tree: both the
  // key type KEY and the item type T must have well defined semantics
  // for copy construction.  The default implementation also requires that
  // the key type support welll defined < semantics.  This method returns a
  // pointer to the inserted item copy, or 0 if an error occurred.
  // NOTE: if an identical key already exists in the tree, no new item
  // is created, and the returned pointer addresses the existing item
  // associated with the existing key.

  int remove (const KEY &k);
  // Removes the item associated with the given key from the tree and
  // destroys it.  Returns 1 if it found the item and successfully
  // destroyed it, 0 if it did not find the item, or -1 if an error
  // occurred.

  void clear (void);
  // Destroys all nodes and sets the root pointer null.

  // These could all be made private methods by making the corresponding
  // class template instantiations friends, but there are some problems
  // with this on certain compilers: leave them all public for now.

// private:

  void RB_rotate_right (ACE_RB_Tree_Node<KEY, T> * x);
  // Method for right rotation of the tree about a given node.

  void RB_rotate_left (ACE_RB_Tree_Node<KEY, T> * x);
  // Method for left rotation of the tree about a given node.

  void RB_delete_fixup (ACE_RB_Tree_Node<KEY, T> * x);
  // Method for restoring Red-Black properties after deletion.

  ACE_RB_Tree_Node<KEY, T> * 
    RB_tree_successor (ACE_RB_Tree_Node<KEY, T> *x) const;
  // Method to find the successor node of the given node in the tree.

  ACE_RB_Tree_Node<KEY, T> * 
    RB_tree_predecessor (ACE_RB_Tree_Node<KEY, T> *x) const;
  // Method to find the predecessor node of the given node in the
  // tree.

  ACE_RB_Tree_Node<KEY, T> * 
    RB_tree_minimum (ACE_RB_Tree_Node<KEY, T> *x) const;
  // Method to find the minimum node of the subtree rooted at the
  // given node.

  ACE_RB_Tree_Node<KEY, T> * 
    RB_tree_maximum (ACE_RB_Tree_Node<KEY, T> *x) const;
  // Method to find the maximum node of the subtree rooted at the
  // given node.

  ACE_RB_Tree_Node<KEY, T> * find_node (const KEY &k);
  // Returns a pointer to a matching node if there is one, a pointer
  // to the node under which to insert the item if the tree is not
  // empty and there is no such match, or 0 if the tree is empty.

  void RB_rebalance (ACE_RB_Tree_Node<KEY, T> * x);
  // Rebalance the tree after insertion of a node.

  // Private members.

  ACE_RB_Tree_Node<KEY, T> *root_;
  // The root of the tree.

  COMPARE_KEYS compare_keys_;
  // Comparison functor for comparing nodes in the tree.

};

template <class KEY, class T, class COMPARE_KEYS, class ACE_LOCK>
class ACE_RB_Tree_Iterator
{
  // = TITLE
  //   Implements an iterator for a Red-Black Tree ADT.
public:
  // = Initialization and termination methods.
  ACE_RB_Tree_Iterator (const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &tree);
  // Constructor.

  ~ACE_RB_Tree_Iterator (void);
  // Destructor.

  KEY *key (void);
  // Accessor for key of node under iterator (if any).

  T *item (void);
  // Accessor for item of node under iterator (if any).

  int first (void);
  // Move to the first item in the tree.

  int last (void);
  // Move to the last item in the tree.

  int next (void);
  // Move to the next item in the tree.

  int previous (void);
  // Move to the previous item in the tree.

  int is_done (void);
  // Returns 0 if the iterator is positioned over a valid ACE_RB_Tree
  // node, returns 1 if not.

private:
  // = Declare private and do not define.

  // Explicitly prevent assignment and copy construction of iterators.
  ACE_UNIMPLEMENTED_FUNC (
    ACE_RB_Tree_Iterator (const ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK> &))
  ACE_UNIMPLEMENTED_FUNC (
    void operator = (const ACE_RB_Tree_Iterator<KEY, T, COMPARE_KEYS, ACE_LOCK> &))

  // Private members.

  const ACE_RB_Tree<KEY, T, COMPARE_KEYS, ACE_LOCK> &tree_;
  // Reference to the ACE_RB_Tree over which we're iterating.

  ACE_RB_Tree_Node <KEY, T> *node_;
  // Pointer to the node currently under the iterator.

};

#if defined (__ACE_INLINE__)
#include "ace/RB_Tree.i"
#endif /* __ACE_INLINE__ */

#if defined (ACE_TEMPLATES_REQUIRE_SOURCE)
#include "ace/RB_Tree.cpp"
#endif /* ACE_TEMPLATES_REQUIRE_SOURCE */

#if defined (ACE_TEMPLATES_REQUIRE_PRAGMA)
#pragma implementation ("RB_Tree.cpp")
#endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */

#endif /* ! defined (ACE_RB_TREE_H) */