_pers_tree.c

数据类型和算法库LEDA 数据类型和算法库LEDA

/*******************************************************************************
+
+  LEDA  3.0
+
+
+  _pers_tree.c
+
+
+  Copyright (c) 1992  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 6600 Saarbruecken, FRG     
+  All rights reserved.
+ 
*******************************************************************************/


#include <LEDA/impl/pers_tree.h>


#define LEFT 0
#define RIGHT 1
#define f_isred(p)   ((p)->f_color)
#define c_isred(p)   ((p)->c_color)
#define f_mred(p)    ((p)->f_color=1)
#define c_mred(p)    ((p)->c_color=1)
#define f_mblack(p)  ((p)->f_color=0)
#define c_mblack(p)  ((p)->c_color=0)
#define f_lchild(p)  ((p)->f_link[0])
#define c_lchild(p)  ((p)->c_link[0])
#define f_rchild(p)  ((p)->f_link[1])
#define c_rchild(p)  ((p)->c_link[1])
#define f_parent(p)  ((p)->f_link[2])
#define c_parent(p)  ((p)->c_link[2])
#define f_isleaf(p)  (f_lchild(p)==(p))
#define c_isleaf(p)  (c_lchild(p)==(p))


void pers_rb_tree::f_rbclear(F_pers_tree_node* p)
{ if (!(f_isleaf(p)))
    { f_rbclear(f_lchild(p));
      f_rbclear(f_rchild(p));
     }
  delete p;
 }

void pers_rb_tree::c_rbclear(C_pers_tree_node* p)
{ if (!(c_isleaf(p)))
    { c_rbclear(c_lchild(p));
      c_rbclear(c_rchild(p));
     }
  delete p;
}


F_pers_tree_node* pers_rb_tree::f_rbsearch(F_pers_tree_node* p, version i)
{
  F_pers_tree_node *q;
  
  q = f_rchild(p);
  while (!(f_isleaf(q)))
  {  
    if (i == q->ver_stamp || vless(i, q->ver_stamp))
      q = f_lchild(q);
    else
      q = f_rchild(q);
  }
  return(q);
}

C_pers_tree_node* pers_rb_tree::c_rbsearch(C_pers_tree_node* p, version i)
{
  C_pers_tree_node *q;
  
  q = c_rchild(p);
  while (!(c_isleaf(q)))
  {
    if (i == q->vers_stamp || vless(i, q->vers_stamp))
      q = c_lchild(q);
    else
      q = c_rchild(q);
  }
  return(q);
}

F_pers_tree_node * pers_rb_tree::f_nleaf(pers_tree_node* newvalue, version i)
{
  F_pers_tree_node* result = new F_pers_tree_node;

  f_mblack(result);
  result->ver_stamp = i;
  f_lchild(result) = f_rchild(result) = result;
  result->poin_value = newvalue;
  return(result);
}

C_pers_tree_node * pers_rb_tree::c_nleaf(int newvalue, version i)
{
  C_pers_tree_node* result = new C_pers_tree_node;

  c_mblack(result);
  result->vers_stamp = i;
  c_lchild(result) = c_rchild(result) = result;
  result->col_value = newvalue;
  return(result);
}

F_pers_tree_node * pers_rb_tree::f_nnode(F_pers_tree_node* c1, F_pers_tree_node* c2)
{
  F_pers_tree_node* result = new F_pers_tree_node;

  f_mred(result);
  if (vless(c1->ver_stamp, c2->ver_stamp))
  {
    f_lchild(result) = c1;
    c1->f_right = 0;
    f_rchild(result) = c2;
    c2->f_right = 1;
  }
  else
  {
    f_lchild(result) = c2;
    c2->f_right = 0;
    f_rchild(result) = c1;
    c1->f_right = 1;
  }
  f_parent(c1) = f_parent(c2) = result;
  result->ver_stamp = (f_lchild(result))->ver_stamp;
  result->poin_value = NULL;
  return(result);
}

C_pers_tree_node* pers_rb_tree::c_nnode(C_pers_tree_node* c1, C_pers_tree_node* c2)
{
  C_pers_tree_node* result = new C_pers_tree_node;

  c_mred(result);
  if (vless(c1->vers_stamp, c2->vers_stamp))
  {
    c_lchild(result) = c1;
    c1->c_right = 0;
    c_rchild(result) = c2;
    c2->c_right = 1;
  }
  else
  {
    c_lchild(result) = c2;
    c2->c_right = 0;
    c_rchild(result) = c1;
    c1->c_right = 1;
  }
  c_parent(c1) = c_parent(c2) = result;
  result->vers_stamp = (c_lchild(result))->vers_stamp;
  result->col_value = 0;  
  return(result);
}

void  pers_rb_tree::f_single_rot(F_pers_tree_node* top_node, int dir)
{
  F_pers_tree_node *temp, *q;

  q = top_node->f_link[1-dir];
  top_node->f_link[1-dir] = temp = q->f_link[dir];
  temp->f_right = 1 - dir;
  f_parent(temp) = top_node;
  q->f_link[dir] = top_node;
  temp = f_parent(top_node);
  f_parent(top_node) = q;
  q->f_right = top_node->f_right;
  temp->f_link[top_node->f_right] = q;
  f_parent(q) = temp;
  top_node->f_right = dir;
  return;
}

void  pers_rb_tree::c_single_rot(C_pers_tree_node* top_node, int dir)
{
  C_pers_tree_node *temp, *q;

  q = top_node->c_link[1-dir];
  top_node->c_link[1-dir] = temp = q->c_link[dir];
  temp->c_right = 1 - dir;
  c_parent(temp) = top_node;
  q->c_link[dir] = top_node;
  temp = c_parent(top_node);
  c_parent(top_node) = q;
  q->c_right = top_node->c_right;
  temp->c_link[top_node->c_right] = q;
  c_parent(q) = temp;
  top_node->c_right = dir;
  return;
}


void  pers_rb_tree::f_double_rot(F_pers_tree_node* top_node, int dir)
{
  F_pers_tree_node *q, *r, *temp;

  q = top_node->f_link[1-dir];
  r = q->f_link[dir];
  top_node->f_link[1-dir] = temp = r->f_link[dir];
  temp->f_right = 1 - dir;
  f_parent(temp) = top_node;
  q->f_link[dir] = (temp = r->f_link[1-dir]);
  temp->f_right = dir;
  f_parent(temp) = q;
  temp = f_parent(top_node);
  r->f_right = top_node->f_right;
  r->f_link[dir] = top_node;
  f_parent(top_node) = r;
  top_node->f_right = dir;
  r->f_link[1-dir] = q;
  f_parent(q) = r;
  temp->f_link[r->f_right] = r;
  f_parent(r) = temp;
  return;
}

void  pers_rb_tree::c_double_rot(C_pers_tree_node* top_node, int dir)
{
  C_pers_tree_node *q, *r, *temp;

  q = top_node->c_link[1-dir];
  r = q->c_link[dir];
  top_node->c_link[1-dir] = temp = r->c_link[dir];
  temp->c_right = 1 - dir;
  c_parent(temp) = top_node;
  q->c_link[dir] = (temp = r->c_link[1-dir]);
  temp->c_right = dir;
  c_parent(temp) = q;
  temp = c_parent(top_node);
  r->c_right = top_node->c_right;
  r->c_link[dir] = top_node;
  c_parent(top_node) = r;
  top_node->c_right = dir;
  r->c_link[1-dir] = q;
  c_parent(q) = r;
  temp->c_link[r->c_right] = r;
  c_parent(r) = temp;
  return;
}


int pers_rb_tree::f_insert(F_pers_tree_node* head, pers_tree_node* newvalue, version i)
{
  int aux_bool;
  F_pers_tree_node *p, *q, *r, *aux_node;

  if (f_rchild(head) == NULL)
  {
    p = f_nleaf(newvalue, i);
    p->f_right = 1;
    f_parent(p) = head;
    f_rchild(head) = p;
    return(0);
  }
  p = f_rbsearch(head, i);
  if (p->ver_stamp == i)
  {
    p->poin_value = newvalue;
    return(1);
  }
  q = f_nleaf(newvalue, i);
  aux_bool = p->f_right;
  aux_node = f_parent(p);
  r = f_nnode(p, q);
  f_parent(r) = aux_node;
  r->f_right = aux_bool;
  aux_node->f_link[aux_bool] = r;
  if (!f_isred(aux_node))
  {
    f_mblack(f_rchild(head));
    return(0);
  }
  q = aux_node;
  p = f_parent(q);
  while ((f_isred(f_lchild(p))) && (f_isred(f_rchild(p))))
  {
    f_mblack(f_lchild(p));
    f_mblack(f_rchild(p));
    f_mred(p);
    r = p;
    q = f_parent(r);
    if (!f_isred(q))
    {
      f_mblack(f_rchild(head));
      return(0);
    }
    p = f_parent(q);
  }
  if (q->f_right == r->f_right)
  {
    f_mred(p);
    f_mblack(q);
    f_single_rot(p, 1-r->f_right);
  }
  else
  {
    f_mblack(r);
    f_mred(p);
    f_double_rot(p, r->f_right);
  }
  f_mblack(f_rchild(head));
  return(0);
}

int pers_rb_tree::c_insert(C_pers_tree_node* head, int newvalue, version i)
{
  int aux_bool;
  C_pers_tree_node *p, *q, *r, *aux_node;

  if (c_rchild(head) == NULL)
  {
    p = c_nleaf(newvalue, i);
    p->c_right = 1;
    c_parent(p) = head;
    c_rchild(head) = p;
    return(0);
  }
  p = c_rbsearch(head, i);
  if (p->vers_stamp == i)
  {
    p->col_value = newvalue;
    return(1);
  }
  q = c_nleaf(newvalue, i);
  aux_bool = p->c_right;
  aux_node = c_parent(p);
  r = c_nnode(p, q);
  c_parent(r) = aux_node;
  r->c_right = aux_bool;
  aux_node->c_link[aux_bool] = r;
  if (!c_isred(aux_node))
  {
    c_mblack(c_rchild(head));
    return(0);
  }
  q = aux_node;
  p = c_parent(q);
  while ((c_isred(c_lchild(p))) && (c_isred(c_rchild(p))))
  {
    c_mblack(c_lchild(p));
    c_mblack(c_rchild(p));
    c_mred(p);
    r = p;
    q = c_parent(r);
    if (!c_isred(q))
    {
      c_mblack(c_rchild(head));
      return(0);
    }
    p = c_parent(q);
  }
  if (q->c_right == r->c_right)
  {
    c_mred(p);
    c_mblack(q);
    c_single_rot(p, 1-r->c_right);
  }
  else
  {
    c_mblack(r);
    c_mred(p);
    c_double_rot(p, r->c_right);
  }
  c_mblack(c_rchild(head));
  return(0);
}



/* insert the new version in the appropriate position and update the 
 * version list
 */

void pers_rb_tree::del_version(version) 
{ if (--v_list->count ==0) del_tree(); }

version pers_rb_tree::copy_version(version i) { return new_version(i); }

version pers_rb_tree::new_version(version i)
{

  version succ = v_list->vl.succ(i);
  
  ver_node p = new VER_pers_tree_node;

  if (succ != nil)
     p->ser_num = (v_list->vl[i]->ser_num + v_list->vl[succ]->ser_num) / 2.0;
  else 
     p->ser_num = v_list->vl[i]->ser_num + 1000;


  p->popul = v_list->vl[i]->popul;
  p->acc_pointer = v_list->vl[i]->acc_pointer;
  v_list->count++;
  return v_list->vl.insert(p,i);
}

/* implementation of the update step (change of left or right child)
 * for a specific persistent node and update operation 
 */
 
void pers_rb_tree::update(F_pers_tree_node* p, pers_tree_node* newvalue, version i)
{ 
  F_pers_tree_node *p1, *i1, *i2;

  version ip = v_list->vl.succ(i);

  if (f_insert(p, newvalue, i) == 1) return;

  if (ip == nil || vless(ip,p->ver_stamp)) return;

  p1 = f_rbsearch(p, i);
  if (p1->f_right)
  {
    i1 = f_lchild(f_parent(p1));
    if (f_isleaf(i1))
      goto la;
    else
      i1 = f_rchild(i1);
la: while (p1 != f_rchild(p) && p1->f_right)
      p1 = f_parent(p1);
    if (p1 == f_rchild(p))
      i2 = NULL;
    else
    {
      i2 = f_rchild(f_parent(p1));
      while (!f_isleaf(i2))
        i2 = f_lchild(i2);
    }
  }
  else
  {
    i2 = f_rchild(f_parent(p1));
    if (f_isleaf(i2))
      goto m;
    else
      i2 = f_lchild(i2);
 m: while (p1->f_right == 0)
      p1 = f_parent(p1);
    i1 = f_lchild(f_parent(p1));
    while (!f_isleaf(i1))
      i1 = f_rchild(i1);
  }
  if (i2 == NULL || vless(ip, i2->ver_stamp))
     f_insert(p, i1->poin_value, ip);
}
   

/* implementation of the update step (change of color) for a specific
 * persistent node and update operation 
 */
 
void pers_rb_tree::up_col(C_pers_tree_node* p, int newvalue, version i)
{ 
  C_pers_tree_node *p1, *i1, *i2;
  
  version ip = v_list->vl.succ(i);

  if (c_insert(p, newvalue, i) == 1) return;

  if (ip ==nil  || vless(ip,p->vers_stamp)) return;

  p1 = c_rbsearch(p, i);
  if (p1->c_right)
  {
    i1 = c_lchild(c_parent(p1));
    if (c_isleaf(i1))
      goto lb;
    else
      i1 = c_rchild(i1);
lb: while (p1 != c_rchild(p) && p1->c_right)
      p1 = c_parent(p1);
    if (p1 == c_rchild(p))
      i2 = NULL;
    else
    {
      i2 = c_rchild(c_parent(p1));
      while (!c_isleaf(i2))
        i2 = c_lchild(i2);
    }
  }
  else
  {
    i2 = c_rchild(c_parent(p1));
    if (c_isleaf(i2))
      goto ma;
    else
      i2 = c_lchild(i2);
ma: while (p1->c_right == 0)
      p1 = c_parent(p1);
    i1 = c_lchild(c_parent(p1));
    while (!c_isleaf(i1))
      i1 = c_rchild(i1);
  }
  if (i2 == NULL || vless(ip, i2->vers_stamp))
     c_insert(p, i1->col_value, ip);
}
   

/* implementation of the access step for a specific persistent node 
 * and version 
 */

pers_tree_node * pers_rb_tree::acc_step(F_pers_tree_node *head, version i)
{
  F_pers_tree_node *q, *i1;
 
  q = f_rbsearch(head, i);
  if (q->ver_stamp == i)
    return(q->poin_value);
  if (vless(q->ver_stamp, i))
    return(q->poin_value);
  if (q->f_right)
  {
     i1 = f_lchild(f_parent(q));
     if (f_isleaf(i1))
       goto t;
     else
       i1 = f_rchild(i1);
  }
  else
  {
    while (q->f_right == 0)
      q = f_parent(q);
    i1 = f_lchild(f_parent(q));
    while (!f_isleaf(i1))
      i1 = f_rchild(i1);
  }
t:return(i1->poin_value);
}
  


/* find out whether a given persistent node is red or not in a 
 * specific version 
 */

int pers_rb_tree::isred(pers_tree_node* p, version i)
{
  C_pers_tree_node *head, *q, *i1;
  
  if (isleaf(p))
    return(0);
  head = p->red;
  q = c_rbsearch(head, i);
  if (q->vers_stamp == i)
    return(q->col_value);
  if (vless(q->vers_stamp, i))
    return(q->col_value);
  if (q->c_right)
  {  
     i1 = c_lchild(c_parent(q));
     if (c_isleaf(i1))
       goto s;
     else
       i1 = c_rchild(i1);
  }
  else
  {
    while (q->c_right == 0)
      q = c_parent(q);
    i1 = c_lchild(c_parent(q));
    while (!c_isleaf(i1))
      i1 = c_rchild(i1);
  }
s:return(i1->col_value);
}

 
/* create a new leaf and initialize the fields with the appropriate values */
 
pers_tree_node* pers_rb_tree::newleaf(void* val, void* inf, pers_tree_node* pred, pers_tree_node* succ, version i)
{
  pers_tree_node *result;