Changeset 932


Ignore:
Timestamp:
Jul 1, 2003, 5:34:45 PM (18 years ago)
Author:
sveta
Message:
  • Code formatting.
Location:
to-imperative/trunk/runtime
Files:
3 edited

Legend:

Unmodified
Added
Removed

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

    r922 r932  
    1313/*  Constructor: create NIL-Table and initialize p - root of RB-tree  */
    1414
    15 Table :: Table():
    16   Object ()
     15  Table :: Table() :
     16Object ()
    1717{   
    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 
    35 Table :: ~Table()
    36 {   
    37     DeleteTree(p);
    38 }
    39 
    40 
    41 void Table :: Bind (Expr const& key, Expr const& val)
     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
     34void Table::Bind (Expr const& key, Expr const& val)
    4235{
    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 
     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}
    6051
    6152
    6253void Table :: Unbind(Expr& key)
    6354{
    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         }
     55  Table *newNode;
     56
     57  if ((newNode = IterativeTreeSearch(key))!=NIL)
     58  {
     59    newNode= RBdelete(newNode);
     60    delete(newNode);
     61  }
    7362}
    7463
    7564
    7665int 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         }
     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  }
    8675}
    8776
    … …  
    9079
    9180int 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 
    101 Expr Table :: Domain ()
    102 { 
    103    Expr res = Expr();
    104    InorderTreeWalk(p, res);     /* p - root */
    105    return res;
    106 }
    107 
     81{
     82  Table *newNode;
     83
     84  if ((newNode = IterativeTreeSearch(key))==NIL)
     85    return 0;
     86  else
     87    return 1;
     88}
    10889
    10990/* Table_copy : this - sourceTable, newTable - result */
    110  
     91
    11192void Table :: Table_copy(Table& newTable)
    11293{  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         }
     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  }
    121102}
    122103
    … …  
    127108{   Table *x;
    128109
    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 
     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}
    143123
    144124/* inserting of element newNode in this-Table  */
    … …  
    148128  Table *x, *y;
    149129  int flag;
    150  
     130
    151131  y=NIL;
    152132  x=p;   /*  root */
    … …  
    155135    y=x;
    156136    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             }
     137    { 
     138      flag=Expr::compare(newNode->key, x->key);
     139      //      if ((newNode->key) == (x->key))
     140      if (!flag)
     141        return;
     142      //          if ((newNode->key) < (x->key))
     143      if (flag==-1)
     144      {
     145        x=x->left;
     146        continue;
     147      }
     148      else
     149      {
     150        x=x->right;
     151        continue;
     152      }
    173153    }
    174154    if ((newNode->hashKey)<(x->hashKey))
    … …  
    179159  newNode->p=y;
    180160  if (y==NIL)
    181       p=newNode;   /*  p - root */
     161    p=newNode;   /*  p - root */
    182162  else
    183163    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;
     164    { 
     165      flag=Expr::compare(newNode->key, x->key);
     166      //    if ((newNode->key) < (x->key))
     167      if (flag==-1)
     168      {
     169        y->left=newNode;
     170        return;
     171      }
     172      else
     173      {
     174        y->right=newNode;
     175        return;
     176      }
     177    }   
     178  if ((newNode->hashKey) < (y->hashKey))
     179    y->left = newNode;
     180  else
     181    y->right = newNode;
    202182}
    203183
    … …  
    250230{  Table *y;
    251231
    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 */
     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);
     252        }
     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);
     274        }
     275        x->p->color=BLACK;
     276        x->p->p->color=RED;
     277        LeftRotate(x->p->p);
     278      }
     279    }
     280  }
     281  p->color=BLACK;    /*    p - root */
    302282}
    303283
    … …  
    309289
    310290  if ((z->left==NIL) || (z->right==NIL))
    311           y=z;
    312   else
    313           y=TreeSuccessor(z);
     291    y=z;
     292  else
     293    y=TreeSuccessor(z);
    314294  if (y->left!=NIL)
    315           x=y->left;
    316   else
    317           x=y->right;
     295    x=y->left;
     296  else
     297    x=y->right;
    318298  x->p=y->p;
    319299  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;
     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;
    326306  if (y!=z)
    327307  {
    328           z->hashKey=y->hashKey;
    329           z->val=y->val;
    330 //   = foe Expr
    331           z->key=y->key;
     308    z->hashKey=y->hashKey;
     309    z->val=y->val;
     310    //   = foe Expr
     311    z->key=y->key;
    332312  }
    333313  if (y->color==BLACK)
    334           RBdeleteFixup(x);
     314    RBdeleteFixup(x);
    335315  return y;
    336316}
    … …  
    342322  while ((x!=p) && (x->color==BLACK))     /*   p - root */
    343323  {
    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           }
     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;
     345          RightRotate(w);
     346          w=x->p->right;
     347        }
     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 */
     353      }
     354    }
     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    }
    406386  }
    407387  x->color=BLACK;
    … …  
    413393Table* Table :: IterativeTreeSearch (Expr const& key)
    414394{  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);
     395  int hash, flag;
     396
     397  hash=Expr_hash(key);
     398  node = p;  /* root */
     399  while ((node!=NIL)&&(node->hashKey!=hash))
     400    if (hash < node->hashKey)
     401      node=node->left;
     402    else
     403      node=node->right;
     404  //  must be CompareExpr     
     405  while ((node!=NIL) && (hash == node->hashKey))
     406  {
     407    flag=Expr::compare(key, node->key);
     408    //     if ( key == node->key)
     409    if (!flag) 
     410      return (node);
     411    //     if  (key < node->key)
     412    if (flag==-1)
     413      node = node->left;
     414    else
     415      node = node->right;   
     416  }
     417  return (NIL);
    438418}
    439419
    … …  
    442422{   Table *child;   
    443423
    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         }
     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  }
    466446}
    467447
    … …  
    469449bool TableEqual(Table* tab1, Table* tab2)
    470450{ 
    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     }
     451  if (tab1==NIL)
     452  {
     453    if (tab2==NIL)
     454      return true;
     455    return false;
     456  }
     457  else
     458  {
     459    if (tab2==NIL)
     460      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)) )
     467      return true;
     468    else
     469      return false;
     470  }
    491471}
    492472
    … …  
    494474void DeleteTree(Table *node)
    495475{   
    496     if (node->left!=NIL)
    497                 DeleteTree(node->left);
    498         if (node->right!=NIL)
    499                 DeleteTree(node->right);
    500         delete(node);
    501 }
    502  
     476  if (node->left!=NIL)
     477    DeleteTree(node->left);
     478  if (node->right!=NIL)
     479    DeleteTree(node->right);
     480  delete(node);
     481}
     482
    503483
    504484/*   return key for Domain  */
    505 void InorderTreeWalk (Table* node, Expr& _res)
     485  void InorderTreeWalk (Table* node, Expr& _res)
    506486{ if (node!=NIL)
    507487  {  InorderTreeWalk(node->left, _res);
    508      InorderTreeWalk(node->right, _res);
    509      _res = _res + (node->key)();
     488    InorderTreeWalk(node->right, _res);
     489    _res = _res + (node->key)();
    510490  }
    511491}

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

    r922 r932  
    4242  Table* RBdelete(Table *);
    4343
    44    public :
     44  public :
    4545
    46    Table ();
    47   ~Table();
    48    void Unbind(Expr& key);
    49    int Lookup (Expr const& key, Expr& val);
    50    int In_table(Expr const& key);
    51   Expr Domain ();
    52    void Table_copy(Table&);
    53    void Replace_Table (Table const&);
    54    void Bind(Expr const& key, Expr const& val);
     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);
    5555
    56    inline unsigned get_type () const;
    57    inline uint32_t hash () const;
    58    inline bool operator==(Object const& _obj) const;
     56  inline unsigned get_type () const;
     57  inline uint32_t hash () const;
     58  inline bool operator==(Object const& _obj) const;
    5959
    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*);
     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*);
    6666};
    6767

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

    r922 r932  
    2727inline bool Table::operator == (Object const& _table) const
    2828{
    29      try {
    30          Table const&  _t=static_cast <Table const&>(_table); 
    31           return TableEqual(p, _t.p);
    32      }
    33      catch (std::bad_cast&)
    34      {
    35        return false;
    36      }
     29  try {
     30    Table const&  _t=static_cast <Table const&>(_table); 
     31    return TableEqual(p, _t.p);
     32  }
     33  catch (std::bad_cast&)
     34  {
     35    return false;
     36  }
    3737}
     38
     39
     40/* Destructor: deleting of this-RBtree */
     41
     42inline Table :: ~Table()
     43{   
     44  DeleteTree(p);
     45}
     46
     47
     48inline Expr Table :: Domain ()
     49{ 
     50  Expr res = Expr();
     51  InorderTreeWalk(p, res);     /* p - root */
     52  return res;
     53}
     54
    3855
    3956}
Note: See TracChangeset for help on using the changeset viewer.