bslalg_bidirectionallink

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

bslalg_bidirectionallinklistutil, 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) {}
     //! MyList_Iterator(const MyList_Iterator& original) = default;
     //! MyList_Iterator& operator=(const MyList_Iterator& other) = default;
     //! ~MyList_Iterator() = default;
 
     // 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);