Changeset 1001


Ignore:
Timestamp:
Jul 10, 2003, 10:55:19 PM (18 years ago)
Author:
sveta
Message:
  • Format of functions is changed.
Location:
to-imperative/trunk/runtime
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • to-imperative/trunk/runtime/rf_table.cc

    r983 r1001  
    2222    if ((_newNode->hashKey) == (x->hashKey)) { 
    2323      flag = Expr::compare(_newNode->key, x->key);
    24       //      if ((newNode->key) == (x->key))
    25       if (!flag)
     24      if (!flag)                    //   case 0 :  ==
    2625        return;
    27       //      if ((newNode->key) < (x->key))
    28       if (flag == -1){
     26      if (flag == -1){              //   case -1 : <
    2927        x = x->left;
    3028        continue;
    … …  
    4543    if ((_newNode->hashKey) == (x->hashKey)) { 
    4644      flag = Expr::compare(_newNode->key, x->key);
    47       //    if ((newNode->key) < (x->key))
    48       if (flag == -1) {
     45      if (flag == -1) {          //  case -1 : <
    4946        y->left = _newNode;
    5047        return;
    … …  
    103100  TableNode *y;
    104101  InsertNode(_x);
    105   _x->color = RED;
    106   while ((_x != root) && (_x->p->color == RED)) {   
     102  _x->color = TableNode::RED;
     103  while ((_x != root) && (_x->p->color == TableNode::RED)) {   
    107104    if (_x->p == _x->p->p->left) {
    108105      y = _x->p->p->right;
    109       if ((y != TableNode::nil) && (y->color == RED)) {
    110         _x->p->color = BLACK;
    111         y->color = BLACK;
    112         _x->p->p->color = RED;
     106      if ((y != TableNode::nil) && (y->color == TableNode::RED)) {
     107        _x->p->color = TableNode::BLACK;
     108        y->color = TableNode::BLACK;
     109        _x->p->p->color = TableNode::RED;
    113110        _x = _x->p->p;
    114111      } else {
    … …  
    117114          LeftRotate_RB(_x);
    118115        }
    119         _x->p->color = BLACK;
    120         _x->p->p->color =RED;
     116        _x->p->color = TableNode::BLACK;
     117        _x->p->p->color =TableNode::RED;
    121118        RightRotate_RB(_x->p->p);
    122119      }
    123120    } else {
    124121      y=_x->p->p->left;
    125       if ((y != TableNode::nil) && (y->color == RED)) {
    126         _x->p->color = BLACK;
    127         y->color = BLACK;
    128         _x->p->p->color = RED;
     122      if ((y != TableNode::nil) && (y->color == TableNode::RED)) {
     123        _x->p->color = TableNode::BLACK;
     124        y->color = TableNode::BLACK;
     125        _x->p->p->color = TableNode::RED;
    129126        _x = _x->p->p;
    130127      } else {
    … …  
    133130          RightRotate_RB(_x);
    134131        }
    135         _x->p->color = BLACK;
    136         _x->p->p->color = RED;
     132        _x->p->color = TableNode::BLACK;
     133        _x->p->p->color = TableNode::RED;
    137134        LeftRotate_RB(_x->p->p);
    138135      }
    139136    }
    140137  }
    141   root->color=BLACK;   
     138  root->color=TableNode::BLACK;   
    142139}
    143140
    … …  
    168165    _z->key = y->key;
    169166  }
    170   if (y->color == BLACK)
     167  if (y->color == TableNode::BLACK)
    171168    DeleteFixup_RB(x);
    172169  return y;
    … …  
    177174{
    178175  TableNode* w;
    179   while ((_x != root) && (_x->color == BLACK)) {
     176  while ((_x != root) && (_x->color == TableNode::BLACK)) {
    180177    if (_x == _x->p->left) {
    181178      w = _x->p->right;
    182       if (w->color == RED) {
    183         w->color = BLACK;
    184         _x->p->color = RED;
     179      if (w->color == TableNode::RED) {
     180        w->color = TableNode::BLACK;
     181        _x->p->color = TableNode::RED;
    185182        LeftRotate_RB(_x->p);
    186183        w = _x->p->right;
    187184      }
    188       if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
    189         w->color = RED;
     185      if ((w->left->color == TableNode::BLACK) && (w->right->color == TableNode::BLACK)) {
     186        w->color = TableNode::RED;
    190187        _x = _x->p;
    191188      } else {
    192         if (w->right->color == BLACK) {
    193           w->left->color = BLACK;
    194           w->color = RED;
     189        if (w->right->color == TableNode::BLACK) {
     190          w->left->color = TableNode::BLACK;
     191          w->color = TableNode::RED;
    195192          RightRotate_RB(w);
    196193          w = _x->p->right;
    197194        }
    198195        w->color = _x->p->color;
    199         _x->p->color = BLACK;
    200         w->right->color = BLACK;
     196        _x->p->color = TableNode::BLACK;
     197        w->right->color = TableNode::BLACK;
    201198        LeftRotate_RB(_x->p);
    202199        _x=root; 
    … …  
    204201    } else {
    205202      w = _x->p->left;
    206       if (w->color == RED) {
    207         w->color = BLACK;
    208         _x->p->color = RED;
     203      if (w->color == TableNode::RED) {
     204        w->color = TableNode::BLACK;
     205        _x->p->color = TableNode::RED;
    209206        RightRotate_RB(_x->p);
    210207        w = _x->p->left;
    211208      }
    212       if ((w->right->color == BLACK) && (w->left->color == BLACK)) {
    213         w->color = RED;
     209      if ((w->right->color == TableNode::BLACK) && (w->left->color == TableNode::BLACK)) {
     210        w->color = TableNode::RED;
    214211        _x = _x->p;
    215212      } else {
    216         if (w->left->color == BLACK) {
    217           w->right->color = BLACK;
    218           w->color = RED;
     213        if (w->left->color == TableNode::BLACK) {
     214          w->right->color = TableNode::BLACK;
     215          w->color = TableNode::RED;
    219216          LeftRotate_RB(w);
    220217          w = _x->p->left;
    221218        }
    222219        w->color = _x->p->color;
    223         _x->p->color = BLACK;
    224         w->left->color = BLACK;
     220        _x->p->color = TableNode::BLACK;
     221        w->left->color = TableNode::BLACK;
    225222        RightRotate_RB(_x->p);
    226223        _x=root; 
    … …  
    228225    }
    229226  }
    230   _x->color=BLACK;
     227  _x->color=TableNode::BLACK;
    231228}
    232229
    … …  
    243240      node = node->left;
    244241    else
    245       node = node->right;
    246   //  must be CompareExpr     
     242      node = node->right;   
    247243  while ((node != TableNode::nil) && (hash == node->hashKey)) {
    248244    flag = Expr::compare(_key, node->key);
    249     //     if ( key == node->key)
    250     if (!flag) 
     245    if (!flag)            //   case 0 : ==
    251246      return (node);
    252     //     if  (key < node->key)
    253     if (flag == -1)
     247    if (flag == -1)       //   case -1 : <
    254248      node = node->left;
    255249    else
    … …  
    260254
    261255
    262 void CopyTree (TableNode* _tab, TableNode* _copy)
     256void CopyTree (TableNode const&  _tab, TableNode& _copy)
    263257{   
    264258  TableNode* child;   
    265   _copy->hashKey = _tab->hashKey;
    266   _copy->key = _tab->key;
    267   _copy->val = _tab->val;
    268   _copy->color = _tab->color;
    269   if (_tab->left == TableNode::nil)
    270     _copy->left = TableNode::nil;
     259  _copy.hashKey = _tab.hashKey;
     260  _copy.key = _tab.key;
     261  _copy.val = _tab.val;
     262  _copy.color = _tab.color;
     263  if (_tab.left == TableNode::nil)
     264    _copy.left = TableNode::nil;
    271265  else {     
    272266    child = new TableNode;
    273     child->p = _copy;
    274     _copy->left = child;
    275     CopyTree(_tab->left, child);
    276   }
    277   if (_tab->right == TableNode::nil)
    278     _copy->right = TableNode::nil;
     267    child->p = &_copy;
     268    _copy.left = child;
     269    CopyTree(*(_tab.left), *child);
     270  }
     271  if (_tab.right == TableNode::nil)
     272    _copy.right = TableNode::nil;
    279273  else {     
    280     child = new(TableNode);
    281     child->p = _copy;
    282     _copy->right = child;
    283     CopyTree(_tab->right, child);
    284   }
    285 }
    286 
    287 bool TableEqual(TableNode* _tab1, TableNode* _tab2)
     274    child = new TableNode;
     275    child->p = &_copy;
     276    _copy.right = child;
     277    CopyTree( *(_tab.right), *child);
     278  }
     279}
     280
     281bool TableEqual(TableNode const& _tab1, TableNode const& _tab2)
    288282{ 
    289   if (_tab1 == TableNode::nil) {
    290     if (_tab2 == TableNode::nil)
     283  if ((&_tab1) == TableNode::nil) {
     284    if ((&_tab2) == TableNode::nil)
    291285      return true;
    292286    return false;
    293287  }
    294288  else {
    295     if (_tab2 == TableNode::nil)
     289    if ((&_tab2) == TableNode::nil)
    296290      return false;
    297     if ( (_tab1->hashKey == _tab2->hashKey) &&
    298       (_tab1->color == _tab2->color) &&
    299       (_tab1->key == _tab2->key) &&
    300       (_tab1->val == _tab2->val) &&
    301       (TableEqual(_tab1->right, _tab2->right)) &&
    302       (TableEqual(_tab1->left, _tab2->left)) )
     291    if ( (_tab1.hashKey == _tab2.hashKey) &&
     292      (_tab1.color == _tab2.color) &&
     293      (_tab1.key == _tab2.key) &&
     294      (_tab1.val == _tab2.val) &&
     295      (TableEqual(*_tab1.right, *_tab2.right)) &&
     296      (TableEqual(*_tab1.left, *_tab2.left)) )
    303297      return true;
    304298    else
    … …  
    318312
    319313
    320 void ListNode (TableNode* _node, Expr& _res)
    321 {
    322   if (_node != TableNode::nil) { 
    323     ListNode(_node->left, _res);
    324     ListNode(_node->right, _res);
    325     _res = _res + (_node->key)();
    326   }
     314void ListNode (TableNode const& _node, Expr& _res)
     315{
     316  if (_node.left != TableNode::nil)  
     317    ListNode( * _node.left, _res);
     318  if (_node.right != TableNode::nil)
     319    ListNode( * _node.right, _res);
     320  _res = _res + (_node.key)();
    327321}
    328322

  • to-imperative/trunk/runtime/rf_table.hh

    r983 r1001  
    1212 
    1313class TableNode;
    14 
    15  
    16 typedef enum {BLACK, RED} node_color;
    1714
    1815class Table :
    … …  
    3330
    3431  public :
     32
    3533  inline Table ();
    3634  inline ~Table();
    … …  
    5149  friend class Table;
    5250
    53   private:
     51  private: 
    5452       
    5553  int hashKey;
    56   node_color color;
     54  enum {BLACK, RED} color;
    5755  Expr key;       // key-expression
    5856  Expr val;       // value-expression
    … …  
    6563  friend TableNode* TreeSuccessor (TableNode*) ;
    6664  friend TableNode* TreeMinimum (TableNode*) ;
    67   friend void ListNode (TableNode*, Expr&) ;
    68   friend void CopyTree (TableNode*, TableNode*) ;
     65  friend void ListNode (TableNode const&, Expr&) ;
     66  friend void CopyTree (TableNode const&, TableNode&) ;
    6967  friend void DeleteTree (TableNode*) ;
    70   friend bool TableEqual (TableNode*, TableNode*) ;
     68  friend bool TableEqual (TableNode const&, TableNode const&) ;
    7169};
    7270

  • to-imperative/trunk/runtime/rf_table.ih

    r983 r1001  
    1919    flag = true;
    2020    TableNode::nil = new TableNode;
    21     TableNode::nil->color = BLACK;
     21    TableNode::nil->color = TableNode::BLACK;
    2222  }
    2323  root = TableNode::nil;
    … …  
    3838  try {
    3939    Table const&  t = static_cast <Table const&>(_table); 
    40     return TableEqual(root, t.root);
     40    return TableEqual(*root, *t.root);
    4141 }
    4242  catch (std::bad_cast&)
    … …  
    5757{ 
    5858  Expr res = Expr();
    59   ListNode(root, res);   
     59  if (root != TableNode::nil)
     60    ListNode(*root, res);   
    6061  return res;
    6162}
    … …  
    125126    node->p = TableNode::nil;       
    126127    _new_table.root = node;   // p - root 
    127     CopyTree(root, node);  // p - root
     128    CopyTree(*root, *node);  // p - root
    128129  }
    129130}
    … …  
    143144    x->p = TableNode::nil;
    144145    root = x;     
    145     CopyTree(_source_table.root, root);
     146    CopyTree(*_source_table.root, *root);
    146147  }
    147148}
Note: See TracChangeset for help on using the changeset viewer.