Changeset 969


Ignore:
Timestamp:
Jul 7, 2003, 10:45:51 PM (18 years ago)
Author:
sveta
Message:
  • Class TABLE.
Location:
to-imperative/trunk/runtime
Files:
3 edited

Legend:

Unmodified
Added
Removed

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

    r932 r969  
    11#include "rf_table.ih"
     2#include <new>
    23
    34namespace rftype
    45{
    56
    6 using namespace rfrt;
    7 
    8 Table *NIL;
    9 
    10 /*  zaglushka */
     7using namespace rfrt; 
     8
     9TableNode* TableNode::nil = NULL;
     10
     11// zaglushka 
    1112int Expr_hash(Expr const&);
    12 
    13 /*  Constructor: create NIL-Table and initialize p - root of RB-tree  */
    14 
    15   Table :: Table() :
    16 Object ()
     13 
     14
     15void Table::Bind (Expr const& _key, Expr const& _val)
     16{
     17  TableNode *newNode;
     18  if ((newNode = IterativeTreeSearch(_key)) == TableNode::nil) {
     19    newNode = new TableNode;
     20    newNode->key = _key;
     21    newNode->hashKey = Expr_hash(_key);
     22    newNode->left = TableNode::nil;
     23    newNode->right = TableNode::nil;
     24    newNode->p = TableNode::nil;
     25    newNode->val = _val;
     26    RB_Insert(newNode);
     27  }
     28  else
     29    newNode->val = _val;
     30}
     31
     32void Table::Unbind (Expr& _key)
     33{
     34  TableNode *newNode;
     35  if ((newNode = IterativeTreeSearch(_key)) != TableNode::nil) {
     36    newNode = RB_Delete(newNode);
     37    delete(newNode);
     38  }
     39}
     40
     41
     42bool Table::Lookup (Expr const& _key, Expr& _val)
    1743{   
    18   static int flag=0;
    19 
    20   printf("Table() \n");
    21   if (!flag)
    22   {
    23     NIL = static_cast <Table *> (new(Table));
    24     NIL->color=BLACK;
    25     NIL->right=NIL;
    26     NIL->left=NIL;
    27     NIL->p=NIL;
    28     flag=1;
    29   }
    30   p=NIL;    /*   p - root */
    31 }
    32 
    33 
    34 void Table::Bind (Expr const& key, Expr const& val)
    35 {
    36   Table *newNode;
    37   if ((newNode =IterativeTreeSearch(key))==NIL)
    38   {
    39     newNode = static_cast <Table *> (new(Table));
    40     newNode->key=key;
    41     newNode->hashKey=Expr_hash(key);
    42     newNode->left=NIL;
    43     newNode->right=NIL;
    44     newNode->p=NIL;
    45     newNode->val=val;
    46     RBinsert(newNode);
    47   }
    48   else
    49     newNode->val=val;
    50 }
    51 
    52 
    53 void Table :: Unbind(Expr& key)
    54 {
    55   Table *newNode;
    56 
    57   if ((newNode = IterativeTreeSearch(key))!=NIL)
    58   {
    59     newNode= RBdelete(newNode);
    60     delete(newNode);
    61   }
    62 }
    63 
    64 
    65 int Table :: Lookup (Expr const& key, Expr& val)
    66 {   Table *newNode;
    67 
    68   if ((newNode = IterativeTreeSearch(key))==NIL)
    69     return 0;   /*  fail(0)  */
    70   else
    71   {
    72     val=newNode->val;
    73     return 1;
    74   }
    75 }
    76 
    77 
    78 /* In-table: returns 0, if key is absent, else - 1 */
    79 
    80 int Table:: In_table(Expr const& key)
    81 {
    82   Table *newNode;
    83 
    84   if ((newNode = IterativeTreeSearch(key))==NIL)
    85     return 0;
    86   else
    87     return 1;
    88 }
    89 
    90 /* Table_copy : this - sourceTable, newTable - result */
    91 
    92 void Table :: Table_copy(Table& newTable)
    93 {  Table *node;
    94 
    95   if (p!=NIL)   /*   p - root */
    96   {
    97     node=static_cast <Table *> (new(Table));
    98     node->p=NIL;       
    99     newTable.p=node;   /* p - root */
    100     CopyTree(p,node);  /* p - root */
    101   }
    102 }
    103 
    104 
    105 /* Replace_Table: this - TargetTable */
    106 
    107 void Table :: Replace_Table (Table const& SourceTable)   
    108 {   Table *x;
    109 
    110   if (p!=NIL)    /*  p - root */
    111   {   
    112     DeleteTree(p);
    113     p=NIL;       /*  p - root*/
    114   }
    115   if (SourceTable.p!= NIL)    /*  p - root */
    116   {
    117     x= static_cast <Table *> (new(Table));
    118     x->p=NIL;
    119     p=x;       /*  p - root */
    120     CopyTree(SourceTable.p,p);    /*  p - root */
    121   }
    122 }
    123 
    124 /* inserting of element newNode in this-Table  */
    125 
    126 void Table :: TreeInsert (Table* newNode)
    127 {
    128   Table *x, *y;
     44  TableNode *newNode;
     45  if ((newNode = IterativeTreeSearch(_key)) == TableNode::nil)
     46    return false;   
     47  else {
     48    _val = newNode->val;
     49    return true;
     50  }
     51}
     52
     53
     54bool Table::InTable (Expr const& _key)
     55{
     56  TableNode *newNode;
     57  if ((newNode = IterativeTreeSearch(_key)) == TableNode::nil)
     58    return false;
     59  else
     60    return true;
     61}
     62
     63 
     64//
     65// Table_copy : this - sourceTable, newTable - result
     66void Table::TableCopy (Table& _new_table)
     67{ 
     68  TableNode *node;
     69  if (root != TableNode::nil) {
     70    node = new TableNode;
     71    node->p = TableNode::nil;       
     72    _new_table.root = node;   // p - root 
     73    CopyTree(root, node);  // p - root
     74  }
     75}
     76
     77 
     78//
     79//  ReplaceTable: this - TargetTable
     80void Table::ReplaceTable (Table const& _source_table)   
     81{   
     82  TableNode* x;
     83  if (root != TableNode::nil) {
     84    DeleteTree(root);
     85    root = TableNode::nil;   
     86  }
     87  if (_source_table.root != TableNode::nil) {   
     88    x = new TableNode;
     89    x->p = TableNode::nil;
     90    root = x;     
     91    CopyTree(_source_table.root, root);
     92  }
     93}
     94
     95
     96// 
     97// inserting of element newNode in this-Table
     98void Table::TreeInsert (TableNode* _newNode)
     99{
     100  TableNode* x;
     101  TableNode* y;
    129102  int flag;
    130 
    131   y=NIL;
    132   x=p;   /*  root */
    133   while (x!=NIL)
    134   {
     103  y = TableNode::nil;
     104  x = root;   
     105  while (x != TableNode::nil) {
    135106    y=x;
    136     if ((newNode->hashKey) == (x->hashKey))
    137     { 
    138       flag=Expr::compare(newNode->key, x->key);
     107    if ((_newNode->hashKey) == (x->hashKey)) { 
     108      flag = Expr::compare(_newNode->key, x->key);
    139109      //      if ((newNode->key) == (x->key))
    140110      if (!flag)
    141111        return;
    142       //          if ((newNode->key) < (x->key))
    143       if (flag==-1)
    144       {
    145         x=x->left;
     112      //      if ((newNode->key) < (x->key))
     113      if (flag == -1){
     114        x = x->left;
    146115        continue;
    147       }
    148       else
    149       {
    150         x=x->right;
     116      } else {
     117        x = x->right;
    151118        continue;
    152119      }
    153120    }
    154     if ((newNode->hashKey)<(x->hashKey))
    155       x=x->left;
    156     else
    157       x=x->right;
    158   }
    159   newNode->p=y;
    160   if (y==NIL)
    161     p=newNode;   /*  p - root */
    162   else
    163     if ((newNode->hashKey) == (x->hashKey))
    164     { 
    165       flag=Expr::compare(newNode->key, x->key);
     121    if ((_newNode->hashKey) < (x->hashKey))
     122      x = x->left;
     123    else
     124      x = x->right;
     125  }
     126  _newNode->p = y;
     127  if (y == TableNode::nil)
     128    root = _newNode; 
     129  else
     130    if ((_newNode->hashKey) == (x->hashKey)) { 
     131      flag = Expr::compare(_newNode->key, x->key);
    166132      //    if ((newNode->key) < (x->key))
    167       if (flag==-1)
    168       {
    169         y->left=newNode;
     133      if (flag == -1) {
     134        y->left = _newNode;
    170135        return;
    171       }
    172       else
    173       {
    174         y->right=newNode;
     136      } else {
     137        y->right = _newNode;
    175138        return;
    176139      }
    177140    }   
    178   if ((newNode->hashKey) < (y->hashKey))
    179     y->left = newNode;
    180   else
    181     y->right = newNode;
    182 }
    183 
    184 
    185 /* Left-Rotate of node x for this-RB-tree */
    186 
    187 void Table :: LeftRotate (Table *x)
    188 { Table *y;
    189 
    190   y=x->right;
    191   x->right=y->left;
    192   y->left->p=x;
    193   y->p=x->p;
    194   if (x->p==NIL)
    195     p=y;   /*   p - root */
    196   else
    197     if (x==x->p->left)
    198       x->p->left=y;
    199     else
    200       x->p->right=y;
    201   y->left=x;
    202   x->p=y;
    203 }
    204 
    205 
    206 /* Right-Rotate of node y for this-RB-tree */
    207 
    208 void Table :: RightRotate (Table *y)
    209 { Table *x;
    210 
    211   x=y->left;
    212   y->left=x->right;
    213   x->right->p=y;
    214   x->p=y->p;
    215   if (y->p==NIL)
    216     p=x;     /*   p - root  */
    217   else
    218     if (y==y->p->right)
    219       y->p->right=x;
    220     else
    221       y->p->left=x;
    222   x->right=y;
    223   y->p=x;
    224 }
    225 
    226 
    227 /* inserting of node x for this-RB-tree */
    228 
    229 void Table :: RBinsert(Table *x)
    230 {  Table *y;
    231 
    232   TreeInsert(x);
    233   x->color=RED;
    234   while ((x!=p)&&(x->p->color==RED))       /*   p - root */
    235   {
    236     if (x->p == x->p->p->left)
    237     {
    238       y=x->p->p->right;
    239       if ((y!=NIL) && (y->color==RED))
    240       {
    241         x->p->color=BLACK;
    242         y->color=BLACK;
    243         x->p->p->color=RED;
    244         x=x->p->p;
    245       }
    246       else
    247       {
    248         if (x==x->p->right)
    249         {
    250           x=x->p;
    251           LeftRotate(x);
     141  if ((_newNode->hashKey) < (y->hashKey))
     142    y->left = _newNode;
     143  else
     144    y->right = _newNode;
     145}
     146
     147
     148void Table::LeftRotate (TableNode* _x)
     149{
     150  TableNode* y;
     151  y = _x->right;
     152  _x->right = y->left;
     153  y->left->p = _x;
     154  y->p = _x->p;
     155  if (_x->p == TableNode::nil)
     156    root = y;   
     157  else
     158    if (_x == _x->p->left)
     159      _x->p->left = y;
     160    else
     161      _x->p->right = y;
     162  y->left = _x;
     163  _x->p = y;
     164}
     165
     166
     167void Table::RightRotate (TableNode* _y)
     168{
     169  TableNode* x;
     170  x = _y->left;
     171  _y->left = x->right;
     172  x->right->p = _y;
     173  x->p = _y->p;
     174  if (_y->p == TableNode::nil)
     175    root = x; 
     176  else
     177    if (_y == _y->p->right)
     178      _y->p->right = x;
     179    else
     180      _y->p->left = x;
     181  x->right = _y;
     182  _y->p = x;
     183}
     184
     185
     186void Table::RB_Insert (TableNode* _x)
     187{ 
     188  TableNode *y;
     189  TreeInsert(_x);
     190  _x->color = RED;
     191  while ((_x != root) && (_x->p->color == RED)) {   
     192    if (_x->p == _x->p->p->left) {
     193      y = _x->p->p->right;
     194      if ((y != TableNode::nil) && (y->color == RED)) {
     195        _x->p->color = BLACK;
     196        y->color = BLACK;
     197        _x->p->p->color = RED;
     198        _x = _x->p->p;
     199      } else {
     200        if (_x == _x->p->right) {
     201          _x = _x->p;
     202          LeftRotate(_x);
    252203        }
    253         x->p->color=BLACK;
    254         x->p->p->color=RED;
    255         RightRotate(x->p->p);
    256       }
    257     }
    258     else
    259     {
    260       y=x->p->p->left;
    261       if ((y!=NIL)&&(y->color==RED))
    262       {
    263         x->p->color=BLACK;
    264         y->color=BLACK;
    265         x->p->p->color=RED;
    266         x=x->p->p;
    267       }
    268       else
    269       {
    270         if (x==x->p->left)
    271         {
    272           x=x->p;
    273           RightRotate(x);
     204        _x->p->color = BLACK;
     205        _x->p->p->color =RED;
     206        RightRotate(_x->p->p);
     207      }
     208    } else {
     209      y=_x->p->p->left;
     210      if ((y != TableNode::nil) && (y->color == RED)) {
     211        _x->p->color = BLACK;
     212        y->color = BLACK;
     213        _x->p->p->color = RED;
     214        _x = _x->p->p;
     215      } else {
     216        if (_x == _x->p->left) {
     217          _x = _x->p;
     218          RightRotate(_x);
    274219        }
    275         x->p->color=BLACK;
    276         x->p->p->color=RED;
    277         LeftRotate(x->p->p);
     220        _x->p->color = BLACK;
     221        _x->p->p->color = RED;
     222        LeftRotate(_x->p->p);
    278223      }
    279224    }
    280225  }
    281   p->color=BLACK;    /*    p - root */
    282 }
    283 
    284 
    285 /* deleting of this-RB-tree node z */
    286 
    287 Table* Table :: RBdelete (Table *z)
    288 { Table *x, *y;
    289 
    290   if ((z->left==NIL) || (z->right==NIL))
    291     y=z;
    292   else
    293     y=TreeSuccessor(z);
    294   if (y->left!=NIL)
    295     x=y->left;
    296   else
    297     x=y->right;
    298   x->p=y->p;
    299   if (y->p==NIL)
    300     p=x;      /*   p - root */
    301   else
    302     if (y==y->p->left)
    303       y->p->left=x;
    304     else
    305       y->p->right=x;
    306   if (y!=z)
    307   {
    308     z->hashKey=y->hashKey;
    309     z->val=y->val;
    310     //   = foe Expr
    311     z->key=y->key;
    312   }
    313   if (y->color==BLACK)
    314     RBdeleteFixup(x);
     226  root->color=BLACK;   
     227}
     228
     229
     230TableNode* Table::RB_Delete (TableNode *_z)
     231{
     232  TableNode* x;
     233  TableNode* y;
     234  if ((_z->left == TableNode::nil) || (_z->right == TableNode::nil))
     235    y = _z;
     236  else
     237    y = TreeSuccessor(_z);
     238  if (y->left != TableNode::nil)
     239    x = y->left;
     240  else
     241    x = y->right;
     242  x->p = y->p;
     243  if (y->p == TableNode::nil)
     244    root = x;     
     245  else
     246    if (y == y->p->left)
     247      y->p->left = x;
     248    else
     249      y->p->right = x;
     250  if (y != _z) {
     251    _z->hashKey = y->hashKey;
     252    _z->val = y->val;
     253    _z->key = y->key;
     254  }
     255  if (y->color == BLACK)
     256    RB_DeleteFixup(x);
    315257  return y;
    316258}
    317259
    318260
    319 void Table :: RBdeleteFixup(Table *x)
    320 { Table *w;
    321 
    322   while ((x!=p) && (x->color==BLACK))     /*   p - root */
    323   {
    324     if (x==x->p->left)
    325     {
    326       w=x->p->right;
    327       if (w->color==RED)
    328       {
    329         w->color=BLACK;
    330         x->p->color=RED;
    331         LeftRotate(x->p);
    332         w=x->p->right;
    333       }
    334       if ((w->left->color==BLACK)&&(w->right->color==BLACK))
    335       {
    336         w->color=RED;
    337         x=x->p;
    338       }
    339       else
    340       {
    341         if (w->right->color==BLACK)
    342         {
    343           w->left->color=BLACK;
    344           w->color=RED;
     261void Table::RB_DeleteFixup (TableNode* _x)
     262{
     263  TableNode* w;
     264  while ((_x != root) && (_x->color == BLACK)) {
     265    if (_x == _x->p->left) {
     266      w = _x->p->right;
     267      if (w->color == RED) {
     268        w->color = BLACK;
     269        _x->p->color = RED;
     270        LeftRotate(_x->p);
     271        w = _x->p->right;
     272      }
     273      if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
     274        w->color = RED;
     275        _x = _x->p;
     276      } else {
     277        if (w->right->color == BLACK) {
     278          w->left->color = BLACK;
     279          w->color = RED;
    345280          RightRotate(w);
    346           w=x->p->right;
     281          w = _x->p->right;
    347282        }
    348         w->color=x->p->color;
    349         x->p->color=BLACK;
    350         w->right->color=BLACK;
    351         LeftRotate(x->p);
    352         x=p;    /*  p - root */
     283        w->color = _x->p->color;
     284        _x->p->color = BLACK;
     285        w->right->color = BLACK;
     286        LeftRotate(_x->p);
     287        _x=root; 
     288      }
     289    } else {
     290      w = _x->p->left;
     291      if (w->color == RED) {
     292        w->color = BLACK;
     293        _x->p->color = RED;
     294        RightRotate(_x->p);
     295        w = _x->p->left;
     296      }
     297      if ((w->right->color == BLACK) && (w->left->color == BLACK)) {
     298        w->color = RED;
     299        _x = _x->p;
     300      } else {
     301        if (w->left->color == BLACK) {
     302          w->right->color = BLACK;
     303          w->color = RED;
     304          LeftRotate(w);
     305          w = _x->p->left;
     306        }
     307        w->color = _x->p->color;
     308        _x->p->color = BLACK;
     309        w->left->color = BLACK;
     310        RightRotate(_x->p);
     311        _x=root; 
    353312      }
    354313    }
    355     else
    356     {
    357       w=x->p->left;
    358       if (w->color==RED)
    359       {
    360         w->color=BLACK;
    361         x->p->color=RED;
    362         RightRotate(x->p);
    363         w=x->p->left;
    364       }
    365       if ((w->right->color==BLACK)&&(w->left->color==BLACK))
    366       {
    367         w->color=RED;
    368         x=x->p;
    369       }
    370       else
    371       {
    372         if (w->left->color==BLACK)
    373         {
    374           w->right->color=BLACK;
    375           w->color=RED;
    376           LeftRotate(w);
    377           w=x->p->left;
    378         }
    379         w->color=x->p->color;
    380         x->p->color=BLACK;
    381         w->left->color=BLACK;
    382         RightRotate(x->p);
    383         x=p;     /*  p - root */
    384       }
    385     }
    386   }
    387   x->color=BLACK;
    388 }
    389 
    390 
    391 /* search of hash at this-Table*/
    392 
    393 Table* Table :: IterativeTreeSearch (Expr const& key)
    394 {  Table *node;
     314  }
     315  _x->color=BLACK;
     316}
     317
     318
     319TableNode* Table::IterativeTreeSearch (Expr const& _key)
     320{ 
     321  TableNode* node;
    395322  int hash, flag;
    396323
    397   hash=Expr_hash(key);
    398   node = p;  /* root */
    399   while ((node!=NIL)&&(node->hashKey!=hash))
     324  hash = Expr_hash(_key);
     325  node = root; 
     326  while ((node != TableNode::nil) && (node->hashKey != hash))
    400327    if (hash < node->hashKey)
    401       node=node->left;
    402     else
    403       node=node->right;
     328      node = node->left;
     329    else
     330      node = node->right;
    404331  //  must be CompareExpr     
    405   while ((node!=NIL) && (hash == node->hashKey))
    406   {
    407     flag=Expr::compare(key, node->key);
     332  while ((node != TableNode::nil) && (hash == node->hashKey)) {
     333    flag = Expr::compare(_key, node->key);
    408334    //     if ( key == node->key)
    409335    if (!flag) 
    410336      return (node);
    411337    //     if  (key < node->key)
    412     if (flag==-1)
     338    if (flag == -1)
    413339      node = node->left;
    414340    else
    415341      node = node->right;   
    416342  }
    417   return (NIL);
    418 }
    419 
    420 
    421 void CopyTree(Table* tab, Table* copy)
    422 {   Table *child;   
    423 
    424   copy->hashKey=tab->hashKey;
    425   copy->key=tab->key;
    426   copy->val=tab->val;
    427   copy->color=tab->color;
    428   if (tab->left==NIL)
    429     copy->left=NIL;
    430   else
    431   {     
    432     child=static_cast<Table *> (new(Table));
    433     child->p=copy;
    434     copy->left=child;
    435     CopyTree(tab->left, child);
    436   }
    437   if (tab->right==NIL)
    438     copy->right=NIL;
    439   else
    440   {     
    441     child=static_cast<Table *> (new(Table));
    442     child->p=copy;
    443     copy->right=child;
    444     CopyTree(tab->right, child);
    445   }
    446 }
    447 
    448 
    449 bool TableEqual(Table* tab1, Table* tab2)
     343  return TableNode::nil;
     344}
     345
     346
     347void CopyTree (TableNode* _tab, TableNode* _copy)
     348{   
     349  TableNode* child;   
     350  _copy->hashKey = _tab->hashKey;
     351  _copy->key = _tab->key;
     352  _copy->val = _tab->val;
     353  _copy->color = _tab->color;
     354  if (_tab->left == TableNode::nil)
     355    _copy->left = TableNode::nil;
     356  else {     
     357    child = new TableNode;
     358    child->p = _copy;
     359    _copy->left = child;
     360    CopyTree(_tab->left, child);
     361  }
     362  if (_tab->right == TableNode::nil)
     363    _copy->right = TableNode::nil;
     364  else {     
     365    child = new(TableNode);
     366    child->p = _copy;
     367    _copy->right = child;
     368    CopyTree(_tab->right, child);
     369  }
     370}
     371
     372
     373bool TableEqual(TableNode* _tab1, TableNode* _tab2)
    450374{ 
    451   if (tab1==NIL)
    452   {
    453     if (tab2==NIL)
     375  if (_tab1 == TableNode::nil) {
     376    if (_tab2 == TableNode::nil)
    454377      return true;
    455378    return false;
    456379  }
    457   else
    458   {
    459     if (tab2==NIL)
     380  else {
     381    if (_tab2 == TableNode::nil)
    460382      return false;
    461     if ( (tab1->hashKey==tab2->hashKey) &&
    462         (tab1->color==tab2->color) &&
    463         (tab1->key==tab2->key) &&
    464         (tab1->val==tab2->val) &&
    465         (TableEqual(tab1->right, tab2->right)) &&
    466         (TableEqual(tab1->left, tab2->left)) )
     383    if ( (_tab1->hashKey == _tab2->hashKey) &&
     384      (_tab1->color == _tab2->color) &&
     385      (_tab1->key == _tab2->key) &&
     386      (_tab1->val == _tab2->val) &&
     387      (TableEqual(_tab1->right, _tab2->right)) &&
     388      (TableEqual(_tab1->left, _tab2->left)) )
    467389      return true;
    468390    else
    … …  
    472394
    473395
    474 void DeleteTree(Table *node)
     396void DeleteTree (TableNode* _node)
    475397{   
    476   if (node->left!=NIL)
    477     DeleteTree(node->left);
    478   if (node->right!=NIL)
    479     DeleteTree(node->right);
    480   delete(node);
    481 }
    482 
    483 
    484 /*   return key for Domain  */
    485   void InorderTreeWalk (Table* node, Expr& _res)
    486 { if (node!=NIL)
    487   {  InorderTreeWalk(node->left, _res);
    488     InorderTreeWalk(node->right, _res);
    489     _res = _res + (node->key)();
    490   }
    491 }
    492 
    493 
    494 /* successor for node x at RBtree  */
    495 
    496 Table*  TreeSuccessor(Table *x)
    497 {
    498   Table *y;
    499   if (x->right !=NIL)
    500     return(TreeMinimum(x->right));
    501   y=x->p;
    502   while ((y!=NIL)&&(x==y->right))
    503   {
    504     x=y;
    505     y=y->p;
     398  if (_node->left != TableNode::nil)
     399    DeleteTree(_node->left);
     400  if (_node->right != TableNode::nil)
     401    DeleteTree(_node->right);
     402  delete(_node);
     403}
     404
     405
     406void InorderTreeWalk (TableNode* _node, Expr& _res)
     407{
     408  if (_node != TableNode::nil) { 
     409    InorderTreeWalk(_node->left, _res);
     410    InorderTreeWalk(_node->right, _res);
     411    _res = _res + (_node->key)();
     412  }
     413}
     414
     415
     416TableNode*  TreeSuccessor(TableNode* _x)
     417{
     418  TableNode* y;
     419  if (_x->right != TableNode::nil)
     420    return TreeMinimum(_x->right);
     421  y=_x->p;
     422  while ((y != TableNode::nil) && (_x == y->right)) {
     423    _x = y;
     424    y = y->p;
    506425  }
    507426  return y;
    … …  
    509428
    510429
    511 
    512 /* search of minimum-key for RBtree, where  x - root */
    513 
    514 Table* TreeMinimum(Table *x)
    515 {
    516   while (x->left!=NIL)
    517     x=x->left;
    518   return x;
    519 }
    520 
    521 /*  hash - zaglushka */
    522 
    523 int Expr_hash(Expr const& key)
    524 {
    525   return key.get_len();
    526 }
    527 
    528 
    529 }
     430TableNode* TreeMinimum (TableNode* _x)
     431{
     432  while (_x->left != TableNode::nil)
     433    _x = _x->left;
     434  return _x;
     435}
     436
     437
     438//  hash - zaglushka
     439int Expr_hash (Expr const& _key)
     440{
     441  return _key.get_len();
     442}
     443
     444
     445}

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

    r932 r969  
    1 #ifndef RED
    2 #define RED 0
    3 #endif
    4 
    5 #ifndef BLACK
    6 #define BLACK 1
    7 #endif
    8 
    91#ifndef __rf_table_hh__
    102#define __rf_table_hh__
    … …  
    179{
    1810
    19 using namespace rfrt;
     11using namespace rfrt; 
     12 
     13class TableNode;
    2014
    21 class Table : public Object
     15 
     16typedef enum {BLACK, RED} node_color;
     17
     18class Table :
     19    public Object
    2220{
     21  private :
    2322 
     23  static ObjectRegister reg;
     24  TableNode* root;    // root of RB-tree 
     25
     26  void TreeInsert (TableNode*);
     27  void RB_Insert (TableNode*);
     28  void LeftRotate (TableNode*);
     29  void RightRotate (TableNode*);
     30  TableNode* IterativeTreeSearch (Expr const&);
     31  void RB_DeleteFixup (TableNode*);
     32  TableNode* RB_Delete (TableNode*);
     33
     34  public :
     35  inline Table ();
     36  inline ~Table();
     37  void Unbind (Expr& _key);
     38  bool Lookup (Expr const& _key, Expr& _val);
     39  bool InTable (Expr const& _key);
     40  inline Expr Domain ();
     41  void TableCopy (Table& _tab);
     42  void ReplaceTable (Table const& _tab);
     43  void Bind (Expr const& _key, Expr const& _val);
     44  inline unsigned get_type () const;
     45  inline uint32_t hash () const;
     46  inline bool operator == (Object const&) const;
     47};
     48 
     49class TableNode
     50{
     51  friend class Table;
     52
    2453  private:
    25 
    26   static ObjectRegister reg;
    27 
     54       
    2855  int hashKey;
    29   int color;
     56  node_color color;
    3057  Expr key;       // key-expression
    3158  Expr val;       // value-expression
    32   Table *left;    // left child
    33   Table *right;   // right child
    34   Table *p;       // parent or root (for pseudo-node)
     59  TableNode* left;    // left child
     60  TableNode* right;   // right child
     61  TableNode* p;       // parent   
    3562
    36   void TreeInsert(Table*);
    37   void RBinsert(Table*);
    38   void LeftRotate(Table*);
    39   void RightRotate(Table*);
    40   Table* IterativeTreeSearch(Expr const&);
    41   void RBdeleteFixup(Table*);
    42   Table* RBdelete(Table *);
     63  static TableNode* nil;   
    4364
    44   public :
    45 
    46   Table ();
    47   inline ~Table();
    48   void Unbind(Expr& key);
    49   int Lookup (Expr const& key, Expr& val);
    50   int In_table(Expr const& key);
    51   inline Expr Domain ();
    52   void Table_copy(Table&);
    53   void Replace_Table (Table const&);
    54   void Bind(Expr const& key, Expr const& val);
    55 
    56   inline unsigned get_type () const;
    57   inline uint32_t hash () const;
    58   inline bool operator==(Object const& _obj) const;
    59 
    60   friend Table* TreeSuccessor(Table* node);
    61   friend Table* TreeMinimum(Table* node);
    62   friend void InorderTreeWalk(Table* node, Expr& res);
    63   friend void CopyTree(Table *tab, Table *copy);
    64   friend void DeleteTree(Table *node);
    65   friend bool TableEqual(Table*, Table*);
     65  friend TableNode* TreeSuccessor (TableNode*) ;
     66  friend TableNode* TreeMinimum (TableNode*) ;
     67  friend void InorderTreeWalk (TableNode*, Expr&) ;
     68  friend void CopyTree (TableNode*, TableNode*) ;
     69  friend void DeleteTree (TableNode*) ;
     70  friend bool TableEqual (TableNode*, TableNode*) ;
    6671};
    6772

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

    r932 r969  
    77#include "rf_object.ih"
    88#include "rf_expr.ih"
    9 
     9#include <new>
    1010
    1111namespace rftype
    1212{
    1313
     14inline Table::Table()
     15  : Object()
     16{
     17  static bool flag = false;
     18  if (!flag) {
     19    flag = true;
     20    TableNode::nil = new TableNode;
     21    TableNode::nil->color = BLACK;
     22  }
     23  root = TableNode::nil;
     24}
    1425
    1526inline unsigned Table::get_type () const
    … …  
    1829}
    1930
    20 
    2131inline uint32_t Table::hash () const
    2232{
    … …  
    2434}
    2535
    26 
    27 inline bool Table::operator == (Object const& _table) const
     36inline bool Table::operator== (Object const& _table) const
    2837{
    2938  try {
    30     Table const&  _t=static_cast <Table const&>(_table); 
    31     return TableEqual(p, _t.p);
    32   }
     39    Table const&  t = static_cast <Table const&>(_table); 
     40    return TableEqual(root, t.root);
     41 }
    3342  catch (std::bad_cast&)
    3443  {
    3544    return false;
    3645  }
     46}
     47
     48//
     49// Destructor: deleting of this-RBtree
     50inline Table::~Table ()
     51{ 
     52   if (root != TableNode::nil)
     53     DeleteTree(root);
    3754}
    3855
    39 
    40 /* Destructor: deleting of this-RBtree */
    41 
    42 inline Table :: ~Table()
    43 {   
    44   DeleteTree(p);
    45 }
    46 
    47 
    48 inline Expr Table :: Domain ()
     56inline Expr Table::Domain ()
    4957{ 
    5058  Expr res = Expr();
    51   InorderTreeWalk(p, res);     /* p - root */
     59  InorderTreeWalk(root, res);   
    5260  return res;
    5361}
    54 
    55 
     62 
    5663}
    5764
Note: See TracChangeset for help on using the changeset viewer.