21 #ifndef ELM_STREE_TREE_H_
22 #define ELM_STREE_TREE_H_
24 #include <elm/compare.h>
25 #include <elm/genstruct/AVLTree.h>
27 namespace elm {
namespace stree {
30 template <
class K,
class T,
class C = Comparator<K> >
32 static const int null = -1;
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; }
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; }
55 ~Tree(
void) {
delete [] nodes; }
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; }
64 {
return C::compare(key, nodes[root].lowerBound()) >= 0 && C::compare(key, nodes[root].upperBound()) <= 0; }
66 # ifdef ELM_STREE_DEBUG
69 for(
int j = 0; j < t; j++)
out <<
"| ";
76 dump(
out, nodes[i].
left(), t + 1);
83 T *
find(
const K& key)
const {
84 ASSERTP(nodes && root >= 0,
"uninitialized stree");
88 while(!nodes[i].isLeaf()) {
89 if(C::compare(key, nodes[nodes[i].
right()].lowerBound()) < 0)
94 return &nodes[i].
data;
Tree(void)
Definition: Tree.h:51
const char endl
Definition: Output.h:221
K ub
Definition: Tree.h:46
K lb
Definition: Tree.h:46
node_t(struct node_t s[], int _ll, int _rl)
Definition: Tree.h:37
IntFormat right(IntFormat fmt)
Definition: Output.h:250
const K & upperBound(void) const
Definition: Tree.h:45
int ll
Definition: Tree.h:47
~Tree(void)
Definition: Tree.h:55
node_t(void)
Definition: Tree.h:36
node_t(const K &_lb, const K &_ub)
Definition: Tree.h:39
Tree(int _root, node_t *_nodes)
Definition: Tree.h:52
sys::SystemOutStream & out
Definition: system_SystemIO.cpp:101
int rl
Definition: Tree.h:47
void set(int _root, node_t *_nodes)
Definition: Tree.h:53
int right(void) const
Definition: Tree.h:43
bool contains(const K &key) const
Definition: Tree.h:63
IntFormat left(IntFormat fmt)
Definition: Output.h:249
struct elm::stree::Tree::node_t node_t
int left(void) const
Definition: Tree.h:42
T * find(const K &key) const
Definition: Tree.h:83
const K & lowerBound(void) const
Definition: Tree.h:44
T data
Definition: Tree.h:48
bool isLeaf(void) const
Definition: Tree.h:41