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

#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 {
    if ((_node->hash_key) == (y->hash_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;
  // _x->right != NIL (definition)
  y = _x->right;
  _x->right = y->left;
  if (y->left != TableNode::nil) {
    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;
  if (_x != TableNode::nil) { 
    _x->p = y;
  }
}


void Table::right_rotate_RB (TableNode* _x)
{ 
  TableNode* y;
  // _x->left !=NIL (def)
  y = _x->left;
  _x->left = y->right;
  if (y->right != TableNode::nil) {
     y->right->p = _x;
  } 
  y->p = _x->p;
  if (_x->p == TableNode::nil) {
    root = y;  
  } else {
    if (_x == _x->p->right) {
      _x->p->right = y; 
    } else {
      _x->p->left = y;
    }
  }
  y->right = _x;
  if (_x != TableNode::nil) { 
    _x->p = y;
  }
}


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 = _z->right;
    if (y != TableNode::nil) {
      while (y->left != TableNode::nil) {
         y = y->left;
      }
    } else {
      x=_z;
      y = x->p;
      while ((y != TableNode::nil) && (x == y->right)) {
        x = y;
        y = y->p;
      }
    }  
  } 
  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) {
    if (node->hash_key != hash) {
      if (hash < node->hash_key) {
        node = node->left;
      } else {
        node = node->right;
      }
    } else {
      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)();
}

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

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


}