Doxygen Generated Documentation of Ben-Jose Trainable SAT Solver Library
redblack.h
1 
2 
3 /*************************************************************
4 
5 This file is part of ben-jose.
6 
7 ben-jose is free software: you can redistribute it and/or modify
8 it under the terms of the version 3 of the GNU General Public
9 License as published by the Free Software Foundation.
10 
11 ben-jose is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15 
16 You should have received a copy of the GNU General Public License
17 along with ben-jose. If not, see <http://www.gnu.org/licenses/>.
18 
19 ------------------------------------------------------------
20 
21 Copyright (C) 2007-2012, 2014-2016. QUIROGA BELTRAN, Jose Luis.
22 Id (cedula): 79523732 de Bogota - Colombia.
23 See https://github.com/joseluisquiroga/ben-jose
24 
25 ben-jose is free software thanks to The Glory of Our Lord
26  Yashua Melej Hamashiaj.
27 Our Resurrected and Living, both in Body and Spirit,
28  Prince of Peace.
29 
30 ------------------------------------------------------------
31 
32 redblack.h
33 
34 Red-black trees template.
35 
36 --------------------------------------------------------------*/
37 
38 
39 #ifndef REDBLACK_H
40 #define REDBLACK_H
41 
42 #include "bj_mem.h"
43 #include "bj_stream.h"
44 #include "stack_trace.h"
45 
46 #define DBG_RBT(prm) DBG(prm)
47 #define REDBLACK_CK(prm) DBG_CK(prm)
48 //define REDBLACK_CK(prm) /**/
49 
50 //define SLOW_REDBLACK_CK(prm) DBG_CK(prm)
51 #define SLOW_REDBLACK_CK(prm)
52 
53 /*
54 The class passed to the template ('node_manager_t') must implement the following methods
55 
56  rbt_nod_ref_t create_node(rbt_obj_t const & obj1);
57  void destroy_all_nodes(redblack<rbt_row_node_handler<obj_t> >& rbt);
58  comparison compare_node_objects(rbt_obj_t const & obj1, rbt_obj_t const & obj2);
59  rbt_nod_ref_t get_null_node_reference();
60  rbt_nod_ref_t& get_right_node_reference_of(rbt_nod_ref_t const & nd);
61  rbt_nod_ref_t& get_left_node_reference_of(rbt_nod_ref_t const & nd);
62  rbt_nod_ref_t& get_parent_node_reference_of(rbt_nod_ref_t const & nd);
63  rbt_obj_t& get_object_of(rbt_nod_ref_t const & nd);
64  rbt_color_t get_color_of(rbt_nod_ref_t const & nd);
65  void set_color_of(rbt_nod_ref_t const & nd, rbt_color_t col);
66 
67 And have public typedefs for:
68 
69  rbt_nod_ref_t; (type of node references ej: void*, long
70  rbt_obj_t; (type of objects ej: long, my_own_class
71 */
72 
73 typedef char comparison;
74 
75 enum rbt_color_t{
76  k_invalid_color,
77  k_red_color,
78  k_black_color
79 };
80 
81 //================================================================
82 // redblack
83 
84 template <bool> struct RBT_ILLEGAL_USE_OF_OBJECT;
85 template <> struct RBT_ILLEGAL_USE_OF_OBJECT<true>{};
86 #define RBT_OBJECT_COPY_ERROR RBT_ILLEGAL_USE_OF_OBJECT<false>()
87 
88 template<class node_manager_t>
89 class redblack {
90 public:
91  typedef typename node_manager_t::rbt_nod_ref_t rbt_nod_ref_t;
92  typedef typename node_manager_t::rbt_obj_t rbt_obj_t;
93 
94 protected:
95 
96  node_manager_t& the_mgr;
97 
98  rbt_nod_ref_t root;
99  rbt_nod_ref_t last_found;
100  rbt_nod_ref_t min_nod;
101  rbt_nod_ref_t max_nod;
102  long rbt_sz;
103 
104 public:
105  redblack(node_manager_t& mgr) : the_mgr(mgr){
106  init_red_black();
107  }
108 
109  ~redblack(){
110  clear_redblack();
111  }
112 
113  // Don't allow copying (error prone):
114  // force use of referenced objs
115 
116  redblack& operator = (redblack& other) {
117  RBT_OBJECT_COPY_ERROR;
118  }
119 
120  redblack(redblack& other){
121  RBT_OBJECT_COPY_ERROR;
122  }
123 
124  void clear_redblack(){
125  destroy_nodes();
126  init_red_black();
127  }
128 
129  long size(){
130  return rbt_sz;
131  }
132 
133  rbt_nod_ref_t get_min(){
134  return min_nod;
135  }
136 
137  rbt_nod_ref_t get_max(){
138  return max_nod;
139  }
140 
141  rbt_nod_ref_t search(rbt_obj_t const & obj){
142  rbt_nod_ref_t the_parent;
143  return search_node(obj, the_parent);
144  }
145 
146  rbt_nod_ref_t rbt_insert(rbt_obj_t const & obj);
147  rbt_nod_ref_t predecessor(rbt_nod_ref_t xx);
148  rbt_nod_ref_t successor(rbt_nod_ref_t xx);
149  rbt_nod_ref_t rbt_remove(rbt_nod_ref_t zz);
150  bool is_empty(){
151  bool ee = (root == get_null());
152  REDBLACK_CK(! ee || (rbt_sz == 0));
153  return ee;
154  }
155 
156  bool check_tree(){
157  print(bj_err, true);
158  return true;
159  }
160 
161  bool check_order();
162 
163  bj_ostream& print(bj_ostream& os,
164  bool just_chks = false, bool htm = false);
165 
166  friend
167  bj_ostream& operator << (bj_ostream& os, redblack<node_manager_t>& rbt){
168  rbt.print(os);
169  return os;
170  }
171 
172  /*
173  friend
174  redblack<node_manager_t>& operator << (redblack<node_manager_t>& rbt,
175  rbt_obj_t const & elem)
176  {
177  rbt.rbt_insert(elem);
178  return rbt;
179  }*/
180 
181  rbt_nod_ref_t get_null(){
182  return the_mgr.get_null_node_reference();
183  }
184 
185  rbt_obj_t& get_obj(rbt_nod_ref_t const & nd){
186  return the_mgr.get_object_of(nd);
187  }
188 
189  bool is_alone(rbt_nod_ref_t const & nd);
190  bool check_refs(rbt_nod_ref_t const & nd, int from = 0);
191  void move_node(rbt_nod_ref_t const & nd, rbt_nod_ref_t const & nd_empty);
192 
193 protected:
194 
195  rbt_nod_ref_t create_node(rbt_obj_t const & obj1){
196  return the_mgr.create_node(obj1);
197  }
198 
199  void destroy_nodes(){
200  the_mgr.destroy_all_nodes(*this);
201  }
202 
203  comparison cmp(rbt_nod_ref_t nod1, rbt_nod_ref_t nod2){
204  return the_mgr.compare_node_objects(get_obj(nod1), get_obj(nod2));
205  }
206 
207  comparison cmp_obj(rbt_nod_ref_t nod1, rbt_obj_t const & obj){
208  return the_mgr.compare_node_objects(get_obj(nod1), obj);
209  }
210 
211  comparison cmp_objs(rbt_obj_t const & obj1, rbt_obj_t const & obj2){
212  return the_mgr.compare_node_objects(obj1, obj2);
213  }
214 
215  rbt_nod_ref_t& get_right(rbt_nod_ref_t const & nd){
216  return the_mgr.get_right_node_reference_of(nd);
217  }
218 
219  rbt_nod_ref_t& get_left(rbt_nod_ref_t const & nd){
220  return the_mgr.get_left_node_reference_of(nd);
221  }
222 
223  rbt_nod_ref_t& get_parent(rbt_nod_ref_t const & nd){
224  return the_mgr.get_parent_node_reference_of(nd);
225  }
226 
227  rbt_color_t get_color(rbt_nod_ref_t const & nd){
228  return the_mgr.get_color_of(nd);
229  }
230 
231  void set_color(rbt_nod_ref_t const & nd, rbt_color_t col){
232  the_mgr.set_color_of(nd, col);
233  }
234 
235  rbt_nod_ref_t& get_grand(rbt_nod_ref_t const & nd){
236  return get_parent(get_parent(nd));
237  }
238 
239  void init_red_black(){
240  root = get_null();
241  last_found = get_null();
242  min_nod = get_null();
243  max_nod = get_null();
244  rbt_sz = 0;
245  }
246 
247  bool check_min_max(){
248  rbt_nod_ref_t min_found = search_min(root);
249  rbt_nod_ref_t max_found = search_max(root);
250  REDBLACK_CK(min_nod == min_found);
251  REDBLACK_CK(max_nod == max_found);
252  REDBLACK_CK(check_refs(root, 1));
253  REDBLACK_CK(check_refs(last_found, 2));
254  REDBLACK_CK(check_refs(min_nod, 3));
255  REDBLACK_CK(check_refs(max_nod, 4));
256  return true;
257  }
258 
259  void insert_update_min_max(rbt_nod_ref_t nod){
260  rbt_sz++;
261  REDBLACK_CK(nod != get_null());
262  if((min_nod == get_null()) || (cmp(min_nod, nod) > 0)){
263  min_nod = nod;
264  }
265  if((max_nod == get_null()) || (cmp(max_nod, nod) < 0)){
266  max_nod = nod;
267  }
268  }
269 
270  void remove_update_min_max(rbt_nod_ref_t nod){
271  rbt_sz--;
272  REDBLACK_CK(nod != get_null());
273  REDBLACK_CK(min_nod != get_null());
274  REDBLACK_CK(max_nod != get_null());
275  if(cmp(min_nod, nod) == 0){
276  REDBLACK_CK(get_left(min_nod) == get_null());
277  REDBLACK_CK(min_nod == nod);
278  min_nod = successor(nod);
279  }
280  if(cmp(max_nod, nod) == 0){
281  REDBLACK_CK(get_right(max_nod) == get_null());
282  REDBLACK_CK(max_nod == nod);
283  max_nod = predecessor(nod);
284  }
285  }
286 
287  void move_update_min_max(rbt_nod_ref_t src,
288  rbt_nod_ref_t dst)
289  {
290  if(last_found == src){
291  last_found = dst;
292  }
293  if(min_nod == src){
294  min_nod = dst;
295  }
296  if(max_nod == src){
297  max_nod = dst;
298  }
299  if(root == src){
300  root = dst;
301  }
302  }
303 
304  rbt_nod_ref_t search_node(rbt_obj_t const & obj, rbt_nod_ref_t& the_parent);
305 
306  rbt_nod_ref_t search_min(rbt_nod_ref_t xx);
307  rbt_nod_ref_t search_max(rbt_nod_ref_t xx);
308  void left_rotate(rbt_nod_ref_t xx);
309  void right_rotate(rbt_nod_ref_t yy);
310  void fix_remove(rbt_nod_ref_t xx, rbt_nod_ref_t parent_yy);
311 
312  bool is_black(rbt_nod_ref_t nod){
313  if(nod == get_null()){ return true; }
314  return (get_color(nod) == k_black_color);
315  }
316 
317  bool is_red(rbt_nod_ref_t nod){
318  if(nod == get_null()){ return false; }
319  return (get_color(nod) == k_red_color);
320  }
321 
322  void set_black(rbt_nod_ref_t nod){
323  if(nod == get_null()){ return; }
324  set_color(nod, k_black_color);
325  }
326 
327  void set_red(rbt_nod_ref_t nod){
328  if(nod == get_null()){ return; }
329  set_color(nod, k_red_color);
330  }
331 
332  bj_ostream& print_rec(bj_ostream& os, rbt_nod_ref_t xx, int tb,
333  bool& prev, rbt_nod_ref_t nod, int& tot,
334  int ctr, bool just_cks);
335 
336 };
337 
338 //================================================================
339 // redblack_iter
340 
341 template<class node_manager_t>
342 class redblack_iter {
343 public:
344  typedef typename node_manager_t::rbt_nod_ref_t rbt_nod_ref_t;
345  typedef typename node_manager_t::rbt_obj_t rbt_obj_t;
346 
347  redblack<node_manager_t>& the_tree;
348  rbt_nod_ref_t the_ref;
349 
350  redblack_iter(redblack<node_manager_t>& rbt) : the_tree(rbt){
351  the_ref = the_tree.get_null();
352  }
353  redblack_iter(redblack_iter& rbt_it): the_tree(rbt_it.the_tree){
354  the_ref = the_tree.get_null();
355  }
356  ~redblack_iter(){
357  }
358 
359  long size(){
360  return the_tree.size();
361  }
362 
363  void go_first_ref(){
364  REDBLACK_CK(the_tree.check_refs(the_ref, 5));
365  the_ref = the_tree.get_min();
366  }
367 
368  void go_last_ref(){
369  REDBLACK_CK(the_tree.check_refs(the_ref, 6));
370  the_ref = the_tree.get_max();
371  }
372 
373  rbt_obj_t& get_obj(){
374  REDBLACK_CK(the_tree.check_refs(the_ref, 7));
375  return the_tree.get_obj(the_ref);
376  }
377 
378  bool in_null(){
379  REDBLACK_CK(the_tree.check_refs(the_ref, 8));
380  return (the_ref == the_tree.get_null());
381  }
382 
383  void go_next(){
384  REDBLACK_CK(the_tree.check_refs(the_ref, 9));
385  the_ref = the_tree.successor(the_ref);
386  }
387 
388  void go_prev(){
389  REDBLACK_CK(the_tree.check_refs(the_ref, 10));
390  the_ref = the_tree.predecessor(the_ref);
391  }
392 
393  rbt_nod_ref_t get_ref(){
394  REDBLACK_CK(the_tree.check_refs(the_ref, 11));
395  return the_ref;
396  }
397 
398  void operator ++ (){
399  go_next();
400  }
401 
402  void operator -- (){
403  go_prev();
404  }
405 
406  void operator ++ (int) { ++(*this); }
407 
408  void operator -- (int) { --(*this); }
409 };
410 
411 //================================================================
412 // FUNCS
413 
414 template<class node_manager_t>
415 bool
416 redblack<node_manager_t>::is_alone(rbt_nod_ref_t const & nd){
417  bool is_e = (
418  (nd != get_null()) &&
419  (get_parent(nd) == get_null()) &&
420  (get_right(nd) == get_null()) &&
421  (get_left(nd) == get_null())
422  );
423  return is_e;
424 }
425 
426 template<class node_manager_t>
427 bool
428 redblack<node_manager_t>::check_refs(rbt_nod_ref_t const & nd, int from){
429  if(nd == get_null()){
430  return true;
431  }
432 
433  rbt_nod_ref_t pre = get_parent(nd);
434  rbt_nod_ref_t lft = get_left(nd);
435  rbt_nod_ref_t rgt = get_right(nd);
436 
437  if(pre != get_null()){
438  rbt_nod_ref_t pre_lft = get_left(pre);
439  rbt_nod_ref_t pre_rgt = get_right(pre);
440  REDBLACK_CK((pre_lft == nd) || (pre_rgt == nd));
441  }
442  if(lft != get_null()){
443  rbt_nod_ref_t lft_pre = get_parent(lft);
444  REDBLACK_CK(lft_pre == nd);
445  }
446  if(rgt != get_null()){
447  rbt_nod_ref_t rgt_pre = get_parent(rgt);
448  REDBLACK_CK(rgt_pre == nd);
449  }
450  return true;
451 }
452 
453 template<class node_manager_t>
454 void
455 redblack<node_manager_t>::move_node(rbt_nod_ref_t const & nd, rbt_nod_ref_t const & alone){
456  REDBLACK_CK(is_alone(alone));
457  REDBLACK_CK(alone != nd);
458  REDBLACK_CK(check_refs(nd, 12));
459  REDBLACK_CK(check_refs(alone, 13));
460 
461  rbt_nod_ref_t pre = get_parent(nd);
462  if(pre != get_null()){
463  if(get_right(pre) == nd){
464  get_right(pre) = alone;
465  } else if(get_left(pre) == nd){
466  get_left(pre) = alone;
467  }
468  }
469  rbt_nod_ref_t lft_nod = get_left(nd);
470  if(lft_nod != get_null()){
471  get_parent(lft_nod) = alone;
472  }
473  rbt_nod_ref_t rgt_nod = get_right(nd);
474  if(rgt_nod != get_null()){
475  get_parent(rgt_nod) = alone;
476  }
477 
478  get_obj(alone) = get_obj(nd);
479  get_parent(alone) = get_parent(nd);
480  get_left(alone) = get_left(nd);
481  get_right(alone) = get_right(nd);
482  set_color(alone, get_color(nd));
483 
484  get_parent(nd) = get_null();;
485  get_left(nd) = get_null();;
486  get_right(nd) = get_null();;
487  REDBLACK_CK(is_alone(nd));
488 
489  move_update_min_max(nd, alone);
490 
491  REDBLACK_CK(check_refs(nd, 14));
492  REDBLACK_CK(check_refs(alone, 15));
493  SLOW_REDBLACK_CK(check_min_max());
494 }
495 
496 
497 template<class node_manager_t>
498 typename redblack<node_manager_t>::rbt_nod_ref_t
499 redblack<node_manager_t>::search_node(rbt_obj_t const & obj, rbt_nod_ref_t& the_parent)
500 {
501  if((last_found != get_null()) && (cmp_obj(last_found, obj) == 0)){
502  the_parent = get_parent(last_found);
503  return last_found;
504  }
505  the_parent = get_null();
506  rbt_nod_ref_t child = root;
507  REDBLACK_CK(is_black(child));
508 
509  while((child != get_null()) && (cmp_obj(child, obj) != 0)){
510  rbt_nod_ref_t lft = get_left(child);
511  rbt_nod_ref_t rgt = get_right(child);
512  REDBLACK_CK(!is_red(child) || (!is_red(lft) && !is_red(rgt)));
513 
514  the_parent = child;
515  if(cmp_obj(child, obj) > 0){
516  child = lft;
517  } else {
518  REDBLACK_CK(cmp_obj(child, obj) < 0);
519  child = rgt;
520  }
521  }
522  if(child != get_null()){ last_found = child; }
523  return child;
524 }
525 
526 template<class node_manager_t>
527 void
528 redblack<node_manager_t>::left_rotate(rbt_nod_ref_t xx){
529  rbt_nod_ref_t yy = get_right(xx);
530  rbt_nod_ref_t yy_lft = get_left(yy);
531 
532  REDBLACK_CK(check_refs(xx, 16));
533  REDBLACK_CK(check_refs(yy, 17));
534 
535  get_right(xx) = yy_lft;
536  if(yy_lft != get_null()){
537  get_parent(yy_lft) = xx;
538  }
539 
540  rbt_nod_ref_t parent_xx = get_parent(xx);
541 
542  get_parent(yy) = parent_xx;
543  if(parent_xx == get_null()){
544  root = yy;
545  } else if(xx == get_left(parent_xx)){
546  get_left(parent_xx) = yy;
547  } else {
548  REDBLACK_CK(xx == get_right(parent_xx));
549  get_right(parent_xx) = yy;
550  }
551 
552  get_left(yy) = xx;
553  get_parent(xx) = yy;
554 
555  REDBLACK_CK(check_refs(parent_xx, 18));
556  REDBLACK_CK(check_refs(yy_lft, 19));
557  REDBLACK_CK(check_refs(xx, 20));
558  REDBLACK_CK(check_refs(yy, 21));
559 }
560 
561 
562 template<class node_manager_t>
563 void
564 redblack<node_manager_t>::right_rotate(rbt_nod_ref_t yy){
565  rbt_nod_ref_t xx = get_left(yy);
566  rbt_nod_ref_t xx_rgt = get_right(xx);
567 
568  REDBLACK_CK(check_refs(xx, 22));
569  REDBLACK_CK(check_refs(yy, 23));
570 
571  get_left(yy) = xx_rgt;
572  if(xx_rgt != get_null()){
573  get_parent(xx_rgt) = yy;
574  }
575 
576  rbt_nod_ref_t parent_yy = get_parent(yy);
577 
578  get_parent(xx) = parent_yy;
579  if(parent_yy == get_null()){
580  root = xx;
581  } else if(yy == get_right(parent_yy)){
582  get_right(parent_yy) = xx;
583  } else {
584  REDBLACK_CK(yy == get_left(parent_yy));
585  get_left(parent_yy) = xx;
586  }
587 
588  get_right(xx) = yy;
589  get_parent(yy) = xx;
590 
591  REDBLACK_CK(check_refs(parent_yy, 24));
592  REDBLACK_CK(check_refs(xx_rgt, 25));
593  REDBLACK_CK(check_refs(xx, 26));
594  REDBLACK_CK(check_refs(yy, 27));
595 }
596 
597 template<class node_manager_t>
598 typename redblack<node_manager_t>::rbt_nod_ref_t
599 redblack<node_manager_t>::rbt_insert(rbt_obj_t const & obj){
600  rbt_nod_ref_t parent = get_null();
601  rbt_nod_ref_t child = search_node(obj, parent);
602  if(child != get_null()){
603  return get_null();
604  }
605 
606  rbt_nod_ref_t zz = create_node(obj);
607  REDBLACK_CK(zz != get_null());
608  REDBLACK_CK(check_refs(zz, 28));
609 
610  get_parent(zz) = parent;
611  if(parent == get_null()){
612  root = zz;
613  } else if(cmp_obj(parent, obj) > 0){
614  REDBLACK_CK(get_left(parent) == get_null());
615  get_left(parent) = zz;
616  } else {
617  REDBLACK_CK(cmp_obj(parent, obj) < 0);
618  REDBLACK_CK(get_right(parent) == get_null());
619  get_right(parent) = zz;
620  }
621  rbt_nod_ref_t created = zz;
622  REDBLACK_CK(check_refs(created, 29));
623 
624  // fix tree (colors and structure)
625  DBG_RBT(int rotations = 0);
626  rbt_nod_ref_t xx = zz;
627  set_red(xx);
628  while((xx != root) && is_red(get_parent(xx))){
629  if(get_parent(xx) == get_left(get_grand(xx))){
630  rbt_nod_ref_t yy = get_right(get_grand(xx));
631  if(is_red(yy)){
632  set_black(get_parent(xx));
633  set_black(yy);
634  set_red(get_grand(xx));
635  xx = get_grand(xx);
636  } else {
637  if(xx == get_right(get_parent(xx))){
638  xx = get_parent(xx);
639  left_rotate(xx);
640  DBG_RBT(rotations++);
641  }
642  REDBLACK_CK(xx == get_left(get_parent(xx)));
643  set_black(get_parent(xx));
644  set_red(get_grand(xx));
645  right_rotate(get_grand(xx));
646  REDBLACK_CK(is_black(get_parent(xx)));
647  DBG_RBT(rotations++);
648  }
649  } else {
650  REDBLACK_CK(get_parent(xx) == get_right(get_grand(xx)));
651  rbt_nod_ref_t yy = get_left(get_grand(xx));
652  if(is_red(yy)){
653  set_black(get_parent(xx));
654  set_black(yy);
655  set_red(get_grand(xx));
656  xx = get_grand(xx);
657  } else {
658  if(xx == get_left(get_parent(xx))){
659  xx = get_parent(xx);
660  right_rotate(xx);
661  DBG_RBT(rotations++);
662  }
663  REDBLACK_CK(xx == get_right(get_parent(xx)));
664  set_black(get_parent(xx));
665  set_red(get_grand(xx));
666  left_rotate(get_grand(xx));
667  REDBLACK_CK(is_black(get_parent(xx)));
668  DBG_RBT(rotations++);
669  }
670  }
671  }
672  set_black(root);
673  REDBLACK_CK(rotations <= 2);
674  insert_update_min_max(created);
675  REDBLACK_CK(check_refs(created, 30));
676  SLOW_REDBLACK_CK(check_min_max());
677  return created;
678 }
679 
680 template<class node_manager_t>
681 typename redblack<node_manager_t>::rbt_nod_ref_t
682 redblack<node_manager_t>::search_min(rbt_nod_ref_t xx){
683  if(xx == get_null()){ return xx; }
684  while(get_left(xx) != get_null()){
685  xx = get_left(xx);
686  }
687  REDBLACK_CK(xx != get_null());
688  return xx;
689 }
690 
691 // added after adapt
692 template<class node_manager_t>
693 typename redblack<node_manager_t>::rbt_nod_ref_t
694 redblack<node_manager_t>::search_max(rbt_nod_ref_t xx){
695  if(xx == get_null()){ return xx; }
696  while(get_right(xx) != get_null()){
697  xx = get_right(xx);
698  }
699  REDBLACK_CK(xx != get_null());
700  return xx;
701 }
702 
703 // added after adapt
704 template<class node_manager_t>
705 typename redblack<node_manager_t>::rbt_nod_ref_t
706 redblack<node_manager_t>::predecessor(rbt_nod_ref_t xx){
707  REDBLACK_CK(xx != get_null());
708  if(get_left(xx) != get_null()){
709  return search_max(get_left(xx));
710  }
711  rbt_nod_ref_t yy = get_parent(xx);
712  while((yy != get_null()) && (xx == get_left(yy))){
713  xx = yy;
714  yy = get_parent(yy);
715  }
716  return yy;
717 }
718 
719 template<class node_manager_t>
720 typename redblack<node_manager_t>::rbt_nod_ref_t
721 redblack<node_manager_t>::successor(rbt_nod_ref_t xx){
722  REDBLACK_CK(xx != get_null());
723  if(get_right(xx) != get_null()){
724  return search_min(get_right(xx));
725  }
726  rbt_nod_ref_t yy = get_parent(xx);
727  while((yy != get_null()) && (xx == get_right(yy))){
728  xx = yy;
729  yy = get_parent(yy);
730  }
731  return yy;
732 }
733 
734 template<class node_manager_t>
735 void
736 redblack<node_manager_t>::fix_remove(rbt_nod_ref_t xx, rbt_nod_ref_t parent){
737  DBG_RBT(int rotations = 0);
738  while((xx != root) && is_black(xx)){
739  REDBLACK_CK(parent != get_null());
740  REDBLACK_CK((xx == get_null()) || (parent == get_parent(xx)));
741  if(xx == get_left(parent)){
742  DBG_RBT(bool first_if = false);
743  DBG(MARK_USED(first_if));
744  rbt_nod_ref_t ww = get_right(parent);
745  if(is_red(ww)){
746  set_black(ww);
747  set_red(parent);
748  left_rotate(parent);
749  ww = get_right(parent);
750  DBG_RBT(first_if = true);
751  DBG_RBT(rotations++);
752  }
753  if( is_black(get_left(ww)) &&
754  is_black(get_right(ww)) )
755  {
756  set_red(ww);
757  xx = parent;
758  if(xx != root){ parent = get_parent(xx); }
759  else { parent = get_null(); }
760  REDBLACK_CK(!first_if || is_red(xx));
761  } else {
762  if(is_black(get_right(ww))){
763  rbt_nod_ref_t oldWw = ww;
764  MARK_USED(oldWw);
765  REDBLACK_CK(is_red(get_left(ww)));
766  set_black(get_left(ww));
767  set_red(ww);
768  right_rotate(ww);
769  ww = get_right(parent);
770  REDBLACK_CK(get_right(ww) == oldWw);
771  DBG_RBT(rotations++);
772  }
773  REDBLACK_CK(is_red(get_right(ww)));
774  if(is_black(parent)){ set_black(ww); }
775  else { set_red(ww); }
776  set_black(parent);
777  set_black(get_right(ww));
778  left_rotate(parent);
779  xx = root;
780  parent = get_null();
781  DBG_RBT(rotations++);
782  }
783  } else {
784  DBG_RBT(int first_if = false);
785  DBG(MARK_USED(first_if));
786  REDBLACK_CK(xx == get_right(parent));
787  rbt_nod_ref_t ww = get_left(parent);
788  if(is_red(ww)){
789  set_black(ww);
790  set_red(parent);
791  right_rotate(parent);
792  ww = get_left(parent);
793  DBG_RBT(first_if = true);
794  DBG_RBT(rotations++);
795  }
796  if( is_black(get_right(ww)) &&
797  is_black(get_left(ww)) )
798  {
799  set_red(ww);
800  xx = parent;
801  if(xx != root){ parent = get_parent(xx); }
802  else { parent = get_null(); }
803  REDBLACK_CK(!first_if || is_red(xx));
804  } else {
805  if(is_black(get_left(ww))){
806  rbt_nod_ref_t oldWw = ww;
807  MARK_USED(oldWw);
808  REDBLACK_CK(is_red(get_right(ww)));
809  set_black(get_right(ww));
810  set_red(ww);
811  left_rotate(ww);
812  ww = get_left(parent);
813  REDBLACK_CK(get_left(ww) == oldWw);
814  DBG_RBT(rotations++);
815  }
816  REDBLACK_CK(is_red(get_left(ww)));
817  if(is_black(parent)){ set_black(ww); }
818  else { set_red(ww); }
819  set_black(parent);
820  set_black(get_left(ww));
821  right_rotate(parent);
822  xx = root;
823  parent = get_null();
824  DBG_RBT(rotations++);
825  }
826  }
827  }
828  set_black(xx);
829  REDBLACK_CK(rotations <= 3);
830 }
831 
832 template<class node_manager_t>
833 typename redblack<node_manager_t>::rbt_nod_ref_t
834 redblack<node_manager_t>::rbt_remove(rbt_nod_ref_t zz){
835  if(zz == get_null()){ return get_null(); }
836  REDBLACK_CK(zz != get_null());
837  REDBLACK_CK(check_refs(zz, 31));
838  remove_update_min_max(zz);
839  if(last_found == zz){
840  last_found = get_null();
841  }
842 
843  rbt_nod_ref_t yy = get_null();
844  if( (get_left(zz) == get_null()) ||
845  (get_right(zz) == get_null()) )
846  {
847  yy = zz;
848  } else {
849  yy = successor(zz);
850  }
851  // yy is the node to remove
852 
853  rbt_nod_ref_t xx = get_null();
854  if(get_left(yy) != get_null()){
855  xx = get_left(yy);
856  } else if(get_right(yy) != get_null()){
857  xx = get_right(yy);
858  }
859 
860  rbt_nod_ref_t parent_yy = get_parent(yy);
861 
862  if(xx != get_null()){ get_parent(xx) = parent_yy; }
863  if(parent_yy == get_null()){
864  root = xx;
865  } else if(yy == get_left(parent_yy)){
866  get_left(parent_yy) = xx;
867  } else {
868  REDBLACK_CK(yy == get_right(parent_yy));
869  get_right(parent_yy) = xx;
870  }
871  if((yy != zz) && (yy != get_null())){
872  move_update_min_max(yy, zz);
873  get_obj(zz) = get_obj(yy);
874  }
875  if(is_black(yy)){ fix_remove(xx, parent_yy); }
876  get_right(yy) = get_null();
877  get_left(yy) = get_null();
878  get_parent(yy) = get_null();
879 
880  SLOW_REDBLACK_CK(check_min_max());
881  return yy;
882 }
883 
884 template<class node_manager_t>
885 bj_ostream&
886 redblack<node_manager_t>::print_rec(bj_ostream& os, rbt_nod_ref_t xx, int tb,
887  bool& prev, rbt_nod_ref_t lst_nod, int& tot,
888  int ctr, bool just_cks)
889 {
890  int ii = 0;
891  if(xx == get_null()){
892  ctr++;
893  if(tot == 0){ tot = ctr; }
894  REDBLACK_CK((tot == 0) || (ctr == tot));
895 
896  if(! just_cks){
897  for(ii = 0; ii < tb; ii++){ os << "\t"; }
898  os << "#nil" << bj_eol;
899  }
900  return os;
901  }
902 
903  char* cl = as_pt_char("");
904  if(is_black(xx)){ ctr++; cl = as_pt_char("#"); }
905 
906  // right subtree
907  rbt_nod_ref_t rgt = get_right(xx);
908  REDBLACK_CK((rgt == get_null()) || (cmp(rgt, xx) > 0));
909  REDBLACK_CK((rgt == get_null()) || (get_parent(rgt) == xx));
910  REDBLACK_CK(!(is_red(xx) && is_red(rgt)));
911  print_rec(os, rgt, tb+1, prev, lst_nod, tot, ctr, just_cks);
912 
913  // node
914  if(! just_cks){
915  for(ii = 0; ii < tb; ii++){ os << "\t"; }
916  os.flush();
917  }
918  REDBLACK_CK(check_refs(xx, 32));
919  char* min = as_pt_char("");
920  if(xx == get_min()){
921  min = as_pt_char("<");
922  }
923  char* max = as_pt_char("");
924  if(xx == get_max()){
925  max = as_pt_char(">");
926  }
927  if(! just_cks){
928  os << cl << min << get_obj(xx) << max << bj_eol;
929  os.flush();
930  }
931  if((lst_nod != get_null()) && (xx == lst_nod)){
932  prev = true;
933  }
934 
935  // left subtree
936  rbt_nod_ref_t lft = get_left(xx);
937  REDBLACK_CK((lft == get_null()) || (cmp(lft, xx) < 0));
938  REDBLACK_CK((lft == get_null()) || (get_parent(lft) == xx));
939  REDBLACK_CK(!(is_red(xx) && is_red(lft)));
940  print_rec(os, lft, tb+1, prev, lst_nod, tot, ctr, just_cks);
941  return os;
942 }
943 
944 template<class node_manager_t>
945 bj_ostream&
946 redblack<node_manager_t>::print(bj_ostream& os, bool just_chks,
947  bool htm)
948 {
949  if(just_chks){
950  htm = false;
951  }
952  if(htm){
953  os << "<HEAD>" << bj_eol;
954  os << "<TITLE>Sermo file</TITLE>" << bj_eol;
955  os << "</HEAD>" << bj_eol;
956  os << "<BODY>" << bj_eol;
957  os << "<PRE>" << bj_eol;
958  }
959 
960  int total = 0;
961  bool prev = false;
962  print_rec(os, root, 0, prev, last_found, total, 0, just_chks);
963  REDBLACK_CK((last_found == get_null()) || prev);
964  REDBLACK_CK(check_min_max());
965 
966  if(htm){
967  os << "</PRE>" << bj_eol;
968  os << "</BODY>" << bj_eol;
969  }
970  return os;
971 }
972 
973 template<class node_manager_t>
974 bool
975 redblack<node_manager_t>::check_order(){
976  redblack_iter<node_manager_t> iter1(*this);
977 
978  redblack<node_manager_t>::rbt_obj_t obj1;
979  redblack<node_manager_t>::rbt_obj_t obj2;
980  bool is_1 = true;
981 
982  iter1.go_first_ref();
983  while(! iter1.in_null()){
984  if(is_1){
985  obj2 = iter1.get_obj();
986  } else {
987  obj1 = obj2;
988  obj2 = iter1.get_obj();
989  comparison cc = cmp_objs(obj1, obj2);
990  if(cc >= 0){
991  abort_func(0, as_pt_char("check_failed !!!"));
992  }
993  }
994  iter1++;
995  }
996  return true;
997 }
998 
999 #endif // REDBLACK_H
1000 
Generated on Fri Jun 16 2017 16:56:09 for Doxygen-Documentation by   doxygen 1.8.11