source: to-imperative/trunk/runtime/rf_table.hh @ 1378

Last change on this file since 1378 was 1378, checked in by orlov, 17 years ago
  • Result of merge from parenth_term branch.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 1.6 KB
Line 
1#ifndef __rf_table_hh__
2#define __rf_table_hh__
3
4#include "rf_object.hh"
5#include "rf_expr.hh"
6#include "rf_types.hh"
7
8namespace rftype
9{
10
11using namespace rfrt; 
12 
13class TableNode;
14
15class Table :
16    public Object
17{
18  private :
19 
20  static ObjectRegister reg;
21  TableNode* root;    // root of RB-tree
22  static size_t count; 
23
24  void insert_node (TableNode*);
25  void insert_node_RB (TableNode*);
26  void left_rotate_RB (TableNode*);
27  void right_rotate_RB (TableNode*);
28  TableNode* search_node (Expr const&);
29  void delete_fixup_RB (TableNode*);
30  TableNode* delete_node_RB (TableNode*);
31
32  public :
33
34  inline Table ();
35  inline Table (Table const&);
36  inline ~Table();
37  inline void unbind (Expr& _key);
38  inline bool lookup (Expr const& _key, Expr& _val);
39  inline bool in_table (Expr const& _key);
40  inline Expr domain ();
41  inline void replace_table (Table const& _tab);
42  inline void bind (Expr const& _key, Expr const& _val);
43  inline unsigned get_type () const;
44  inline uint32_t hash () const;
45  inline bool operator == (Object const&) const; 
46  inline pxx::WString to_string () const;
47};
48 
49class TableNode 
50{
51  friend class Table;
52
53  private: 
54       
55  int hash_key;
56  enum {BLACK, RED} color;
57  Expr key;       // key-expression
58  Expr val;       // value-expression
59  TableNode* left;    // left child
60  TableNode* right;   // right child
61  TableNode* p;       // parent   
62
63  static TableNode* nil;   
64
65  friend void list_node (TableNode const&, Expr&) ;
66  friend void copy_tree (TableNode const&, TableNode&) ;
67  friend void delete_tree (TableNode*) ;
68  friend bool table_equal (TableNode const&, TableNode const&) ;
69};
70
71}
72
73
74#endif      //__rf_table_hh__
Note: See TracBrowser for help on using the repository browser.