bslstl_treenode Component

Provide a POD-like tree node type holding a parameterized value. More...

Namespaces
namespace	bslstl

Detailed Description

Outline

Purpose
Classes
Description
- Usage
  - Example 1: Allocating and Deallocating TreeNode Objects.
  - Example 2: Creating a Simple Tree of TreeNode Objects.

Purpose:: Provide a POD-like tree node type holding a parameterized value.

Classes:

bslstl::TreeNode

a tree node holding a parameterized value

See also:: bslstl_treenodefactory, Component bslstl_set, Component bslstl_map

Description:

This component provides a single POD-like class, TreeNode, used to represent a node in a red-black binary search tree holding a value of a parameterized type. A TreeNode inherits from bslalg::RbTreeNode, so it may be used with bslalg::RbTreeUtil functions, and adds an attribute value of the parameterized VALUE. The following inheritance hierarchy diagram shows the classes involved and their methods:

    ,----------------.
   ( bslstl::TreeNode )
    `----------------'
             |       value
             V
   ,------------------.
  ( bslalg::RbTreeNode )
   `------------------'
                   ctor
                   dtor
                   makeBlack
                   makeRed
                   setParent
                   setLeftChild
                   setRightChild
                   setColor
                   toggleColor
                   parent
                   leftChild
                   rightChild
                   isBlack
                   isRed
                   color

This class is "POD-like" to facilitate efficient allocation and use in the context of a container implementation. In order to meet the essential requirements of a POD type, both this class and bslalg::RbTreeNode do not define a constructor or destructor. The manipulator, value, returns a modifiable reference to the object that may be constructed in-place by the appropriate bsl::allocator_traits object.

Usage:: In this section we show intended usage of this component.

Example 1: Allocating and Deallocating TreeNode Objects.:: In the following example we define a factory class for allocating and destroying TreeNode objects.

First, we define the interface for the class NodeFactory:

  template <class VALUE, class ALLOCATOR>
  class NodeFactory {

The parameterized ALLOCATOR is intended to allocate objects of the parameterized VALUE, so to use it to allocate objects of TreeNode<VALUE> we must rebind it to the tree node type. Note that in general, we use allocator_traits to perform actions using an allocator (including the rebind below):

      // PRIVATE TYPES
      typedef typename bsl::allocator_traits<ALLOCATOR>::template
                             rebind_traits<TreeNode<VALUE> > AllocatorTraits;
      typedef typename AllocatorTraits::allocator_type       NodeAllocator;

      // DATA
      NodeAllocator d_allocator;  // rebound tree-node allocator

      // NOT IMPLEMENTED
      NodeFactory(const NodeFactory&);
      NodeFactory& operator=(const NodeFactory&);

    public:
      // CREATORS
      NodeFactory(const ALLOCATOR& allocator);
          // Create a tree node-factory that will use the specified
          // 'allocator' to supply memory.

      // MANIPULATORS
      TreeNode<VALUE> *createNode(const VALUE& value);
          // Create a new 'TreeNode' object holding the specified 'value'.

      void deleteNode(bslalg::RbTreeNode *node);
          // Destroy and deallocate the specified 'node'.  The behavior is
          // undefined unless 'node' is the address of a
          // 'TreeNode<VALUE>' object.
  };

Now, we implement the NodeFactory type:

  template <class VALUE, class ALLOCATOR>
  inline
  NodeFactory<VALUE, ALLOCATOR>::NodeFactory(const ALLOCATOR& allocator)
  : d_allocator(allocator)
  {
  }

We implement the createNode function by using the rebound allocator_traits for our allocator to in-place copy-construct the supplied value into the value data member of our result node object. Note that TreeNode is a POD-like type, without a constructor, so we do not need to call its constructor here:

  template <class VALUE, class ALLOCATOR>
  inline
  TreeNode<VALUE> *
  NodeFactory<VALUE, ALLOCATOR>::createNode(const VALUE& value)
  {
      TreeNode<VALUE> *result = AllocatorTraits::allocate(d_allocator, 1);
      AllocatorTraits::construct(d_allocator,
                                 bsls::Util::addressOf(result->value()),
                                 value);
      return result;
  }

Finally, we implement the function deleteNode. Again, we use the rebound allocator_traits for our tree node type, this time to destroy the value date member of node, and then to deallocate its footprint. Note that TreeNode is a POD-like type, so we do not need to call its destructor here:

  template <class VALUE, class ALLOCATOR>
  inline
  void NodeFactory<VALUE, ALLOCATOR>::deleteNode(bslalg::RbTreeNode *node)
  {
      TreeNode<VALUE> *treeNode = static_cast<TreeNode<VALUE> *>(node);
      AllocatorTraits::destroy(d_allocator,
                               bsls::Util::addressOf(treeNode->value()));
      AllocatorTraits::deallocate(d_allocator, treeNode, 1);
  }

Example 2: Creating a Simple Tree of TreeNode Objects.:: In the following example we create a container-type Set for holding a set of values of a parameterized VALUE.

First, we define a comparator for VALUE of TreeNode<VALUE> objects. This type is designed to be supplied to functions in bslalg::RbTreeUtil. Note that, for simplicity, this type uses operator< to compare values, rather than a client defined comparator type.

  template <class VALUE>
  class Comparator {
    public:
      // CREATORS
      Comparator() {}
          // Create a node-value comparator.

      // ACCESSORS
      bool operator()(const VALUE&              lhs,
                      const bslalg::RbTreeNode& rhs) const;
      bool operator()(const bslalg::RbTreeNode& lhs,
                      const VALUE&              rhs) const;
          // Return 'true' if the specified 'lhs' is less than (ordered
          // before) the specified 'rhs', and 'false' otherwise.  The
          // behavior is undefined unless the supplied 'bslalg::RbTreeNode'
          // object is of the derived 'TreeNode<VALUE>' type.
  };

Then, we implement the comparison methods of Comparator. Note that the supplied RbTreeNode objects must be static_cast to TreeNode<VALUE> to access their value:

  template <class VALUE>
  inline
  bool Comparator<VALUE>::operator()(const VALUE&              lhs,
                                     const bslalg::RbTreeNode& rhs) const
  {
      return lhs < static_cast<const TreeNode<VALUE>& >(rhs).value();
  }

  template <class VALUE>
  inline
  bool Comparator<VALUE>::operator()(const bslalg::RbTreeNode& lhs,
                                     const VALUE&              rhs) const
  {
      return static_cast<const TreeNode<VALUE>& >(lhs).value() < rhs;
  }

Now, having defined the requisite helper types, we define the public interface for Set. Note that for the purposes of illustrating the use of TreeNode a number of simplifications have been made. For example, this implementation provides only insert, remove, isMember, and numMembers operations:

  template <class VALUE,
            class ALLOCATOR = bsl::allocator<VALUE> >
  class Set {
      // PRIVATE TYPES
      typedef Comparator<VALUE>             ValueComparator;
      typedef NodeFactory<VALUE, ALLOCATOR> Factory;

      // DATA
      bslalg::RbTreeAnchor d_tree;     // tree of node objects
      Factory              d_factory;  // allocator for node objects

      // NOT IMPLEMENTED
      Set(const Set&);
      Set& operator=(const Set&);

    public:
      // CREATORS
      Set(const ALLOCATOR& allocator = ALLOCATOR());
          // Create an empty set.  Optionally specify a 'allocator' used to
          // supply memory.  If 'allocator' is not specified, a default
          // constructed 'ALLOCATOR' object is used.

      ~Set();
          // Destroy this set.

      // MANIPULATORS
      void insert(const VALUE& value);
          // Insert the specified value into this set.

      bool remove(const VALUE& value);
          // If 'value' is a member of this set, then remove it and return
          // 'true', and return 'false' otherwise.

      // ACCESSORS
      bool isElement(const VALUE& value) const;
          // Return 'true' if the specified 'value' is a member of this set,
          // and 'false' otherwise.

      int numElements() const;
          // Return the number of elements in this set.
  };

Now, we define the implementation of Set:

  // CREATORS
  template <class VALUE, class ALLOCATOR>
  inline
  Set<VALUE, ALLOCATOR>::Set(const ALLOCATOR& allocator)
  : d_tree()
  , d_factory(allocator)
  {
  }

  template <class VALUE, class ALLOCATOR>
  inline
  Set<VALUE, ALLOCATOR>::~Set()
  {
      bslalg::RbTreeUtil::deleteTree(&d_tree, &d_factory);
  }

  // MANIPULATORS
  template <class VALUE, class ALLOCATOR>
  void Set<VALUE, ALLOCATOR>::insert(const VALUE& value)
  {
      int comparisonResult;
      ValueComparator comparator;
      bslalg::RbTreeNode *parent =
          bslalg::RbTreeUtil::findUniqueInsertLocation(&comparisonResult,
                                                       &d_tree,
                                                       comparator,
                                                       value);
      if (0 != comparisonResult) {
          bslalg::RbTreeNode *node = d_factory.createNode(value);
          bslalg::RbTreeUtil::insertAt(&d_tree,
                                       parent,
                                       comparisonResult < 0,
                                       node);
      }
  }

  template <class VALUE, class ALLOCATOR>
  bool Set<VALUE, ALLOCATOR>::remove(const VALUE& value)
  {
      bslalg::RbTreeNode *node =
                  bslalg::RbTreeUtil::find(d_tree, ValueComparator(), value);
      if (node) {
          bslalg::RbTreeUtil::remove(&d_tree, node);
          d_factory.deleteNode(node);
      }
      return node;
  }

  // ACCESSORS
  template <class VALUE, class ALLOCATOR>
  inline
  bool Set<VALUE, ALLOCATOR>::isElement(const VALUE& value) const
  {
      ValueComparator comparator;
      return bslalg::RbTreeUtil::find(d_tree, comparator, value);
  }

  template <class VALUE, class ALLOCATOR>
  inline
  int Set<VALUE, ALLOCATOR>::numElements() const
  {
      return d_tree.numNodes();
  }

Notice that the definition and implementation of Set never directly uses the TreeNode type, but instead use it indirectly through Comparator, and NodeFactory, and uses it via its base-class bslalg::RbTreeNode.

Finally, we test our Set.

  Set<int> set;
  assert(0 == set.numElements());

  set.insert(1);
  assert(set.isElement(1));
  assert(1 == set.numElements());

  set.insert(1);
  assert(set.isElement(1));
  assert(1 == set.numElements());

  set.insert(2);
  assert(set.isElement(1));
  assert(set.isElement(2));
  assert(2 == set.numElements());

Component bslstl_treenode [Package bslstl]

Namespaces

Detailed Description

Component bslstl_treenode
[Package bslstl]