bslalg_bidirectionalnode Component

Provide a node holding a value in a doubly-linked list. More...

Namespaces
namespace	bslalg

Detailed Description

Outline

Purpose
Classes
Description
- Usage
  - Example 1: Creating and Using a List Template Class

Purpose:: Provide a node holding a value in a doubly-linked list.

Classes:

bslalg::BidirectionalNode

Node holding a value in a linked list

See also:: Component bslalg_bidirectionallink, Component bslalg_bidirectionallinklistutil, Component bslalg_hashtableimputil

Description:

This component provides a single POD-like class, bslalg::BidirectionalNode, used to represent a node in a doubly-linked (bidirectional) list holding a value of a parameterized type. A bslalg::BidirectionalNode publicly derives from bslalg::BidirectionalLink, so it may be used with bslalg::BidirectionalLinkListUtil functions, and adds an attribute value of the template parameter type VALUE. The following inheritance hierarchy diagram shows the classes involved and their methods:

                  ,-------------------------.
                 ( bslalg::BidirectionalNode )
                  `-------------------------'
                               |      value
                               |      (all CREATORS unimplemented)
                               V
                  ,-------------------------.
                 ( bslalg::BidirectionalLink )
                  `-------------------------'
                                      ctor
                                      dtor
                                      setNextLink
                                      setPreviousLink
                                      nextLink
                                      previousLink

This class is "POD-like" to facilitate efficient allocation and use in the context of container implementations. In order to meet the essential requirements of a POD type, neither this class nor bslalg::BidirectionalLink define a constructor or destructor. The manipulator, value, returns a modifiable reference to the stored object that may be constructed in-place, for example, by the appropriate bsl::allocator_traits methods. While not strictly a POD, this class is a standard-layout type according to the C++11 standard.

Usage:: This section illustrates intended usage of this component.

Example 1: Creating and Using a List Template Class:: Suppose we want to create a linked list template class called MyList.

First, we create an iterator helper class, which will eventually be defined as a nested type within the MyList class.

                              // ===============
                              // MyList_Iterator
                              // ===============

  template <class PAYLOAD>
  class MyList_Iterator {
      // This iterator is used to refer to positions within a list.

      // PRIVATE TYPES
      typedef bslalg::BidirectionalNode<PAYLOAD> Node;

      // DATA
      Node *d_node;    // Pointer to a node within a list.

      // FRIENDS
      template <class OTHER_PAYLOAD>
      friend bool operator==(MyList_Iterator<OTHER_PAYLOAD>,
                             MyList_Iterator<OTHER_PAYLOAD>);

    public:
      // CREATORS
      MyList_Iterator() : d_node(0) {}
      explicit
      MyList_Iterator(Node *node) : d_node(node) {}

      // MANIPULATORS
      MyList_Iterator operator++();

      // ACCESSORS
      const PAYLOAD& operator*() const { return d_node->value(); }
  };

 ============================================================================
                                FREE OPERATORS
 ----------------------------------------------------------------------------

  template <class PAYLOAD>
  bool operator==(MyList_Iterator<PAYLOAD> lhs,
                  MyList_Iterator<PAYLOAD> rhs);

  template <class PAYLOAD>
  bool operator!=(MyList_Iterator<PAYLOAD> lhs,
                  MyList_Iterator<PAYLOAD> rhs);

Then, we implement the functions for the iterator type.

                                  // ---------------
                                  // MyList_Iterator
                                  // ---------------

  // MANIPULATORS
  template <class PAYLOAD>
  inline
  MyList_Iterator<PAYLOAD> MyList_Iterator<PAYLOAD>::operator++()
  {
      d_node = static_cast<Node *>(d_node->nextLink());
      return *this;
  }

  template <class PAYLOAD>
  inline
  bool operator==(MyList_Iterator<PAYLOAD> lhs,
                  MyList_Iterator<PAYLOAD> rhs)
  {
      return lhs.d_node == rhs.d_node;
  }

  template <class PAYLOAD>
  inline
  bool operator!=(MyList_Iterator<PAYLOAD> lhs,
                  MyList_Iterator<PAYLOAD> rhs)
  {
      return !(lhs == rhs);
  }

Next, we define our MyList class, with MyList::Iterator being a public typedef of MyList_Iterator. For brevity, we will omit much of te that a full, general-purpose list class would have.

                                  // ======
                                  // MyList
                                  // ======

  template <class PAYLOAD>
  class MyList {
      // Doubly-linked list storing objects of type 'PAYLOAD'.

      // PRIVATE TYPES
      typedef bslalg::BidirectionalNode<PAYLOAD> Node;

    public:
      // PUBLIC TYPES
      typedef PAYLOAD                    ValueType;
      typedef MyList_Iterator<ValueType> Iterator;

      // DATA
      Node             *d_begin;          // First node, if any, in the list.
      Node             *d_end;            // Last node, if any, in the list.
      bslma::Allocator *d_allocator_p;    // Allocator used for allocating
                                          // and freeing nodes.

    public:
      // CREATORS
      explicit
      MyList(bslma::Allocator *basicAllocator = 0)
      : d_begin(0)
      , d_end(0)
      , d_allocator_p(bslma::Default::allocator(basicAllocator))
      {}

      ~MyList();

      // MANIPULATORS
      Iterator begin();
      Iterator end();
      void pushBack(const ValueType& value);
      void popBack();
  };

Then, we implement the functions for the MyList class:

                                  // ------
                                  // MyList
                                  // ------

  // CREATORS
  template <class PAYLOAD>
  MyList<PAYLOAD>::~MyList()
  {
      for (Node *p = d_begin; p; ) {
          Node *toDelete = p;
          p = (Node *) p->nextLink();

          bslma::DestructionUtil::destroy(&toDelete->value());
          d_allocator_p->deleteObjectRaw(
                         static_cast<bslalg::BidirectionalLink *>(toDelete));
      }
  }

  // MANIPULATORS
  template <class PAYLOAD>
  inline
  typename MyList<PAYLOAD>::Iterator MyList<PAYLOAD>::begin()
  {
      return Iterator(d_begin);
  }

  template <class PAYLOAD>
  inline
  typename MyList<PAYLOAD>::Iterator MyList<PAYLOAD>::end()
  {
      return Iterator(0);
  }

  template <class PAYLOAD>
  void MyList<PAYLOAD>::pushBack(const PAYLOAD& value)
  {
      Node *node = (Node *) d_allocator_p->allocate(sizeof(Node));
      node->setNextLink(0);
      node->setPreviousLink(d_end);
      bslalg::ScalarPrimitives::copyConstruct(&node->value(),
                                              value,
                                              d_allocator_p);

      if (d_end) {
          BSLS_ASSERT_SAFE(d_begin);

          d_end->setNextLink(node);
          d_end = node;
      }
      else {
          BSLS_ASSERT_SAFE(0 == d_begin);

          d_begin = d_end = node;
      }
  }

  template <class PAYLOAD>
  void MyList<PAYLOAD>::popBack()
  {
      BSLS_ASSERT_SAFE(d_begin && d_end);

      Node *toDelete = d_end;
      d_end = (Node *) d_end->previousLink();

      if (d_begin != toDelete) {
          BSLS_ASSERT_SAFE(0 != d_end);
          d_end->setNextLink(0);
      }
      else {
          BSLS_ASSERT_SAFE(0 == d_end);
          d_begin = 0;
      }

      bslma::DestructionUtil::destroy(&toDelete->value());
      d_allocator_p->deleteObjectRaw(
                         static_cast<bslalg::BidirectionalLink *>(toDelete));
  }

Next, in main, we use our MyList class to store a list of ints:

  MyList<int> intList;

Then, we declare an array of ints to populate it with:

  int intArray[] = { 8, 2, 3, 5, 7, 2 };
  enum { NUM_INTS = sizeof intArray / sizeof *intArray };

Now, we iterate, pushing ints to the list:

  for (const int *pInt = intArray; pInt < intArray + NUM_INTS; ++pInt) {
      intList.pushBack(*pInt);
  }

Finally, we use our Iterator type to traverse the list and observe its values:

  MyList<int>::Iterator it = intList.begin();
  assert(8 == *it);
  assert(2 == *++it);
  assert(3 == *++it);
  assert(5 == *++it);
  assert(7 == *++it);
  assert(2 == *++it);
  assert(intList.end() == ++it);

Component bslalg_bidirectionalnode [Package bslalg]

Namespaces

Detailed Description

Component bslalg_bidirectionalnode
[Package bslalg]