csRedBlackTree< K, Allocator, Ordering > Class Template Reference
[Containers]
A red-black-tree. More...
#include <csutil/redblacktree.h>
Classes | |
| class | ConstIterator |
| Const iterator for tree. More... | |
| class | ConstReverseIterator |
| Const reverse iterator for tree. More... | |
| class | Iterator |
| Iterator for tree. More... | |
| class | ReverseIterator |
| Reverse iterator for tree. More... | |
Public Member Functions | |
| bool | Contains (const K &key) const |
| Check whether a key is in the tree. | |
| csRedBlackTree (const Allocator &alloc=Allocator()) | |
| Construct a new tree. | |
| bool | Delete (const K &key) |
| Delete a key. | |
| void | DeleteAll () |
| Delete all keys. | |
| bool | DeleteExact (const K *key) |
| Delete a specific instance of a key. | |
| void | Empty () |
| Delete all the keys. (Idiomatic alias for DeleteAll().). | |
| ReverseIterator | GetReverseIterator () |
| Get an iterator for iterating over the entire tree. | |
| bool | In (const K &key) const |
| Check whether a key is in the tree. | |
| const K * | Insert (const K &key) |
| Insert a key. | |
| bool | IsEmpty () const |
| Returns whether this tree has no nodes. | |
| ~csRedBlackTree () | |
| Destroy the tree. | |
Protected Member Functions | |
| Node * | CreateNode (Node *parent, const K &key) |
| Create a new tree node. | |
| void | DeleteFixup (Node *node, Node *nilParent) |
| Fix up the RB tree after a deletion. | |
| void | DeleteNode (Node *node) |
| Delete a node from the tree. | |
| void | InsertFixup (Node *node) |
| Fix up the RB tree after an insert. | |
| bool | IsBlack (Node *node) const |
| Check whether a node is black. Note that 0 nodes are by definition black. | |
| bool | IsRed (Node *node) const |
| Check whether a node is red. | |
| template<typename K2 > | |
| Node * | LocateNode (Node *node, const K2 &other) const |
| Find a node for a key. | |
| Node * | LocateNodeExact (Node *node, const K *key) const |
| Find the node which has a given instance of a key. | |
| void | RecursiveCopy (Node *&to, Node *parent, const Node *from) |
| Duplicate a subtree. | |
| void | RecursiveDelete (Node *node) |
| Recursively delete a subtree. | |
| Node * | RecursiveFindInsertCandidate (Node *parent, Node *&node, const K &key, uint depth, InsertCandidate &candidate) |
| Locate the place where a new node needs to be inserted. | |
| template<typename CB > | |
| void | RecursiveTraverseInOrder (Node *node, CB &callback) const |
| Traverse tree. | |
| void | RotateLeft (Node *pivot) |
| Left-rotate subtree around 'pivot'. | |
| void | RotateRight (Node *pivot) |
| Right-rotate subtree around 'pivot'. | |
Static Protected Member Functions | |
| static Node * | Predecessor (const Node *node) |
| Return largest node with a key smaller than 'node's. | |
| static Node * | Successor (const Node *node) |
| Return smallest node with a key greater than 'node's. | |
|
| |
| class | ConstIterator |
| Locate key that is equal to other. | |
| class | ConstReverseIterator |
| Locate key that is equal to other. | |
| class | Iterator |
| Locate key that is equal to other. | |
| template<typename K2 > | |
| K & | FindInternal (const K2 &other, K &fallback) |
| Locate key that is equal to other. | |
| template<typename K2 > | |
| K * | FindInternal (const K2 &other) |
| Locate key that is equal to other. | |
| template<typename K2 > | |
| Node * | RecursiveFindGSE (Node *node, const K2 &other) const |
| Locate greatest key that is smaller or equal to 'other'. | |
| template<typename K2 > | |
| Node * | RecursiveFindSGE (Node *node, const K2 &other) const |
| Locate smallest key that is greater or equal to 'other'. | |
| void | Delete (Iterator &it) |
| Delete the 'next' element pointed at by the iterator. | |
| template<typename K2 > | |
| const K & | Find (const K2 &other, const K &fallback) const |
| Locate key that is equal to other. | |
| template<typename K2 > | |
| const K * | Find (const K2 &other) const |
| Locate key that is equal to other. | |
| template<typename K2 > | |
| const K & | FindGreatestSmallerEqual (const K2 &other, const K &fallback) const |
| Locate key that is equal to other. | |
| template<typename K2 > | |
| const K * | FindGreatestSmallerEqual (const K2 &other) const |
| Locate greatest key smaller or equal to other. | |
| template<typename K2 > | |
| const K & | FindSmallestGreaterEqual (const K2 &other, const K &fallback) const |
| Locate key that is equal to other. | |
| template<typename K2 > | |
| const K * | FindSmallestGreaterEqual (const K2 &other) const |
| Locate smallest key greater or equal to other. | |
| Iterator | GetIterator () |
| Get an iterator for iterating over the entire tree. | |
| ConstIterator | GetIterator () const |
| Get an iterator for iterating over the entire tree. | |
| ConstReverseIterator | GetReverseIterator () const |
| Get an iterator for iterating over the entire tree. | |
| template<typename CB > | |
| void | TraverseInOrder (CB &callback) const |
| Traverse tree. | |
Detailed Description
template<typename K, typename Allocator = CS::Container::DefaultRedBlackTreeAllocator<K>, template< typename K, typename K2 > class Ordering = CS::Container::RedBlackTreeOrderingTotal>
class csRedBlackTree< K, Allocator, Ordering >
A red-black-tree.
- Uniqueness of keys
- Keys do not need to be unique. However, searching for a non-unique key Find() will return an equivalent key, not necessarily the identical key.
- The ordering of the key is controlled by changing the Ordering template parameter which defaults to total ordering. Total ordering is selected by CS::Container::RedBlackTreeOrderingTotal. Partial ordering is selected by CS::Container::RedBlackTreeOrderingPartial. Strict Weak ordering is selected by CS::Container::RedBlackTreeOrderingStrictWeak.
- The various "Find" methods can take keys of an alternative type (designated K2). Operators available must cover the comparisons of the ordering parameter. The ordering of K2 should, sensibly, be the same as that of K.
- Remarks:
- The key has to fullfill the requirements made by the Ordering class.
- Only stores keys. If you need a key-value-map, look at csRedBlackTreeMap.
- The allocator has to return memory blocks at least aligned to two byte boundaries. (This is usually already the case.)
-
Allocation requests to the allocator have a size of
csRedBlackTree<K>::allocationUnitSize.
Definition at line 242 of file redblacktree.h.
Constructor & Destructor Documentation
| csRedBlackTree< K, Allocator, Ordering >::csRedBlackTree | ( | const Allocator & | alloc = Allocator() |
) | [inline] |
Construct a new tree.
- Parameters:
-
allocatorBlockSize Block size in bytes used by the internal block allocator for nodes.
Definition at line 765 of file redblacktree.h.
| csRedBlackTree< K, Allocator, Ordering >::~csRedBlackTree | ( | ) | [inline] |
Destroy the tree.
Definition at line 771 of file redblacktree.h.
Member Function Documentation
| bool csRedBlackTree< K, Allocator, Ordering >::Contains | ( | const K & | key | ) | const [inline] |
Check whether a key is in the tree.
- Remarks:
- This is rigidly equivalent to Contains(key), but may be considered more idiomatic by some.
Definition at line 820 of file redblacktree.h.
| Node* csRedBlackTree< K, Allocator, Ordering >::CreateNode | ( | Node * | parent, | |
| const K & | key | |||
| ) | [inline, protected] |
Create a new tree node.
Definition at line 267 of file redblacktree.h.
| void csRedBlackTree< K, Allocator, Ordering >::Delete | ( | Iterator & | it | ) | [inline] |
Delete the 'next' element pointed at by the iterator.
- Remarks:
- Will repoint the iterator to the following element.
Reimplemented in csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 1027 of file redblacktree.h.
| bool csRedBlackTree< K, Allocator, Ordering >::Delete | ( | const K & | key | ) | [inline] |
Delete a key.
- Returns:
- Whether the deletion was successful. Fails if the key is not in the tree.
Definition at line 791 of file redblacktree.h.
| void csRedBlackTree< K, Allocator, Ordering >::DeleteAll | ( | ) | [inline] |
Delete all keys.
Reimplemented in csRedBlackTreeMap< K, T, Allocator, Ordering >, and csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 876 of file redblacktree.h.
| bool csRedBlackTree< K, Allocator, Ordering >::DeleteExact | ( | const K * | key | ) | [inline] |
Delete a specific instance of a key.
- Returns:
- Whether the deletion was successful. Fails if the key is not in the tree.
Definition at line 803 of file redblacktree.h.
| void csRedBlackTree< K, Allocator, Ordering >::DeleteFixup | ( | Node * | node, | |
| Node * | nilParent | |||
| ) | [inline, protected] |
Fix up the RB tree after a deletion.
Definition at line 490 of file redblacktree.h.
| void csRedBlackTree< K, Allocator, Ordering >::DeleteNode | ( | Node * | node | ) | [inline, protected] |
Delete a node from the tree.
Definition at line 454 of file redblacktree.h.
| void csRedBlackTree< K, Allocator, Ordering >::Empty | ( | ) | [inline] |
Delete all the keys. (Idiomatic alias for DeleteAll().).
Reimplemented in csRedBlackTreeMap< K, T, Allocator, Ordering >, and csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 882 of file redblacktree.h.
| const K& csRedBlackTree< K, Allocator, Ordering >::Find | ( | const K2 & | other, | |
| const K & | fallback | |||
| ) | const [inline] |
Locate key that is equal to other.
Definition at line 831 of file redblacktree.h.
| const K* csRedBlackTree< K, Allocator, Ordering >::Find | ( | const K2 & | other | ) | const [inline] |
Locate key that is equal to other.
Definition at line 825 of file redblacktree.h.
| const K& csRedBlackTree< K, Allocator, Ordering >::FindGreatestSmallerEqual | ( | const K2 & | other, | |
| const K & | fallback | |||
| ) | const [inline] |
Locate key that is equal to other.
Definition at line 867 of file redblacktree.h.
| const K* csRedBlackTree< K, Allocator, Ordering >::FindGreatestSmallerEqual | ( | const K2 & | other | ) | const [inline] |
Locate greatest key smaller or equal to other.
Definition at line 861 of file redblacktree.h.
| K& csRedBlackTree< K, Allocator, Ordering >::FindInternal | ( | const K2 & | other, | |
| K & | fallback | |||
| ) | [inline, protected] |
Locate key that is equal to other.
Definition at line 749 of file redblacktree.h.
| K* csRedBlackTree< K, Allocator, Ordering >::FindInternal | ( | const K2 & | other | ) | [inline, protected] |
Locate key that is equal to other.
Definition at line 743 of file redblacktree.h.
| const K& csRedBlackTree< K, Allocator, Ordering >::FindSmallestGreaterEqual | ( | const K2 & | other, | |
| const K & | fallback | |||
| ) | const [inline] |
Locate key that is equal to other.
Definition at line 850 of file redblacktree.h.
| const K* csRedBlackTree< K, Allocator, Ordering >::FindSmallestGreaterEqual | ( | const K2 & | other | ) | const [inline] |
Locate smallest key greater or equal to other.
Definition at line 844 of file redblacktree.h.
| Iterator csRedBlackTree< K, Allocator, Ordering >::GetIterator | ( | ) | [inline] |
Get an iterator for iterating over the entire tree.
Reimplemented in csRedBlackTreeMap< K, T, Allocator, Ordering >, and csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 1018 of file redblacktree.h.
| ConstIterator csRedBlackTree< K, Allocator, Ordering >::GetIterator | ( | ) | const [inline] |
Get an iterator for iterating over the entire tree.
Reimplemented in csRedBlackTreeMap< K, T, Allocator, Ordering >, and csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 963 of file redblacktree.h.
| ReverseIterator csRedBlackTree< K, Allocator, Ordering >::GetReverseIterator | ( | ) | [inline] |
Get an iterator for iterating over the entire tree.
Reimplemented in csRedBlackTreeMap< K, T, Allocator, Ordering >, and csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 1091 of file redblacktree.h.
| ConstReverseIterator csRedBlackTree< K, Allocator, Ordering >::GetReverseIterator | ( | ) | const [inline] |
Get an iterator for iterating over the entire tree.
Reimplemented in csRedBlackTreeMap< K, T, Allocator, Ordering >, and csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 971 of file redblacktree.h.
| bool csRedBlackTree< K, Allocator, Ordering >::In | ( | const K & | key | ) | const [inline] |
Check whether a key is in the tree.
Definition at line 811 of file redblacktree.h.
| const K* csRedBlackTree< K, Allocator, Ordering >::Insert | ( | const K & | key | ) | [inline] |
Insert a key.
- Returns:
- A pointer to the copy of the key stored in the tree.
Definition at line 777 of file redblacktree.h.
| void csRedBlackTree< K, Allocator, Ordering >::InsertFixup | ( | Node * | node | ) | [inline, protected] |
Fix up the RB tree after an insert.
Definition at line 388 of file redblacktree.h.
| bool csRedBlackTree< K, Allocator, Ordering >::IsBlack | ( | Node * | node | ) | const [inline, protected] |
Check whether a node is black. Note that 0 nodes are by definition black.
Definition at line 382 of file redblacktree.h.
| bool csRedBlackTree< K, Allocator, Ordering >::IsEmpty | ( | ) | const [inline] |
Returns whether this tree has no nodes.
Reimplemented in csRedBlackTreeMap< K, T, Allocator, Ordering >, and csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 884 of file redblacktree.h.
| bool csRedBlackTree< K, Allocator, Ordering >::IsRed | ( | Node * | node | ) | const [inline, protected] |
Check whether a node is red.
Definition at line 385 of file redblacktree.h.
| Node* csRedBlackTree< K, Allocator, Ordering >::LocateNode | ( | Node * | node, | |
| const K2 & | other | |||
| ) | const [inline, protected] |
Find a node for a key.
Definition at line 566 of file redblacktree.h.
| Node* csRedBlackTree< K, Allocator, Ordering >::LocateNodeExact | ( | Node * | node, | |
| const K * | key | |||
| ) | const [inline, protected] |
Find the node which has a given instance of a key.
Definition at line 586 of file redblacktree.h.
| static Node* csRedBlackTree< K, Allocator, Ordering >::Predecessor | ( | const Node * | node | ) | [inline, static, protected] |
Return largest node with a key smaller than 'node's.
Definition at line 626 of file redblacktree.h.
| void csRedBlackTree< K, Allocator, Ordering >::RecursiveCopy | ( | Node *& | to, | |
| Node * | parent, | |||
| const Node * | from | |||
| ) | [inline, protected] |
Duplicate a subtree.
Definition at line 716 of file redblacktree.h.
| void csRedBlackTree< K, Allocator, Ordering >::RecursiveDelete | ( | Node * | node | ) | [inline, protected] |
Recursively delete a subtree.
Definition at line 732 of file redblacktree.h.
| Node* csRedBlackTree< K, Allocator, Ordering >::RecursiveFindGSE | ( | Node * | node, | |
| const K2 & | other | |||
| ) | const [inline, protected] |
Locate greatest key that is smaller or equal to 'other'.
Definition at line 647 of file redblacktree.h.
| Node* csRedBlackTree< K, Allocator, Ordering >::RecursiveFindInsertCandidate | ( | Node * | parent, | |
| Node *& | node, | |||
| const K & | key, | |||
| uint | depth, | |||
| InsertCandidate & | candidate | |||
| ) | [inline, protected] |
Locate the place where a new node needs to be inserted.
Definition at line 287 of file redblacktree.h.
| Node* csRedBlackTree< K, Allocator, Ordering >::RecursiveFindSGE | ( | Node * | node, | |
| const K2 & | other | |||
| ) | const [inline, protected] |
Locate smallest key that is greater or equal to 'other'.
Definition at line 678 of file redblacktree.h.
| void csRedBlackTree< K, Allocator, Ordering >::RecursiveTraverseInOrder | ( | Node * | node, | |
| CB & | callback | |||
| ) | const [inline, protected] |
Traverse tree.
Definition at line 708 of file redblacktree.h.
| void csRedBlackTree< K, Allocator, Ordering >::RotateLeft | ( | Node * | pivot | ) | [inline, protected] |
Left-rotate subtree around 'pivot'.
Definition at line 342 of file redblacktree.h.
| void csRedBlackTree< K, Allocator, Ordering >::RotateRight | ( | Node * | pivot | ) | [inline, protected] |
Right-rotate subtree around 'pivot'.
Definition at line 362 of file redblacktree.h.
| static Node* csRedBlackTree< K, Allocator, Ordering >::Successor | ( | const Node * | node | ) | [inline, static, protected] |
Return smallest node with a key greater than 'node's.
Definition at line 608 of file redblacktree.h.
| void csRedBlackTree< K, Allocator, Ordering >::TraverseInOrder | ( | CB & | callback | ) | const [inline] |
Traverse tree.
Reimplemented in csRedBlackTreeMap< K, T, Allocator, Ordering >, and csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 889 of file redblacktree.h.
Friends And Related Function Documentation
friend class ConstIterator [friend] |
Locate key that is equal to other.
Reimplemented in csRedBlackTreeMap< K, T, Allocator, Ordering >, and csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 926 of file redblacktree.h.
friend class ConstReverseIterator [friend] |
Locate key that is equal to other.
Reimplemented in csRedBlackTreeMap< K, T, Allocator, Ordering >, and csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 958 of file redblacktree.h.
friend class Iterator [friend] |
Locate key that is equal to other.
Reimplemented in csRedBlackTreeMap< K, T, Allocator, Ordering >, and csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 1013 of file redblacktree.h.
The documentation for this class was generated from the following file:
- csutil/redblacktree.h
Generated for Crystal Space 2.0 by doxygen 1.6.1