The Tree Container Library

The sequential_tree interface includes the common interface . Although the sequential_tree doesn't have some of the same operations available to only associative trees, sequential_tree has some additional operations of it's own. Those operations are described below. The documentation below applies to TCL versions 3.50 and higher. The latest version of the TCL can be downloaded from the TCL download page.

Inserting Nodes

• void push_back(const stored_type& element)
  Inserts element as the last child of the parent in which it's called. This operation does not return an iterator, for the sake of STL compatibility. If you need to perform the same operation, but want an iterator returned pointing to the newly inserted node, use the common insert(stored_type&) operation.
  Complexity: Logarithmic
• iterator insert(const_iterator pos, const stored_type& element)
  Inserts an element before pos. Caller must insure pos is in a valid range. Returns an iterator pointing to the inserted node, if successful, end() if not.
  Complexity: Logarithmic
• iterator insert(const stored_type& element)
  Inserts element at the end of the node's children.
  Equivalent to insert(end(), element)
  Complexity: Logarithmic
• iterator insert(const_iterator pos, const tree_type& tree_obj)
  Inserts a tree_node and it's descendants before pos. Caller must insure pos is in a valid range. Returns an iterator pointing to the inserted top node of the tree if successful, end() if not.
  Complexity: Logarithmic
• iterator insert(const tree_type& tree_obj)
  Inserts tree_obj at the end of the node's children.
  Equivalent to insert(end(), tree_obj)
  Complexity: Logarithmic
• void insert(const_iterator pos, size_type num, const stored_type& element)
  Inserts num copies of element before pos. Caller must insure that pos is within a valid range.
  Complexity: Logarithmic
• void insert(const_iterator pos, input_iterator it_beg, input_iterator it_end)
  Inserts the elements in the range [it_beg, it_end) before pos. Caller must insure pos is within a valid range. input_iterator can be an iterator of a STL container of a TCL container. If a TCL container, input_iterator can either be a child or descendant iterator.
  Complexity: Logarithmic

Setting Node State

• void set(const stored_type& element)
  Set's the node's stored_type value to element. This operation is not available to associative tree's, since it may modify the 'key' value of the node, and invalidate the natural node order of associative trees.
  Complexity: Constant
• void set(const tree_type& tree_obj)
  Replaces the node with tree_obj. The previous node's contents, including any children and descendants, are erased and replace with the new tree's/node's contents, including any children and descendants.
  Complexity: Logarithmic

Removing Nodes

• void pop_back()
  Removes the last child node. Caller must insure there is at least one child node.
  Complexity: Logarithmic

Child Node Access

• tree_type& operator [](int index)
  Returns the child node specified by index.
  Throws std::out_of_range if the index is invalid.
  Complexity: Constant
• const tree_type& operator [](int index) const
  Returns a const reference to the child node specified by index.
  Throws std::out_of_range if the index is invalid.
  Complexity: Constant
• tree_type& front()
const tree_type& front() const
  Returns the first child node. Caller must insure there is at least one child node.
  Complexity: Constant
• tree_type& back()
const tree_type& back() const
  Returns the last child node. Caller must insure there is at least one child node.
  Complexity: Constant

Sorting child nodes

• void sort()
  Sorts the child nodes using the less-than operator of stored_type. This operator must be defined for stored type to use this operation. Sorts only the children within the node which it's called.
  Complexity: Logarithmic
• void sort(const pPred& predicate)
  Sorts the child nodes using the passed predicate function. The predicate function must have the signature:
  void predicate(const stored_type& lhs, const stored_type& rhs)
  Sorts only the children within the node which it's called.
  Complexity: Logarithmic
• template<typename T> void sort(const T& function_object)
  Sorts the child nodes using the function object. The function object should define the call operator with the signature as below.
  bool operator ()(const stored_type& lhs, const stored_type& rhs) const
  Sorts only the children within the node which it's called.
  Complexity: Logarithmic

Sorting descendant nodes

• void sort_descendants()
  Sorts the descendant nodes using the less-than operator of stored_type. This operator must be defined for stored type to use this operation. Sorts all descendants of the node which it's called.
  Complexity: Logarithmic
• void sort_descendants(const pPred& predicate)
  Sorts the descendant nodes using the passed predicate function. The predicate function must have the signature:
  void predicate(const stored_type& lhs, const stored_type& rhs)
  Sorts all descendants of the node which it's called.
  Complexity: Logarithmic
• template<typename T> void sort_descendants(const T& function_object)
  Sorts the descendant nodes using the function object. The function object should define the call operator with the signature as below.
  bool operator ()(const stored_type& lhs, const stored_type& rhs) const
  Sorts all descendants of the node which it's called.
  Complexity: Logarithmic

Capacity Operations

• void reserve(size_type sz)
  Reserves internal memory for at least sz nodes.
  Complexity: Logarithmic
• size_type capacity()
  Returns the number of child nodes the node may contain without reallocating memory.
  Complexity: Logarithmic