source: to-imperative/trunk/runtime/rf_table.cc @ 1226

#include "rf_table.ih"
#include <new>

namespace rftype
{

using namespace rfrt;  

TableNode* TableNode::nil = NULL;
  
size_t Table::count = 0;

//
// inserting of element newNode in this-Table
void Table::insert_node (TableNode* _node)
{
  TableNode* x;
  TableNode* y;
  int flag;
  y = TableNode::nil;
  x = root;
  while (x != TableNode::nil) {
    y=x;
    if ((_node->hash_key) == (x->hash_key)) {
      flag = Expr::compare(_node->key, x->key);
      if (!flag) {                      //   case 0 :  ==
        return;
      } else if (flag < 0) {            //   case < 0 : <
        x = x->left;
      } else {
        x = x->right;
      }
    } else if ((_node->hash_key) < (x->hash_key)) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  _node->p = y;
  if (y == TableNode::nil) {
    root = _node;
  } else {
    //
    // FIXME: Here we already chosen valid direction, so probably we
    // should introduce a flag indicating that direction to avoid possible
    // duplicated compare(). [pooh 2003-08-15]
    if ((_node->hash_key) == (y->hash_key)) {
      flag = Expr::compare(_node->key, y->key);
      if (flag < 0) {
        y->left = _node;
      } else {
        y->right = _node;
      }
    } else if ((_node->hash_key) < (y->hash_key)) {
      y->left = _node;
    } else {
      y->right = _node;
    }
  }
}


void Table::left_rotate_RB (TableNode* _x)
{ 
  TableNode* y;
  y = _x->right;
  _x->right = y->left;
  y->left->p = _x;
  y->p = _x->p;
  if (_x->p == TableNode::nil)
    root = y;   
  else
    if (_x == _x->p->left)
      _x->p->left = y;
    else
      _x->p->right = y;
  y->left = _x;
  _x->p = y;
}


void Table::right_rotate_RB (TableNode* _y)
{ 
  TableNode* x;
  x = _y->left;
  _y->left = x->right;
  x->right->p = _y;
  x->p = _y->p;
  if (_y->p == TableNode::nil)
    root = x;  
  else
    if (_y == _y->p->right)
      _y->p->right = x;
    else
      _y->p->left = x;
  x->right = _y;
  _y->p = x;
}


void Table::insert_node_RB (TableNode* _x)
{  
  TableNode *y;
  insert_node(_x);
  _x->color = TableNode::RED;
  while ((_x != root) && (_x->p->color == TableNode::RED)) {   
    if (_x->p == _x->p->p->left) {
      y = _x->p->p->right;
      if ((y != TableNode::nil) && (y->color == TableNode::RED)) {
        _x->p->color = TableNode::BLACK;
        y->color = TableNode::BLACK;
        _x->p->p->color = TableNode::RED;
        _x = _x->p->p;
      } else {
        if (_x == _x->p->right) {
          _x = _x->p;
          left_rotate_RB(_x);
        }
        _x->p->color = TableNode::BLACK;
        _x->p->p->color =TableNode::RED;
        right_rotate_RB(_x->p->p);
      }
    } else {
      y=_x->p->p->left;
      if ((y != TableNode::nil) && (y->color == TableNode::RED)) {
        _x->p->color = TableNode::BLACK;
        y->color = TableNode::BLACK;
        _x->p->p->color = TableNode::RED;
        _x = _x->p->p;
      } else {
        if (_x == _x->p->left) {
          _x = _x->p;
          right_rotate_RB(_x);
        }
        _x->p->color = TableNode::BLACK;
        _x->p->p->color = TableNode::RED;
        left_rotate_RB(_x->p->p);
      }
    }
  }
  root->color=TableNode::BLACK;   
}


TableNode* Table::delete_node_RB (TableNode *_z)
{ 
  TableNode* x;
  TableNode* y;
  if ((_z->left == TableNode::nil) || (_z->right == TableNode::nil))
    y = _z;
  else
    y = tree_successor(_z);
  if (y->left != TableNode::nil)
    x = y->left;
  else
    x = y->right;
  x->p = y->p;
  if (y->p == TableNode::nil)
    root = x;     
  else
    if (y == y->p->left)
      y->p->left = x;
    else
      y->p->right = x;
  if (y != _z) {
    _z->hash_key = y->hash_key;
    _z->val = y->val;
    _z->key = y->key;
  }
  if (y->color == TableNode::BLACK)
    delete_fixup_RB(x);
  return y;
}


void Table::delete_fixup_RB (TableNode* _x)
{ 
  TableNode* w;
  while ((_x != root) && (_x->color == TableNode::BLACK)) {
    if (_x == _x->p->left) {
      w = _x->p->right;
      if (w->color == TableNode::RED) {
        w->color = TableNode::BLACK;
        _x->p->color = TableNode::RED;
        left_rotate_RB(_x->p);
        w = _x->p->right;
      }
      if ((w->left->color == TableNode::BLACK) && (w->right->color == TableNode::BLACK)) {
        w->color = TableNode::RED;
        _x = _x->p;
      } else {
        if (w->right->color == TableNode::BLACK) {
          w->left->color = TableNode::BLACK;
          w->color = TableNode::RED;
          right_rotate_RB(w);
          w = _x->p->right;
        }
        w->color = _x->p->color;
        _x->p->color = TableNode::BLACK;
        w->right->color = TableNode::BLACK;
        left_rotate_RB(_x->p);
        _x=root;  
      }
    } else {
      w = _x->p->left;
      if (w->color == TableNode::RED) {
        w->color = TableNode::BLACK;
        _x->p->color = TableNode::RED;
        right_rotate_RB(_x->p);
        w = _x->p->left;
      }
      if ((w->right->color == TableNode::BLACK) && (w->left->color == TableNode::BLACK)) {
        w->color = TableNode::RED;
        _x = _x->p;
      } else {
        if (w->left->color == TableNode::BLACK) {
          w->right->color = TableNode::BLACK;
          w->color = TableNode::RED;
          left_rotate_RB(w);
          w = _x->p->left;
        }
        w->color = _x->p->color;
        _x->p->color = TableNode::BLACK;
        w->left->color = TableNode::BLACK;
        right_rotate_RB(_x->p);
        _x=root;  
      }
    }
  }
  _x->color=TableNode::BLACK;
}


TableNode* Table::search_node (Expr const& _key)
{  
  TableNode* node;
  int hash, flag;

  hash = expr_hash(_key);
  node = root;  
  while ((node != TableNode::nil) && (node->hash_key != hash)) {
    if (hash < node->hash_key)
      node = node->left;
    else
      node = node->right;
  }
  while ((node != TableNode::nil) && (hash == node->hash_key)) {
    flag = Expr::compare(_key, node->key);
    if (!flag)            //   case 0 : ==
      return (node);
    if (flag < 0)         //   case < 0 : <
      node = node->left;
    else
      node = node->right;    
  }
  return TableNode::nil;
}


void copy_tree (TableNode const&  _tab, TableNode& _copy)
{   
  TableNode* child;   
  _copy.hash_key = _tab.hash_key;
  _copy.key = _tab.key;
  _copy.val = _tab.val;
  _copy.color = _tab.color;
  if (_tab.left == TableNode::nil)
    _copy.left = TableNode::nil;
  else {     
    child = new TableNode;
    child->p = &_copy;
    _copy.left = child;
    copy_tree(*(_tab.left), *child);
  }
  if (_tab.right == TableNode::nil)
    _copy.right = TableNode::nil;
  else {     
    child = new TableNode;
    child->p = &_copy;
    _copy.right = child;
    copy_tree( *(_tab.right), *child);
  }
}

bool table_equal(TableNode const& _tab1, TableNode const& _tab2)
{  
  if ((&_tab1) == TableNode::nil) {
    if ((&_tab2) == TableNode::nil)
      return true;
    return false;
  }
  else {
    if ((&_tab2) == TableNode::nil)
      return false;
    if ( (_tab1.hash_key == _tab2.hash_key) &&
      (_tab1.color == _tab2.color) &&
      (_tab1.key == _tab2.key) &&
      (_tab1.val == _tab2.val) &&
      (table_equal(*_tab1.right, *_tab2.right)) &&
      (table_equal(*_tab1.left, *_tab2.left)) )
      return true;
    else 
      return false; 
  }
}


void delete_tree (TableNode* _node)
{   
  if (_node->left != TableNode::nil)
    delete_tree(_node->left);
  if (_node->right != TableNode::nil)
    delete_tree(_node->right);
  delete(_node);
}


void list_node (TableNode const& _node, Expr& _res)
{ 
  if (_node.left != TableNode::nil)   
    list_node( * _node.left, _res);
  if (_node.right != TableNode::nil)
    list_node( * _node.right, _res);
  _res = _res + (_node.key)();
}


TableNode*  tree_successor(TableNode* _x)
{
  TableNode* y;
  if (_x->right != TableNode::nil)
    return tree_minimum(_x->right);
  y=_x->p;
  while ((y != TableNode::nil) && (_x == y->right)) {
    _x = y;
    y = y->p;
  }
  return y;
}


TableNode* tree_minimum (TableNode* _x)
{
  while (_x->left != TableNode::nil)
    _x = _x->left;
  return _x;
}


}