bslalg_bidirectionallink Component

Provide a basic link type for building doubly-linked lists. More...

Namespaces
namespace	bslalg

Detailed Description

Outline

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

Purpose:: Provide a basic link type for building doubly-linked lists.

Classes:

bslalg::BidirectionalLink

A node in a doubly-linked list

See also:: Component bslalg_bidirectionallinklistutil, Component bslalg_hashtableimputil

Description:: This component provides a single POD-like class, BidirectionalLink, used to represent a node in a doubly-linked list. A BidirectionalLink provides the address to its preceding node, and the address of its successor node. A null-pointer value for either address signifies the end of the list. BidirectionalLink does not, however, contain "payload" data (e.g., a value), as it is intended to work with generalized list operations (see bslalg_bidirectionallinklistutil). Clients creating a doubly-linked list must define their own node type that incorporates BidirectionalLink (generally via inheritance), and that maintains the "value" stored in that node.

: -----------------------------------------------------------------------------

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, it will be called MyList.

First, we create the MyNode class, which derives from the BidirectionalLink class to carry a PAYLOAD object.

  template <class PAYLOAD>
  class MyNode : public bslalg::BidirectionalLink {
    public:
      // PUBLIC TYPES
      typedef PAYLOAD  ValueType;

    private:
      // DATA
      ValueType     d_value;

    private:
      // NOT IMPLEMENTED
      MyNode();
      MyNode(const MyNode&);
      MyNode& operator=(const MyNode&);

    public:
      // CREATOR
      ~MyNode() {}
          // Destroy this object.

      // MANIPULATOR
      ValueType& value() { return d_value; }
          // Return a reference to the modifiable value stored in this node.

      // ACCESSOR
      const ValueType& value() const { return d_value; }
          // Return a reference to the non-modifiable value stored in this
          // node.
  };

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

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

  template <class PAYLOAD>
  class MyList_Iterator {
      // PRIVATE TYPES
      typedef MyNode<PAYLOAD> Node;

      // DATA
      Node *d_node;

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

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

      // MANIPULATORS
      MyList_Iterator operator++();

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

Then, we define our MyList class, with MyList::Iterator being a public typedef of MyList_Iterator. For brevity, we will omit a lot of functionality that a full, general-purpose list class would have, implementing only what we will need for this example.

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

  template <class PAYLOAD>
  class MyList {
      // PRIVATE TYPES
      typedef MyNode<PAYLOAD> Node;

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

    private:
      // DATA
      Node             *d_begin;
      Node             *d_end;
      bslma::Allocator *d_allocator_p;

    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();
  };

Next, we implement the functions for the iterator type.

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

  // MANIPULATORS
  template <class PAYLOAD>
  MyList_Iterator<PAYLOAD> MyList_Iterator<PAYLOAD>::operator++()
  {
      d_node = (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);
  }

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();

          d_allocator_p->deleteObjectRaw(toDelete);
      }
  }

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

  template <class PAYLOAD>
  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;
      }

      d_allocator_p->deleteObject(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_bidirectionallink [Package bslalg]

Namespaces

Detailed Description

Component bslalg_bidirectionallink
[Package bslalg]