Component bslstl_treeiterator [Package bslstl]

Provide an STL compliant iterator for a tree of TreeNode objects. More...

Namespaces
namespace	bslstl

---

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage
    • Example 1: Navigating a Tree Using TreeIterator

Purpose:

Provide an STL compliant iterator for a tree of TreeNode objects.

Classes:

bslstl::TreeIterator

an STL compliant bidirectional binary tree iterator

See also:

Component bslstl_treenode, Component bslalg_rbtreeutil, Component bslstl_map

Description:

This component provides an STL-compliant bidirectional iterator over a binary tree of bslstl::TreeNode objects. The requirements of a bidirectional STL iterator are outlined in the C++11 standard in section [24.2.6] under the tag [bidirectional.iterators]. A TreeIterator object is parameterized on VALUE, NODE, and DIFFERENCE_TYPE. The parameterized VALUE indicates the type of the value value to which this iterator provides a references, and may be const-qualified for const-iterators. The parameterized NODE indicates the type of the node objects in this tree. Note that NODE is not necessarily TreeNode<VALUE> as VALUE may be const-qualified. Finally, the parameterized DIFFERENCE_TYPE determines the, standard required, difference_type for the iterator. NODE must derives from bslalg::RbTreeNode, and contains a value method that returns a reference providing modifiable access to a type that is convertible to the parameterized VALUE (e.g., a bslstl::TreeNode object).

Usage:

In this section we show intended use of this component.

Example 1: Navigating a Tree Using TreeIterator:

In the following example we create a simple tree and then use a TreeIterator to navigate its elements.

First, we define a type IntNode for the nodes of our tree. IntNode inherits from bslalg::RbTreeNode (allowing it to be operated on by bslalg::RbTreeUtil), and supplies an integer payload:

  class IntNode : public bslalg::RbTreeNode {
      // DATA
      int d_value;  // actual value represented by the node

    public:
      // MANIPULATORS
  int& value() { return d_value; }
      // Return a reference providing modifiable access to the 'value' of
      // this object.

  // ACCESSORS
  const int& value() const { return d_value; }
      // Return a reference providing non-modifiable access to the
      // 'value' of this object.
  };

Then, we define a comparison function for IntNode objects. This type is designed to be supplied to functions in bslalg::RbTreeUtil:

  class IntNodeComparator {
    public:
      // CREATORS
      IntNodeComparator() {}
          // Create a node-value comparator.

      // ACCESSORS
      bool operator()(const bslalg::RbTreeNode& node, int value) const {
          return static_cast<const IntNode&>(node).value() < value;
      }

      bool operator()(int value, const bslalg::RbTreeNode& node) const {
         return value < static_cast<const IntNode&>(node).value();
      }
  };

Next, we define the signature of the example function where we will navigate a tree using a TreeIterator:

  void exampleTreeNavigationFunction()
  {

Then, we define a bslalg::RbTreeAnchor object to hold our tree, and a series of nodes that we will use to populate the tree:

      enum { NUM_NODES = 5 };

      bslalg::RbTreeAnchor tree;
      IntNode              nodes[NUM_NODES];

Next, we assign values to each of the nodes and insert them into tree using bslalg::RbTreeUtil, supplying the insert function an instance of the comparator we defined earlier:

      for (int i = 0; i < NUM_NODES; ++i) {
          nodes[i].value() = i;
          bslalg::RbTreeUtil::insert(&tree, IntNodeComparator(), &nodes[i]);
      }

      assert(5 == tree.numNodes());

Then, we create a type alias for a TreeIterator providing non-modifiable access to elements in the tree. Note that in this instance, the iterator must provide non-modifiable access as modifying the key value for a node would invalidate ordering of the binary search tree:

      typedef TreeIterator<const int, IntNode, std::ptrdiff_t>
                                                           ConstTreeIterator;

Now, we create an instance of the TreeIterator and use it to navigate the elements of tree, printing their values to the console:

      ConstTreeIterator iterator(tree.firstNode());
      ConstTreeIterator endIterator(tree.sentinel());
      for (; iterator != endIterator; ++iterator) {
          printf("Node value: %d\n", *iterator);
      }
  }

Finally, we observe the following console output:

  Node value: 0
  Node value: 1
  Node value: 2
  Node value: 3
  Node value: 4