source: to-imperative/trunk/c++/runtime/rf_table.hh @ 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: 1.9 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  size_t size;
25
26  void insert_node (TableNode*);
27  void insert_node_RB (TableNode*);
28  void left_rotate_RB (TableNode*);
29  void right_rotate_RB (TableNode*);
30  TableNode* search_node (Expr const&) const;
31  void delete_fixup_RB (TableNode*);
32  TableNode* delete_node_RB (TableNode*);
33
34  public :
35
36  inline Table ();
37  inline Table (Table const&);
38  inline ~Table();
39  inline void unbind (Expr& _key);
40  inline bool lookup (Expr const& _key, Expr& _val) const;
41  inline bool in_table (Expr const& _key) const;
42  inline Expr domain () const;
43  inline Expr values () const;
44  inline Expr entries () const;
45  inline size_t get_size () const;
46  inline void replace_table (Table const& _tab);
47  inline void clear ();
48  inline void bind (Expr const& _key, Expr const& _val);
49  inline unsigned get_type () const;
50  inline uint32_t hash () const;
51  inline bool operator == (Object const&) const; 
52  inline pxx::WString to_string () const;
53};
54 
55class TableNode 
56{
57  friend class Table;
58
59  private: 
60       
61  int hash_key;
62  enum {BLACK, RED} color;
63  Expr key;       // key-expression
64  Expr val;       // value-expression
65  TableNode* left;    // left child
66  TableNode* right;   // right child
67  TableNode* p;       // parent   
68
69  static TableNode* nil;   
70
71  friend void list_node (TableNode const&, Expr&) ;
72  friend void list_values (TableNode const&, Expr&) ;
73  friend void list_entries (TableNode const&, Expr&) ;
74  friend void copy_tree (TableNode const&, TableNode&) ;
75  friend void delete_tree (TableNode*) ;
76  friend bool table_equal (TableNode const&, TableNode const&) ;
77};
78
79}
80
81
82#endif      //__rf_table_hh__
Note: See TracBrowser for help on using the repository browser.