Elm  2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
Tree.h
1 /*
2  * stree::Tree class interface
3  *
4  * This file is part of OTAWA
5  * Copyright (c) 2013, IRIT UPS.
6  *
7  * OTAWA is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * OTAWA is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with OTAWA; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 #ifndef ELM_STREE_TREE_H_
22 #define ELM_STREE_TREE_H_
23 
24 #include <elm/assert.h>
25 #include <elm/compare.h>
26 
27 namespace elm { namespace stree {
28 
29 // Tree class
30 template <class K, class T, class C = Comparator<K> >
31 class Tree {
32  static const int null = -1;
33 
34 public:
35  typedef struct node_t {
36  inline node_t(void): ll(0), rl(0) { }
37  inline node_t(struct node_t s[], int _ll, int _rl)
38  : lb(s[_ll].lb), ub(s[_rl].ub), ll(_ll), rl(_rl) { }
39  inline node_t(const K& _lb, const K& _ub)
40  : lb(_lb), ub(_ub), ll(null), rl(null) { }
41  inline bool isLeaf(void) const { return ll == null; }
42  inline int left(void) const { return ll; }
43  inline int right(void) const { return rl; }
44  inline const K& lowerBound(void) const { return lb; }
45  inline const K& upperBound(void) const { return ub; }
46  K lb, ub;
47  int ll, rl;
48  T data;
49  } node_t;
50 
51  inline Tree(void): root(-1), nodes(0) { }
52  inline Tree(int _root, node_t *_nodes): root(_root), nodes(_nodes) { }
53  inline void set(int _root, node_t *_nodes) { root = _root; nodes = _nodes; }
54 
55  ~Tree(void) { delete [] nodes; }
56 
57  inline const T& get(const K& key, const T& def) const
58  { T *val = find(key); if(!val) return def; else return *val; }
59  inline const T& get(const K& key) const
60  { T *val = find(key); ASSERTP(val, "out of tree"); return *val; }
61  inline T& get(const K& key)
62  { T *val = find(key); ASSERTP(val, "out of tree"); return *val; }
63  inline bool contains(const K& key) const
64  { return C::compare(key, nodes[root].lowerBound()) >= 0 && C::compare(key, nodes[root].upperBound()) <= 0; }
65 
66 # ifdef ELM_STREE_DEBUG
67  void dump(io::Output& out = cout, int i = -1, int t = 0) {
68  if(i < 0) i = root;
69  for(int j = 0; j < t; j++) out << "| ";
70  out << "|- ";
71  out << nodes[i].lowerBound() << " - " << nodes[i].upperBound();
72  if(nodes[i].isLeaf())
73  out << " -> " << nodes[i].data << io::endl;
74  else {
75  out << io::endl;
76  dump(out, nodes[i].left(), t + 1);
77  dump(out, nodes[i].right(), t + 1);
78  }
79  }
80 # endif
81 
82 protected:
83  T *find(const K& key) const {
84  ASSERTP(nodes && root >= 0, "uninitialized stree");
85  int i = root;
86  if(!contains(key))
87  return 0;
88  while(!nodes[i].isLeaf()) {
89  if(C::compare(key, nodes[nodes[i].right()].lowerBound()) < 0)
90  i = nodes[i].left();
91  else
92  i = nodes[i].right();
93  }
94  return &nodes[i].data;
95  }
96 
97 private:
98  int root;
99  node_t *nodes;
100 };
101 
102 } } // elm::stree
103 
104 #endif /* ELM_STREE_TREE_H_ */
elm::t::out
typename type_info< T >::out_t out
Definition: type_info.h:284
elm::stree::Tree::node_t::node_t
node_t(const K &_lb, const K &_ub)
Definition: Tree.h:39
elm::stree::Tree::Tree
Tree(void)
Definition: Tree.h:51
elm::stree::Tree::node_t::upperBound
const K & upperBound(void) const
Definition: Tree.h:45
elm::stree::Tree::node_t::lb
K lb
Definition: Tree.h:46
elm::stree::Tree::get
const T & get(const K &key) const
Definition: Tree.h:59
elm::stree::Tree::node_t::lowerBound
const K & lowerBound(void) const
Definition: Tree.h:44
elm::stree::Tree::set
void set(int _root, node_t *_nodes)
Definition: Tree.h:53
elm::stree::Tree::node_t::left
int left(void) const
Definition: Tree.h:42
elm::stree::Tree::contains
bool contains(const K &key) const
Definition: Tree.h:63
elm::cout
io::Output cout
elm::stree::Tree::Tree
Tree(int _root, node_t *_nodes)
Definition: Tree.h:52
elm::stree::Tree::node_t::rl
int rl
Definition: Tree.h:47
elm
Definition: adapter.h:26
elm::stree::Tree::get
const T & get(const K &key, const T &def) const
Definition: Tree.h:57
elm::null
T * null(void)
Definition: types.h:39
elm::io::endl
const EOL endl
Definition: io_Output.cpp:880
elm::stree::Tree
Definition: Tree.h:31
elm::stree::Tree::get
T & get(const K &key)
Definition: Tree.h:61
elm::stree::Tree::node_t::ub
K ub
Definition: Tree.h:46
elm::stree::Tree::node_t
struct elm::stree::Tree::node_t node_t
elm::stree::Tree::node_t::node_t
node_t(void)
Definition: Tree.h:36
elm::stree::Tree::node_t::ll
int ll
Definition: Tree.h:47
elm::stree::Tree::node_t::node_t
node_t(struct node_t s[], int _ll, int _rl)
Definition: Tree.h:37
elm::stree::Tree::find
T * find(const K &key) const
Definition: Tree.h:83
elm::stree::Tree::node_t
Definition: Tree.h:35
elm::io::right
IntFormat right(IntFormat fmt)
Definition: Output.h:264
elm::io::left
IntFormat left(IntFormat fmt)
Definition: Output.h:263
elm::stree::Tree::node_t::data
T data
Definition: Tree.h:48
elm::stree::Tree::~Tree
~Tree(void)
Definition: Tree.h:55
elm::io::Output
Definition: Output.h:179
elm::stree::Tree::node_t::right
int right(void) const
Definition: Tree.h:43
elm::stree::Tree::node_t::isLeaf
bool isLeaf(void) const
Definition: Tree.h:41