source: to-imperative/trunk/c++/runtime/rf_table.cc @ 2752

Last change on this file since 2752 was 2752, checked in by orlov, 13 years ago
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.5 KB
Line 
1#include "rf_table.ih"
2#include <new>
3
4namespace rftype
5{
6
7using namespace rfrt; 
8
9TableNode* TableNode::nil = NULL;
10 
11size_t Table::count = 0;
12
13//
14// inserting of element newNode in this-Table
15void Table::insert_node (TableNode* _node)
16{
17  TableNode* x;
18  TableNode* y;
19  int flag;
20  y = TableNode::nil;
21  x = root;
22  while (x != TableNode::nil) {
23    y=x;
24    if ((_node->hash_key) == (x->hash_key)) {
25      flag = Expr::compare(_node->key, x->key);
26      if (!flag) {                      //   case 0 :  ==
27        return;
28      } else 
29        if (flag < 0) {            //   case < 0 : <
30          x = x->left;
31        } else {
32          x = x->right;
33          }
34    } else 
35      if ((_node->hash_key) < (x->hash_key)) {
36        x = x->left;
37      } else {
38        x = x->right;
39      }
40  }
41  _node->p = y;
42  if (y == TableNode::nil) {
43    root = _node;
44  } else {
45    if ((_node->hash_key) == (y->hash_key)) {
46      if (flag < 0) {
47        y->left = _node;
48      } else {
49        y->right = _node;
50      }
51    } else {
52      if ((_node->hash_key) < (y->hash_key)) {
53        y->left = _node;
54      } else {
55        y->right = _node;
56      }
57    }
58  }
59}
60
61
62void Table::left_rotate_RB (TableNode* _x)
63{ 
64  TableNode* y;
65  // _x->right != NIL (definition)
66  y = _x->right;
67  _x->right = y->left;
68  if (y->left != TableNode::nil) {
69    y->left->p = _x;
70   } 
71  y->p = _x->p;
72  if (_x->p == TableNode::nil) {
73    root = y;   
74  } else {
75    if (_x == _x->p->left) {
76      _x->p->left = y;
77    } else {
78      _x->p->right = y;
79    }
80  }
81  y->left = _x;
82  if (_x != TableNode::nil) { 
83    _x->p = y;
84  }
85}
86
87
88void Table::right_rotate_RB (TableNode* _x)
89{ 
90  TableNode* y;
91  // _x->left !=NIL (def)
92  y = _x->left;
93  _x->left = y->right;
94  if (y->right != TableNode::nil) {
95     y->right->p = _x;
96  } 
97  y->p = _x->p;
98  if (_x->p == TableNode::nil) {
99    root = y; 
100  } else {
101    if (_x == _x->p->right) {
102      _x->p->right = y; 
103    } else {
104      _x->p->left = y;
105    }
106  }
107  y->right = _x;
108  if (_x != TableNode::nil) { 
109    _x->p = y;
110  }
111}
112
113
114void Table::insert_node_RB (TableNode* _x)
115{ 
116  TableNode *y;
117  insert_node(_x);
118  _x->color = TableNode::RED;
119  while ((_x != root) && (_x->p->color == TableNode::RED)) {   
120    if (_x->p == _x->p->p->left) {
121      y = _x->p->p->right;
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;
126        _x = _x->p->p;
127      } else {
128        if (_x == _x->p->right) {
129          _x = _x->p;
130          left_rotate_RB(_x);
131        }
132        _x->p->color = TableNode::BLACK;
133        _x->p->p->color =TableNode::RED;
134        right_rotate_RB(_x->p->p);
135      }
136    } else {
137      y=_x->p->p->left;
138      if ((y != TableNode::nil) && (y->color == TableNode::RED)) {
139        _x->p->color = TableNode::BLACK;
140        y->color = TableNode::BLACK;
141        _x->p->p->color = TableNode::RED;
142        _x = _x->p->p;
143      } else {
144        if (_x == _x->p->left) {
145          _x = _x->p;
146          right_rotate_RB(_x);
147        }
148        _x->p->color = TableNode::BLACK;
149        _x->p->p->color = TableNode::RED;
150        left_rotate_RB(_x->p->p);
151      }
152    }
153  }
154  root->color=TableNode::BLACK;   
155}
156
157
158TableNode* Table::delete_node_RB (TableNode *_z)
159{ 
160  TableNode* x;
161  TableNode* y;
162  if ((_z->left == TableNode::nil) || (_z->right == TableNode::nil)) {
163    y = _z;
164  } else {
165    y = _z->right;
166    if (y != TableNode::nil) {
167      while (y->left != TableNode::nil) {
168         y = y->left;
169      }
170    } else {
171      x=_z;
172      y = x->p;
173      while ((y != TableNode::nil) && (x == y->right)) {
174        x = y;
175        y = y->p;
176      }
177    } 
178  } 
179  if (y->left != TableNode::nil) {
180    x = y->left;
181  } else {
182    x = y->right;
183  }
184  x->p = y->p;
185  if (y->p == TableNode::nil) {
186    root = x;     
187  } else {
188    if (y == y->p->left) {
189      y->p->left = x;
190    } else {
191      y->p->right = x;
192    }
193  }
194  if (y != _z) {
195    _z->hash_key = y->hash_key;
196    _z->val = y->val;
197    _z->key = y->key;
198  }
199  if (y->color == TableNode::BLACK) {
200    delete_fixup_RB(x);
201  }
202  return y;
203}
204
205void Table::delete_fixup_RB (TableNode* _x)
206{ 
207  TableNode* w;
208  while ((_x != root) && (_x->color == TableNode::BLACK)) {
209    if (_x == _x->p->left) {
210      w = _x->p->right;
211      if (w->color == TableNode::RED) {
212        w->color = TableNode::BLACK;
213        _x->p->color = TableNode::RED;
214        left_rotate_RB(_x->p);
215        w = _x->p->right;
216      }
217      if ((w->left->color == TableNode::BLACK) && (w->right->color == TableNode::BLACK)) {
218        w->color = TableNode::RED;
219        _x = _x->p;
220      } else {
221        if (w->right->color == TableNode::BLACK) {
222          w->left->color = TableNode::BLACK;
223          w->color = TableNode::RED;
224          right_rotate_RB(w);
225          w = _x->p->right;
226        }
227        w->color = _x->p->color;
228        _x->p->color = TableNode::BLACK;
229        w->right->color = TableNode::BLACK;
230        left_rotate_RB(_x->p);
231        _x=root; 
232      }
233    } else {
234      w = _x->p->left;
235      if (w->color == TableNode::RED) {
236        w->color = TableNode::BLACK;
237        _x->p->color = TableNode::RED;
238        right_rotate_RB(_x->p);
239        w = _x->p->left;
240      }
241      if ((w->right->color == TableNode::BLACK) && (w->left->color == TableNode::BLACK)) {
242        w->color = TableNode::RED;
243        _x = _x->p;
244      } else {
245        if (w->left->color == TableNode::BLACK) {
246          w->right->color = TableNode::BLACK;
247          w->color = TableNode::RED;
248          left_rotate_RB(w);
249          w = _x->p->left;
250        }
251        w->color = _x->p->color;
252        _x->p->color = TableNode::BLACK;
253        w->left->color = TableNode::BLACK;
254        right_rotate_RB(_x->p);
255        _x=root; 
256      }
257    }
258  }
259  _x->color=TableNode::BLACK;
260}
261
262
263TableNode* Table::search_node (Expr const& _key) const
264{ 
265  TableNode* node;
266  int hash, flag;
267
268  hash = expr_hash(_key);
269  node = root; 
270  while (node != TableNode::nil) {
271    if (node->hash_key != hash) {
272      if (hash < node->hash_key) {
273        node = node->left;
274      } else {
275        node = node->right;
276      }
277    } else {
278      flag = Expr::compare(_key, node->key);
279      if (!flag) {            //   case 0 : ==
280        return (node);
281      }
282      if (flag < 0) {         //   case < 0 : <
283        node = node->left;
284      } else {
285        node = node->right;
286      }   
287    }
288  }
289  return TableNode::nil;
290}
291
292
293void copy_tree (TableNode const&  _tab, TableNode& _copy)
294{   
295  TableNode* child;   
296  _copy.hash_key = _tab.hash_key;
297  _copy.key = _tab.key;
298  _copy.val = _tab.val;
299  _copy.color = _tab.color;
300  if (_tab.left == TableNode::nil) {
301    _copy.left = TableNode::nil;
302  } else {     
303    child = new TableNode;
304    child->p = &_copy;
305    _copy.left = child;
306    copy_tree(*(_tab.left), *child);
307  }
308  if (_tab.right == TableNode::nil) {
309    _copy.right = TableNode::nil;
310  } else {     
311    child = new TableNode;
312    child->p = &_copy;
313    _copy.right = child;
314    copy_tree( *(_tab.right), *child);
315  }
316}
317
318bool table_equal(TableNode const& _tab1, TableNode const& _tab2)
319{ 
320  if ((&_tab1) == TableNode::nil) {
321    if ((&_tab2) == TableNode::nil) {
322      return true;
323    }
324    return false;
325  }
326  else {
327    if ((&_tab2) == TableNode::nil) {
328      return false;
329    }
330    if ( (_tab1.hash_key == _tab2.hash_key) &&
331      (_tab1.color == _tab2.color) &&
332      (_tab1.key == _tab2.key) &&
333      (_tab1.val == _tab2.val) &&
334      (table_equal(*_tab1.right, *_tab2.right)) &&
335      (table_equal(*_tab1.left, *_tab2.left)) ) {
336      return true;
337    } else { 
338      return false;
339    } 
340  }
341}
342
343
344void delete_tree (TableNode* _node)
345{   
346  if (_node->left != TableNode::nil) {
347    delete_tree(_node->left);
348  }
349  if (_node->right != TableNode::nil) {
350    delete_tree(_node->right);
351  }
352  delete(_node);
353}
354
355
356void list_node (TableNode const& _node, Expr& _res)
357{ 
358  if (_node.left != TableNode::nil) {   
359    list_node( * _node.left, _res);
360  }
361  if (_node.right != TableNode::nil) {
362    list_node( * _node.right, _res);
363  }
364  _res = _res + (_node.key)();
365}
366
367void list_values (TableNode const& _node, Expr& _res)
368{ 
369  if (_node.left != TableNode::nil) {   
370    list_values( * _node.left, _res);
371  }
372  if (_node.right != TableNode::nil) {
373    list_values( * _node.right, _res);
374  }
375  _res = _res + _node.val();
376}
377
378void list_entries (TableNode const& _node, Expr& _res)
379{ 
380  if (_node.left != TableNode::nil) {   
381    list_entries( * _node.left, _res);
382  }
383  if (_node.right != TableNode::nil) {
384    list_entries( * _node.right, _res);
385  }
386  _res = _res + (_node.key() + _node.val())();
387}
388
389
390}
Note: See TracBrowser for help on using the repository browser.