BalancedTree< Obj > Class Template Reference

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

#include <BalancedTree.h>

List of all members.

Classes
struct	BTNode
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

---

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

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:

• general/include/BalancedTree.h