name.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * *
3  * Copyright (C) 2007-2013 by Johan De Taeye, frePPLe bvba *
4  * *
5  * This library is free software; you can redistribute it and/or modify it *
6  * under the terms of the GNU Affero General Public License as published *
7  * by the Free Software Foundation; either version 3 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This library is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU Affero General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU Affero General Public *
16  * License along with this program. *
17  * If not, see <http://www.gnu.org/licenses/>. *
18  * *
19  ***************************************************************************/
20 
21 #define FREPPLE_CORE
22 #include "frepple/utils.h"
23 
24 namespace frepple
25 {
26 namespace utils
27 {
28 
30 {
31  // Tree is already empty
32  if (empty()) return;
33 
34  // Erase all elements
35  for (TreeNode* x = begin(); x != end(); x = begin())
36  {
37  Object *o = dynamic_cast<Object*>(x);
38  if (o && o->getType().raiseEvent(o, SIG_REMOVE))
39  delete(x); // The destructor calls the erase method
40  else
41  throw DataException("Can't delete object");
42  }
43 }
44 
45 
47 {
48  if (!z) throw LogicException("Inserting null pointer in tree");
49 
50  // Use the hint to create the proper starting point in the tree
51  int comp;
52  TreeNode* y;
53  if (!hint)
54  {
55  // Effectively no hint given
56  hint = header.parent;
57  y = &header;
58  }
59  else
60  {
61  // Check if the hint is a good starting point to descend
62  while (hint->parent)
63  {
64  comp = z->nm.compare(hint->parent->nm);
65  if ((comp>0 && hint == hint->parent->left)
66  || (comp<0 && hint == hint->parent->right))
67  // Move the hint up to the parent node
68  // If I'm left child of my parent && new node needs right insert
69  // or I'm right child of my parent && new node needs left insert
70  hint = hint->parent;
71  else
72  break;
73  }
74  y = hint->parent;
75  }
76 
77  // Step down the tree till we found a proper empty leaf node in the tree
78  for (; hint; hint = comp<0 ? hint->left : hint->right)
79  {
80  y = hint;
81  // Exit the function if the key is already found
82  comp = z->nm.compare(hint->nm);
83  if (!comp) return hint;
84  }
85 
86  if (y == &header || z->nm < y->nm)
87  {
88  // Inserting as a new left child
89  y->left = z; // also makes leftmost() = z when y == header
90  if (y == &header)
91  {
92  // Inserting a first element in the list
93  header.parent = z;
94  header.right = z;
95  }
96  // maintain leftmost() pointing to min node
97  else if (y == header.left) header.left = z;
98  }
99  else
100  {
101  // Inserting as a new right child
102  y->right = z;
103  // Maintain rightmost() pointing to max node.
104  if (y == header.right) header.right = z;
105  }
106 
107  // Set parent and child pointers of the new node
108  z->parent = y;
109  z->left = NULL;
110  z->right = NULL;
111 
112  // Increase the node count
113  ++count;
114 
115  // Rebalance the tree
116  rebalance(z);
117  return z;
118 }
119 
120 
121 void Tree::rebalance(TreeNode* x)
122 {
123  x->color = red;
124 
125  while (x != header.parent && x->parent->color == red)
126  {
127  if (x->parent == x->parent->parent->left)
128  {
129  TreeNode* y = x->parent->parent->right;
130  if (y && y->color == red)
131  {
132  x->parent->color = black;
133  y->color = black;
134  x->parent->parent->color = red;
135  x = x->parent->parent;
136  }
137  else
138  {
139  if (x == x->parent->right)
140  {
141  x = x->parent;
142  rotateLeft(x);
143  }
144  x->parent->color = black;
145  x->parent->parent->color = red;
146  rotateRight(x->parent->parent);
147  }
148  }
149  else
150  {
151  TreeNode* y = x->parent->parent->left;
152  if (y && y->color == red)
153  {
154  x->parent->color = black;
155  y->color = black;
156  x->parent->parent->color = red;
157  x = x->parent->parent;
158  }
159  else
160  {
161  if (x == x->parent->left)
162  {
163  x = x->parent;
164  rotateRight(x);
165  }
166  x->parent->color = black;
167  x->parent->parent->color = red;
168  rotateLeft(x->parent->parent);
169  }
170  }
171  }
172  header.parent->color = black;
173 }
174 
175 
177 {
178  // A colorless node was never inserted in the tree, and shouldn't be
179  // removed from it either...
180  if (!z || z->color == none) return;
181 
182  TreeNode* y = z;
183  TreeNode* x = NULL;
184  TreeNode* x_parent = NULL;
185  --count;
186  if (y->left == NULL) // z has at most one non-null child. y == z.
187  x = y->right; // x might be null.
188  else if (y->right == NULL) // z has exactly one non-null child. y == z.
189  x = y->left; // x is not null.
190  else
191  {
192  // z has two non-null children. Set y to
193  y = y->right; // z's successor. x might be null.
194  while (y->left != NULL) y = y->left;
195  x = y->right;
196  }
197  if (y != z)
198  {
199  // relink y in place of z. y is z's successor
200  z->left->parent = y;
201  y->left = z->left;
202  if (y != z->right)
203  {
204  x_parent = y->parent;
205  if (x) x->parent = y->parent;
206  y->parent->left = x; // y must be a child of left
207  y->right = z->right;
208  z->right->parent = y;
209  }
210  else
211  x_parent = y;
212  if (header.parent == z) header.parent = y;
213  else if (z->parent->left == z) z->parent->left = y;
214  else z->parent->right = y;
215  y->parent = z->parent;
216  std::swap(y->color, z->color);
217  y = z;
218  // y now points to node to be actually deleted
219  }
220  else
221  {
222  // y == z
223  x_parent = y->parent;
224  if (x) x->parent = y->parent;
225  if (header.parent == z) header.parent = x;
226  else if (z->parent->left == z) z->parent->left = x;
227  else z->parent->right = x;
228  if (header.left == z)
229  {
230  if (z->right == NULL) // z->left must be null also
231  header.left = z->parent;
232  // makes leftmost == header if z == root
233  else
234  header.left = minimum(x);
235  }
236  if (header.right == z)
237  {
238  if (z->left == NULL) // z->right must be null also
239  header.right = z->parent;
240  // makes rightmost == header if z == root
241  else // x == z->left
242  header.right = maximum(x);
243  }
244  }
245  if (y->color != red)
246  {
247  while (x != header.parent && (x == NULL || x->color == black))
248  if (x == x_parent->left)
249  {
250  TreeNode* w = x_parent->right;
251  if (w->color == red)
252  {
253  w->color = black;
254  x_parent->color = red;
255  rotateLeft(x_parent);
256  w = x_parent->right;
257  }
258  if ((w->left == NULL || w->left->color == black) &&
259  (w->right == NULL || w->right->color == black))
260  {
261  w->color = red;
262  x = x_parent;
263  x_parent = x_parent->parent;
264  }
265  else
266  {
267  if (w->right == NULL || w->right->color == black)
268  {
269  w->left->color = black;
270  w->color = red;
271  rotateRight(w);
272  w = x_parent->right;
273  }
274  w->color = x_parent->color;
275  x_parent->color = black;
276  if (w->right) w->right->color = black;
277  rotateLeft(x_parent);
278  break;
279  }
280  }
281  else
282  {
283  // same as above, with right <-> left.
284  TreeNode* w = x_parent->left;
285  if (w->color == red)
286  {
287  w->color = black;
288  x_parent->color = red;
289  rotateRight(x_parent);
290  w = x_parent->left;
291  }
292  if ((w->right == NULL || w->right->color == black) &&
293  (w->left == NULL || w->left->color == black))
294  {
295  w->color = red;
296  x = x_parent;
297  x_parent = x_parent->parent;
298  }
299  else
300  {
301  if (w->left == NULL || w->left->color == black)
302  {
303  w->right->color = black;
304  w->color = red;
305  rotateLeft(w);
306  w = x_parent->left;
307  }
308  w->color = x_parent->color;
309  x_parent->color = black;
310  if (w->left) w->left->color = black;
311  rotateRight(x_parent);
312  break;
313  }
314  }
315  if (x) x->color = black;
316  }
317 }
318 
319 
320 void Tree::rotateLeft(TreeNode* x)
321 {
322  TreeNode* y = x->right;
323  x->right = y->left;
324  if (y->left != NULL) y->left->parent = x;
325  y->parent = x->parent;
326 
327  if (x == header.parent)
328  // x was the root
329  header.parent = y;
330  else if (x == x->parent->left)
331  // x was on the left of its parent
332  x->parent->left = y;
333  else
334  // x was on the right of its parent
335  x->parent->right = y;
336  y->left = x;
337  x->parent = y;
338 }
339 
340 
341 void Tree::rotateRight(TreeNode* x)
342 {
343  TreeNode* y = x->left;
344  x->left = y->right;
345  if (y->right != NULL) y->right->parent = x;
346  y->parent = x->parent;
347 
348  if (x == header.parent)
349  // x was the root
350  header.parent = y;
351  else if (x == x->parent->right)
352  // x was on the right of its parent
353  x->parent->right = y;
354  else
355  // x was on the left of its parent
356  x->parent->left = y;
357  y->right = x;
358  x->parent = y;
359 }
360 
361 
363 {
364  // Checks for an empty tree
365  if (empty() || begin() == end())
366  {
367  bool ok = (empty() &&
368  begin() == end() &&
369  header.left == &header &&
370  header.right == &header);
371  if (!ok) throw LogicException("Invalid empty tree");
372  return;
373  }
374 
375  unsigned int len = countBlackNodes(header.left);
376  size_t counter = 0;
377  for (TreeNode* x = begin(); x != end(); x = x->increment())
378  {
379  TreeNode* L = x->left;
380  TreeNode* R = x->right;
381  ++counter;
382 
383  if (x->color == none)
384  // Nodes must have a color
385  throw LogicException("Colorless node included in a tree");
386 
387  if (x->color == red)
388  if ((L && L->color == red) || (R && R->color == red))
389  // A red node can have only NULL and black children
390  throw LogicException("Wrong color on node");
391 
392  if (L && x->nm<L->nm)
393  // Left child isn't smaller
394  throw LogicException("Wrong sorting on left node");
395 
396  if (R && R->nm<x->nm)
397  // Right child isn't bigger
398  throw LogicException("Wrong sorting on right node");
399 
400  if (!L && !R && countBlackNodes(x) != len)
401  // All leaf nodes have the same number of black nodes on their path
402  // to the root
403  throw LogicException("Unbalanced count of black nodes");
404  }
405 
406  // Check whether the header has a good pointer to the leftmost element
407  if (header.left != minimum(header.parent))
408  throw LogicException("Incorrect tree minimum");
409 
410  // Check whether the header has a good pointer to the rightmost element
411  if (header.right != maximum(header.parent))
412  throw LogicException("Incorrect tree maximum");
413 
414  // Check whether the measured node count match the expectation?
415  if (counter != size())
416  throw LogicException("Incorrect tree size");
417 
418  // If we reach this point, then this tree is healthy
419 }
420 
421 } // end namespace
422 } // end namespace