![]() |
Public API Reference |
![]() |
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. | |
template<typename K2 > | |
const K * | Find (const K2 &other) const |
Locate key that is equal to other. | |
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 * | FindSmallestGreaterEqual (const K2 &other) const |
Locate smallest key greater or equal to other. | |
template<typename K2 > | |
const K & | FindSmallestGreaterEqual (const K2 &other, const K &fallback) const |
Locate smallest key greater or 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 & | FindGreatestSmallerEqual (const K2 &other, const K &fallback) const |
Locate greatest key smaller or equal to other. | |
template<typename CB > | |
void | TraverseInOrder (CB &callback) const |
Traverse 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'. | |
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'. | |
template<typename K2 > | |
K * | FindInternal (const K2 &other) |
Locate key that is equal to other. | |
template<typename K2 > | |
K & | FindInternal (const K2 &other, K &fallback) |
Locate key that is equal to other. | |
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 |
Get an iterator for iterating over the entire tree. | |
class | ConstReverseIterator |
Get an iterator for iterating over the entire tree. | |
class | Iterator |
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. | |
Iterator | GetIterator () |
Get an iterator for iterating over the entire tree. | |
void | Delete (Iterator &it) |
Delete the 'next' element pointed at by the iterator. |
A red-black-tree.
csRedBlackTree<K>::allocationUnitSize
. Definition at line 242 of file redblacktree.h.
csRedBlackTree< K, Allocator, Ordering >::csRedBlackTree | ( | const Allocator & | alloc = Allocator() | ) | [inline] |
Construct a new tree.
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.
bool csRedBlackTree< K, Allocator, Ordering >::Contains | ( | const K & | key | ) | const [inline] |
Check whether a key is in the tree.
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.
bool csRedBlackTree< K, Allocator, Ordering >::Delete | ( | const K & | key | ) | [inline] |
Delete a key.
Definition at line 791 of file redblacktree.h.
void csRedBlackTree< K, Allocator, Ordering >::Delete | ( | Iterator & | it | ) | [inline] |
Delete the 'next' element pointed at by the iterator.
Reimplemented in csRedBlackTreeMap< typename TreeTraitsType::MeshNodeKeyType, MeshNode *, MeshNodeTreeBlockRefAlloc >.
Definition at line 1027 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.
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 [inline] |
Locate key that is equal to other.
Definition at line 825 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 >::FindGreatestSmallerEqual | ( | const K2 & | other | ) | const [inline] |
Locate greatest key smaller or equal to other.
Definition at line 861 of file redblacktree.h.
const K& csRedBlackTree< K, Allocator, Ordering >::FindGreatestSmallerEqual | ( | const K2 & | other, |
const K & | fallback | ||
) | const [inline] |
Locate greatest key smaller or equal to other.
Definition at line 867 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.
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.
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.
const K& csRedBlackTree< K, Allocator, Ordering >::FindSmallestGreaterEqual | ( | const K2 & | other, |
const K & | fallback | ||
) | const [inline] |
Locate smallest key greater or equal to other.
Definition at line 850 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.
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.
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.
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.
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.
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.
friend class ConstIterator [friend] |
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 926 of file redblacktree.h.
friend class ConstReverseIterator [friend] |
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 958 of file redblacktree.h.
friend class Iterator [friend] |
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 1013 of file redblacktree.h.