frepple::utils::Tree Class Reference
This class implements a binary tree data structure. It is used as a container for entities keyed by their name.
More...
#include <utils.h>
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 3431 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 3439 of file utils.h.
Constructor & Destructor Documentation
frepple::utils::Tree::Tree |
( |
bool |
b = false |
) |
[inline] |
Default constructor.
Definition at line 3536 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 3550 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 3556 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 3566 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 3562 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 3613 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 3631 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 3652 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 3573 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 3590 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: