BalancedTree< Obj > Class Template Reference

Class BalancedTree (container class intended to keep an ordered sequence of objects, supports fast $n \log n $ ninsertions). More...

#include <BalancedTree.h>

List of all members.

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

BTNodetheRoot

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 $n \log n $ 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 $n \log n $ asymptotic insertions which cannot be achieved using standard vector<...> and list<...>.

Definition at line 34 of file BalancedTree.h.


Constructor & Destructor Documentation

template<class Obj>
BalancedTree< Obj >::BalancedTree  )  [inline]
 

Default constructor.

Definition at line 66 of file BalancedTree.h.

template<class Obj>
template<class ConstObjIter>
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().

template<class Obj>
BalancedTree< Obj >::~BalancedTree  )  [inline]
 

Destructor recursively frees memory.

Definition at line 72 of file BalancedTree.h.

References BalancedTree< Obj >::theRoot.


Member Function Documentation

template<class Obj>
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.

template<class Obj>
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().

template<class Obj>
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.

template<class Obj>
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.

template<class Obj>
template<class ConstObjIter>
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().

template<class Obj>
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().

template<class Obj>
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().

template<class Obj>
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.


Member Data Documentation

template<class Obj>
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:
Generated on Sun Dec 3 10:58:58 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.6