Skip to content

node_raw_class_doc

erikerlandson edited this page May 12, 2011 · 5 revisions

st_tree Home / st_tree Documentation

tree<Data, raw<>, Alloc>::node_type

tree_type – the type of the tree that contains this node
node_type – data type of nodes contained by the node. This is a recursive definition, as a node is a container for child nodes of same type.
data_type – alias for the Data template param: the data payload type at each node
allocator_type – the allocator type used by the node

value_type – data type contained by the node container class. The value type of a node is its node_type.
pointer – pointer to value_type
reference – reference to value_type
const_pointer – pointer to constant value_type
const_reference – reference to constant value_type
size_type – represents size (unsigned) values
difference_type – represents difference (signed) values

iterator – iterates over child nodes (random access)
const_iterator

bf_iterator – iterates over subtree starting at this node as root, breadth first traversal
const_bf_iterator
df_pre_iterator – iterates over subtree, depth-first preorder traversal
const_df_pre_iterator
df_post_iterator – iterates over subtree, depth-first postorder traversal
const_df_post_iterator

node_type() – default constructor: typically only used internally
~node_type() – destructor

node_raw(const node_raw& src) – copy constructor: typically used internally
node_raw& operator=(const node_raw& rhs) – deep assignment: data() and children of (rhs) are copied to the node. Node maintains its position in its parent’s child container. Throws cycle_exception if assignment would create a cycle in the tree (if (rhs) is ancestor of the node).

data_type& data() – return reference to data payload of the node
const data_type& data() const

size_type ply() const – return the node’s ply in the tree. The ply of root node is 0. The ply of the root’s children is 1, etc.
size_type depth() const – the depth of the node’s subtree
size_type subtree_size() – the number of nodes in the node’s subtree
bool is_root() const – true if the node has no parent

node_type& parent() – return reference to node’s parent (throw parent_exception if no parent)
const node_type& parent() const

tree_type& tree() – return reference to the tree that the node is a member of.
const tree_type& tree() const

bool is_ancestor(const node_type& n) const – true if the node is an ancestor of (n)

size_type size() const – returns the number of the node’s children
bool empty() const – true if the node has no children

node_type& operator[](size_type n) – return the (n)th child of the node
const node_type& operator[](size_type n) const

void push_back(const data_type& data) – append a new child node with data payload (data).
void push_back(const node_type& src) – append a deep-copy of (src) to the node’s children.
void push_back(const tree_type& src) – append a deep-copy of (src).root() to the node’s children.

iterator insert(const data_type& data) – append a new child node with data payload (data). returns iterator that points to new child.
iterator insert(const node_type& src) – append a deep-copy of (src) to the node’s children. returns iterator that points to new child.
iterator insert(const tree_type& src) – append a deep-copy of (src).root() to the node’s children. returns iterator that points to new child.

void pop_back() – pop the last child node off the end

node_type& front() – returns reference to first child
const node_type& front() const
node_type& back() – returns reference to last child
const node_type& back() const

void erase(const iterator& j) – erase the child node at (j)
void erase(const iterator& F, const iterator& L) – erase node’s children on the iterator interval [F, L)
void erase() – erase the node from its parent

void clear() – erase all the node’s children: reset to empty.

void swap(node_type& b) – swap data and children with node (b). throws cycle_exception if swap would create a cycle in tree (e.g. if node is ancestor of (b))

void graft(node_type& src) – removes (src) from its current location and appends to the nodes children. Throws cycle_exception if operation would create cycle in the tree.
void graft(tree_type& src) – graft (src).root()

bool operator==(const node_type& rhs) const – true if node is equal to (rhs). Two nodes are equal if their data instances are equal, and if their child nodes are lexicographically equal (as defined by iterating begin() to end()).
bool operator!=(const node_type& rhs) const

bool operator<(const node_type& rhs) const – true if node is less than (rhs). Node (a) is less than (b) if a.data() < b.data(), otherwise if the children of (a) are lexicographically less than children of (b) (iterating begin() to end()).
bool operator>(const node_type& rhs) const
bool operator<=(const node_type& rhs) const
bool operator>=(const node_type& rhs) const

iterator begin() – iteration over child nodes (random access)
const_iterator begin() const
iterator end()
const_iterator end() const

bf_iterator bf_begin() – iteration over nodes of subtree: breadth first traversal
const_bf_iterator bf_begin() const
bf_iterator bf_end()
const_bf_iterator bf_end() const

df_pre_iterator df_pre_begin() – iteration over nodes of subtree: depth first pre order traversal
const_df_pre_iterator df_pre_begin() const
df_pre_iterator df_pre_end()
const_df_pre_iterator df_pre_end() const

df_post_iterator df_post_begin() – iteration over nodes of subtree: depth first post order traversal
const_df_post_iterator df_post_begin() const
df_post_iterator df_post_end()
const_df_post_iterator df_post_end() const

Clone this wiki locally