_pers_tree.c

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

  F_pers_tree_node *res1, *res2;
  C_pers_tree_node *res3;
  
  result = new pers_tree_node;
  res1   = new F_pers_tree_node;
  res2   = new F_pers_tree_node;
  res3   = new C_pers_tree_node;
   
    result->key = val;
    result->info = inf;
    result->parent = NULL;
    result->right = 1;
    result->is_leaf = 1;
    result->copy = NULL;

    result->next = v_list->used;
    v_list->used = result;

    res1->ver_stamp = res2->ver_stamp = res3->vers_stamp = i;

    f_lchild(res1) = f_rchild(res1) = f_parent(res1) = NULL;
    f_lchild(res2) = f_rchild(res2) = f_parent(res2) = NULL;
    c_lchild(res3) = c_rchild(res3) = c_parent(res3) = NULL;

    res1->f_right = res2->f_right = res3->c_right = 1;
    res1->f_color = res2->f_color = res3->c_color = 0;

    res1->poin_value = res2->poin_value = NULL; 
    res3->col_value = 0;  

    f_insert(res1, pred, i);
    f_insert(res2, succ, i);
    c_insert(res3, 0, i);

    result->link[0] = res1;
    result->link[1] = res2;
    result->red     = res3;

    return result;
}

/* create a new persistent node and initialize its fields with the
 * appropriate values 
 */
 
pers_tree_node* pers_rb_tree::newnode(pers_tree_node* c1, pers_tree_node* c2, version i)
{
  // c1 and c2 are leaves

  pers_tree_node *result;
  F_pers_tree_node *res1, *res2,  *res4;   // s.n. : res4 pointer to leaf (copy)
  C_pers_tree_node *res3;
  
  result = new pers_tree_node;
  res1   = new F_pers_tree_node;
  res2   = new F_pers_tree_node;
  res3   = new C_pers_tree_node;
  res4   = new F_pers_tree_node;

    result->parent = NULL;

    result->next = v_list->used;
    v_list->used = result;

    res1->ver_stamp = res2->ver_stamp = res3->vers_stamp = i;

    f_lchild(res1) = f_rchild(res1) = f_parent(res1) = NULL;
    f_lchild(res2) = f_rchild(res2) = f_parent(res2) = NULL;
    f_lchild(res4) = f_rchild(res4) = f_parent(res4) = NULL;
    c_lchild(res3) = c_rchild(res3) = c_parent(res3) = NULL;

    res1->f_right = res2->f_right = res3->c_right = res4->f_right = 1;
    res1->f_color = res2->f_color = res3->c_color = res4->f_color = 0;

    res1->poin_value = res2->poin_value = res4->poin_value = NULL; 
    res3->col_value = 1;  

    c_insert(res3, 1, i);

    if (cmp_keys(c1->key, c2->key) < 1)
    {
      f_insert(res1, c1, i);
      f_insert(res2, c2, i);
      f_insert(res4, c1, i);
      result->key = c1->key;
    }
    else
    {
      f_insert(res1, c2, i);
      f_insert(res2, c1, i);
      f_insert(res4, c2, i);
      result->key = c2->key;
    }

    result->link[0] = res1;
    result->link[1] = res2;
    result->red     = res3;
    result->copy    = res4;
    result->is_leaf = 0;

    return(result);
}

  
/* implementation of the single rotation for the fully persistent
 * red-black tree
 */

pers_tree_node* pers_rb_tree::single_rot(pers_tree_node* top_node, int dir, version i)
{
  pers_tree_node *temp, *q, *newroot;
  
  newroot = NULL;
  q = child(1 - dir, top_node, i);
  temp = child(dir, q, i);
  update(top_node->link[1 - dir], temp, i);
  update(q->link[dir], top_node, i);
  if ((temp = top_node->parent) == NULL)
    newroot = q;
  top_node->parent = q;
  if (temp != NULL)
    update(temp->link[top_node->right], q, i);
  top_node->right = dir;
  return(newroot);
}

/* implementation of the double rotation for the fully persistent
 * red-black tree
 */

pers_tree_node* pers_rb_tree::double_rot(pers_tree_node* top_node, int dir, version i)
{
  pers_tree_node *q, *r, *temp, *newroot;
  
  newroot = NULL;
  q = child(1 - dir, top_node, i);
  r = child(dir, q, i);
  temp = child(dir, r, i);
  update(top_node->link[1 - dir], temp, i);
  temp = child(1 - dir, r, i);
  update(q->link[dir], temp, i);
  if ((temp = top_node->parent) == NULL)
    newroot = r;
  update(r->link[dir], top_node, i);
  update(r->link[1 - dir], q, i);
  if (temp != NULL)
    update(temp->link[top_node->right], r, i);
  return(newroot);
}

/* the root is colored black after each  update operation */

void pers_rb_tree::m_b_root(version i)
{
  pers_tree_node *p;

  p = v_list->vl[i]->acc_pointer;

  if (p != NULL && !isleaf(p) && isred(p, i))
     up_col(p->red, 0, i);
}




//------------------------------------------------------------------------------
// member functions
//------------------------------------------------------------------------------


void pers_rb_tree::init_tree()
{
   /* create dummy (empty) version 0 */
   ver_node v = new VER_pers_tree_node;
   v->ser_num =  0;
   v->popul   =  0;
   v->acc_pointer = NULL;
   v_list = new V_LIST;
   v_list->vl.append(v);
   v_list->count = 1;

   v_list->used = NULL;

}

pers_tree_node* pers_rb_tree::search(void *val, pers_tree_node*& copy, version i)
{
  pers_tree_node *p, *q;

  copy = NULL;
  
  if ((p = v_list->vl[i]->acc_pointer) == NULL)
    return(NULL);

  p->parent = NULL;
  p->right = 1;
  while (!isleaf(p))
  {
    int v = cmp_keys(val, get_key(p,i));

    if (v < 1)
    { if (v==0) copy = p;
      q = p;
      p = child(0, p, i);
      p->parent = q;
      p->right = 0;
     }
    else
    { q = p;
      p = child(1, p, i);
      p->parent = q;
      p->right = 1;
     }
   }

   return p;
}


 
version  pers_rb_tree::del(void *val, version i1)
{
  pers_tree_node *pos_del, *par1, *par2, *root, *newroot, *temp, *copy;

  version i  = new_version(i1);
  
  if ((pos_del = search(val, copy, i1)) == NULL) return i; //empty tree

  if (cmp_keys(pos_del->key, val) != 0) return i;  // key not found


  if ((--(v_list->vl[i]->popul)) == 0)
  {
    v_list->vl[i]->acc_pointer = NULL;
    return i;
  }


  //update links to neighbor leaves

  pers_tree_node* pred = child(0,pos_del,i);
  pers_tree_node* succ = child(1,pos_del,i);

  if (pred) update(pred->link[1],succ,i);
  if (succ) update(succ->link[0],pred,i);


  root = v_list->vl[i]->acc_pointer;

  if ((par1 = pos_del->parent) == root)
  {
    v_list->vl[i]->acc_pointer = sibling(pos_del, i);
    goto end;
   }

  par2 = par1->parent;
  pos_del = sibling(pos_del, i);
  update(par2->link[par1->right], pos_del, i);
  pos_del->parent = par2;
  pos_del->right = par1->right;

  if (copy != NULL && copy != par1)  // we have to overwrite copy  by pred
  {
    update(copy->copy, pred, i);

   }
  

  if (isred(par1, i))
    goto end;
  if (isred(pos_del, i))
  {
    up_col(pos_del->red, 0, i);
    goto end;
  }
  par1 = sibling(pos_del, i);
  while ((!isred(par1, i)) && (!isred(child(0, par1, i), i)) &&
         (!isred(child(1, par1, i), i)))
  {
    up_col(par1->red, 1, i);
    pos_del = pos_del->parent;
    if (isred(pos_del, i))
    {
      up_col(pos_del->red, 0, i);
      goto end;
    }
    if (pos_del == root)
      goto end;
    else
      par1 = sibling(pos_del, i);
  }
  par2 = pos_del->parent;
  if (isred(par1, i))
  {
    up_col(par2->red, 1, i);
    up_col(par1->red, 0,i);
    if ((newroot = single_rot(par2, pos_del->right, i)) != NULL)
      v_list->vl[i]->acc_pointer = newroot;
    par1 = sibling(pos_del,i);
    if ((!isred(child(0, par1, i), i)) && (!isred(child(1, par1, i), i)))
    {
      up_col(par1->red, 1, i);
      up_col((pos_del->parent)->red, 0, i);
      goto end;
    }
  }
  par2 = pos_del->parent;
  if (!pos_del->right)
    if (isred(child(0, par1, i), i))
    {
      temp = child(0, par1, i);
      up_col(temp->red, isred(par2, i), i);
      up_col(par2->red, 0, i);
      newroot = double_rot(par2, LEFT, i);
    }
    else
    {
      up_col(par1->red, isred(par2, i), i);
      up_col(par2->red, 0, i);
      temp = child(1, par1, i);
      up_col(temp->red, 0, i);
      newroot = single_rot(par2, LEFT, i);
    }
  else
    if (isred(child(0, par1, i), i))
    {
      up_col(par1->red, isred(par2, i), i);
      up_col(par2->red, 0, i);
      temp = child(0, par1, i);
      up_col(temp->red, 0, i);
      newroot = single_rot(par2, RIGHT, i);
    }
    else
    {
      temp = child(1, par1, i);
      up_col(temp->red, isred(par2, i), i);
      up_col(par2->red, 0, i);
      newroot = double_rot(par2, RIGHT, i);
    }
  if (newroot != NULL)
    v_list->vl[i]->acc_pointer = newroot;

end:
  m_b_root(i);
  return i;
}


version pers_rb_tree::insert(void *val, void* info, version i1)
{
  int aux_bool; 
  pers_tree_node *p, *q, *r, *aux_node, *root, *newroot, *temp;

  version i = new_version(i1);

  p = search(val, i1);

  if (p && cmp_keys(p->key, val) == 0) return i;  // key already there

  copy_key(val);
  copy_inf(info);
  
  if (p == NULL)   // empty tree
  { p = newleaf(val, info, nil, nil, i);
    v_list->vl[i]->acc_pointer = p;
    v_list->vl[i]->popul = 1;
    goto end;
   }

  (v_list->vl[i]->popul)++;

  if (cmp_keys(val, p->key) > 0)   // new rightmost leaf 
    { q = newleaf(val,info, p, nil, i);   
      update(p->link[1], q, i);
     }
  else // new  leaf before  p 
    { pers_tree_node * pred = child(0,p,i);
      q = newleaf(val,info, pred, p, i);   
      update(p->link[0], q, i);
      if (pred) update(pred->link[1], q, i);
     }

  aux_bool = p->right;
  r = newnode(p, q, i);

  if (p->parent == NULL)
  {
    v_list->vl[i]->acc_pointer = r;
    goto end;
  }
  aux_node = p->parent;
  r->right = aux_bool;
  update(aux_node->link[aux_bool], r, i);

  if (!isred(aux_node, i))
     goto end;

  q = aux_node;
  p = q->parent;
  root = v_list->vl[i]->acc_pointer;
  while ((isred(child(0, p, i), i)) && (isred(child(1, p, i), i)))
  {
    temp = child(0, p, i);
    up_col(temp->red, 0, i);
    temp = child(1, p, i);
    up_col(temp->red, 0, i);
    up_col(p->red, 1, i);
    if (p == root)
      goto end;
    r = p;
    q = r->parent;
    if (!isred(q, i))
      goto end;
    p = q->parent;
  }
  if (q->right == r->right)
  {
    up_col(p->red, 1, i);
    up_col(q->red, 0, i);
    newroot = single_rot(p, 1 - r->right, i);
  }
  else
  {
    up_col(r->red, 0, i);
    up_col(p->red, 1, i);
    newroot = double_rot(p, r->right, i);
  }

  if (newroot != NULL)
    v_list->vl[i]->acc_pointer = newroot;

end:
  m_b_root(i);
  return i;
}


version pers_rb_tree::change_inf(pers_tree_node* p, void* info, version i1)
{
  version i = new_version(i1);

  p = search(p->key, i1);  // setting parent pointers

  pers_tree_node* pred = child(0,p,i);
  pers_tree_node* succ = child(1,p,i);

  copy_inf(info);
  pers_tree_node* q = newleaf(p->key,info, pred, succ, i);   


  if (pred) update(pred->link[1],q,i);
  if (succ) update(succ->link[0],q,i);

  q->right = p->right;
  update(p->parent->link[q->right], q, i);

  return i;

}



pers_tree_node* pers_rb_tree::min(version v)
{ pers_tree_node* r = v_list->vl[v]->acc_pointer;
  if (r == nil) return nil;
  while ( ! isleaf(r)) r = child(0,r,v);
  return r;
}  

pers_tree_node* pers_rb_tree::max(version v)
{ pers_tree_node* r = v_list->vl[v]->acc_pointer;
  if (r == nil) return nil;
  while ( ! isleaf(r)) r = child(1,r,v);
  return r;
}  

void pers_rb_tree::print(pers_tree_node *p, version v)
{ if (p)
  { if (isleaf(p))  
    { print_key(p->key);
      cout << " ";
     }
    else
     { print(child(0, p, v), v);
       print(child(1, p, v), v);
      }
   }
}  

void pers_rb_tree::del_tree()
{ 
  while (v_list->used)
  { pers_tree_node* p = v_list->used;
    v_list->used = v_list->used->next;

    f_rbclear(f_rchild(p->link[0]));
    delete p->link[0];

    f_rbclear(f_rchild(p->link[1]));
    delete p->link[1];

    if (p->copy != nil)
    {
      f_rbclear(f_rchild(p->copy));
      delete p->copy;
     }

    c_rbclear(c_rchild(p->red));
    delete p->red;

    if (isleaf(p))
    { clear_key(p->key);
      clear_inf(p->info);
     }

    delete p;
   }

   ver_node q;
   forall(q, v_list->vl) delete q;

   delete v_list;
 }  


pers_tree_node*  pers_rb_tree::lookup(void *val,version v)
{ pers_tree_node* p = search(val,v);
  return (p && cmp_keys(key(p), val) == 0) ? p : nil;
 }

pers_tree_node* pers_rb_tree::locate(void *val,version v)
{ pers_tree_node* p = search(val,v);
  return ( p && cmp_keys(key(p), val) >= 0) ?  p : nil;
 }

pers_tree_node* pers_rb_tree::locate_pred(void *val,version v)
{ pers_tree_node* p = search(val,v);
  if (p==0) return nil;
  if (cmp_keys(key(p), val) <= 0)  return p;
  return child(0,p,v);

}




void pers_rb_tree::draw(DRAW_NODE_FCT draw_node,
                        DRAW_EDGE_FCT draw_edge, 
                        version v, pers_tree_node* r, 
                        double x1, double x2, double y, 
                        double ydist, double last_x)
{ 

  double x = (x1+x2)/2;

  if (r==NULL) return;

  if (last_x != 0) draw_edge(last_x,y+ydist,x,y);

  if (isleaf(r)) 
     draw_node(x,y,r->key);
  else
    { draw_node(x,y,get_key(r,v));
      draw(draw_node,draw_edge,v,child(0,r,v),x1,x,y-ydist,ydist,x);
      draw(draw_node,draw_edge,v,child(1,r,v),x,x2,y-ydist,ydist,x);
     }
}

void pers_rb_tree::draw(DRAW_NODE_FCT draw_node,
                        DRAW_EDGE_FCT draw_edge, 
                        version v, double x1, double x2, double y, double ydist)
{ draw(draw_node,draw_edge,v,v_list->vl[v]->acc_pointer,x1,x2,y,ydist,0); }