# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1435089137 18000
# Node ID 028689700a4713c5971279956876c68112949f3e
# Parent  1198fe3684a6ec74b5a65d7165b828c27d3ec28b
Updated Queue to have a const_iterator too and to support a copy constructor (problem 1.3.41

diff -r 1198fe3684a6 -r 028689700a47 algs4-c++/src/Queue.cpp
--- a/algs4-c++/src/Queue.cpp	Tue Jun 23 12:28:03 2015 -0500
+++ b/algs4-c++/src/Queue.cpp	Tue Jun 23 14:52:17 2015 -0500
@@ -25,6 +25,13 @@
         std::cout << *iter << std::endl;
         }
 
+    Queue<long> q2( queue );
+    std::cout << "Copied queue to q2.  q2 has " << q2.size() << " entries." << std::endl;
+    for ( auto iter = q2.begin(); iter != q2.end(); ++iter ) {
+        std::cout << *iter << std::endl;
+        }
+
+
     std::cout << "Dequeuing entries..." << std::endl;
 
     while ( ! queue.is_empty() ) {
@@ -34,5 +41,9 @@
 
     std::cout << "Queue has " << queue.size() << " entries." << std::endl;
 
+
+    // Silently empty q2 to avoid the assertion in the destructor.
+    while ( ! q2.is_empty() )
+        q2.dequeue();
     }
 
diff -r 1198fe3684a6 -r 028689700a47 algs4-c++/src/Queue.hpp
--- a/algs4-c++/src/Queue.hpp	Tue Jun 23 12:28:03 2015 -0500
+++ b/algs4-c++/src/Queue.hpp	Tue Jun 23 14:52:17 2015 -0500
@@ -5,6 +5,7 @@
 
 #include <cstddef>
 #include <cassert>
+#include <iterator>
 
 template <typename T>
 class Queue {
@@ -21,9 +22,7 @@
 public:
 
     ////////////////////////////////////
-    class iterator;
-    friend class iterator;
-    class iterator {
+    class iterator : public std::iterator<std::forward_iterator_tag, T> {
 
     public:
 
@@ -42,9 +41,31 @@
 
     ////////////////////////////////////
 
+    class const_iterator : public std::iterator<std::forward_iterator_tag, T> {
+
+    public:
+
+        const_iterator( const Node *c );
+
+        const_iterator& operator++();
+        const_iterator operator++(int);
+
+        const T operator*();
+        bool operator!=( typename Queue<T>::const_iterator );
+
+    private:
+
+        const Node *curr;
+        };
+
+    ////////////////////////////////////
+
     Queue( void );
     ~Queue( void );
 
+    // 1.3.41 Copy constructor.
+    Queue( const Queue<T> &q );
+
     void enqueue( T &item );
     T dequeue( void );
 
@@ -53,6 +74,8 @@
 
     iterator begin( void );
     iterator end( void );
+    const_iterator begin( void ) const;
+    const_iterator end( void ) const;
 
 
 private:
@@ -71,6 +94,19 @@
     last (nullptr)
     {
     }
+
+// 1.3.41
+template <typename T>
+Queue<T>::Queue( const Queue<T> &q ) :
+    N (0),
+    first (nullptr),
+    last (nullptr)
+    {
+    for ( auto it = q.begin(); it != q.end(); ++it ) {
+        T item = *it;    
+        this->enqueue( item );
+        }
+    }
     
 template <typename T>
 Queue<T>::~Queue( void ) {
@@ -136,6 +172,16 @@
     return Queue<T>::iterator( nullptr );
     }
 
+template <typename T>
+typename Queue<T>::const_iterator Queue<T>::begin( void ) const {
+    return Queue<T>::const_iterator( first );
+    }
+
+template <typename T>
+typename Queue<T>::const_iterator Queue<T>::end( void ) const {
+    return Queue<T>::const_iterator( nullptr );
+    }
+
 
 ////////////////////////////////////////////////////////////////////////////////
 
@@ -173,6 +219,42 @@
     return this->curr != other.curr;
     }
 
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+Queue<T>::const_iterator::const_iterator( const Node *c ) :
+    curr (c)
+    {
+    }
+
+template <typename T>
+typename Queue<T>::const_iterator & Queue<T>::const_iterator::operator++() {
+    if ( this->curr != nullptr ) {
+        this->curr = this->curr->next;
+        }
+    return *this;
+    }
+
+template <typename T>
+typename Queue<T>::const_iterator Queue<T>::const_iterator::operator++( int ) {
+    auto t = Queue<T>::const_iterator( *this );
+
+    if ( this->curr != nullptr ) {
+        this->curr = this->curr->next;
+        }
+    return t;
+    }
+
+template <typename T>
+const T Queue<T>::const_iterator::operator*() {
+    return this->curr->item;
+    }
+
+template <typename T>
+bool Queue<T>::const_iterator::operator!=( typename Queue<T>::const_iterator other ) {
+    return this->curr != other.curr;
+    }
+
 
 #endif