template class detangled::raw_tree¶
Overview¶
raw_tree is a container which behaves like a tree. More…
#include <raw_tree.h> template <typename T> class raw_tree { public: // typedefs typedef T value_type; typedef value_type& reference; typedef ptrdiff_t difference_type; typedef size_t size_type; // fields const typedef value_type& const_reference; // construction raw_tree(); template <typename U> raw_tree(U&& value); raw_tree(raw_tree&& other); // methods raw_tree& operator=(raw_tree&& other); void swap(raw_tree<T>& other); const T& operator*() const; T& operator*(); bool has_parent() const; const raw_tree& parent() const; raw_tree& parent(); template <side wing> bool is_side() const; side get_side() const; template <side wing> bool has_child() const; bool has_child(side wing) const; template <side wing> const raw_tree& child() const; const raw_tree& child(side wing) const; template <side wing> raw_tree& child(); raw_tree& child(side wing); size_t size() const; template <side child, side grand_child> void reshape(); template <side wing> void rotate(); void rotate(side wing); void flip(); template <side wing> void replace(raw_tree<T>&& child); void replace(side wing, raw_tree<T>&& child); template <side wing, typename... Args> void emplace(Args&&... args); template <typename... Args> void emplace(side wing, Args&&... args); template <side wing, side gc_wing, typename... Args> void splice(Args&&... args); template <side wing> raw_tree detach(); raw_tree detach(side wing); template <traversal_order order, side wing> iterator<raw_tree<T>, order, wing> begin(); template <traversal_order order, side wing> iterator<const raw_tree<T>, order, wing> begin() const; template <traversal_order order, side wing> iterator<raw_tree<T>, order, wing> end(); template <traversal_order order, side wing> iterator<const raw_tree<T>, order, wing> end() const; RAW_TREE_MAKE_ALIAS(inl, in, left); RAW_TREE_MAKE_ALIAS(inr, in, right); RAW_TREE_MAKE_ALIAS(prel, pre, left); RAW_TREE_MAKE_ALIAS(prer, pre, right); RAW_TREE_MAKE_ALIAS(postl, post, left); RAW_TREE_MAKE_ALIAS(postr, post, right); template <side wing> const raw_tree<T>& child() const; template <side wing> raw_tree<T>& child(); template <side wing> raw_tree<T> detach(); };
Detailed Documentation¶
raw_tree is a container which behaves like a tree.
Overview:
Typical usage:
raw_tree<std::string> messages("world "); messages.replace<side::left>("Hello "); messages.replace<side::right>("!");
Recursive Container:
It is a container because it allows storing elements of a fixed type and allows client-code meaningful ways to access the elements. It is foundationally unlike other containers in that it’s internal storage is recursive. This allows usage patterns which allow treating a subtree like a tree.
Accessing values:
Clients may create detangled::iterator s to iterate over the contained values. See raw_tree::begin() for more. Other than this raw_tree::parent(), raw_tree::child etc. are methods which can be used for accessing other nodes from a tree node.
Similarity with std containers:
It is most closely related to std::list for the following reasons:
Nodes are stored on the heap.
The head / root node is stored on the stack like a standard container head.
It has splice like operations which allow stitching pieces from one container object to another container object.
detangled::accessors pointing to nodes in a tree are valid acrossraw_tree::detachandraw_tree::replaceoperations (but readdetangled::accessordocumentation for exceptions).
Relations:
Other than the data stored at a node the other elements that a raw_tree object contains are references to a parent and upto two children (left and right).
Children:
Each node has two children which it owns (a.k.a. deletes when going out of scope). The first child is referred to as left and the second is right.
Methods which are used for performing operations on any one of the two children are non-type-templated with the side enum (raw_tree::has_child<side::left>() for example). Each child is guaranteed to refer to this.
Parent:
Parent relations are non-owning (i.e. we may die without affecting the parent). We are guaranteed to be found at either the right or left child position of the parent node.
Root nodes are exceptions. See the parent() methods for details on the result for these.
Operations:
Operations (methods) of the tree objects are categorizable and the following notes help in remembering the classification and specific gotchas.
Safety of methods:
Almost all referential operations are unsafe and client code should be satisfied before attempting to access or modify a relation. For example raw_tree::detach<side::right>() when there no side::right child present is undefined access.
The above is done for efficiency. Many algorithmic situations would result in preconditions being true without any effective way to determine it beforehand (meaning we wouldn’t know them at compile time). Clients can be efficient by bypassing safety checks in those situations.
Non-mutating and Mutating methods:
Non-mutating operations allow client code to access data on the tree including through a chain of relation nodes without modifying the tree in any way. Values stored at nodes are also accessible and classified as non-mutating operations.
Additionally non-mutating operations have two forms. non-const and ... const; ones. For example:
const raw_tree &parent() const; raw_tree &parent();
They are functionally equivalent and present to enable client code to work effectively with both const and non-const references.
Mutating operations allow client code to add, remove or reshape the tree. reshape, rotate, detach are examples of these.
Generated documentation will list out a subset of the methods (one's for
which documentation is listed typically). The actual class has non-const
and non-templated versions of many of the methods.
Side as template argument vs function argument:
Methods which deal with child (and grandchild) nodes require specifying the specific child. Two methods are provided for this category of methods, ones in which this specification is given through:
A template argument (
has_child<side::left>())A function argument (
has_child(side::left))
The template argument is specified when the wing being sought is available at compile time. These can be inlined during compilation and optimizers can optimize across these boundaries. The function-argument version uses the template version.
Parameters:
T |
is the value type of the stored element. |
Construction¶
template <typename U> raw_tree(U&& value)
Construct a tree with a single value. TODO(ghochee): Class template for creating empty trees so that client side code like for loops can run more naturally.
Parameters:
value |
is of a type and category which can be used for constructing value_ correctly. |
raw_tree(raw_tree&& other)
Move operations would deep -move a node. other may be a root node.
Complexity: O(1)
Parameters:
other |
refers to the node we are moving into this location. |
Methods¶
void swap(raw_tree<T>& other)
Deep swaps this with other. To do a shallow swap, call swap on the values (swap(*first, *second) instead of swap(first, second)).
Neither node can be an ancestor of the other. `other` need not be part
of the same tree. Either may be a *root* node. Calling swap between
ancestrally related nodes would result in undefined behaviour
(eventually a segfault but could also result in a busy loop). This
isn't just an implementation defect, *deep* swap between such nodes is
nonsensical.
Complexity: O(1)
Parameters:
other |
refers to the other tree node we wish to swap with. |
const T& operator*() const
Returns:
the stored value.
bool has_parent() const
Returns:
true iff we are not a root node.
const raw_tree& parent() const
Returns:
a reference to the parent node, undefined if we are root node.
template <side wing> bool is_side() const
Returns:
true iff we are wing -sided child of our parent. Always false for root node.
side get_side() const
Returns:
the side that this node is on, undefined if we are root.
template <side wing> bool has_child() const
Returns:
true iff wing -sided child is present.
template <side wing> const raw_tree& child() const
Parameters:
wing |
is the side that we want. |
Returns:
a reference to our wing -side child.
size_t size() const
Complexity: O(N) since we don’t maintain counts so we have to iterate.
Returns:
the size of the tree.
template <side child, side grand_child> void reshape()
Reshapes this node and the relative positions of the children (and grand-children) while maintaining the traversal_order::in sequence. The specification of what reshaping is to be done is specified through the parameters child and grand_child. Specified with the parameters, the function call may be treated as a command.
Complexity: O(1)
After the reshaping command the value at this will change (because we reshape without moving this node). Any reshaping command which would make an absent node the root will cause undefined behaviour (likely segfault). For example R, R when the left child is absent is an error.
Examples:
Before:
1 === this node
/ \
/ \
child<side::left> === 0 child<side::right> === 2
/ \ / \
/ \ / \
left-left left-right right-left right-right
command: L, R
right(2)
/ \
/ \
left(0) right-right
/ \
/ \
left-left this(1)
\
\
right-left
command: R, R
left(0)
/ \
/ \
left-left this(1)
/ \
/ \
left-right right(2)
/ \
/ \
right-left right-right
Parameters:
child |
is the |
grand_child |
is the |
template <side wing> void rotate()
Performs wing -side rotation as described in common literature (e.g. left-rotation).
rotate<wing>() is identical to reshape<wing, wing>().
Parameters:
wing |
is the side to which we want rotation. |
void flip()
Switch the left and right children.
template <side wing> void replace(raw_tree<T>&& child)
Replace wing -sided child of this.
Parameters:
child |
is the node we wish to bring in. |
template <side wing, typename... Args> void emplace(Args&&... args)
Create wing -sided child of this.
Parameters:
Args |
are the types of the arguments for emplacement construction. |
args |
are the constructor args for construction of |
template <side wing, side gc_wing, typename... Args> void splice(Args&&... args)
Equivalent emplacing a node and moving existing node to a grand_child location.
Parameters:
wing |
is the side where we wish to emplace. |
gc_wing |
is the side where we wish to move the existing node. |
args |
are the constructor arguments for construction of |
template <side wing> raw_tree detach()
Detaches a child node making it a root node. Undefined is not present.
Parameters:
wing |
is the child |
template <traversal_order order, side wing> iterator<raw_tree<T>, order, wing> begin()
Returns an iterator for the tree rooted at this.
For example begin<traversal_order::pre, side::left>() would return an iterator which would follow left -sided inorder traversal over the subtree rooted at this. Due to the nature of this container it is possible to have the following construct:
for (auto it = root_node.begin<traversal_order::post, side::left>(); it != root_node.end<...>; ++it) { if (meets_some_condition(*it)) { for (auto jt = it->begin<traversal_order::in, side::left>(); jt != it->end<...>(); ++jt) { ... } } }
which effectively iterates through a subtree at *it inorder if meets_some_condition is satisfied. This kind of construction allows for complex algorithmic expressiveness cleanly.
Parameters:
order |
is the |
wing |
is the |
Returns:
an iterator for the tree rooted at this.
template <traversal_order order, side wing> iterator<raw_tree<T>, order, wing> end()
Returns an iterator which compares equal with an iterator which starts from begin and has navigated through all the nodes (depending on the specific order and wing).
Specifically
std::advance(tree.begin<traversal_order::post, side::right>(), tree.size()) == \ tree.end<traversal_order::post, side::right>()
is always true. Note that the traversal_order, wing pair has to be the same for the begin and end iterators (even though they are convertible from one to another). Comparing iterators with different orders / wings is not guaranteed to be correct.
See detangled::accessor::accessor() for information on end for iterators.