Mercurial > Algorithms__Sedgewick
changeset 24:028689700a47
Updated Queue to have a const_iterator too and to support a copy constructor (problem 1.3.41
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Tue, 23 Jun 2015 14:52:17 -0500 |
parents | 1198fe3684a6 |
children | 3cdac4c29445 |
files | algs4-c++/src/Queue.cpp algs4-c++/src/Queue.hpp |
diffstat | 2 files changed, 96 insertions(+), 3 deletions(-) [+] |
line diff
1.1 --- a/algs4-c++/src/Queue.cpp Tue Jun 23 12:28:03 2015 -0500 1.2 +++ b/algs4-c++/src/Queue.cpp Tue Jun 23 14:52:17 2015 -0500 1.3 @@ -25,6 +25,13 @@ 1.4 std::cout << *iter << std::endl; 1.5 } 1.6 1.7 + Queue<long> q2( queue ); 1.8 + std::cout << "Copied queue to q2. q2 has " << q2.size() << " entries." << std::endl; 1.9 + for ( auto iter = q2.begin(); iter != q2.end(); ++iter ) { 1.10 + std::cout << *iter << std::endl; 1.11 + } 1.12 + 1.13 + 1.14 std::cout << "Dequeuing entries..." << std::endl; 1.15 1.16 while ( ! queue.is_empty() ) { 1.17 @@ -34,5 +41,9 @@ 1.18 1.19 std::cout << "Queue has " << queue.size() << " entries." << std::endl; 1.20 1.21 + 1.22 + // Silently empty q2 to avoid the assertion in the destructor. 1.23 + while ( ! q2.is_empty() ) 1.24 + q2.dequeue(); 1.25 } 1.26
2.1 --- a/algs4-c++/src/Queue.hpp Tue Jun 23 12:28:03 2015 -0500 2.2 +++ b/algs4-c++/src/Queue.hpp Tue Jun 23 14:52:17 2015 -0500 2.3 @@ -5,6 +5,7 @@ 2.4 2.5 #include <cstddef> 2.6 #include <cassert> 2.7 +#include <iterator> 2.8 2.9 template <typename T> 2.10 class Queue { 2.11 @@ -21,9 +22,7 @@ 2.12 public: 2.13 2.14 //////////////////////////////////// 2.15 - class iterator; 2.16 - friend class iterator; 2.17 - class iterator { 2.18 + class iterator : public std::iterator<std::forward_iterator_tag, T> { 2.19 2.20 public: 2.21 2.22 @@ -42,9 +41,31 @@ 2.23 2.24 //////////////////////////////////// 2.25 2.26 + class const_iterator : public std::iterator<std::forward_iterator_tag, T> { 2.27 + 2.28 + public: 2.29 + 2.30 + const_iterator( const Node *c ); 2.31 + 2.32 + const_iterator& operator++(); 2.33 + const_iterator operator++(int); 2.34 + 2.35 + const T operator*(); 2.36 + bool operator!=( typename Queue<T>::const_iterator ); 2.37 + 2.38 + private: 2.39 + 2.40 + const Node *curr; 2.41 + }; 2.42 + 2.43 + //////////////////////////////////// 2.44 + 2.45 Queue( void ); 2.46 ~Queue( void ); 2.47 2.48 + // 1.3.41 Copy constructor. 2.49 + Queue( const Queue<T> &q ); 2.50 + 2.51 void enqueue( T &item ); 2.52 T dequeue( void ); 2.53 2.54 @@ -53,6 +74,8 @@ 2.55 2.56 iterator begin( void ); 2.57 iterator end( void ); 2.58 + const_iterator begin( void ) const; 2.59 + const_iterator end( void ) const; 2.60 2.61 2.62 private: 2.63 @@ -71,6 +94,19 @@ 2.64 last (nullptr) 2.65 { 2.66 } 2.67 + 2.68 +// 1.3.41 2.69 +template <typename T> 2.70 +Queue<T>::Queue( const Queue<T> &q ) : 2.71 + N (0), 2.72 + first (nullptr), 2.73 + last (nullptr) 2.74 + { 2.75 + for ( auto it = q.begin(); it != q.end(); ++it ) { 2.76 + T item = *it; 2.77 + this->enqueue( item ); 2.78 + } 2.79 + } 2.80 2.81 template <typename T> 2.82 Queue<T>::~Queue( void ) { 2.83 @@ -136,6 +172,16 @@ 2.84 return Queue<T>::iterator( nullptr ); 2.85 } 2.86 2.87 +template <typename T> 2.88 +typename Queue<T>::const_iterator Queue<T>::begin( void ) const { 2.89 + return Queue<T>::const_iterator( first ); 2.90 + } 2.91 + 2.92 +template <typename T> 2.93 +typename Queue<T>::const_iterator Queue<T>::end( void ) const { 2.94 + return Queue<T>::const_iterator( nullptr ); 2.95 + } 2.96 + 2.97 2.98 //////////////////////////////////////////////////////////////////////////////// 2.99 2.100 @@ -173,6 +219,42 @@ 2.101 return this->curr != other.curr; 2.102 } 2.103 2.104 +//////////////////////////////////////////////////////////////////////////////// 2.105 + 2.106 +template <typename T> 2.107 +Queue<T>::const_iterator::const_iterator( const Node *c ) : 2.108 + curr (c) 2.109 + { 2.110 + } 2.111 + 2.112 +template <typename T> 2.113 +typename Queue<T>::const_iterator & Queue<T>::const_iterator::operator++() { 2.114 + if ( this->curr != nullptr ) { 2.115 + this->curr = this->curr->next; 2.116 + } 2.117 + return *this; 2.118 + } 2.119 + 2.120 +template <typename T> 2.121 +typename Queue<T>::const_iterator Queue<T>::const_iterator::operator++( int ) { 2.122 + auto t = Queue<T>::const_iterator( *this ); 2.123 + 2.124 + if ( this->curr != nullptr ) { 2.125 + this->curr = this->curr->next; 2.126 + } 2.127 + return t; 2.128 + } 2.129 + 2.130 +template <typename T> 2.131 +const T Queue<T>::const_iterator::operator*() { 2.132 + return this->curr->item; 2.133 + } 2.134 + 2.135 +template <typename T> 2.136 +bool Queue<T>::const_iterator::operator!=( typename Queue<T>::const_iterator other ) { 2.137 + return this->curr != other.curr; 2.138 + } 2.139 + 2.140 2.141 #endif 2.142