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

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