This class implements a binary tree data structure. It is used as a container for entities keyed by their name.
More...
List of all members.
Detailed Description
This class implements a binary tree data structure. It is used as a container for entities keyed by their name.
Technically, the data structure can be described as a red-black tree with intrusive tree nodes.
- See also:
- HasName
Definition at line 3273 of file utils.h.
Member Enumeration Documentation
The algorithm assigns a color to each node in the tree. The color is used to keep the tree balanced.
A node with color 'none' is a node that hasn't been inserted yet in the tree.
- Enumerator:
-
Definition at line 3281 of file utils.h.
Constructor & Destructor Documentation
frepple::utils::Tree::Tree |
( |
bool |
b = false |
) |
[inline] |
Default constructor.
Definition at line 3378 of file utils.h.
frepple::utils::Tree::~Tree |
( |
|
) |
[inline] |
Destructor.
By default, the objects in the tree are not deleted when the tree is deleted. This is done for performance reasons: the program can shut down faster.
Definition at line 3392 of file utils.h.
Member Function Documentation
TreeNode* frepple::utils::Tree::begin |
( |
|
) |
const [inline] |
Returns an iterator to the start of the list.
The user will need to take care of properly acquiring a read lock on on the tree object.
Definition at line 3398 of file utils.h.
void frepple::utils::Tree::clear |
( |
|
) |
|
Remove all elements from the tree.
Definition at line 36 of file name.cpp.
bool frepple::utils::Tree::empty |
( |
|
) |
const [inline] |
Returns true if the list is empty.
Its complexity is O(1).
Definition at line 3408 of file utils.h.
TreeNode* frepple::utils::Tree::end |
( |
|
) |
const [inline] |
Returns an iterator pointing beyond the last element in the list.
The user will need to take care of properly acquiring a read lock on on the tree object.
Definition at line 3404 of file utils.h.
void frepple::utils::Tree::erase |
( |
TreeNode * |
x |
) |
|
Remove a node from the tree.
Definition at line 190 of file name.cpp.
TreeNode* frepple::utils::Tree::find |
( |
const string & |
k |
) |
const [inline] |
Search for an element in the tree.
Profiling shows this function has a significant impact on the CPU time (mainly because of the string comparisons), and has been optimized as much as possible.
Definition at line 3455 of file utils.h.
TreeNode* frepple::utils::Tree::findLowerBound |
( |
const string & |
k, |
|
|
bool * |
f | |
|
) |
| | const [inline] |
Find the element with this given key or the element immediately preceding it.
The second argument is a boolean that is set to true when the element is found in the list.
Definition at line 3473 of file utils.h.
Insert a new node in the tree. The second argument is a hint on the proper location in the tree.
Profiling shows this function has a significant impact on the cpu time (mainly because of the string comparisons), and has been optimized as much as possible.
Definition at line 57 of file name.cpp.
Insert a new node in the tree.
Definition at line 3494 of file utils.h.
void frepple::utils::Tree::rename |
( |
TreeNode * |
obj, |
|
|
string |
newname | |
|
) |
| | [inline] |
Renames an existing node, and adjusts its position in the tree.
Definition at line 3415 of file utils.h.
size_t frepple::utils::Tree::size |
( |
|
) |
const [inline] |
This method returns the number of nodes inserted in this tree.
Its complexity is O(1), so it can be called on large trees without any performance impact.
Definition at line 3432 of file utils.h.
void frepple::utils::Tree::verify |
( |
|
) |
const |
Verifies the integrity of the tree and returns true if everything is correct.
The tree should be locked before calling this function.
Definition at line 379 of file name.cpp.
The documentation for this class was generated from the following files: