home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / basic / _pers_tr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  23.8 KB  |  1,144 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _pers_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/pers_tree.h>
  18.  
  19.  
  20. #define LEFT 0
  21. #define RIGHT 1
  22. #define f_isred(p)   ((p)->f_color)
  23. #define c_isred(p)   ((p)->c_color)
  24. #define f_mred(p)    ((p)->f_color=1)
  25. #define c_mred(p)    ((p)->c_color=1)
  26. #define f_mblack(p)  ((p)->f_color=0)
  27. #define c_mblack(p)  ((p)->c_color=0)
  28. #define f_lchild(p)  ((p)->f_link[0])
  29. #define c_lchild(p)  ((p)->c_link[0])
  30. #define f_rchild(p)  ((p)->f_link[1])
  31. #define c_rchild(p)  ((p)->c_link[1])
  32. #define f_parent(p)  ((p)->f_link[2])
  33. #define c_parent(p)  ((p)->c_link[2])
  34. #define f_isleaf(p)  (f_lchild(p)==(p))
  35. #define c_isleaf(p)  (c_lchild(p)==(p))
  36.  
  37.  
  38. void pers_rb_tree::f_rbclear(F_NODE* p)
  39. { if (!(f_isleaf(p)))
  40.     { f_rbclear(f_lchild(p));
  41.       f_rbclear(f_rchild(p));
  42.      }
  43.   delete p;
  44.  }
  45.  
  46. void pers_rb_tree::c_rbclear(C_NODE* p)
  47. { if (!(c_isleaf(p)))
  48.     { c_rbclear(c_lchild(p));
  49.       c_rbclear(c_rchild(p));
  50.      }
  51.   delete p;
  52. }
  53.  
  54.  
  55. F_NODE* pers_rb_tree::f_rbsearch(F_NODE* p, version i)
  56. {
  57.   F_NODE *q;
  58.   
  59.   q = f_rchild(p);
  60.   while (!(f_isleaf(q)))
  61.   {  
  62.     if (i == q->ver_stamp || vless(i, q->ver_stamp))
  63.       q = f_lchild(q);
  64.     else
  65.       q = f_rchild(q);
  66.   }
  67.   return(q);
  68. }
  69.  
  70. C_NODE* pers_rb_tree::c_rbsearch(C_NODE* p, version i)
  71. {
  72.   C_NODE *q;
  73.   
  74.   q = c_rchild(p);
  75.   while (!(c_isleaf(q)))
  76.   {
  77.     if (i == q->vers_stamp || vless(i, q->vers_stamp))
  78.       q = c_lchild(q);
  79.     else
  80.       q = c_rchild(q);
  81.   }
  82.   return(q);
  83. }
  84.  
  85. F_NODE * pers_rb_tree::f_nleaf(NODE* newvalue, version i)
  86. {
  87.   F_NODE* result = new F_NODE;
  88.  
  89.   f_mblack(result);
  90.   result->ver_stamp = i;
  91.   f_lchild(result) = f_rchild(result) = result;
  92.   result->poin_value = newvalue;
  93.   return(result);
  94. }
  95.  
  96. C_NODE * pers_rb_tree::c_nleaf(int newvalue, version i)
  97. {
  98.   C_NODE* result = new C_NODE;
  99.  
  100.   c_mblack(result);
  101.   result->vers_stamp = i;
  102.   c_lchild(result) = c_rchild(result) = result;
  103.   result->col_value = newvalue;
  104.   return(result);
  105. }
  106.  
  107. F_NODE * pers_rb_tree::f_nnode(F_NODE* c1, F_NODE* c2)
  108. {
  109.   F_NODE* result = new F_NODE;
  110.  
  111.   f_mred(result);
  112.   if (vless(c1->ver_stamp, c2->ver_stamp))
  113.   {
  114.     f_lchild(result) = c1;
  115.     c1->f_right = 0;
  116.     f_rchild(result) = c2;
  117.     c2->f_right = 1;
  118.   }
  119.   else
  120.   {
  121.     f_lchild(result) = c2;
  122.     c2->f_right = 0;
  123.     f_rchild(result) = c1;
  124.     c1->f_right = 1;
  125.   }
  126.   f_parent(c1) = f_parent(c2) = result;
  127.   result->ver_stamp = (f_lchild(result))->ver_stamp;
  128.   result->poin_value = NULL;
  129.   return(result);
  130. }
  131.  
  132. C_NODE* pers_rb_tree::c_nnode(C_NODE* c1, C_NODE* c2)
  133. {
  134.   C_NODE* result = new C_NODE;
  135.  
  136.   c_mred(result);
  137.   if (vless(c1->vers_stamp, c2->vers_stamp))
  138.   {
  139.     c_lchild(result) = c1;
  140.     c1->c_right = 0;
  141.     c_rchild(result) = c2;
  142.     c2->c_right = 1;
  143.   }
  144.   else
  145.   {
  146.     c_lchild(result) = c2;
  147.     c2->c_right = 0;
  148.     c_rchild(result) = c1;
  149.     c1->c_right = 1;
  150.   }
  151.   c_parent(c1) = c_parent(c2) = result;
  152.   result->vers_stamp = (c_lchild(result))->vers_stamp;
  153.   result->col_value = 0;  
  154.   return(result);
  155. }
  156.  
  157. void  pers_rb_tree::f_single_rot(F_NODE* top_node, int dir)
  158. {
  159.   F_NODE *temp, *q;
  160.  
  161.   q = top_node->f_link[1-dir];
  162.   top_node->f_link[1-dir] = temp = q->f_link[dir];
  163.   temp->f_right = 1 - dir;
  164.   f_parent(temp) = top_node;
  165.   q->f_link[dir] = top_node;
  166.   temp = f_parent(top_node);
  167.   f_parent(top_node) = q;
  168.   q->f_right = top_node->f_right;
  169.   temp->f_link[top_node->f_right] = q;
  170.   f_parent(q) = temp;
  171.   top_node->f_right = dir;
  172.   return;
  173. }
  174.  
  175. void  pers_rb_tree::c_single_rot(C_NODE* top_node, int dir)
  176. {
  177.   C_NODE *temp, *q;
  178.  
  179.   q = top_node->c_link[1-dir];
  180.   top_node->c_link[1-dir] = temp = q->c_link[dir];
  181.   temp->c_right = 1 - dir;
  182.   c_parent(temp) = top_node;
  183.   q->c_link[dir] = top_node;
  184.   temp = c_parent(top_node);
  185.   c_parent(top_node) = q;
  186.   q->c_right = top_node->c_right;
  187.   temp->c_link[top_node->c_right] = q;
  188.   c_parent(q) = temp;
  189.   top_node->c_right = dir;
  190.   return;
  191. }
  192.  
  193.  
  194. void  pers_rb_tree::f_double_rot(F_NODE* top_node, int dir)
  195. {
  196.   F_NODE *q, *r, *temp;
  197.  
  198.   q = top_node->f_link[1-dir];
  199.   r = q->f_link[dir];
  200.   top_node->f_link[1-dir] = temp = r->f_link[dir];
  201.   temp->f_right = 1 - dir;
  202.   f_parent(temp) = top_node;
  203.   q->f_link[dir] = (temp = r->f_link[1-dir]);
  204.   temp->f_right = dir;
  205.   f_parent(temp) = q;
  206.   temp = f_parent(top_node);
  207.   r->f_right = top_node->f_right;
  208.   r->f_link[dir] = top_node;
  209.   f_parent(top_node) = r;
  210.   top_node->f_right = dir;
  211.   r->f_link[1-dir] = q;
  212.   f_parent(q) = r;
  213.   temp->f_link[r->f_right] = r;
  214.   f_parent(r) = temp;
  215.   return;
  216. }
  217.  
  218. void  pers_rb_tree::c_double_rot(C_NODE* top_node, int dir)
  219. {
  220.   C_NODE *q, *r, *temp;
  221.  
  222.   q = top_node->c_link[1-dir];
  223.   r = q->c_link[dir];
  224.   top_node->c_link[1-dir] = temp = r->c_link[dir];
  225.   temp->c_right = 1 - dir;
  226.   c_parent(temp) = top_node;
  227.   q->c_link[dir] = (temp = r->c_link[1-dir]);
  228.   temp->c_right = dir;
  229.   c_parent(temp) = q;
  230.   temp = c_parent(top_node);
  231.   r->c_right = top_node->c_right;
  232.   r->c_link[dir] = top_node;
  233.   c_parent(top_node) = r;
  234.   top_node->c_right = dir;
  235.   r->c_link[1-dir] = q;
  236.   c_parent(q) = r;
  237.   temp->c_link[r->c_right] = r;
  238.   c_parent(r) = temp;
  239.   return;
  240. }
  241.  
  242.  
  243. int pers_rb_tree::f_insert(F_NODE* head, NODE* newvalue, version i)
  244. {
  245.   int aux_bool;
  246.   F_NODE *p, *q, *r, *aux_node;
  247.  
  248.   if (f_rchild(head) == NULL)
  249.   {
  250.     p = f_nleaf(newvalue, i);
  251.     p->f_right = 1;
  252.     f_parent(p) = head;
  253.     f_rchild(head) = p;
  254.     return(0);
  255.   }
  256.   p = f_rbsearch(head, i);
  257.   if (p->ver_stamp == i)
  258.   {
  259.     p->poin_value = newvalue;
  260.     return(1);
  261.   }
  262.   q = f_nleaf(newvalue, i);
  263.   aux_bool = p->f_right;
  264.   aux_node = f_parent(p);
  265.   r = f_nnode(p, q);
  266.   f_parent(r) = aux_node;
  267.   r->f_right = aux_bool;
  268.   aux_node->f_link[aux_bool] = r;
  269.   if (!f_isred(aux_node))
  270.   {
  271.     f_mblack(f_rchild(head));
  272.     return(0);
  273.   }
  274.   q = aux_node;
  275.   p = f_parent(q);
  276.   while ((f_isred(f_lchild(p))) && (f_isred(f_rchild(p))))
  277.   {
  278.     f_mblack(f_lchild(p));
  279.     f_mblack(f_rchild(p));
  280.     f_mred(p);
  281.     r = p;
  282.     q = f_parent(r);
  283.     if (!f_isred(q))
  284.     {
  285.       f_mblack(f_rchild(head));
  286.       return(0);
  287.     }
  288.     p = f_parent(q);
  289.   }
  290.   if (q->f_right == r->f_right)
  291.   {
  292.     f_mred(p);
  293.     f_mblack(q);
  294.     f_single_rot(p, 1-r->f_right);
  295.   }
  296.   else
  297.   {
  298.     f_mblack(r);
  299.     f_mred(p);
  300.     f_double_rot(p, r->f_right);
  301.   }
  302.   f_mblack(f_rchild(head));
  303.   return(0);
  304. }
  305.  
  306. int pers_rb_tree::c_insert(C_NODE* head, int newvalue, version i)
  307. {
  308.   int aux_bool;
  309.   C_NODE *p, *q, *r, *aux_node;
  310.  
  311.   if (c_rchild(head) == NULL)
  312.   {
  313.     p = c_nleaf(newvalue, i);
  314.     p->c_right = 1;
  315.     c_parent(p) = head;
  316.     c_rchild(head) = p;
  317.     return(0);
  318.   }
  319.   p = c_rbsearch(head, i);
  320.   if (p->vers_stamp == i)
  321.   {
  322.     p->col_value = newvalue;
  323.     return(1);
  324.   }
  325.   q = c_nleaf(newvalue, i);
  326.   aux_bool = p->c_right;
  327.   aux_node = c_parent(p);
  328.   r = c_nnode(p, q);
  329.   c_parent(r) = aux_node;
  330.   r->c_right = aux_bool;
  331.   aux_node->c_link[aux_bool] = r;
  332.   if (!c_isred(aux_node))
  333.   {
  334.     c_mblack(c_rchild(head));
  335.     return(0);
  336.   }
  337.   q = aux_node;
  338.   p = c_parent(q);
  339.   while ((c_isred(c_lchild(p))) && (c_isred(c_rchild(p))))
  340.   {
  341.     c_mblack(c_lchild(p));
  342.     c_mblack(c_rchild(p));
  343.     c_mred(p);
  344.     r = p;
  345.     q = c_parent(r);
  346.     if (!c_isred(q))
  347.     {
  348.       c_mblack(c_rchild(head));
  349.       return(0);
  350.     }
  351.     p = c_parent(q);
  352.   }
  353.   if (q->c_right == r->c_right)
  354.   {
  355.     c_mred(p);
  356.     c_mblack(q);
  357.     c_single_rot(p, 1-r->c_right);
  358.   }
  359.   else
  360.   {
  361.     c_mblack(r);
  362.     c_mred(p);
  363.     c_double_rot(p, r->c_right);
  364.   }
  365.   c_mblack(c_rchild(head));
  366.   return(0);
  367. }
  368.  
  369.  
  370.  
  371. /* insert the new version in the appropriate position and update the 
  372.  * version list
  373.  */
  374.  
  375. version pers_rb_tree::new_version(version i)
  376. {
  377.  
  378.   version succ = v_list->vl.succ(i);
  379.   
  380.   ver_node p = new VER_NODE;
  381.  
  382.   if (succ != nil)
  383.      p->ser_num = (v_list->vl[i]->ser_num + v_list->vl[succ]->ser_num) / 2.0;
  384.   else 
  385.      p->ser_num = v_list->vl[i]->ser_num + 1000;
  386.  
  387.  
  388.   p->popul = v_list->vl[i]->popul;
  389.   p->acc_pointer = v_list->vl[i]->acc_pointer;
  390.   v_list->count++;
  391.   return v_list->vl.insert(p,i);
  392. }
  393.  
  394. /* implementation of the update step (change of left or right child)
  395.  * for a specific persistent node and update operation 
  396.  */
  397.  
  398. void pers_rb_tree::update(F_NODE* p, NODE* newvalue, version i)
  399. { 
  400.   F_NODE *p1, *i1, *i2;
  401.  
  402.   version ip = v_list->vl.succ(i);
  403.  
  404.   if (f_insert(p, newvalue, i) == 1) return;
  405.  
  406.   if (ip == nil || vless(ip,p->ver_stamp)) return;
  407.  
  408.   p1 = f_rbsearch(p, i);
  409.   if (p1->f_right)
  410.   {
  411.     i1 = f_lchild(f_parent(p1));
  412.     if (f_isleaf(i1))
  413.       goto la;
  414.     else
  415.       i1 = f_rchild(i1);
  416. la: while (p1 != f_rchild(p) && p1->f_right)
  417.       p1 = f_parent(p1);
  418.     if (p1 == f_rchild(p))
  419.       i2 = NULL;
  420.     else
  421.     {
  422.       i2 = f_rchild(f_parent(p1));
  423.       while (!f_isleaf(i2))
  424.         i2 = f_lchild(i2);
  425.     }
  426.   }
  427.   else
  428.   {
  429.     i2 = f_rchild(f_parent(p1));
  430.     if (f_isleaf(i2))
  431.       goto m;
  432.     else
  433.       i2 = f_lchild(i2);
  434.  m: while (p1->f_right == 0)
  435.       p1 = f_parent(p1);
  436.     i1 = f_lchild(f_parent(p1));
  437.     while (!f_isleaf(i1))
  438.       i1 = f_rchild(i1);
  439.   }
  440.   if (i2 == NULL || vless(ip, i2->ver_stamp))
  441.      f_insert(p, i1->poin_value, ip);
  442. }
  443.    
  444.  
  445. /* implementation of the update step (change of color) for a specific
  446.  * persistent node and update operation 
  447.  */
  448.  
  449. void pers_rb_tree::up_col(C_NODE* p, int newvalue, version i)
  450. { 
  451.   C_NODE *p1, *i1, *i2;
  452.   
  453.   version ip = v_list->vl.succ(i);
  454.  
  455.   if (c_insert(p, newvalue, i) == 1) return;
  456.  
  457.   if (ip ==nil  || vless(ip,p->vers_stamp)) return;
  458.  
  459.   p1 = c_rbsearch(p, i);
  460.   if (p1->c_right)
  461.   {
  462.     i1 = c_lchild(c_parent(p1));
  463.     if (c_isleaf(i1))
  464.       goto lb;
  465.     else
  466.       i1 = c_rchild(i1);
  467. lb: while (p1 != c_rchild(p) && p1->c_right)
  468.       p1 = c_parent(p1);
  469.     if (p1 == c_rchild(p))
  470.       i2 = NULL;
  471.     else
  472.     {
  473.       i2 = c_rchild(c_parent(p1));
  474.       while (!c_isleaf(i2))
  475.         i2 = c_lchild(i2);
  476.     }
  477.   }
  478.   else
  479.   {
  480.     i2 = c_rchild(c_parent(p1));
  481.     if (c_isleaf(i2))
  482.       goto ma;
  483.     else
  484.       i2 = c_lchild(i2);
  485. ma: while (p1->c_right == 0)
  486.       p1 = c_parent(p1);
  487.     i1 = c_lchild(c_parent(p1));
  488.     while (!c_isleaf(i1))
  489.       i1 = c_rchild(i1);
  490.   }
  491.   if (i2 == NULL || vless(ip, i2->vers_stamp))
  492.      c_insert(p, i1->col_value, ip);
  493. }
  494.    
  495.  
  496. /* implementation of the access step for a specific persistent node 
  497.  * and version 
  498.  */
  499.  
  500. NODE * pers_rb_tree::acc_step(F_NODE *head, version i)
  501. {
  502.   F_NODE *q, *i1;
  503.  
  504.   q = f_rbsearch(head, i);
  505.   if (q->ver_stamp == i)
  506.     return(q->poin_value);
  507.   if (vless(q->ver_stamp, i))
  508.     return(q->poin_value);
  509.   if (q->f_right)
  510.   {
  511.      i1 = f_lchild(f_parent(q));
  512.      if (f_isleaf(i1))
  513.        goto t;
  514.      else
  515.        i1 = f_rchild(i1);
  516.   }
  517.   else
  518.   {
  519.     while (q->f_right == 0)
  520.       q = f_parent(q);
  521.     i1 = f_lchild(f_parent(q));
  522.     while (!f_isleaf(i1))
  523.       i1 = f_rchild(i1);
  524.   }
  525. t:return(i1->poin_value);
  526. }
  527.   
  528.  
  529.  
  530. /* find out whether a given persistent node is red or not in a 
  531.  * specific version 
  532.  */
  533.  
  534. int pers_rb_tree::isred(NODE* p, version i)
  535. {
  536.   C_NODE *head, *q, *i1;
  537.   
  538.   if (isleaf(p))
  539.     return(0);
  540.   head = p->red;
  541.   q = c_rbsearch(head, i);
  542.   if (q->vers_stamp == i)
  543.     return(q->col_value);
  544.   if (vless(q->vers_stamp, i))
  545.     return(q->col_value);
  546.   if (q->c_right)
  547.   {  
  548.      i1 = c_lchild(c_parent(q));
  549.      if (c_isleaf(i1))
  550.        goto s;
  551.      else
  552.        i1 = c_rchild(i1);
  553.   }
  554.   else
  555.   {
  556.     while (q->c_right == 0)
  557.       q = c_parent(q);
  558.     i1 = c_lchild(c_parent(q));
  559.     while (!c_isleaf(i1))
  560.       i1 = c_rchild(i1);
  561.   }
  562. s:return(i1->col_value);
  563. }
  564.  
  565.  
  566. /* create a new leaf and initialize the fields with the appropriate values */
  567.  
  568. NODE* pers_rb_tree::newleaf(void* val, void* inf, NODE* pred, NODE* succ, version i)
  569. {
  570.   NODE *result;
  571.   F_NODE *res1, *res2;
  572.   C_NODE *res3;
  573.   
  574.   result = new NODE;
  575.   res1   = new F_NODE;
  576.   res2   = new F_NODE;
  577.   res3   = new C_NODE;
  578.    
  579.     result->key = val;
  580.     result->info = inf;
  581.     result->parent = NULL;
  582.     result->right = 1;
  583.     result->is_leaf = 1;
  584.     result->copy = NULL;
  585.  
  586.     result->next = v_list->used;
  587.     v_list->used = result;
  588.  
  589.     res1->ver_stamp = res2->ver_stamp = res3->vers_stamp = i;
  590.  
  591.     f_lchild(res1) = f_rchild(res1) = f_parent(res1) = NULL;
  592.     f_lchild(res2) = f_rchild(res2) = f_parent(res2) = NULL;
  593.     c_lchild(res3) = c_rchild(res3) = c_parent(res3) = NULL;
  594.  
  595.     res1->f_right = res2->f_right = res3->c_right = 1;
  596.     res1->f_color = res2->f_color = res3->c_color = 0;
  597.  
  598.     res1->poin_value = res2->poin_value = NULL; 
  599.     res3->col_value = 0;  
  600.  
  601.     f_insert(res1, pred, i);
  602.     f_insert(res2, succ, i);
  603.     c_insert(res3, 0, i);
  604.  
  605.     result->link[0] = res1;
  606.     result->link[1] = res2;
  607.     result->red     = res3;
  608.  
  609.     return result;
  610. }
  611.  
  612. /* create a new persistent node and initialize its fields with the
  613.  * appropriate values 
  614.  */
  615.  
  616. NODE* pers_rb_tree::newnode(NODE* c1, NODE* c2, version i)
  617. {
  618.   // c1 and c2 are leaves
  619.  
  620.   NODE *result;
  621.   F_NODE *res1, *res2,  *res4;   // s.n. : res4 pointer to leaf (copy)
  622.   C_NODE *res3;
  623.   
  624.   result = new NODE;
  625.   res1   = new F_NODE;
  626.   res2   = new F_NODE;
  627.   res3   = new C_NODE;
  628.   res4   = new F_NODE;
  629.  
  630.     result->parent = NULL;
  631.  
  632.     result->next = v_list->used;
  633.     v_list->used = result;
  634.  
  635.     res1->ver_stamp = res2->ver_stamp = res3->vers_stamp = i;
  636.  
  637.     f_lchild(res1) = f_rchild(res1) = f_parent(res1) = NULL;
  638.     f_lchild(res2) = f_rchild(res2) = f_parent(res2) = NULL;
  639.     f_lchild(res4) = f_rchild(res4) = f_parent(res4) = NULL;
  640.     c_lchild(res3) = c_rchild(res3) = c_parent(res3) = NULL;
  641.  
  642.     res1->f_right = res2->f_right = res3->c_right = res4->f_right = 1;
  643.     res1->f_color = res2->f_color = res3->c_color = res4->f_color = 0;
  644.  
  645.     res1->poin_value = res2->poin_value = res4->poin_value = NULL; 
  646.     res3->col_value = 1;  
  647.  
  648.     c_insert(res3, 1, i);
  649.  
  650.     if (cmp_keys(c1->key, c2->key) < 1)
  651.     {
  652.       f_insert(res1, c1, i);
  653.       f_insert(res2, c2, i);
  654.       f_insert(res4, c1, i);
  655.       result->key = c1->key;
  656.     }
  657.     else
  658.     {
  659.       f_insert(res1, c2, i);
  660.       f_insert(res2, c1, i);
  661.       f_insert(res4, c2, i);
  662.       result->key = c2->key;
  663.     }
  664.  
  665.     result->link[0] = res1;
  666.     result->link[1] = res2;
  667.     result->red     = res3;
  668.     result->copy    = res4;
  669.     result->is_leaf = 0;
  670.  
  671.     return(result);
  672. }
  673.  
  674.   
  675. /* implementation of the single rotation for the fully persistent
  676.  * red-black tree
  677.  */
  678.  
  679. NODE* pers_rb_tree::single_rot(NODE* top_node, int dir, version i)
  680. {
  681.   NODE *temp, *q, *newroot;
  682.   
  683.   newroot = NULL;
  684.   q = child(1 - dir, top_node, i);
  685.   temp = child(dir, q, i);
  686.   update(top_node->link[1 - dir], temp, i);
  687.   update(q->link[dir], top_node, i);
  688.   if ((temp = top_node->parent) == NULL)
  689.     newroot = q;
  690.   top_node->parent = q;
  691.   if (temp != NULL)
  692.     update(temp->link[top_node->right], q, i);
  693.   top_node->right = dir;
  694.   return(newroot);
  695. }
  696.  
  697. /* implementation of the double rotation for the fully persistent
  698.  * red-black tree
  699.  */
  700.  
  701. NODE* pers_rb_tree::double_rot(NODE* top_node, int dir, version i)
  702. {
  703.   NODE *q, *r, *temp, *newroot;
  704.   
  705.   newroot = NULL;
  706.   q = child(1 - dir, top_node, i);
  707.   r = child(dir, q, i);
  708.   temp = child(dir, r, i);
  709.   update(top_node->link[1 - dir], temp, i);
  710.   temp = child(1 - dir, r, i);
  711.   update(q->link[dir], temp, i);
  712.   if ((temp = top_node->parent) == NULL)
  713.     newroot = r;
  714.   update(r->link[dir], top_node, i);
  715.   update(r->link[1 - dir], q, i);
  716.   if (temp != NULL)
  717.     update(temp->link[top_node->right], r, i);
  718.   return(newroot);
  719. }
  720.  
  721. /* the root is colored black after each  update operation */
  722.  
  723. void pers_rb_tree::m_b_root(version i)
  724. {
  725.   NODE *p;
  726.  
  727.   p = v_list->vl[i]->acc_pointer;
  728.  
  729.   if (p != NULL && !isleaf(p) && isred(p, i))
  730.      up_col(p->red, 0, i);
  731. }
  732.  
  733.  
  734.  
  735.  
  736. //------------------------------------------------------------------------------
  737. // member functions
  738. //------------------------------------------------------------------------------
  739.  
  740.  
  741. void pers_rb_tree::init_tree()
  742. {
  743.    /* create dummy (empty) version 0 */
  744.    ver_node v = new VER_NODE;
  745.    v->ser_num =  0;
  746.    v->popul   =  0;
  747.    v->acc_pointer = NULL;
  748.    v_list = new V_LIST;
  749.    v_list->vl.append(v);
  750.    v_list->count = 1;
  751.  
  752.    v_list->used = NULL;
  753.  
  754. }
  755.  
  756. NODE* pers_rb_tree::search(void *val, NODE*& copy, version i)
  757. {
  758.   NODE *p, *q;
  759.  
  760.   copy = NULL;
  761.   
  762.   if ((p = v_list->vl[i]->acc_pointer) == NULL)
  763.     return(NULL);
  764.  
  765.   p->parent = NULL;
  766.   p->right = 1;
  767.   while (!isleaf(p))
  768.   {
  769.     int v = cmp_keys(val, get_key(p,i));
  770.  
  771.     if (v < 1)
  772.     { if (v==0) copy = p;
  773.       q = p;
  774.       p = child(0, p, i);
  775.       p->parent = q;
  776.       p->right = 0;
  777.      }
  778.     else
  779.     { q = p;
  780.       p = child(1, p, i);
  781.       p->parent = q;
  782.       p->right = 1;
  783.      }
  784.    }
  785.  
  786.    return p;
  787. }
  788.  
  789.  
  790.  
  791. version  pers_rb_tree::del(void *val, version i1)
  792. {
  793.   NODE *pos_del, *par1, *par2, *root, *newroot, *temp, *copy;
  794.   
  795.   if ((pos_del = search(val, copy, i1)) == NULL) return i1; //empty tree
  796.  
  797.   if (cmp_keys(pos_del->key, val) != 0) return i1;  // key not found
  798.  
  799.   version i  = new_version(i1);
  800.  
  801.   if ((--(v_list->vl[i]->popul)) == 0)
  802.   {
  803.     v_list->vl[i]->acc_pointer = NULL;
  804.     return i;
  805.   }
  806.  
  807.  
  808.   //update links to neighbor leaves
  809.  
  810.   NODE* pred = child(0,pos_del,i);
  811.   NODE* succ = child(1,pos_del,i);
  812.  
  813.   if (pred) update(pred->link[1],succ,i);
  814.   if (succ) update(succ->link[0],pred,i);
  815.  
  816.  
  817.   root = v_list->vl[i]->acc_pointer;
  818.  
  819.   if ((par1 = pos_del->parent) == root)
  820.   {
  821.     v_list->vl[i]->acc_pointer = sibling(pos_del, i);
  822.     goto end;
  823.    }
  824.  
  825.   par2 = par1->parent;
  826.   pos_del = sibling(pos_del, i);
  827.   update(par2->link[par1->right], pos_del, i);
  828.   pos_del->parent = par2;
  829.   pos_del->right = par1->right;
  830.  
  831.   if (copy != NULL && copy != par1)  // we have to overwrite copy  by pred
  832.   {
  833.     update(copy->copy, pred, i);
  834.  
  835.    }
  836.   
  837.  
  838.   if (isred(par1, i))
  839.     goto end;
  840.   if (isred(pos_del, i))
  841.   {
  842.     up_col(pos_del->red, 0, i);
  843.     goto end;
  844.   }
  845.   par1 = sibling(pos_del, i);
  846.   while ((!isred(par1, i)) && (!isred(child(0, par1, i), i)) &&
  847.          (!isred(child(1, par1, i), i)))
  848.   {
  849.     up_col(par1->red, 1, i);
  850.     pos_del = pos_del->parent;
  851.     if (isred(pos_del, i))
  852.     {
  853.       up_col(pos_del->red, 0, i);
  854.       goto end;
  855.     }
  856.     if (pos_del == root)
  857.       goto end;
  858.     else
  859.       par1 = sibling(pos_del, i);
  860.   }
  861.   par2 = pos_del->parent;
  862.   if (isred(par1, i))
  863.   {
  864.     up_col(par2->red, 1, i);
  865.     up_col(par1->red, 0,i);
  866.     if ((newroot = single_rot(par2, pos_del->right, i)) != NULL)
  867.       v_list->vl[i]->acc_pointer = newroot;
  868.     par1 = sibling(pos_del,i);
  869.     if ((!isred(child(0, par1, i), i)) && (!isred(child(1, par1, i), i)))
  870.     {
  871.       up_col(par1->red, 1, i);
  872.       up_col((pos_del->parent)->red, 0, i);
  873.       goto end;
  874.     }
  875.   }
  876.   par2 = pos_del->parent;
  877.   if (!pos_del->right)
  878.     if (isred(child(0, par1, i), i))
  879.     {
  880.       temp = child(0, par1, i);
  881.       up_col(temp->red, isred(par2, i), i);
  882.       up_col(par2->red, 0, i);
  883.       newroot = double_rot(par2, LEFT, i);
  884.     }
  885.     else
  886.     {
  887.       up_col(par1->red, isred(par2, i), i);
  888.       up_col(par2->red, 0, i);
  889.       temp = child(1, par1, i);
  890.       up_col(temp->red, 0, i);
  891.       newroot = single_rot(par2, LEFT, i);
  892.     }
  893.   else
  894.     if (isred(child(0, par1, i), i))
  895.     {
  896.       up_col(par1->red, isred(par2, i), i);
  897.       up_col(par2->red, 0, i);
  898.       temp = child(0, par1, i);
  899.       up_col(temp->red, 0, i);
  900.       newroot = single_rot(par2, RIGHT, i);
  901.     }
  902.     else
  903.     {
  904.       temp = child(1, par1, i);
  905.       up_col(temp->red, isred(par2, i), i);
  906.       up_col(par2->red, 0, i);
  907.       newroot = double_rot(par2, RIGHT, i);
  908.     }
  909.   if (newroot != NULL)
  910.     v_list->vl[i]->acc_pointer = newroot;
  911.  
  912. end:
  913.   m_b_root(i);
  914.   return i;
  915. }
  916.  
  917.  
  918. version pers_rb_tree::insert(void *val, void* info, version i1)
  919. {
  920.   int aux_bool; 
  921.   NODE *p, *q, *r, *aux_node, *root, *newroot, *temp;
  922.  
  923.   p = search(val, i1);
  924.  
  925.   if (p && cmp_keys(p->key, val) == 0) return i1;  // key already there
  926.  
  927.   version i = new_version(i1);
  928.  
  929.   copy_key(val);
  930.   copy_inf(info);
  931.   
  932.   if (p == NULL)   // empty tree
  933.   { copy_key(val);
  934.     copy_inf(info);
  935.     p = newleaf(val, info, nil, nil, i);
  936.     v_list->vl[i]->acc_pointer = p;
  937.     v_list->vl[i]->popul = 1;
  938.     goto end;
  939.   }
  940.  
  941.   (v_list->vl[i]->popul)++;
  942.  
  943.   if (cmp_keys(val, p->key) > 0)   // new rightmost leaf 
  944.     { q = newleaf(val,info, p, nil, i);   
  945.       update(p->link[1], q, i);
  946.      }
  947.   else // new  leaf before  p 
  948.     { NODE * pred = child(0,p,i);
  949.       q = newleaf(val,info, pred, p, i);   
  950.       update(p->link[0], q, i);
  951.       if (pred) update(pred->link[1], q, i);
  952.      }
  953.  
  954.   aux_bool = p->right;
  955.   r = newnode(p, q, i);
  956.  
  957.   if (p->parent == NULL)
  958.   {
  959.     v_list->vl[i]->acc_pointer = r;
  960.     goto end;
  961.   }
  962.   aux_node = p->parent;
  963.   r->right = aux_bool;
  964.   update(aux_node->link[aux_bool], r, i);
  965.  
  966.   if (!isred(aux_node, i))
  967.      goto end;
  968.  
  969.   q = aux_node;
  970.   p = q->parent;
  971.   root = v_list->vl[i]->acc_pointer;
  972.   while ((isred(child(0, p, i), i)) && (isred(child(1, p, i), i)))
  973.   {
  974.     temp = child(0, p, i);
  975.     up_col(temp->red, 0, i);
  976.     temp = child(1, p, i);
  977.     up_col(temp->red, 0, i);
  978.     up_col(p->red, 1, i);
  979.     if (p == root)
  980.       goto end;
  981.     r = p;
  982.     q = r->parent;
  983.     if (!isred(q, i))
  984.       goto end;
  985.     p = q->parent;
  986.   }
  987.   if (q->right == r->right)
  988.   {
  989.     up_col(p->red, 1, i);
  990.     up_col(q->red, 0, i);
  991.     newroot = single_rot(p, 1 - r->right, i);
  992.   }
  993.   else
  994.   {
  995.     up_col(r->red, 0, i);
  996.     up_col(p->red, 1, i);
  997.     newroot = double_rot(p, r->right, i);
  998.   }
  999.  
  1000.   if (newroot != NULL)
  1001.     v_list->vl[i]->acc_pointer = newroot;
  1002.  
  1003. end:
  1004.   m_b_root(i);
  1005.   return i;
  1006. }
  1007.  
  1008.  
  1009. version pers_rb_tree::change_inf(NODE* p, void* info, version i1)
  1010. {
  1011.   version i = new_version(i1);
  1012.  
  1013.   p = search(p->key, i1);  // setting parent pointers
  1014.  
  1015.   NODE* pred = child(0,p,i);
  1016.   NODE* succ = child(1,p,i);
  1017.  
  1018.   copy_inf(info);
  1019.   NODE* q = newleaf(p->key,info, pred, succ, i);   
  1020.  
  1021.  
  1022.   if (pred) update(pred->link[1],q,i);
  1023.   if (succ) update(succ->link[0],q,i);
  1024.  
  1025.   q->right = p->right;
  1026.   update(p->parent->link[q->right], q, i);
  1027.  
  1028.   return i;
  1029.  
  1030. }
  1031.  
  1032.  
  1033.  
  1034. NODE* pers_rb_tree::min(version v)
  1035. { NODE* r = v_list->vl[v]->acc_pointer;
  1036.   if (r == nil) return nil;
  1037.   while ( ! isleaf(r)) r = child(0,r,v);
  1038.   return r;
  1039. }  
  1040.  
  1041. NODE* pers_rb_tree::max(version v)
  1042. { NODE* r = v_list->vl[v]->acc_pointer;
  1043.   if (r == nil) return nil;
  1044.   while ( ! isleaf(r)) r = child(1,r,v);
  1045.   return r;
  1046. }  
  1047.  
  1048. void pers_rb_tree::print(NODE *p, version v)
  1049. { if (p)
  1050.   { if (isleaf(p))  
  1051.     { print_key(p->key);
  1052.       cout << " ";
  1053.      }
  1054.     else
  1055.      { print(child(0, p, v), v);
  1056.        print(child(1, p, v), v);
  1057.       }
  1058.    }
  1059. }  
  1060.  
  1061. void pers_rb_tree::del_tree()
  1062. { 
  1063.   while (v_list->used)
  1064.   { NODE* p = v_list->used;
  1065.     v_list->used = v_list->used->next;
  1066.  
  1067.     f_rbclear(f_rchild(p->link[0]));
  1068.     delete p->link[0];
  1069.  
  1070.     f_rbclear(f_rchild(p->link[1]));
  1071.     delete p->link[1];
  1072.  
  1073.     if (p->copy != nil)
  1074.     {
  1075.       f_rbclear(f_rchild(p->copy));
  1076.       delete p->copy;
  1077.      }
  1078.  
  1079.     c_rbclear(c_rchild(p->red));
  1080.     delete p->red;
  1081.  
  1082.     if (isleaf(p))
  1083.     { clear_key(p->key);
  1084.       clear_inf(p->info);
  1085.      }
  1086.  
  1087.     delete p;
  1088.    }
  1089.  
  1090.    ver_node q;
  1091.    forall(q, v_list->vl) delete q;
  1092.  
  1093.    delete v_list;
  1094.  }  
  1095.  
  1096.  
  1097. NODE*  pers_rb_tree::lookup(void *val,version v)
  1098. { NODE* p = search(val,v);
  1099.   return (p && cmp_keys(key(p), val) == 0) ? p : nil;
  1100.  }
  1101.  
  1102. NODE* pers_rb_tree::locate(void *val,version v)
  1103. { NODE* p = search(val,v);
  1104.   return ( p && cmp_keys(key(p), val) >= 0) ?  p : nil;
  1105.  }
  1106.  
  1107. NODE* pers_rb_tree::locate_pred(void *val,version v)
  1108. { NODE* p = search(val,v);
  1109.   if (p==0) return nil;
  1110.   if (cmp_keys(key(p), val) <= 0)  return p;
  1111.   return child(0,p,v);
  1112.  
  1113. }
  1114.  
  1115.  
  1116.  
  1117.  
  1118. void pers_rb_tree::draw(DRAW_NODE_FCT draw_node,
  1119.                         DRAW_EDGE_FCT draw_edge, 
  1120.                         version v, NODE* r, 
  1121.                         double x1, double x2, double y, 
  1122.                         double ydist, double last_x)
  1123. { 
  1124.  
  1125.   double x = (x1+x2)/2;
  1126.  
  1127.   if (r==NULL) return;
  1128.  
  1129.   if (last_x != 0) draw_edge(last_x,y+ydist,x,y);
  1130.  
  1131.   if (isleaf(r)) 
  1132.      draw_node(x,y,r->key);
  1133.   else
  1134.     { draw_node(x,y,get_key(r,v));
  1135.       draw(draw_node,draw_edge,v,child(0,r,v),x1,x,y-ydist,ydist,x);
  1136.       draw(draw_node,draw_edge,v,child(1,r,v),x,x2,y-ydist,ydist,x);
  1137.      }
  1138. }
  1139.  
  1140. void pers_rb_tree::draw(DRAW_NODE_FCT draw_node,
  1141.                         DRAW_EDGE_FCT draw_edge, 
  1142.                         version v, double x1, double x2, double y, double ydist)
  1143. { draw(draw_node,draw_edge,v,v_list->vl[v]->acc_pointer,x1,x2,y,ydist,0); }
  1144.