Changeset 922


Ignore:
Timestamp:
Jul 1, 2003, 2:52:30 AM (18 years ago)
Author:
orlov
Message:
  • Get the project successfully build.
Location:
to-imperative/trunk
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • to-imperative/trunk/library/Makefile

    r917 r922  
    11SUBDIRS = \
    2   Access Arithm Box Class Convert StdIO String
     2  Access Arithm Box Class Convert StdIO String Table
    33
    44TOPDIR = ..
  • to-imperative/trunk/runtime/rf_table.cc

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

    r913 r922  
    1111namespace rftype
    1212{
    13 
    14 using namespace rfrt;
    15 
    16 Table *NIL;
    17 
    18 /*  zaglushka */
    19 int Expr_hash(Expr const&);
    20 
    21 /*  Constructor: create NIL-Table and initialize p - root of RB-tree  */
    22 
    23 Table :: Table():
    24   Object ()
    25 {   
    26         static int flag=0;
    27 
    28     if (!flag)
    29         {
    30         NIL = static_cast <Table *> (new(Table));
    31         NIL->color=BLACK;
    32         NIL->right=NIL;
    33         NIL->left=NIL;
    34         NIL->p=NIL;
    35         flag=1;
    36         }
    37     p=NIL;    /*   p - root */
    38 }
    39 
    40 
    41 /* Destructor: deleting of this-RBtree */
    42 
    43 Table :: ~Table()
    44 {   
    45     DeleteTree(p);
    46 }
    4713
    4814
     
    7137}
    7238
    73 
    74 void Table :: Bind (Expr const& key, Expr const& val)
    75 {
    76    Table *newNode;
    77     if ((newNode =IterativeTreeSearch(key))==NIL)
    78         {
    79           newNode = static_cast <Table *> (new(Table));
    80           newNode->key=key;
    81           newNode->hashKey=Expr_hash(key);
    82           newNode->left=NIL;
    83           newNode->right=NIL;
    84           newNode->p=NIL;
    85           newNode->val=val;
    86           RBinsert(newNode);
    87         }
    88         else
    89           newNode->val=val;
    90 }
    91 
    92 
    93 
    94 
    95 void Table :: Unbind(Expr& key)
    96 {
    97         Table *newNode;
    98 
    99         if ((newNode = IterativeTreeSearch(key))==NIL);
    100 //              printf("error hash not exists\n");
    101         else
    102         {
    103                 newNode= RBdelete(newNode);
    104                 delete(newNode);
    105         }
    106 }
    107 
    108 
    109 int Table :: Lookup (Expr const& key, Expr& val)
    110 {       Table *newNode;
    111 
    112         if ((newNode = IterativeTreeSearch(key))==NIL)
    113                 return 0;   /*  fail(0)  */
    114         else
    115         {
    116                val=newNode->val;
    117                return 1;
    118         }
    119 }
    120 
    121 
    122 /* In-table: returns 0, if key is absent, else - 1 */
    123 
    124 int Table:: In_table(Expr const& key)
    125 {       Table *newNode;
    126 
    127         if ((newNode = IterativeTreeSearch(key))==NIL)
    128                 return 0;
    129         else
    130                 return 1;
    131 }
    132 
    133 
    134 Expr Table :: Domain ()
    135 
    136    Expr res = Expr();
    137    InorderTreeWalk(p, res);     /* p - root */
    138    return res;
    139 }
    140 
    141 
    142 /* Table_copy : this - sourceTable, newTable - result */
    143  
    144 void Table :: Table_copy(Table& newTable)
    145 {  Table *node;
    146        
    147         if (p!=NIL)   /*   p - root */
    148         {
    149         node=static_cast <Table *> (new(Table));
    150         node->p=NIL;       
    151         newTable.p=node;   /* p - root */
    152         CopyTree(p,node);  /* p - root */
    153         }
    154 }
    155 
    156 
    157 /* Replace_Table: this - TargetTable */
    158 
    159 void Table :: Replace_Table (Table const& SourceTable)   
    160 {   Table *x;
    161 
    162     if (p!=NIL)    /*  p - root */
    163         {         
    164                 DeleteTree(p);
    165         p=NIL;       /*  p - root*/
    166         }
    167     if (SourceTable.p!= NIL)    /*  p - root */
    168         {
    169         x= static_cast <Table *> (new(Table));
    170         x->p=NIL;
    171         p=x;       /*  p - root */
    172         CopyTree(SourceTable.p,p);    /*  p - root */
    173         }
    174 }
    175 
    176 
    177 /* inserting of element newNode in this-Table  */
    178 
    179 void Table :: TreeInsert (Table* newNode)
    180 {
    181   Table *x, *y;
    182   int flag;
    183  
    184   y=NIL;
    185   x=p;   /*  root */
    186   while (x!=NIL)
    187   {
    188     y=x;
    189     if ((newNode->hashKey) == (x->hashKey))
    190         { 
    191             flag=Expr::compare(newNode->key, x->key);
    192 //          if ((newNode->key) == (x->key))
    193             if (!flag)
    194               return;
    195 //          if ((newNode->key) < (x->key))
    196             if (flag==-1)
    197             {
    198                x=x->left;
    199                continue;
    200             }
    201             else
    202             {
    203                 x=x->right;
    204                 continue;
    205             }
    206     }
    207     if ((newNode->hashKey)<(x->hashKey))
    208       x=x->left;
    209     else
    210       x=x->right;
    211   }
    212   newNode->p=y;
    213   if (y==NIL)
    214       p=newNode;   /*  p - root */
    215   else
    216     if ((newNode->hashKey) == (x->hashKey))
    217         { 
    218               flag=Expr::compare(newNode->key, x->key);
    219 //              if ((newNode->key) < (x->key))
    220               if (flag==-1)
    221                 {
    222                     y->left=newNode;
    223                         return;
    224                 }
    225               else
    226                 {
    227                     y->right=newNode;
    228                         return;
    229                 }
    230      }   
    231          if ((newNode->hashKey) < (y->hashKey))
    232        y->left = newNode;
    233      else
    234        y->right = newNode;
    235 }
    236 
    237 
    238 /* Left-Rotate of node x for this-RB-tree */
    239 
    240 void Table :: LeftRotate (Table *x)
    241 { Table *y;
    242 
    243   y=x->right;
    244   x->right=y->left;
    245   y->left->p=x;
    246   y->p=x->p;
    247   if (x->p==NIL)
    248     p=y;   /*   p - root */
    249   else
    250     if (x==x->p->left)
    251       x->p->left=y;
    252     else
    253       x->p->right=y;
    254   y->left=x;
    255   x->p=y;
    256 }
    257 
    258 
    259 /* Right-Rotate of node y for this-RB-tree */
    260 
    261 void Table :: RightRotate (Table *y)
    262 { Table *x;
    263 
    264   x=y->left;
    265   y->left=x->right;
    266   x->right->p=y;
    267   x->p=y->p;
    268   if (y->p==NIL)
    269     p=x;     /*   p - root  */
    270   else
    271     if (y==y->p->right)
    272       y->p->right=x;
    273     else
    274       y->p->left=x;
    275   x->right=y;
    276   y->p=x;
    277 }
    278 
    279 
    280 /* inserting of node x for this-RB-tree */
    281 
    282 void Table :: RBinsert(Table *x)
    283 {  Table *y;
    284 
    285     TreeInsert(x);
    286         x->color=RED;
    287     while ((x!=p)&&(x->p->color==RED))       /*   p - root */
    288         {
    289                 if (x->p == x->p->p->left)
    290                 {
    291                         y=x->p->p->right;
    292                     if ((y!=NIL) && (y->color==RED))
    293                         {
    294                            x->p->color=BLACK;
    295                            y->color=BLACK;
    296                            x->p->p->color=RED;
    297                            x=x->p->p;
    298                         }
    299                     else
    300                         {
    301                            if (x==x->p->right)
    302                            {
    303                                 x=x->p;
    304                                 LeftRotate(x);
    305                            }
    306                            x->p->color=BLACK;
    307                            x->p->p->color=RED;
    308                            RightRotate(x->p->p);
    309                         }
    310                 }       
    311                 else
    312                 {
    313                     y=x->p->p->left;
    314                     if ((y!=NIL)&&(y->color==RED))
    315                         {
    316                            x->p->color=BLACK;
    317                            y->color=BLACK;
    318                            x->p->p->color=RED;
    319                            x=x->p->p;
    320                         }
    321                     else
    322                         {
    323                            if (x==x->p->left)
    324                            {
    325                                    x=x->p;
    326                                    RightRotate(x);
    327                            }
    328                            x->p->color=BLACK;
    329                            x->p->p->color=RED;
    330                            LeftRotate(x->p->p);
    331                         }
    332                 }
    333         }
    334         p->color=BLACK;    /*    p - root */
    335 }
    336 
    337 
    338 /* deleting of this-RB-tree node z */
    339 
    340 Table* Table :: RBdelete (Table *z)
    341 { Table *x, *y;
    342 
    343   if ((z->left==NIL) || (z->right==NIL))
    344           y=z;
    345   else
    346           y=TreeSuccessor(z);
    347   if (y->left!=NIL)
    348           x=y->left;
    349   else
    350           x=y->right;
    351   x->p=y->p;
    352   if (y->p==NIL)
    353           p=x;      /*   p - root */
    354   else
    355           if (y==y->p->left)
    356                   y->p->left=x;
    357           else
    358                   y->p->right=x;
    359   if (y!=z)
    360   {
    361           z->hashKey=y->hashKey;
    362           z->val=y->val;
    363 //   = foe Expr
    364           z->key=y->key;
    365   }
    366   if (y->color==BLACK)
    367           RBdeleteFixup(x);
    368   return y;
    369 }
    370 
    371 
    372 void Table :: RBdeleteFixup(Table *x)
    373 { Table *w;
    374 
    375   while ((x!=p) && (x->color==BLACK))     /*   p - root */
    376   {
    377           if (x==x->p->left)
    378       {
    379                   w=x->p->right;
    380                   if (w->color==RED)
    381                   {
    382                           w->color=BLACK;
    383                           x->p->color=RED;
    384                           LeftRotate(x->p);
    385                           w=x->p->right;
    386                   }
    387                   if ((w->left->color==BLACK)&&(w->right->color==BLACK))
    388           {
    389                           w->color=RED;
    390                           x=x->p;
    391                   }
    392                   else
    393                   {
    394                           if (w->right->color==BLACK)
    395                           {
    396                                   w->left->color=BLACK;
    397                                   w->color=RED;
    398                                   RightRotate(w);
    399                                   w=x->p->right;
    400                           }
    401                           w->color=x->p->color;
    402                           x->p->color=BLACK;
    403                           w->right->color=BLACK;
    404                           LeftRotate(x->p);
    405                           x=p;    /*  p - root */
    406                   }
    407           }
    408           else
    409           {
    410                   w=x->p->left;
    411                   if (w->color==RED)
    412                   {
    413                           w->color=BLACK;
    414                           x->p->color=RED;
    415                           RightRotate(x->p);
    416                           w=x->p->left;
    417                   }
    418                   if ((w->right->color==BLACK)&&(w->left->color==BLACK))
    419           {
    420                           w->color=RED;
    421                           x=x->p;
    422                   }
    423                   else
    424                   {
    425                           if (w->left->color==BLACK)
    426                           {
    427                                   w->right->color=BLACK;
    428                                   w->color=RED;
    429                                   LeftRotate(w);
    430                                   w=x->p->left;
    431                           }
    432                           w->color=x->p->color;
    433                           x->p->color=BLACK;
    434                           w->left->color=BLACK;
    435                           RightRotate(x->p);
    436                           x=p;     /*  p - root */
    437                   }
    438           }
    439   }
    440   x->color=BLACK;
    441 }
    442 
    443 
    444 /* search of hash at this-Table*/
    445 
    446 Table* Table :: IterativeTreeSearch (Expr const& key)
    447 {  Table *node;
    448    int hash, flag;
    449 
    450    hash=Expr_hash(key);
    451    node = p;  /* root */
    452    while ((node!=NIL)&&(node->hashKey!=hash))
    453      if (hash < node->hashKey)
    454        node=node->left;
    455      else
    456        node=node->right;
    457 //  must be CompareExpr     
    458    while ((node!=NIL) && (hash == node->hashKey))
    459          {
    460            flag=Expr::compare(key, node->key);
    461 //         if ( key == node->key)
    462            if (!flag) 
    463              return (node);
    464 //         if  (key < node->key)
    465            if (flag==-1)
    466              node = node->left;
    467            else
    468              node = node->right;         
    469          }
    470    return (NIL);
    471 }
    472 
    473 
    474 void CopyTree(Table* tab, Table* copy)
    475 {   Table *child;   
    476 
    477     copy->hashKey=tab->hashKey;
    478     copy->key=tab->key;
    479     copy->val=tab->val;
    480     copy->color=tab->color;
    481     if (tab->left==NIL)
    482                 copy->left=NIL;
    483         else
    484         {     
    485                 child=static_cast<Table *> (new(Table));
    486                 child->p=copy;
    487                 copy->left=child;
    488                 CopyTree(tab->left, child);
    489         }
    490     if (tab->right==NIL)
    491                 copy->right=NIL;
    492         else
    493         {     
    494                 child=static_cast<Table *> (new(Table));
    495                 child->p=copy;
    496                 copy->right=child;
    497                 CopyTree(tab->right, child);
    498         }
    499 }
    500 
    501 
    502 bool TableEqual(Table* tab1, Table* tab2)
    503 
    504     if (tab1==NIL)
    505     {
    506        if (tab2==NIL)
    507          return true;
    508        return false;
    509     }
    510     else
    511     {
    512        if (tab2==NIL)
    513           return false;
    514        if ( (tab1->hashKey==tab2->hashKey) &&
    515             (tab1->color==tab2->color) &&
    516             (tab1->key==tab2->key) &&
    517             (tab1->val==tab2->val) &&
    518             (TableEqual(tab1->right, tab2->right)) &&
    519             (TableEqual(tab1->left, tab2->left)) )
    520           return true;
    521         else
    522           return false;
    523     }
    524 }
    525 
    526 
    527 void DeleteTree(Table *node)
    528 {   
    529     if (node->left!=NIL)
    530                 DeleteTree(node->left);
    531         if (node->right!=NIL)
    532                 DeleteTree(node->right);
    533         delete(node);
    534 }
    535  
    536 
    537 /*   return key for Domain  */
    538 void InorderTreeWalk (Table* node, Expr& _res)
    539 { if (node!=NIL)
    540   {  InorderTreeWalk(node->left, _res);
    541      InorderTreeWalk(node->right, _res);
    542      _res = _res + (node->key)();
    543   }
    544 }
    545 
    546 
    547 /* successor for node x at RBtree  */
    548 
    549 Table*  TreeSuccessor(Table *x)
    550 {
    551   Table *y;
    552   if (x->right !=NIL)
    553     return(TreeMinimum(x->right));
    554   y=x->p;
    555   while ((y!=NIL)&&(x==y->right))
    556   {
    557     x=y;
    558     y=y->p;
    559   }
    560   return y;
    561 }
    562 
    563 
    564 
    565 /* search of minimum-key for RBtree, where  x - root */
    566 
    567 Table* TreeMinimum(Table *x)
    568 {
    569   while (x->left!=NIL)
    570     x=x->left;
    571   return x;
    572 }
    573 
    574 /*  hash - zaglushka */
    575 
    576 int Expr_hash(Expr const& key)
    577 {
    578   return key.get_len();
    579 }
    580 
    581 
    58239}
    58340
  • to-imperative/trunk/samples/Makefile

    r917 r922  
    1111  Syntax \
    1212  StdIO  \
    13   String
     13  String \
     14  Table
    1415
    1516samples : override SUBDIRS =
Note: See TracChangeset for help on using the changeset viewer.