BalancedTree< Obj > Class Template Reference
Class BalancedTree (container class intended to keep an ordered sequence of objects, supports fast
ninsertions).
More...
#include <BalancedTree.h>
Public Member Functions | |
| BalancedTree () | |
| Default constructor. | |
| template<class ConstObjIter> | |
| BalancedTree (const ConstObjIter &B, const ConstObjIter &E) | |
| Constructor. Creates a tree for a sequence in range [B,E). | |
| ~BalancedTree () | |
| Destructor recursively frees memory. | |
| int | size () const |
| template<class ConstObjIter> | |
| void | insert (int pos, const ConstObjIter &B, const ConstObjIter &E) |
| Insert a sequence of objects bounded by [B,E) into a position pos. | |
| void | insert (int pos, const Obj &obj) |
| Insert an object obj into position pos. | |
| list< Obj > | getList () const |
| Get an ordered list of objects stored in a balanced tree. | |
Private Member Functions | |
| void | getList (BTNode *node, list< Obj > &result) const |
| Get an ordered list of objects in a subtree with a root node. | |
| void | insert (BTNode *parent, BTNode *node, int offset, const Obj &obj) |
| Insert an onject obj into a subtree with a root node at the offset position offset. | |
| void | rotateLeft (BTNode *parent, BTNode *child) |
| Left rotation. | |
| void | rotateRight (BTNode *parent, BTNode *child) |
| Right rotation. | |
Private Attributes | |
| BTNode * | theRoot |
Classes | |
| struct | BTNode |
Detailed Description
template<class Obj>
class BalancedTree< Obj >
Class BalancedTree (container class intended to keep an ordered sequence of objects, supports fast ninsertions).
Typical usage for this class is generation of trivial elements of groups, where a lot of insertions of relators is performed, i.e., start from a trivial word and cosequently insert relators (with their inverses and cyclic permutations). The result will be a word representing the identity of the group. The main feature of this class - fast asymptotic insertions which cannot be achieved using standard vector<...> and list<...>.
Definition at line 34 of file BalancedTree.h.
Constructor & Destructor Documentation
| BalancedTree< Obj >::BalancedTree | ( | ) | [inline] |
| BalancedTree< Obj >::BalancedTree | ( | const ConstObjIter & | B, | |
| const ConstObjIter & | E | |||
| ) | [inline] |
Constructor. Creates a tree for a sequence in range [B,E).
Definition at line 68 of file BalancedTree.h.
References BalancedTree< Obj >::insert().
| BalancedTree< Obj >::~BalancedTree | ( | ) | [inline] |
Destructor recursively frees memory.
Definition at line 72 of file BalancedTree.h.
References BalancedTree< Obj >::theRoot.
Member Function Documentation
| int BalancedTree< Obj >::size | ( | ) | const [inline] |
Definition at line 83 of file BalancedTree.h.
References BalancedTree< Obj >::theRoot, BalancedTree< Obj >::BTNode::weight1, and BalancedTree< Obj >::BTNode::weight2.
| void BalancedTree< Obj >::insert | ( | int | pos, | |
| const ConstObjIter & | B, | |||
| const ConstObjIter & | E | |||
| ) | [inline] |
Insert a sequence of objects bounded by [B,E) into a position pos.
Definition at line 98 of file BalancedTree.h.
Referenced by BalancedTree< Obj >::BalancedTree(), and BalancedTree< Obj >::insert().
| void BalancedTree< Obj >::insert | ( | int | pos, | |
| const Obj & | obj | |||
| ) | [inline] |
Insert an object obj into position pos.
Definition at line 105 of file BalancedTree.h.
References BalancedTree< Obj >::insert(), and BalancedTree< Obj >::theRoot.
| list< Obj > BalancedTree< Obj >::getList | ( | ) | const [inline] |
Get an ordered list of objects stored in a balanced tree.
Definition at line 113 of file BalancedTree.h.
References BalancedTree< Obj >::theRoot.
Referenced by BalancedTree< Obj >::getList().
| void BalancedTree< Obj >::getList | ( | BTNode * | node, | |
| list< Obj > & | result | |||
| ) | const [inline, private] |
Get an ordered list of objects in a subtree with a root node.
Definition at line 128 of file BalancedTree.h.
References BalancedTree< Obj >::getList(), BalancedTree< Obj >::BTNode::subtree1, BalancedTree< Obj >::BTNode::subtree2, and BalancedTree< Obj >::BTNode::theObject.
| void BalancedTree< Obj >::insert | ( | BTNode * | parent, | |
| BTNode * | node, | |||
| int | offset, | |||
| const Obj & | obj | |||
| ) | [inline, private] |
Insert an onject obj into a subtree with a root node at the offset position offset.
Definition at line 136 of file BalancedTree.h.
References BalancedTree< Obj >::BTNode::height1, BalancedTree< Obj >::BTNode::height2, BalancedTree< Obj >::insert(), BalancedTree< Obj >::rotateLeft(), BalancedTree< Obj >::rotateRight(), BalancedTree< Obj >::BTNode::subtree1, BalancedTree< Obj >::BTNode::subtree2, BalancedTree< Obj >::BTNode::weight1, and BalancedTree< Obj >::BTNode::weight2.
| void BalancedTree< Obj >::rotateLeft | ( | BTNode * | parent, | |
| BTNode * | child | |||
| ) | [inline, private] |
Left rotation.
Definition at line 168 of file BalancedTree.h.
References BalancedTree< Obj >::BTNode::height1, BalancedTree< Obj >::BTNode::height2, BalancedTree< Obj >::BTNode::subtree1, BalancedTree< Obj >::BTNode::subtree2, BalancedTree< Obj >::theRoot, BalancedTree< Obj >::BTNode::weight1, and BalancedTree< Obj >::BTNode::weight2.
Referenced by BalancedTree< Obj >::insert().
| void BalancedTree< Obj >::rotateRight | ( | BTNode * | parent, | |
| BTNode * | child | |||
| ) | [inline, private] |
Right rotation.
Definition at line 217 of file BalancedTree.h.
References BalancedTree< Obj >::BTNode::height1, BalancedTree< Obj >::BTNode::height2, BalancedTree< Obj >::BTNode::subtree1, BalancedTree< Obj >::BTNode::subtree2, BalancedTree< Obj >::theRoot, BalancedTree< Obj >::BTNode::weight1, and BalancedTree< Obj >::BTNode::weight2.
Referenced by BalancedTree< Obj >::insert().
Member Data Documentation
BTNode* BalancedTree< Obj >::theRoot [private] |
Definition at line 274 of file BalancedTree.h.
Referenced by BalancedTree< Obj >::getList(), BalancedTree< Obj >::insert(), BalancedTree< Obj >::rotateLeft(), BalancedTree< Obj >::rotateRight(), BalancedTree< Obj >::size(), and BalancedTree< Obj >::~BalancedTree().
The documentation for this class was generated from the following file:
- general/include/BalancedTree.h
