source: to-imperative/trunk/runtime/rf_table.cc @ 1221

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