ezEngine  Milestone 7
ezSetBase< KeyType, Comparer > Class Template Reference

A set container that only stores whether an element resides in it or not. Similar to STL::set. More...

#include <Set.h>

Inheritance diagram for ezSetBase< KeyType, Comparer >:

Classes

struct  Iterator
 Base class for all iterators. More...
 
struct  NilNode
 Only used by the sentinel node. More...
 
struct  Node
 A node storing the key. More...
 

Public Member Functions

bool IsEmpty () const
 Returns whether there are no elements in the set. O(1) operation.
 
ezUInt32 GetCount () const
 Returns the number of elements currently stored in the set. O(1) operation.
 
void Clear ()
 Destroys all elements in the set and resets its size to zero.
 
Iterator GetIterator () const
 Returns a constant Iterator to the very first element.
 
Iterator GetLastIterator () const
 Returns a constant Iterator to the very last element. For reverse traversal.
 
Iterator Insert (const KeyType &key)
 Inserts the key into the tree and returns an Iterator to it. O(log n) operation.
 
bool Remove (const KeyType &key)
 Erases the element with the given key, if it exists. O(log n) operation.
 
Iterator Remove (const Iterator &pos)
 Erases the element at the given Iterator. O(log n) operation.
 
Iterator Find (const KeyType &key) const
 Searches for key, returns an Iterator to it or an invalid iterator, if no such key is found. O(log n) operation.
 
bool Contains (const KeyType &key) const
 Checks whether the given key is in the container.
 
bool Contains (const ezSetBase< KeyType, Comparer > &operand) const
 Checks whether the given key is in the container.
 
Iterator LowerBound (const KeyType &key) const
 Returns an Iterator to the element with a key equal or larger than the given key. Returns an invalid iterator, if there is no such element.
 
Iterator UpperBound (const KeyType &key) const
 Returns an Iterator to the element with a key that is LARGER than the given key. Returns an invalid iterator, if there is no such element.
 
void Union (const ezSetBase< KeyType, Comparer > &operand)
 Makes this set the union of itself and the operand.
 
void Difference (const ezSetBase< KeyType, Comparer > &operand)
 Makes this set the difference of itself and the operand, i.e. subtracts operand.
 
void Intersection (const ezSetBase< KeyType, Comparer > &operand)
 Makes this set the intersection of itself and the operand.
 
ezAllocatorBaseGetAllocator () const
 Returns the allocator that is used by this instance.
 
bool operator== (const ezSetBase< KeyType, Comparer > &rhs) const
 Comparison operator.
 
bool operator!= (const ezSetBase< KeyType, Comparer > &rhs) const
 Comparison operator.
 
ezUInt64 GetHeapMemoryUsage () const
 Returns the amount of bytes that are currently allocated on the heap.
 

Protected Member Functions

 ezSetBase (const Comparer &comparer, ezAllocatorBase *pAllocator)
 Initializes the set to be empty.
 
 ezSetBase (const ezSetBase< KeyType, Comparer > &cc, ezAllocatorBase *pAllocator)
 Copies all keys from the given set into this one.
 
 ~ezSetBase ()
 Destroys all elements in the set.
 
void operator= (const ezSetBase< KeyType, Comparer > &rhs)
 Copies all keys from the given set into this one.
 

Private Member Functions

NodeInternal_Find (const KeyType &key) const
 
NodeInternal_LowerBound (const KeyType &key) const
 
NodeInternal_UpperBound (const KeyType &key) const
 
void Constructor ()
 
NodeAcquireNode (const KeyType &key, int m_uiLevel, Node *pParent)
 Creates one new node and initializes it.
 
void ReleaseNode (Node *pNode)
 Destroys the given node.
 
NodeSkewNode (Node *root)
 Red-Black Tree stuff(Anderson Tree to be exact). More...
 
NodeSplitNode (Node *root)
 
NodeInsert (Node *root, const KeyType &key, Node *&pInsertedNode)
 
NodeRemove (Node *root, const KeyType &key, bool &bRemoved)
 
NodeGetLeftMost () const
 Returns the left-most node of the tree(smallest key).
 
NodeGetRightMost () const
 Returns the right-most node of the tree(largest key).
 

Private Attributes

Nodem_pRoot
 Root node of the tree.
 
NilNode m_NilNode
 Sentinel node.
 
ezUInt32 m_uiCount
 Number of active nodes in the tree.
 
ezDeque< Node,
ezNullAllocatorWrapper, false > 
m_Elements
 Data store. Keeps all the nodes.
 
Nodem_pFreeElementStack
 Stack of recently discarded nodes to quickly acquire new nodes.
 
Comparer m_Comparer
 Comparer object.
 

Detailed Description

template<typename KeyType, typename Comparer>
class ezSetBase< KeyType, Comparer >

A set container that only stores whether an element resides in it or not. Similar to STL::set.

Sets are similar to maps that do not store a value (or only a bool that is always true). Sets can be used to reduce an unordered number of elements to only those that are unique. Insertion/erasure/lookup in sets is quite fast (O (log n)). This container is implemented with a red-black tree, so it will always be a balanced tree.

Member Function Documentation

template<typename KeyType , typename Comparer >
ezSetBase< KeyType, Comparer >::Node * ezSetBase< KeyType, Comparer >::SkewNode ( Node root)
private

Red-Black Tree stuff(Anderson Tree to be exact).

Code taken from here: http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx


The documentation for this class was generated from the following files: