1 : /* _________________________________________________________________________
2 : *
3 : * UTILIB: A utility library for developing portable C++ codes.
4 : * Copyright (c) 2001, Sandia National Laboratories.
5 : * This software is distributed under the GNU Lesser General Public License.
6 : * For more information, see the README file in the top UTILIB directory.
7 : * _________________________________________________________________________
8 : */
9 :
10 : /**
11 : * \file AbstractSplayTree.h
12 : *
13 : * Defines the utilib::AbstractSplayTree class
14 : */
15 :
16 : #ifndef utilib_AbstractSplayTree_h
17 : #define utilib_AbstractSplayTree_h
18 :
19 : #include <utilib/utilib_config.h>
20 : #include <utilib/std_headers.h>
21 :
22 : #ifdef _MSC_VER
23 : /* TODO - Try compiling with msvc and find out if this is needed.*/
24 : #include "crtdbg.h"
25 : #endif
26 :
27 : #include <utilib/_generic.h>
28 : #include <utilib/AbstractSplayTree.h>
29 : #include <utilib/exception_mngr.h>
30 : #include <utilib/compare.h>
31 : #include <utilib/PackBuf.h>
32 :
33 : namespace utilib {
34 :
35 : /// A simple macro used internally for the splay tree code.
36 : #define node_size(x) (((x)==NULL) ? 0 : ((x)->size))
37 :
38 :
39 : /**
40 : * Implements an abstract class for defining the core operations of a
41 : * top-down splay tree.
42 : *
43 : * This is adapted from code developed by D. Sleator, which itself is
44 : * adapted from simple top-down splay, at the bottom of 669 of
45 : * \if GeneratingLaTeX Sleator and Tarjan~\cite{SleTar85}. \endif
46 : * \if GeneratingHTML SleTar85. \endif
47 : * Sleator's code can be aquired from
48 : *
49 : * http://www-cgi.cs.cmu.edu/afs/cs/user/sleator/www/home.html
50 : */
51 : template <class T, class KEY>
52 : class AbstractSplayTree
53 : {
54 : public:
55 :
56 : /// Constructor, which specifies a name for the tree.
57 : explicit AbstractSplayTree(const char* nameBuff = "Unnamed");
58 :
59 : /// Destructor.
60 262 : virtual ~AbstractSplayTree() {clear();}
61 :
62 : /// Copy operator
63 : AbstractSplayTree<T,KEY>& operator=(const AbstractSplayTree<T,KEY>& tree);
64 :
65 : /// Returns \c true if the tree is empty and \c false otherwise.
66 : bool empty() const {return (tree == 0);}
67 :
68 : /// Returns \c true if the tree is not empty and \c false otherwise.
69 : operator bool() const {return (tree != 0);}
70 :
71 : /// Returns the size of the splay tree.
72 400659 : int size() const { return (tree ? tree->size : 0); }
73 :
74 : /// Return the value of \c Sense.
75 : OrderSense sense() {return Sense;}
76 :
77 : /// Set the value of \c Sense.
78 : void setSense(OrderSense sense_) {Sense=sense_;}
79 :
80 : /// Perform a splay operation starting from the root of the tree.
81 117558 : void splay(const KEY& key)
82 117558 : {tree = exec_splay(&key,tree);}
83 :
84 : /**
85 : * Return the item in the splay tree with rank \a r.
86 : * Returns a null item if a bad rank value is passed in.
87 : */
88 : virtual T* find_rank(int r);
89 :
90 : /**
91 : * Return the item in the splay tree with rank \a r.
92 : * Returns a null item if a bad rank value is passed in.
93 : */
94 10701 : virtual const T* find_rank(int r) const
95 : {
96 10701 : AbstractSplayTree<T,KEY>* Tthis = const_cast< AbstractSplayTree<T,KEY>* >(this);
97 10701 : T* tmp = Tthis->find_rank(r);
98 10701 : return tmp;
99 : }
100 :
101 : /**
102 : * Return the item in the splay tree with the given key.
103 : * Returns null if the tree is empty or if the item is not
104 : * in the tree.
105 : */
106 0 : virtual T* find(const KEY& key)
107 : {
108 0 : splay(key);
109 0 : if (!tree) return tree;
110 0 : if (tree->compare(key) == 0) return tree;
111 0 : else return (T*)0;
112 : }
113 :
114 : /// Return the top of the splay tree.
115 270584 : T* top() {return tree;}
116 :
117 : /// Return the top of the splay tree.
118 : const T* top() const {return tree;}
119 :
120 : /**
121 : * Add a key to the splay tree and return the splay tree item
122 : * that contains it.
123 : */
124 170701 : virtual T* add(KEY& key)
125 170701 : {return insert(&key);}
126 :
127 : /**
128 : * Remove a splay tree item with the given key.
129 : * The status flag is \c true if the key was found and \c false
130 : * otherwise.
131 : */
132 0 : virtual void remove(KEY& key, bool& status)
133 : {
134 0 : T* tmp = find(key);
135 0 : if (tmp) extract(tmp,status);
136 0 : else status = false;
137 : }
138 :
139 : /**
140 : * Remove a splay tree item.
141 : * The status flag is \c true if the item was found and \c false
142 : * otherwise.
143 : */
144 99883 : virtual void remove(T*& item, bool& status)
145 : {
146 99883 : if (!item)
147 0 : status = false;
148 : else {
149 99883 : extract(item,status);
150 99883 : item = 0;
151 : }
152 : }
153 :
154 : /**
155 : * Remove a splay tree item and return the item's key.
156 : * The status flag is \c true if the item was found and \c false
157 : * otherwise.
158 : */
159 0 : virtual void remove(T*& item, KEY& key, bool& status)
160 : {
161 0 : if (!item)
162 0 : status = false;
163 : else {
164 0 : key = item->key();
165 0 : extract(item,status);
166 0 : item = 0;
167 : }
168 : }
169 :
170 : /// Returns the rank of the top (0...size-1)
171 117558 : int rank(const KEY& key)
172 : {
173 117558 : splay(key);
174 117558 : if (!tree) return 0;
175 117558 : return (tree->left ? tree->left->size : 0);
176 : }
177 :
178 : ///
179 626 : void balance() const
180 : {
181 626 : int n = size()/2;
182 626 : find_rank(n);
183 : }
184 :
185 : /// Empty out a splay tree.
186 : void clear(T* ptr=0);
187 :
188 : protected:
189 :
190 : // void print_tree(ostream& os, int d, T* item);
191 :
192 :
193 : /**
194 : * Search for an item with a given key on a tree rooted at \a item.
195 : * If an item is found in the tree, it is splayed to the root.
196 : * Otherwise, the item put at the root is the last one before \c NULL
197 : * that would have been reached in a normal binary search.
198 : * (It is a neighbor of i in the tree.) This method of splaying
199 : * is very convenient for facilitating a variety of other operations.
200 : */
201 : T* exec_splay(const KEY* key, T* item);
202 :
203 : /// Add a key to the tree.
204 : virtual T* insert(KEY* key);
205 :
206 : /**
207 : * Remove a splay tree item.
208 : * The status flag is \c true if the item was found and \c false
209 : * otherwise.
210 : */
211 : virtual void extract(T* item, bool& status);
212 :
213 : /// The current root of the splay tree.
214 : T* tree;
215 :
216 : /// Specifies the ordering within the tree: increasing or decreasing.
217 : OrderSense Sense;
218 :
219 : /// The name of the class instance.
220 : const char* name;
221 :
222 : };
223 :
224 :
225 :
226 :
227 :
228 : template <class T, class KEY>
229 262 : AbstractSplayTree<T,KEY>::AbstractSplayTree(const char* nameBuff)
230 : : tree(0),
231 : Sense(increasing),
232 262 : name(nameBuff)
233 : {
234 262 : if (!name)
235 0 : name = "";
236 : }
237 :
238 :
239 :
240 : template <class T, class KEY>
241 : AbstractSplayTree<T,KEY>&
242 : AbstractSplayTree<T,KEY>::operator=(
243 381 : const AbstractSplayTree<T,KEY>& t)
244 : {
245 381 : if (t.tree) {
246 : // Balance the tree first to avoid pathological behavior
247 381 : t.balance();
248 381 : tree = t.tree->clone();
249 : }
250 : else
251 0 : tree = 0;
252 381 : Sense = t.Sense;
253 381 : name = "";
254 381 : return *this;
255 : }
256 :
257 :
258 : template <class T, class KEY>
259 699794 : T* AbstractSplayTree<T,KEY>::exec_splay(const KEY* key, T* t)
260 : {
261 699794 : T N((KEY*)key), *l, *r, *y;
262 : int comp, l_size, r_size;
263 :
264 699794 : if (t == 0) return t;
265 699682 : comp = Sense*t->compare(*key);
266 699682 : if (comp == 0) return t;
267 :
268 350596 : N.left = N.right = NULL;
269 350596 : l = r = &N;
270 350596 : l_size = r_size = 0;
271 :
272 506975 : while (1) {
273 857571 : if (comp > 0) {
274 262551 : if (t->left == NULL) break;
275 258932 : if ((Sense*t->left->compare(*key)) > 0) {
276 140427 : y = t->left; /* rotate right */
277 140427 : t->left = y->right;
278 140427 : y->right = t;
279 140427 : t->size = node_size(t->left) + node_size(t->right) + 1;
280 140427 : t = y;
281 140427 : if (t->left == NULL) break;
282 : }
283 257311 : r->left = t; /* link right */
284 257311 : r = t;
285 257311 : t = t->left;
286 257311 : r_size += 1+ node_size(r->right);
287 595020 : } else if (comp < 0) {
288 457446 : if (t->right == NULL) break;
289 252825 : if ((Sense*t->right->compare(*key)) < 0) {
290 106018 : y = t->right; /* rotate left */
291 106018 : t->right = y->left;
292 106018 : y->left = t;
293 106018 : t->size = node_size(t->left) + node_size(t->right) + 1;
294 106018 : t = y;
295 106018 : if (t->right == NULL) break;
296 : }
297 249664 : l->right = t; /* link left */
298 249664 : l = t;
299 249664 : t = t->right;
300 249664 : l_size += 1+ node_size(l->left);
301 : } else {
302 137574 : break;
303 : }
304 506975 : comp = Sense*t->compare(*key);
305 : }
306 350596 : l_size += node_size(t->left); /* Now l_size and r_size are the sizes of */
307 350596 : r_size += node_size(t->right); /* the left and right trees we just built.*/
308 350596 : t->size = l_size + r_size + 1;
309 :
310 350596 : l->right = r->left = NULL;
311 :
312 : /* The following two loops correct the size fields of the right path */
313 : /* from the left child of the root and the right path from the left */
314 : /* child of the root. */
315 600260 : for (y = N.right; y != NULL; y = y->right) {
316 249664 : y->size = l_size;
317 249664 : l_size -= 1+ node_size(y->left);
318 : }
319 607907 : for (y = N.left; y != NULL; y = y->left) {
320 257311 : y->size = r_size;
321 257311 : r_size -= 1+ node_size(y->right);
322 : }
323 :
324 350596 : l->right = t->left; /* assemble */
325 350596 : r->left = t->right;
326 350596 : t->left = N.right;
327 350596 : t->right = N.left;
328 :
329 350596 : return t;
330 : }
331 :
332 :
333 :
334 : template <class T, class KEY>
335 113087 : T* AbstractSplayTree<T,KEY>::insert(KEY* newkey)
336 : {
337 113087 : T* newroot = new T(newkey);
338 113087 : if (tree == NULL) {
339 112 : newroot->left = newroot->right = NULL;
340 : }
341 : else {
342 112975 : if ((Sense*newroot->compare(tree->key())) < 0) {
343 5197 : newroot->left = tree->left;
344 5197 : newroot->right = tree;
345 5197 : tree->left = NULL;
346 5197 : tree->size = 1+ node_size(tree->right);
347 : } else {
348 107778 : newroot->right = tree->right;
349 107778 : newroot->left = tree;
350 107778 : tree->right = NULL;
351 107778 : tree->size = 1+ node_size(tree->left);
352 : }
353 : }
354 :
355 113087 : newroot->size = 1 + node_size(newroot->left) + node_size(newroot->right);
356 113087 : tree = newroot;
357 113087 : return tree;
358 : }
359 :
360 :
361 :
362 : template <class T, class KEY>
363 99883 : void AbstractSplayTree<T,KEY>::extract(T* node, bool& status) {
364 : T* x;
365 : int tsize;
366 :
367 99883 : if (tree==NULL) return;
368 99883 : tsize = tree->size;
369 99883 : tree = exec_splay(&(node->key()),tree);
370 99883 : if ((Sense*node->compare(tree->key())) == 0) { // found it
371 99883 : status = true;
372 99883 : if (tree->left == NULL) {
373 0 : x = tree->right;
374 : } else {
375 99883 : x = exec_splay(&(node->key()), tree->left);
376 99883 : x->right = tree->right;
377 : }
378 99883 : delete tree;
379 99883 : if (x != NULL) {
380 99883 : x->size = tsize-1;
381 : }
382 99883 : tree = x;
383 : }
384 : else {
385 0 : status = false;
386 0 : node = 0;
387 : }
388 : }
389 :
390 :
391 :
392 : template <class T, class KEY>
393 111891 : T* AbstractSplayTree<T,KEY>::find_rank(int r)
394 : {
395 111891 : T* tmp=tree;
396 : int lsize;
397 111891 : if ((r < 0) || (r >= node_size(tmp))) return NULL;
398 39066 : for (;;) {
399 150952 : lsize = node_size(tmp->left);
400 150952 : if (r < lsize) {
401 25267 : tmp = tmp->left;
402 125685 : } else if (r > lsize) {
403 13799 : r = r - lsize - 1;
404 13799 : tmp = tmp->right;
405 : } else {
406 111886 : break;
407 : }
408 : }
409 111886 : tree = exec_splay(&(tmp->key()),tree);
410 111886 : return tmp;
411 : }
412 :
413 : #if 0
414 : void AbstractSplayTree<T,KEY>::print_tree(ostream& os, int d,
415 : T* t) {
416 : int i;
417 : if (tree == NULL) return;
418 : print_tree(os,d+1,tree->right);
419 : for (i=0; i<d; i++) os << " ";
420 : dowrite(tree,os);
421 : //os << "(" << node_size(tree) << "," << tree->ctr << ")" << endl;
422 : print_tree(os,d+1,tree->left);
423 : }
424 : #endif
425 :
426 :
427 : template <class T, class KEY>
428 27348 : void AbstractSplayTree<T,KEY>::clear(T* ptr)
429 : {
430 27348 : if (!ptr) {
431 514 : if (tree) {
432 : // Before we clear the tree, we rebalance it
433 : // This prevents pathological cases where clear recurses so
434 : // long that it eats up the stack!
435 245 : balance();
436 : // Clear the tree
437 245 : clear(tree);
438 245 : tree=0;
439 : }
440 514 : return;
441 : }
442 26834 : if (ptr->left)
443 19703 : clear(ptr->left);
444 26834 : if (ptr->right)
445 6886 : clear(ptr->right);
446 26834 : delete ptr;
447 : }
448 :
449 : #undef node_size
450 :
451 : } // namespace utilib
452 :
453 : /// Out-stream operator for writing the contents of a AbstractSplayTree
454 : template <class T, class KEY>
455 5 : inline std::ostream& operator<<(std::ostream& os, const utilib::AbstractSplayTree<T,KEY>& obj)
456 : {
457 5 : os << obj.size() << std::endl;
458 :
459 5 : const T* node = obj.find_rank(0);
460 5 : int i=1;
461 10080 : while (node) {
462 : //os << node->ctr << " ";
463 10070 : node->write(os);
464 10070 : os << std::endl;
465 10070 : node = obj.find_rank(i++);
466 : }
467 5 : return os;
468 : }
469 :
470 : /// Out-stream operator for writing the contents of a AbstractSplayTree
471 : template <class T, class KEY>
472 : inline utilib::PackBuffer& operator<<(utilib::PackBuffer& os,
473 : const utilib::AbstractSplayTree<T,KEY>& obj)
474 : {
475 : os << obj.size();
476 :
477 : const T* node = obj.find_rank(0);
478 : int i=1;
479 : while (node) {
480 : node->write(os);
481 : node = obj.find_rank(i++);
482 : }
483 : return os;
484 : }
485 :
486 :
487 : /// In-stream operator for reading the contents of a AbstractSplayTree
488 : template <class T, class KEY>
489 : inline std::istream& operator>>(std::istream& is, utilib::AbstractSplayTree<T,KEY>& obj)
490 : {
491 : int Size;
492 : is >> Size;
493 : for (int i=0; i<Size; i++) {
494 : T* item = 0;
495 : item->read(is);
496 : obj.add(item);
497 : }
498 : return is;
499 : }
500 :
501 : /// In-stream operator for reading the contents of a AbstractSplayTree
502 : template <class T, class KEY>
503 : inline utilib::UnPackBuffer& operator>>(utilib::UnPackBuffer& is,
504 : utilib::AbstractSplayTree<T,KEY>& obj)
505 : {
506 : int Size;
507 : is >> Size;
508 : for (int i=0; i<Size; i++) {
509 : T* item = 0;
510 : item->read(is);
511 : obj.add(item);
512 : }
513 : return is;
514 : }
515 :
516 :
517 :
518 : #endif
|
