开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_pers_tree.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：25k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

_pers_tree.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _pers_tree.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #include <LEDA/impl/pers_tree.h>
  16. #define LEFT 0
  17. #define RIGHT 1
  18. #define f_isred(p)   ((p)->f_color)
  19. #define c_isred(p)   ((p)->c_color)
  20. #define f_mred(p)    ((p)->f_color=1)
  21. #define c_mred(p)    ((p)->c_color=1)
  22. #define f_mblack(p)  ((p)->f_color=0)
  23. #define c_mblack(p)  ((p)->c_color=0)
  24. #define f_lchild(p)  ((p)->f_link[0])
  25. #define c_lchild(p)  ((p)->c_link[0])
  26. #define f_rchild(p)  ((p)->f_link[1])
  27. #define c_rchild(p)  ((p)->c_link[1])
  28. #define f_parent(p)  ((p)->f_link[2])
  29. #define c_parent(p)  ((p)->c_link[2])
  30. #define f_isleaf(p)  (f_lchild(p)==(p))
  31. #define c_isleaf(p)  (c_lchild(p)==(p))
  34. void pers_rb_tree::f_rbclear(F_pers_tree_node* p)
  35. { if (!(f_isleaf(p)))
  36.     { f_rbclear(f_lchild(p));
  37.       f_rbclear(f_rchild(p));
  38.      }
  39.   delete p;
  40.  }
  42. void pers_rb_tree::c_rbclear(C_pers_tree_node* p)
  43. { if (!(c_isleaf(p)))
  44.     { c_rbclear(c_lchild(p));
  45.       c_rbclear(c_rchild(p));
  46.      }
  47.   delete p;
  48. }
  51. F_pers_tree_node* pers_rb_tree::f_rbsearch(F_pers_tree_node* p, Version i)
  52. {
  53.   F_pers_tree_node *q;
  54.   
  55.   q = f_rchild(p);
  56.   while (!(f_isleaf(q)))
  57.   {  
  58.     if (i == q->ver_stamp || vless(i, q->ver_stamp))
  59.       q = f_lchild(q);
  60.     else
  61.       q = f_rchild(q);
  62.   }
  63.   return(q);
  64. }
  66. C_pers_tree_node* pers_rb_tree::c_rbsearch(C_pers_tree_node* p, Version i)
  67. {
  68.   C_pers_tree_node *q;
  69.   
  70.   q = c_rchild(p);
  71.   while (!(c_isleaf(q)))
  72.   {
  73.     if (i == q->vers_stamp || vless(i, q->vers_stamp))
  74.       q = c_lchild(q);
  75.     else
  76.       q = c_rchild(q);
  77.   }
  78.   return(q);
  79. }
  81. F_pers_tree_node * pers_rb_tree::f_nleaf(pers_tree_node* newvalue, Version i)
  82. {
  83.   F_pers_tree_node* result = new F_pers_tree_node;
  85.   f_mblack(result);
  86.   result->ver_stamp = i;
  87.   f_lchild(result) = f_rchild(result) = result;
  88.   result->poin_value = newvalue;
  89.   return(result);
  90. }
  92. C_pers_tree_node * pers_rb_tree::c_nleaf(int newvalue, Version i)
  93. {
  94.   C_pers_tree_node* result = new C_pers_tree_node;
  96.   c_mblack(result);
  97.   result->vers_stamp = i;
  98.   c_lchild(result) = c_rchild(result) = result;
  99.   result->col_value = newvalue;
  100.   return(result);
  101. }
  103. F_pers_tree_node * pers_rb_tree::f_nnode(F_pers_tree_node* c1, F_pers_tree_node* c2)
  104. {
  105.   F_pers_tree_node* result = new F_pers_tree_node;
  107.   f_mred(result);
  108.   if (vless(c1->ver_stamp, c2->ver_stamp))
  109.   {
  110.     f_lchild(result) = c1;
  111.     c1->f_right = 0;
  112.     f_rchild(result) = c2;
  113.     c2->f_right = 1;
  114.   }
  115.   else
  116.   {
  117.     f_lchild(result) = c2;
  118.     c2->f_right = 0;
  119.     f_rchild(result) = c1;
  120.     c1->f_right = 1;
  121.   }
  122.   f_parent(c1) = f_parent(c2) = result;
  123.   result->ver_stamp = (f_lchild(result))->ver_stamp;
  124.   result->poin_value = NULL;
  125.   return(result);
  126. }
  128. C_pers_tree_node* pers_rb_tree::c_nnode(C_pers_tree_node* c1, C_pers_tree_node* c2)
  129. {
  130.   C_pers_tree_node* result = new C_pers_tree_node;
  132.   c_mred(result);
  133.   if (vless(c1->vers_stamp, c2->vers_stamp))
  134.   {
  135.     c_lchild(result) = c1;
  136.     c1->c_right = 0;
  137.     c_rchild(result) = c2;
  138.     c2->c_right = 1;
  139.   }
  140.   else
  141.   {
  142.     c_lchild(result) = c2;
  143.     c2->c_right = 0;
  144.     c_rchild(result) = c1;
  145.     c1->c_right = 1;
  146.   }
  147.   c_parent(c1) = c_parent(c2) = result;
  148.   result->vers_stamp = (c_lchild(result))->vers_stamp;
  149.   result->col_value = 0;  
  150.   return(result);
  151. }
  153. void  pers_rb_tree::f_single_rot(F_pers_tree_node* top_node, int dir)
  154. {
  155.   F_pers_tree_node *temp, *q;
  157.   q = top_node->f_link[1-dir];
  158.   top_node->f_link[1-dir] = temp = q->f_link[dir];
  159.   temp->f_right = 1 - dir;
  160.   f_parent(temp) = top_node;
  161.   q->f_link[dir] = top_node;
  162.   temp = f_parent(top_node);
  163.   f_parent(top_node) = q;
  164.   q->f_right = top_node->f_right;
  165.   temp->f_link[top_node->f_right] = q;
  166.   f_parent(q) = temp;
  167.   top_node->f_right = dir;
  168.   return;
  169. }
  171. void  pers_rb_tree::c_single_rot(C_pers_tree_node* top_node, int dir)
  172. {
  173.   C_pers_tree_node *temp, *q;
  175.   q = top_node->c_link[1-dir];
  176.   top_node->c_link[1-dir] = temp = q->c_link[dir];
  177.   temp->c_right = 1 - dir;
  178.   c_parent(temp) = top_node;
  179.   q->c_link[dir] = top_node;
  180.   temp = c_parent(top_node);
  181.   c_parent(top_node) = q;
  182.   q->c_right = top_node->c_right;
  183.   temp->c_link[top_node->c_right] = q;
  184.   c_parent(q) = temp;
  185.   top_node->c_right = dir;
  186.   return;
  187. }
  190. void  pers_rb_tree::f_double_rot(F_pers_tree_node* top_node, int dir)
  191. {
  192.   F_pers_tree_node *q, *r, *temp;
  194.   q = top_node->f_link[1-dir];
  195.   r = q->f_link[dir];
  196.   top_node->f_link[1-dir] = temp = r->f_link[dir];
  197.   temp->f_right = 1 - dir;
  198.   f_parent(temp) = top_node;
  199.   q->f_link[dir] = (temp = r->f_link[1-dir]);
  200.   temp->f_right = dir;
  201.   f_parent(temp) = q;
  202.   temp = f_parent(top_node);
  203.   r->f_right = top_node->f_right;
  204.   r->f_link[dir] = top_node;
  205.   f_parent(top_node) = r;
  206.   top_node->f_right = dir;
  207.   r->f_link[1-dir] = q;
  208.   f_parent(q) = r;
  209.   temp->f_link[r->f_right] = r;
  210.   f_parent(r) = temp;
  211.   return;
  212. }
  214. void  pers_rb_tree::c_double_rot(C_pers_tree_node* top_node, int dir)
  215. {
  216.   C_pers_tree_node *q, *r, *temp;
  218.   q = top_node->c_link[1-dir];
  219.   r = q->c_link[dir];
  220.   top_node->c_link[1-dir] = temp = r->c_link[dir];
  221.   temp->c_right = 1 - dir;
  222.   c_parent(temp) = top_node;
  223.   q->c_link[dir] = (temp = r->c_link[1-dir]);
  224.   temp->c_right = dir;
  225.   c_parent(temp) = q;
  226.   temp = c_parent(top_node);
  227.   r->c_right = top_node->c_right;
  228.   r->c_link[dir] = top_node;
  229.   c_parent(top_node) = r;
  230.   top_node->c_right = dir;
  231.   r->c_link[1-dir] = q;
  232.   c_parent(q) = r;
  233.   temp->c_link[r->c_right] = r;
  234.   c_parent(r) = temp;
  235.   return;
  236. }
  239. int pers_rb_tree::f_insert(F_pers_tree_node* head, pers_tree_node* newvalue, Version i)
  240. {
  241.   int aux_bool;
  242.   F_pers_tree_node *p, *q, *r, *aux_node;
  244.   if (f_rchild(head) == NULL)
  245.   {
  246.     p = f_nleaf(newvalue, i);
  247.     p->f_right = 1;
  248.     f_parent(p) = head;
  249.     f_rchild(head) = p;
  250.     return(0);
  251.   }
  252.   p = f_rbsearch(head, i);
  253.   if (p->ver_stamp == i)
  254.   {
  255.     p->poin_value = newvalue;
  256.     return(1);
  257.   }
  258.   q = f_nleaf(newvalue, i);
  259.   aux_bool = p->f_right;
  260.   aux_node = f_parent(p);
  261.   r = f_nnode(p, q);
  262.   f_parent(r) = aux_node;
  263.   r->f_right = aux_bool;
  264.   aux_node->f_link[aux_bool] = r;
  265.   if (!f_isred(aux_node))
  266.   {
  267.     f_mblack(f_rchild(head));
  268.     return(0);
  269.   }
  270.   q = aux_node;
  271.   p = f_parent(q);
  272.   while ((f_isred(f_lchild(p))) && (f_isred(f_rchild(p))))
  273.   {
  274.     f_mblack(f_lchild(p));
  275.     f_mblack(f_rchild(p));
  276.     f_mred(p);
  277.     r = p;
  278.     q = f_parent(r);
  279.     if (!f_isred(q))
  280.     {
  281.       f_mblack(f_rchild(head));
  282.       return(0);
  283.     }
  284.     p = f_parent(q);
  285.   }
  286.   if (q->f_right == r->f_right)
  287.   {
  288.     f_mred(p);
  289.     f_mblack(q);
  290.     f_single_rot(p, 1-r->f_right);
  291.   }
  292.   else
  293.   {
  294.     f_mblack(r);
  295.     f_mred(p);
  296.     f_double_rot(p, r->f_right);
  297.   }
  298.   f_mblack(f_rchild(head));
  299.   return(0);
  300. }
  302. int pers_rb_tree::c_insert(C_pers_tree_node* head, int newvalue, Version i)
  303. {
  304.   int aux_bool;
  305.   C_pers_tree_node *p, *q, *r, *aux_node;
  307.   if (c_rchild(head) == NULL)
  308.   {
  309.     p = c_nleaf(newvalue, i);
  310.     p->c_right = 1;
  311.     c_parent(p) = head;
  312.     c_rchild(head) = p;
  313.     return(0);
  314.   }
  315.   p = c_rbsearch(head, i);
  316.   if (p->vers_stamp == i)
  317.   {
  318.     p->col_value = newvalue;
  319.     return(1);
  320.   }
  321.   q = c_nleaf(newvalue, i);
  322.   aux_bool = p->c_right;
  323.   aux_node = c_parent(p);
  324.   r = c_nnode(p, q);
  325.   c_parent(r) = aux_node;
  326.   r->c_right = aux_bool;
  327.   aux_node->c_link[aux_bool] = r;
  328.   if (!c_isred(aux_node))
  329.   {
  330.     c_mblack(c_rchild(head));
  331.     return(0);
  332.   }
  333.   q = aux_node;
  334.   p = c_parent(q);
  335.   while ((c_isred(c_lchild(p))) && (c_isred(c_rchild(p))))
  336.   {
  337.     c_mblack(c_lchild(p));
  338.     c_mblack(c_rchild(p));
  339.     c_mred(p);
  340.     r = p;
  341.     q = c_parent(r);
  342.     if (!c_isred(q))
  343.     {
  344.       c_mblack(c_rchild(head));
  345.       return(0);
  346.     }
  347.     p = c_parent(q);
  348.   }
  349.   if (q->c_right == r->c_right)
  350.   {
  351.     c_mred(p);
  352.     c_mblack(q);
  353.     c_single_rot(p, 1-r->c_right);
  354.   }
  355.   else
  356.   {
  357.     c_mblack(r);
  358.     c_mred(p);
  359.     c_double_rot(p, r->c_right);
  360.   }
  361.   c_mblack(c_rchild(head));
  362.   return(0);
  363. }
  367. /* insert the new version in the appropriate position and update the 
  368.  * version list
  369.  */
  371. void pers_rb_tree::del_version(Version) 
  372. { if (--v_list->count ==0) del_tree(); }
  374. Version pers_rb_tree::copy_version(Version i) { return new_version(i); }
  376. Version pers_rb_tree::new_version(Version i)
  377. {
  379.   Version succ = v_list->vl.succ(i);
  380.   
  381.   ver_node p = new VER_pers_tree_node;
  383.   if (succ != nil)
  384.      p->ser_num = (v_list->vl[i]->ser_num + v_list->vl[succ]->ser_num) / 2.0;
  385.   else 
  386.      p->ser_num = v_list->vl[i]->ser_num + 1000;
  389.   p->popul = v_list->vl[i]->popul;
  390.   p->acc_pointer = v_list->vl[i]->acc_pointer;
  391.   v_list->count++;
  392.   return v_list->vl.insert(p,i);
  393. }
  395. /* implementation of the update step (change of left or right child)
  396.  * for a specific persistent node and update operation 
  397.  */
  398.  
  399. void pers_rb_tree::update(F_pers_tree_node* p, pers_tree_node* newvalue, Version i)
  400. { 
  401.   F_pers_tree_node *p1, *i1, *i2;
  403.   Version ip = v_list->vl.succ(i);
  405.   if (f_insert(p, newvalue, i) == 1) return;
  407.   if (ip == nil || vless(ip,p->ver_stamp)) return;
  409.   p1 = f_rbsearch(p, i);
  410.   if (p1->f_right)
  411.   {
  412.     i1 = f_lchild(f_parent(p1));
  413.     if (f_isleaf(i1))
  414.       goto la;
  415.     else
  416.       i1 = f_rchild(i1);
  417. la: while (p1 != f_rchild(p) && p1->f_right)
  418.       p1 = f_parent(p1);
  419.     if (p1 == f_rchild(p))
  420.       i2 = NULL;
  421.     else
  422.     {
  423.       i2 = f_rchild(f_parent(p1));
  424.       while (!f_isleaf(i2))
  425.         i2 = f_lchild(i2);
  426.     }
  427.   }
  428.   else
  429.   {
  430.     i2 = f_rchild(f_parent(p1));
  431.     if (f_isleaf(i2))
  432.       goto m;
  433.     else
  434.       i2 = f_lchild(i2);
  435.  m: while (p1->f_right == 0)
  436.       p1 = f_parent(p1);
  437.     i1 = f_lchild(f_parent(p1));
  438.     while (!f_isleaf(i1))
  439.       i1 = f_rchild(i1);
  440.   }
  441.   if (i2 == NULL || vless(ip, i2->ver_stamp))
  442.      f_insert(p, i1->poin_value, ip);
  443. }
  444.    
  446. /* implementation of the update step (change of color) for a specific
  447.  * persistent node and update operation 
  448.  */
  449.  
  450. void pers_rb_tree::up_col(C_pers_tree_node* p, int newvalue, Version i)
  451. { 
  452.   C_pers_tree_node *p1, *i1, *i2;
  453.   
  454.   Version ip = v_list->vl.succ(i);
  456.   if (c_insert(p, newvalue, i) == 1) return;
  458.   if (ip ==nil  || vless(ip,p->vers_stamp)) return;
  460.   p1 = c_rbsearch(p, i);
  461.   if (p1->c_right)
  462.   {
  463.     i1 = c_lchild(c_parent(p1));
  464.     if (c_isleaf(i1))
  465.       goto lb;
  466.     else
  467.       i1 = c_rchild(i1);
  468. lb: while (p1 != c_rchild(p) && p1->c_right)
  469.       p1 = c_parent(p1);
  470.     if (p1 == c_rchild(p))
  471.       i2 = NULL;
  472.     else
  473.     {
  474.       i2 = c_rchild(c_parent(p1));
  475.       while (!c_isleaf(i2))
  476.         i2 = c_lchild(i2);
  477.     }
  478.   }
  479.   else
  480.   {
  481.     i2 = c_rchild(c_parent(p1));
  482.     if (c_isleaf(i2))
  483.       goto ma;
  484.     else
  485.       i2 = c_lchild(i2);
  486. ma: while (p1->c_right == 0)
  487.       p1 = c_parent(p1);
  488.     i1 = c_lchild(c_parent(p1));
  489.     while (!c_isleaf(i1))
  490.       i1 = c_rchild(i1);
  491.   }
  492.   if (i2 == NULL || vless(ip, i2->vers_stamp))
  493.      c_insert(p, i1->col_value, ip);
  494. }
  495.    
  497. /* implementation of the access step for a specific persistent node 
  498.  * and version 
  499.  */
  501. pers_tree_node * pers_rb_tree::acc_step(F_pers_tree_node *head, Version i)
  502. {
  503.   F_pers_tree_node *q, *i1;
  504.  
  505.   q = f_rbsearch(head, i);
  506.   if (q->ver_stamp == i)
  507.     return(q->poin_value);
  508.   if (vless(q->ver_stamp, i))
  509.     return(q->poin_value);
  510.   if (q->f_right)
  511.   {
  512.      i1 = f_lchild(f_parent(q));
  513.      if (f_isleaf(i1))
  514.        goto t;
  515.      else
  516.        i1 = f_rchild(i1);
  517.   }
  518.   else
  519.   {
  520.     while (q->f_right == 0)
  521.       q = f_parent(q);
  522.     i1 = f_lchild(f_parent(q));
  523.     while (!f_isleaf(i1))
  524.       i1 = f_rchild(i1);
  525.   }
  526. t:return(i1->poin_value);
  527. }
  528.   
  531. /* find out whether a given persistent node is red or not in a 
  532.  * specific version 
  533.  */
  535. int pers_rb_tree::isred(pers_tree_node* p, Version i)
  536. {
  537.   C_pers_tree_node *head, *q, *i1;
  538.   
  539.   if (isleaf(p))
  540.     return(0);
  541.   head = p->red;
  542.   q = c_rbsearch(head, i);
  543.   if (q->vers_stamp == i)
  544.     return(q->col_value);
  545.   if (vless(q->vers_stamp, i))
  546.     return(q->col_value);
  547.   if (q->c_right)
  548.   {  
  549.      i1 = c_lchild(c_parent(q));
  550.      if (c_isleaf(i1))
  551.        goto s;
  552.      else
  553.        i1 = c_rchild(i1);
  554.   }
  555.   else
  556.   {
  557.     while (q->c_right == 0)
  558.       q = c_parent(q);
  559.     i1 = c_lchild(c_parent(q));
  560.     while (!c_isleaf(i1))
  561.       i1 = c_rchild(i1);
  562.   }
  563. s:return(i1->col_value);
  564. }
  566.  
  567. /* create a new leaf and initialize the fields with the appropriate values */
  568.  
  569. pers_tree_node* pers_rb_tree::newleaf(void* val, void* inf, pers_tree_node* pred, pers_tree_node* succ, Version i)
  570. {
  571.   pers_tree_node *result;
  572.   F_pers_tree_node *res1, *res2;
  573.   C_pers_tree_node *res3;
  574.   
  575.   result = new pers_tree_node;
  576.   res1   = new F_pers_tree_node;
  577.   res2   = new F_pers_tree_node;
  578.   res3   = new C_pers_tree_node;
  579.    
  580.     result->key = val;
  581.     result->info = inf;
  582.     result->parent = NULL;
  583.     result->right = 1;
  584.     result->is_leaf = 1;
  585.     result->copy = NULL;
  587.     result->next = v_list->used;
  588.     v_list->used = result;
  590.     res1->ver_stamp = res2->ver_stamp = res3->vers_stamp = i;
  592.     f_lchild(res1) = f_rchild(res1) = f_parent(res1) = NULL;
  593.     f_lchild(res2) = f_rchild(res2) = f_parent(res2) = NULL;
  594.     c_lchild(res3) = c_rchild(res3) = c_parent(res3) = NULL;
  596.     res1->f_right = res2->f_right = res3->c_right = 1;
  597.     res1->f_color = res2->f_color = res3->c_color = 0;
  599.     res1->poin_value = res2->poin_value = NULL; 
  600.     res3->col_value = 0;  
  602.     f_insert(res1, pred, i);
  603.     f_insert(res2, succ, i);
  604.     c_insert(res3, 0, i);
  606.     result->link[0] = res1;
  607.     result->link[1] = res2;
  608.     result->red     = res3;
  610.     return result;
  611. }
  613. /* create a new persistent node and initialize its fields with the
  614.  * appropriate values 
  615.  */
  616.  
  617. pers_tree_node* pers_rb_tree::newnode(pers_tree_node* c1, pers_tree_node* c2, Version i)
  618. {
  619.   // c1 and c2 are leaves
  621.   pers_tree_node *result;
  622.   F_pers_tree_node *res1, *res2,  *res4;   // s.n. : res4 pointer to leaf (copy)
  623.   C_pers_tree_node *res3;
  624.   
  625.   result = new pers_tree_node;
  626.   res1   = new F_pers_tree_node;
  627.   res2   = new F_pers_tree_node;
  628.   res3   = new C_pers_tree_node;
  629.   res4   = new F_pers_tree_node;
  631.     result->parent = NULL;
  633.     result->next = v_list->used;
  634.     v_list->used = result;
  636.     res1->ver_stamp = res2->ver_stamp = res3->vers_stamp = i;
  638.     f_lchild(res1) = f_rchild(res1) = f_parent(res1) = NULL;
  639.     f_lchild(res2) = f_rchild(res2) = f_parent(res2) = NULL;
  640.     f_lchild(res4) = f_rchild(res4) = f_parent(res4) = NULL;
  641.     c_lchild(res3) = c_rchild(res3) = c_parent(res3) = NULL;
  643.     res1->f_right = res2->f_right = res3->c_right = res4->f_right = 1;
  644.     res1->f_color = res2->f_color = res3->c_color = res4->f_color = 0;
  646.     res1->poin_value = res2->poin_value = res4->poin_value = NULL; 
  647.     res3->col_value = 1;  
  649.     c_insert(res3, 1, i);
  651.     if (cmp_keys(c1->key, c2->key) < 1)
  652.     {
  653.       f_insert(res1, c1, i);
  654.       f_insert(res2, c2, i);
  655.       f_insert(res4, c1, i);
  656.       result->key = c1->key;
  657.     }
  658.     else
  659.     {
  660.       f_insert(res1, c2, i);
  661.       f_insert(res2, c1, i);
  662.       f_insert(res4, c2, i);
  663.       result->key = c2->key;
  664.     }
  666.     result->link[0] = res1;
  667.     result->link[1] = res2;
  668.     result->red     = res3;
  669.     result->copy    = res4;
  670.     result->is_leaf = 0;
  672.     return(result);
  673. }
  675.   
  676. /* implementation of the single rotation for the fully persistent
  677.  * red-black tree
  678.  */
  680. pers_tree_node* pers_rb_tree::single_rot(pers_tree_node* top_node, int dir, Version i)
  681. {
  682.   pers_tree_node *temp, *q, *newroot;
  683.   
  684.   newroot = NULL;
  685.   q = child(1 - dir, top_node, i);
  686.   temp = child(dir, q, i);
  687.   update(top_node->link[1 - dir], temp, i);
  688.   update(q->link[dir], top_node, i);
  689.   if ((temp = top_node->parent) == NULL)
  690.     newroot = q;
  691.   top_node->parent = q;
  692.   if (temp != NULL)
  693.     update(temp->link[top_node->right], q, i);
  694.   top_node->right = dir;
  695.   return(newroot);
  696. }
  698. /* implementation of the double rotation for the fully persistent
  699.  * red-black tree
  700.  */
  702. pers_tree_node* pers_rb_tree::double_rot(pers_tree_node* top_node, int dir, Version i)
  703. {
  704.   pers_tree_node *q, *r, *temp, *newroot;
  705.   
  706.   newroot = NULL;
  707.   q = child(1 - dir, top_node, i);
  708.   r = child(dir, q, i);
  709.   temp = child(dir, r, i);
  710.   update(top_node->link[1 - dir], temp, i);
  711.   temp = child(1 - dir, r, i);
  712.   update(q->link[dir], temp, i);
  713.   if ((temp = top_node->parent) == NULL)
  714.     newroot = r;
  715.   update(r->link[dir], top_node, i);
  716.   update(r->link[1 - dir], q, i);
  717.   if (temp != NULL)
  718.     update(temp->link[top_node->right], r, i);
  719.   return(newroot);
  720. }
  722. /* the root is colored black after each  update operation */
  724. void pers_rb_tree::m_b_root(Version i)
  725. {
  726.   pers_tree_node *p;
  728.   p = v_list->vl[i]->acc_pointer;
  730.   if (p != NULL && !isleaf(p) && isred(p, i))
  731.      up_col(p->red, 0, i);
  732. }
  737. //------------------------------------------------------------------------------
  738. // member functions
  739. //------------------------------------------------------------------------------
  742. void pers_rb_tree::init_tree()
  743. {
  744.    /* create dummy (empty) version 0 */
  745.    ver_node v = new VER_pers_tree_node;
  746.    v->ser_num =  0;
  747.    v->popul   =  0;
  748.    v->acc_pointer = NULL;
  749.    v_list = new V_LIST;
  750.    v_list->vl.append(v);
  751.    v_list->count = 1;
  753.    v_list->used = NULL;
  755. }
  757. pers_tree_node* pers_rb_tree::search(void *val, pers_tree_node*& copy, Version i)
  758. {
  759.   pers_tree_node *p, *q;
  761.   copy = NULL;
  762.   
  763.   if ((p = v_list->vl[i]->acc_pointer) == NULL)
  764.     return(NULL);
  766.   p->parent = NULL;
  767.   p->right = 1;
  768.   while (!isleaf(p))
  769.   {
  770.     int v = cmp_keys(val, get_key(p,i));
  772.     if (v < 1)
  773.     { if (v==0) copy = p;
  774.       q = p;
  775.       p = child(0, p, i);
  776.       p->parent = q;
  777.       p->right = 0;
  778.      }
  779.     else
  780.     { q = p;
  781.       p = child(1, p, i);
  782.       p->parent = q;
  783.       p->right = 1;
  784.      }
  785.    }
  787.    return p;
  788. }
  791.  
  792. Version  pers_rb_tree::del(void *val, Version i1)
  793. {
  794.   pers_tree_node *pos_del, *par1, *par2, *root, *newroot, *temp, *copy;
  796.   Version i  = new_version(i1);
  797.   
  798.   if ((pos_del = search(val, copy, i1)) == NULL) return i; //empty tree
  800.   if (cmp_keys(pos_del->key, val) != 0) return i;  // key not found
  803.   if ((--(v_list->vl[i]->popul)) == 0)
  804.   {
  805.     v_list->vl[i]->acc_pointer = NULL;
  806.     return i;
  807.   }
  810.   //update links to neighbor leaves
  812.   pers_tree_node* pred = child(0,pos_del,i);
  813.   pers_tree_node* succ = child(1,pos_del,i);
  815.   if (pred) update(pred->link[1],succ,i);
  816.   if (succ) update(succ->link[0],pred,i);
  819.   root = v_list->vl[i]->acc_pointer;
  821.   if ((par1 = pos_del->parent) == root)
  822.   {
  823.     v_list->vl[i]->acc_pointer = sibling(pos_del, i);
  824.     goto end;
  825.    }
  827.   par2 = par1->parent;
  828.   pos_del = sibling(pos_del, i);
  829.   update(par2->link[par1->right], pos_del, i);
  830.   pos_del->parent = par2;
  831.   pos_del->right = par1->right;
  833.   if (copy != NULL && copy != par1)  // we have to overwrite copy  by pred
  834.   {
  835.     update(copy->copy, pred, i);
  837.    }
  838.   
  840.   if (isred(par1, i))
  841.     goto end;
  842.   if (isred(pos_del, i))
  843.   {
  844.     up_col(pos_del->red, 0, i);
  845.     goto end;
  846.   }
  847.   par1 = sibling(pos_del, i);
  848.   while ((!isred(par1, i)) && (!isred(child(0, par1, i), i)) &&
  849.          (!isred(child(1, par1, i), i)))
  850.   {
  851.     up_col(par1->red, 1, i);
  852.     pos_del = pos_del->parent;
  853.     if (isred(pos_del, i))
  854.     {
  855.       up_col(pos_del->red, 0, i);
  856.       goto end;
  857.     }
  858.     if (pos_del == root)
  859.       goto end;
  860.     else
  861.       par1 = sibling(pos_del, i);
  862.   }
  863.   par2 = pos_del->parent;
  864.   if (isred(par1, i))
  865.   {
  866.     up_col(par2->red, 1, i);
  867.     up_col(par1->red, 0,i);
  868.     if ((newroot = single_rot(par2, pos_del->right, i)) != NULL)
  869.       v_list->vl[i]->acc_pointer = newroot;
  870.     par1 = sibling(pos_del,i);
  871.     if ((!isred(child(0, par1, i), i)) && (!isred(child(1, par1, i), i)))
  872.     {
  873.       up_col(par1->red, 1, i);
  874.       up_col((pos_del->parent)->red, 0, i);
  875.       goto end;
  876.     }
  877.   }
  878.   par2 = pos_del->parent;
  879.   if (!pos_del->right)
  880.     if (isred(child(0, par1, i), i))
  881.     {
  882.       temp = child(0, par1, i);
  883.       up_col(temp->red, isred(par2, i), i);
  884.       up_col(par2->red, 0, i);
  885.       newroot = double_rot(par2, LEFT, i);
  886.     }
  887.     else
  888.     {
  889.       up_col(par1->red, isred(par2, i), i);
  890.       up_col(par2->red, 0, i);
  891.       temp = child(1, par1, i);
  892.       up_col(temp->red, 0, i);
  893.       newroot = single_rot(par2, LEFT, i);
  894.     }
  895.   else
  896.     if (isred(child(0, par1, i), i))
  897.     {
  898.       up_col(par1->red, isred(par2, i), i);
  899.       up_col(par2->red, 0, i);
  900.       temp = child(0, par1, i);
  901.       up_col(temp->red, 0, i);
  902.       newroot = single_rot(par2, RIGHT, i);
  903.     }
  904.     else
  905.     {
  906.       temp = child(1, par1, i);
  907.       up_col(temp->red, isred(par2, i), i);
  908.       up_col(par2->red, 0, i);
  909.       newroot = double_rot(par2, RIGHT, i);
  910.     }
  911.   if (newroot != NULL)
  912.     v_list->vl[i]->acc_pointer = newroot;
  914. end:
  915.   m_b_root(i);
  916.   return i;
  917. }
  920. Version pers_rb_tree::insert(void *val, void* info, Version i1)
  921. {
  922.   int aux_bool; 
  923.   pers_tree_node *p, *q, *r, *aux_node, *root, *newroot, *temp;
  925.   Version i = new_version(i1);
  927.   p = search(val, i1);
  929.   if (p && cmp_keys(p->key, val) == 0) return i;  // key already there
  931.   copy_key(val);
  932.   copy_inf(info);
  933.   
  934.   if (p == NULL)   // empty tree
  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.    }
  941.   (v_list->vl[i]->popul)++;
  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.     { pers_tree_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.      }
  954.   aux_bool = p->right;
  955.   r = newnode(p, q, i);
  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);
  966.   if (!isred(aux_node, i))
  967.      goto end;
  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.   }
  1000.   if (newroot != NULL)
  1001.     v_list->vl[i]->acc_pointer = newroot;
  1003. end:
  1004.   m_b_root(i);
  1005.   return i;
  1006. }
  1009. Version pers_rb_tree::change_inf(pers_tree_node* p, void* info, Version i1)
  1010. {
  1011.   Version i = new_version(i1);
  1013.   p = search(p->key, i1);  // setting parent pointers
  1015.   pers_tree_node* pred = child(0,p,i);
  1016.   pers_tree_node* succ = child(1,p,i);
  1018.   copy_inf(info);
  1019.   pers_tree_node* q = newleaf(p->key,info, pred, succ, i);   
  1022.   if (pred) update(pred->link[1],q,i);
  1023.   if (succ) update(succ->link[0],q,i);
  1025.   q->right = p->right;
  1026.   update(p->parent->link[q->right], q, i);
  1028.   return i;
  1030. }
  1034. pers_tree_node* pers_rb_tree::min(Version v)
  1035. { pers_tree_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. }  
  1041. pers_tree_node* pers_rb_tree::max(Version v)
  1042. { pers_tree_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. }  
  1048. void pers_rb_tree::print(pers_tree_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. }  
  1061. void pers_rb_tree::del_tree()
  1062. { 
  1063.   while (v_list->used)
  1064.   { pers_tree_node* p = v_list->used;
  1065.     v_list->used = v_list->used->next;
  1067.     f_rbclear(f_rchild(p->link[0]));
  1068.     delete p->link[0];
  1070.     f_rbclear(f_rchild(p->link[1]));
  1071.     delete p->link[1];
  1073.     if (p->copy != nil)
  1074.     {
  1075.       f_rbclear(f_rchild(p->copy));
  1076.       delete p->copy;
  1077.      }
  1079.     c_rbclear(c_rchild(p->red));
  1080.     delete p->red;
  1082.     if (isleaf(p))
  1083.     { clear_key(p->key);
  1084.       clear_inf(p->info);
  1085.      }
  1087.     delete p;
  1088.    }
  1090.    ver_node q;
  1091.    forall(q, v_list->vl) delete q;
  1093.    delete v_list;
  1094.  }  
  1097. pers_tree_node*  pers_rb_tree::lookup(void *val,Version v)
  1098. { pers_tree_node* p = search(val,v);
  1099.   return (p && cmp_keys(key(p), val) == 0) ? p : nil;
  1100.  }
  1102. pers_tree_node* pers_rb_tree::locate(void *val,Version v)
  1103. { pers_tree_node* p = search(val,v);
  1104.   return ( p && cmp_keys(key(p), val) >= 0) ?  p : nil;
  1105.  }
  1107. pers_tree_node* pers_rb_tree::locate_pred(void *val,Version v)
  1108. { pers_tree_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);
  1113. }
  1118. void pers_rb_tree::draw(DRAW_NODE_FCT draw_node,
  1119.                         DRAW_EDGE_FCT draw_edge, 
  1120.                         Version v, pers_tree_node* r, 
  1121.                         double x1, double x2, double y, 
  1122.                         double ydist, double last_x)
  1123. { 
  1125.   double x = (x1+x2)/2;
  1127.   if (r==NULL) return;
  1129.   if (last_x != 0) draw_edge(last_x,y+ydist,x,y);
  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. }
  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); }