Elm  2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
Tree.h
1 /*
2  * avl::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_AVL_TREE_H
22 #define ELM_AVL_TREE_H
23 
24 #include <elm/inhstruct/BinTree.h>
25 
26 namespace elm { namespace avl {
27 
28 // AVLTree class
29 class Tree: public inhstruct::BinTree {
30 public:
31  virtual ~Tree(void);
32 
33  // AVLNode class
34  class Node: public BinTree::Node {
35  friend class Tree;
36  int h;
37  public:
38  inline Node *_left(void) const { return (Node *)left(); };
39  inline Node *_right(void) const { return (Node *)right(); };
40  #ifdef ELM_DEBUG_AVLTREE
41  virtual void dump(void) = 0;
42  #endif
43  };
44 
45 private:
46  Node *insert(Node *cur, Node *node);
47  Node *remove(Node *cur, Node *node);
48  Node *removeGreatest(Node *root, Node *&res);
49  Node *removeLeast(Node *root, Node *&res);
50  Node *rotateSingleLeft(Node *node);
51  Node *rotateDoubleLeft(Node *node);
52  Node *rotateSingleRight(Node *node);
53  Node *rotateDoubleRight(Node *node);
54  Node *remap(Node *left, Node *right);
55  Node *balanceLeft(Node *cur, Node*& left);
56  Node *balanceRight(Node *cur, Node*& left);
57  void clean(Node *node);
58  inline Node *_root(void) const { return (Node *)root(); };
59  inline int height(Node *node) const { return node ? node->h : 0; };
60 
61  inline void computeHeight(Node *node) {
62  int hleft = height(node->_left()), hright = height(node->_right());
63  if(hleft > hright)
64  node->h = hleft + 1;
65  else
66  node->h = hright + 1;
67  }
68 
69 protected:
70  virtual int compare(Node *node1, Node *node2) = 0;
71  virtual void free(Node *node);
72 
73 public:
74 
75  // Accessors
76  inline bool isEmpty(void) { return BinTree::isEmpty(); }
77  inline int count(void) { return BinTree::count(); }
78  Node *get(Node *node);
79  inline bool contains(Node *node) { return get(node) != 0; }
80  inline void visit(Visitor *visitor) { return BinTree::visit(visitor); }
81  inline void search(Visitor *visitor) { BinTree::search(visitor); }
82 
83  // Modifiers
84  void insert(Node *node);
85  void remove(Node *node);
86  inline void clean(void) { clean(_root()); }
87 
88  // Debug
89  #ifdef ELM_DEBUG_AVLTREE
90  void dump(Node *node = 0, int level = 0);
91  #endif
92 };
93 
94 } } // elm::avl
95 
96 #endif // ELM_AVL_TREE_H
elm::avl::dump
static void dump(Tree::Node *node, int tab=0)
Definition: avl_Tree.cpp:64
elm::inhstruct::BinTree
Definition: BinTree.h:13
elm::avl::Tree::count
int count(void)
Definition: Tree.h:77
elm::avl::Tree::~Tree
virtual ~Tree(void)
elm::avl::Tree::get
Node * get(Node *node)
Definition: avl_Tree.cpp:123
elm::inhstruct::BinTree::root
Node * root(void) const
Definition: BinTree.h:90
elm::avl::Tree::visit
void visit(Visitor *visitor)
Definition: Tree.h:80
elm::avl::Tree::free
virtual void free(Node *node)
Definition: avl_Tree.cpp:363
elm::avl::Tree::Node::_right
Node * _right(void) const
Definition: Tree.h:39
elm::avl::Tree
Definition: Tree.h:29
elm::avl::Tree::Node::_left
Node * _left(void) const
Definition: Tree.h:38
elm::avl::Tree::clean
void clean(void)
Definition: Tree.h:86
elm
Definition: adapter.h:26
elm::avl::Tree::search
void search(Visitor *visitor)
Definition: Tree.h:81
elm::avl::Tree::isEmpty
bool isEmpty(void)
Definition: Tree.h:76
elm::avl::Tree::compare
virtual int compare(Node *node1, Node *node2)=0
elm::count
int count(const C &c, const P &p)
Definition: util.h:65
elm::avl::Tree::Node
Definition: Tree.h:34
elm::avl::Tree::contains
bool contains(Node *node)
Definition: Tree.h:79
elm::inhstruct::BinTree::Visitor
Definition: BinTree.h:28
elm::io::right
IntFormat right(IntFormat fmt)
Definition: Output.h:264
elm::io::left
IntFormat left(IntFormat fmt)
Definition: Output.h:263