title: c++ how implement iterator for a doubly linked list
body: <p>I am using this text book</p>
  
  <p><a href="http://cpp.datastructures.net" rel="nofollow">http://cpp.datastructures.net</a></p>
  
  <p>chapter 5 iterator usage: </p>
  
  <p><a href="http://cpp.datastructures.net/source/ch05/CPP/IteratorPrint.cpp-DSACiterator.html" rel="nofollow">http://cpp.datastructures.net/source/ch05/CPP/IteratorPrint.cpp-DSACiterator.html</a></p>
  
  <p>here is how i implement it (the ObjectIterator class)</p>
  
  <pre><code>#include &lt;iostream&gt;
  
  using namespace std;
  
  class PositionException {
  protected:
      string message;
  public:
      PositionException(const string &amp;m) {
          message = m;
      }
      void print() {
          cout &lt;&lt; message &lt;&lt; endl;
      }
  };
  
  
  template &lt;typename T&gt;
  
  class NodeList {
  
  protected:
  
      struct Node {
          Node *prev;
          Node *next;
          T item;
          Node(T i = T(), Node *p = NULL, Node *n = NULL) : item(i), prev(p), next(n) {}
  
      };
  
  
      typedef Node * NodePtr;
  
  public:
      class Position {
      protected:
          NodePtr node;
      public:
          bool isNull() {
              return node == NULL;
          }
          Position(NodePtr n = NULL) : node(n) {}
          T&amp; element() {
              return node-&gt;item;
          }
  
          friend class NodeList;
      };
  
  
      class ObjectIterator {
      protected:
          NodePtr node;
      public:
          ObjectIterator(NodePtr n = NULL) : node(n) {}
  
          bool hasNext() {
  
              if (node-&gt;next == NULL) {
                  return false;
              }
  
              if (node-&gt;next-&gt;next == NULL) {
                  return false;
              }
              return true;
          }
          ObjectIterator next() {
              return ObjectIterator(node-&gt;next);
          }
          T&amp; element() {
              return node-&gt;item;
          }
          friend class NodeList;
  
  
      };
  
  protected:
      int sz;
      NodePtr header;
      NodePtr trailer;
  
  public:
      NodeList() {
          header = new Node();
          trailer = new Node();
          header-&gt;next = trailer;
          trailer-&gt;prev = header;
          sz = 0;
      }
  
      bool isEmpty() const {
          return size() == 0;
      }
      int size() const {
          return sz;
      }
  
      bool isFirst(const Position&amp; p) const {
          return p.node-&gt;prev == header;
      }
      bool isLast(const Position&amp; p) const {
          return p.node-&gt;next = trailer;
      }
  
  
      Position first() const {
          if (isEmpty()) {
              throw PositionException("no first for empty list");
          }
          return Position(header-&gt;next);
      }
  
      Position last() const {
          if (isEmpty()) {
              throw PositionException("no last for emtpy list");
          }
          return Position(trailer-&gt;prev);
      }
  
  
      Position before(const Position&amp; p) const{
          if (p.node-&gt;prev == header) {
              throw PositionException("already the first element, nothing before it");
          }
          return Position(p.node-&gt;prev);
      }
  
      Position after(const Position&amp; p) const{
          if (p.node-&gt;next == trailer) {
              throw PositionException("already the last element, nothing after it");
          }
          return Position(p.node-&gt;next);
      }
  
  
  
  
      Position insertAfter(const Position&amp; p, const T&amp; o) {
          NodePtr node = new Node(o, p.node, p.node-&gt;next);
          p.node-&gt;next-&gt;prev = node;
          p.node-&gt;next = node;
          sz++;
          return Position(node);
      }
  
      Position insertBefore(const Position&amp; p, const T&amp; o) {
          NodePtr node = new Node(o, p.node-&gt;prev, p.node);
          p.node-&gt;prev-&gt;next = node;
          p.node-&gt;prev = node;
          sz++;
          return Position(node);
      }
  
      void remove(const Position&amp; p) {
          p.node-&gt;prev-&gt;next = p.node-&gt;next;
          p.node-&gt;next-&gt;prev = p.node-&gt;prev;
  
          sz--;
          delete p.node;
      }
  
      void removeFirst() {
          remove(first());
      }
  
      void removeLast() {
          remove(last());
      }
  
  
      void replaceElement(const Position&amp; p, const T&amp; element) {
          if (p.isNull()) {
              throw PositionException("p is null");
          }
          p.node-&gt;item = element;
      }
  
      Position insertFirst(const T&amp; o) {
          NodePtr node = new Node(o, header, header-&gt;next);
          header-&gt;next-&gt;prev = node;
          header-&gt;next = node;
          sz++;
          return Position(node);
      }
  
      Position insertLast(const T&amp; o) {
          NodePtr node = new Node(o, trailer-&gt;prev, trailer);
          trailer-&gt;prev-&gt;next = node;
          trailer-&gt;prev = node;
          sz++;
          return Position(node);
      }
  
      void copyFrom(const NodeList&lt;T&gt;&amp; nl) {
          sz = nl.sz;
  
          if (nl.sz &gt; 0) {
              Position p0 = nl.first();
              Position p = insertFirst(p0.node-&gt;item);
  
              while (!nl.isLast(p0)) {
                  p0 = nl.after(p0);
                  insertAfter(p, p0.node-&gt;item);
              }
          }
      }
  
      void emptyList() {
          while (!isEmpty()) {
              removeFirst();
          }
      }
  
      ~NodeList() {
          emptyList();
          delete header;
          delete trailer;
      }
  
      NodeList&lt;T&gt;&amp; operator=(const NodeList&lt;T&gt;&amp; nl) {
          emptyList();
          copyFrom(nl);
      }
  
      NodeList(const NodeList&lt;T&gt;&amp; nl) {
          emptyList();
          copyFrom(nl);
      }
  
      void print() {
          cout &lt;&lt; "size is: " &lt;&lt; size() &lt;&lt; endl;
  
          if (size() &gt; 0) {
              ObjectIterator i = elements();
              while (i.hasNext()) {
                  cout &lt;&lt; i.element() &lt;&lt; "\t";
                  i = i.next();
              }
              cout &lt;&lt; endl;
          }
      }
  
  
      ObjectIterator elements() {
          if (isEmpty()) {
              throw PositionException("iterator error: empty");
          }
          return ObjectIterator(header-&gt;next);
      }
  
      void swapItems(const Position&amp; p1, const Position&amp; p2) {
          T temp = p1.node-&gt;item;
          p1.node-&gt;item = p2.node-&gt;item;
          p2.node-&gt;item = temp;
  
      }
  
  };
  </code></pre>
  
  <p>If i don't use the iterator, the following code for printing is correct</p>
  
  <pre><code>void print() {
      if (size() &gt; 0) {
  
          NodePtr n = header-&gt;next;
          while (n != trailer) {
              cout &lt;&lt; n-&gt;item &lt;&lt; "\t";
              n = n-&gt;next;
          }
  
          cout &lt;&lt; endl;
      }
  
  }
  </code></pre>
  
  <p>If I use the iterator for the print function</p>
  
  <pre><code>void print() {
      cout &lt;&lt; "size is: " &lt;&lt; size() &lt;&lt; endl;
  
      if (size() &gt; 0) {
          ObjectIterator i = elements();
          while (i.hasNext()) {
              cout &lt;&lt; i.element() &lt;&lt; "\t";
              i = i.next();
          }
          cout &lt;&lt; endl;
      }
  }
  </code></pre>
  
  <p>one of the node is missing. 
  The book does not provide the correct way to implement the iterator</p>