Mercurial > Algorithms__Sedgewick
changeset 21:ec700842d182
MErged changes from home and server.
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Tue, 23 Jun 2015 10:17:43 -0500 |
| parents | 86281e8f24ba a149b424b4e2 |
| children | c2cbfdf528f6 |
| files | |
| diffstat | 15 files changed, 1064 insertions(+), 1122 deletions(-) [+] |
line diff
1.1 --- a/algs4-c++/src/Bag.cpp Mon Jun 22 15:38:25 2015 -0500 1.2 +++ b/algs4-c++/src/Bag.cpp Tue Jun 23 10:17:43 2015 -0500 1.3 @@ -1,182 +1,7 @@ 1.4 -// g++ -D BAG_MAIN -std=c++0x Bag.cpp 1.5 -// g++ -D BAG_MAIN -std=c++11 Bag.cpp 1.6 - 1.7 +// g++ -std=c++11 Bag.cpp 1.8 1.9 #include "Bag.hpp" 1.10 1.11 -#include <cassert> 1.12 -#include <cstddef> 1.13 - 1.14 -#include <iostream> 1.15 - 1.16 -template <typename T> 1.17 -Bag<T>::Bag( void ) : 1.18 - N (0), 1.19 - list (nullptr) 1.20 - { 1.21 - } 1.22 - 1.23 -template <typename T> 1.24 -Bag<T>::~Bag( void ) { 1.25 - // This will leak memory, won't it? 1.26 - while ( list ) { 1.27 - Node * next = list->next; 1.28 - delete list; 1.29 - list = next; 1.30 - } 1.31 - } 1.32 - 1.33 -template <typename T> 1.34 -void Bag<T>::add( T &item ) { 1.35 - Node * node = new Node(); 1.36 - node->item = item; 1.37 - node->next = list; 1.38 - list = node; 1.39 - N++; 1.40 - } 1.41 - 1.42 -template <typename T> 1.43 -bool Bag<T>::is_empty( void ) { 1.44 - return N == 0; 1.45 - } 1.46 - 1.47 -template <typename T> 1.48 -size_t Bag<T>::size( void ) { 1.49 - return N; 1.50 - } 1.51 - 1.52 -template <typename T> 1.53 -typename Bag<T>::iterator Bag<T>::begin( void ) { 1.54 - return Bag<T>::iterator( list ); 1.55 - } 1.56 - 1.57 -template <typename T> 1.58 -typename Bag<T>::iterator Bag<T>::end( void ) { 1.59 - return Bag<T>::iterator( nullptr ); 1.60 - } 1.61 - 1.62 - 1.63 -//////////////////////////////////////////////////////////////////////////////// 1.64 - 1.65 -template <typename T> 1.66 -Bag<T>::iterator::iterator( Node *c ) : 1.67 - curr (c) 1.68 - { 1.69 - } 1.70 - 1.71 -template <typename T> 1.72 -typename Bag<T>::iterator & Bag<T>::iterator::operator++() { 1.73 - if ( this->curr != nullptr ) { 1.74 - this->curr = this->curr->next; 1.75 - } 1.76 - return *this; 1.77 - } 1.78 - 1.79 -template <typename T> 1.80 -typename Bag<T>::iterator Bag<T>::iterator::operator++( int ) { 1.81 - auto t = Bag<T>::iterator( *this ); 1.82 - 1.83 - if ( this->curr != nullptr ) { 1.84 - this->curr = this->curr->next; 1.85 - } 1.86 - return t; 1.87 - } 1.88 - 1.89 -template <typename T> 1.90 -T Bag<T>::iterator::operator*() { 1.91 - return this->curr->item; 1.92 - } 1.93 - 1.94 -template <typename T> 1.95 -bool Bag<T>::iterator::operator!=( typename Bag<T>::iterator other ) { 1.96 - return this->curr != other.curr; 1.97 - } 1.98 - 1.99 -//////////////////////////////////////////////////////////////////////////////// 1.100 - 1.101 - 1.102 -#ifdef EXERCISES 1.103 - 1.104 -// 1.3.19 1.105 -// Returns the item if entry was found. If the entry did not exist, then the returned value is undefined. 1.106 -template <typename T> 1.107 -T Bag<T>::delete_bottom( void ) { 1.108 - Node *prev, *curr; 1.109 - T item; 1.110 - 1.111 - prev = nullptr; 1.112 - curr = list; 1.113 - if ( curr ) { 1.114 - while ( curr->next ) { 1.115 - prev = curr; 1.116 - curr = curr->next; 1.117 - } 1.118 - 1.119 - item = curr->item; 1.120 - delete curr; 1.121 - if ( prev ) 1.122 - prev->next = nullptr; 1.123 - else 1.124 - list = nullptr; 1.125 - 1.126 - N--; 1.127 - } 1.128 - 1.129 - return item; 1.130 - } 1.131 - 1.132 - 1.133 -// 1.3.20 1.134 -// Returns the item if entry was found. If the entry did not exist, then the returned value is undefined. 1.135 -template <typename T> 1.136 -T Bag<T>::remove( size_t k ) { 1.137 - Node *prev, *curr; 1.138 - size_t i=0; 1.139 - T item; 1.140 - 1.141 - prev = nullptr; 1.142 - curr = list; 1.143 - while ( curr && (i < k) ) { 1.144 - prev = curr; 1.145 - curr = curr->next; 1.146 - ++i; 1.147 - } 1.148 - 1.149 - if ( curr &&( i == k) ) { 1.150 - item = curr->item; 1.151 - if ( prev ) 1.152 - prev->next = curr->next; 1.153 - else 1.154 - list = curr->next;; 1.155 - delete curr; 1.156 - N--; 1.157 - } 1.158 - 1.159 - return item; 1.160 - } 1.161 - 1.162 -// 1.3.21 1.163 -// Returns true if the specified key is in the bag. 1.164 -template <typename T> 1.165 -bool Bag<T>::find( T key ) { 1.166 - Node *curr = list; 1.167 - 1.168 - while ( curr ) { 1.169 - if ( curr->item == key ) 1.170 - return true; 1.171 - curr = curr->next; 1.172 - } 1.173 - 1.174 - return false; 1.175 - } 1.176 - 1.177 -#endif 1.178 - 1.179 - 1.180 -//////////////////////////////////////////////////////////////////////////////// 1.181 - 1.182 -#ifdef BAG_MAIN 1.183 - 1.184 #include <iostream> 1.185 1.186 int main ( int argc, char **argv ) { 1.187 @@ -197,5 +22,3 @@ 1.188 } 1.189 1.190 } 1.191 - 1.192 -#endif
2.1 --- a/algs4-c++/src/Bag.hpp Mon Jun 22 15:38:25 2015 -0500 2.2 +++ b/algs4-c++/src/Bag.hpp Tue Jun 23 10:17:43 2015 -0500 2.3 @@ -1,16 +1,16 @@ 2.4 +// Linked list based bag after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2 2.5 + 2.6 #ifndef BAG_HPP 2.7 #define BAG_HPP 2.8 2.9 #include <cstddef> 2.10 2.11 -// Linked list based bag after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2 2.12 - 2.13 template <typename T> 2.14 class Bag { 2.15 2.16 private: 2.17 2.18 - //////////////////////////////////// 2.19 +//////////////////////////////////// 2.20 class Node { 2.21 public: 2.22 T item; 2.23 @@ -53,6 +53,12 @@ 2.24 iterator begin( void ); 2.25 iterator end( void ); 2.26 2.27 +#ifdef EXERCISES 2.28 + T delete_bottom( void ); 2.29 + T remove( size_t k ); 2.30 + bool find( T key ); 2.31 +#endif 2.32 + 2.33 private: 2.34 2.35 size_t N; 2.36 @@ -61,6 +67,172 @@ 2.37 }; 2.38 2.39 2.40 +//////////////////////////////////////////////////////////////////////////////// 2.41 + 2.42 + 2.43 +template <typename T> 2.44 +Bag<T>::Bag( void ) : 2.45 + N (0), 2.46 + list (nullptr) 2.47 + { 2.48 + } 2.49 + 2.50 +template <typename T> 2.51 +Bag<T>::~Bag( void ) { 2.52 + // This will leak memory, won't it? 2.53 + while ( list ) { 2.54 + Node * next = list->next; 2.55 + delete list; 2.56 + list = next; 2.57 + } 2.58 + } 2.59 + 2.60 +template <typename T> 2.61 +void Bag<T>::add( T &item ) { 2.62 + Node * node = new Node(); 2.63 + node->item = item; 2.64 + node->next = list; 2.65 + list = node; 2.66 + N++; 2.67 + } 2.68 + 2.69 +template <typename T> 2.70 +bool Bag<T>::is_empty( void ) { 2.71 + return N == 0; 2.72 + } 2.73 + 2.74 +template <typename T> 2.75 +size_t Bag<T>::size( void ) { 2.76 + return N; 2.77 + } 2.78 + 2.79 +template <typename T> 2.80 +typename Bag<T>::iterator Bag<T>::begin( void ) { 2.81 + return Bag<T>::iterator( list ); 2.82 + } 2.83 + 2.84 +template <typename T> 2.85 +typename Bag<T>::iterator Bag<T>::end( void ) { 2.86 + return Bag<T>::iterator( nullptr ); 2.87 + } 2.88 + 2.89 + 2.90 +//////////////////////////////////////////////////////////////////////////////// 2.91 + 2.92 +template <typename T> 2.93 +Bag<T>::iterator::iterator( Node *c ) : 2.94 + curr (c) 2.95 + { 2.96 + } 2.97 + 2.98 +template <typename T> 2.99 +typename Bag<T>::iterator & Bag<T>::iterator::operator++() { 2.100 + if ( this->curr != nullptr ) { 2.101 + this->curr = this->curr->next; 2.102 + } 2.103 + return *this; 2.104 + } 2.105 + 2.106 +template <typename T> 2.107 +typename Bag<T>::iterator Bag<T>::iterator::operator++( int ) { 2.108 + auto t = Bag<T>::iterator( *this ); 2.109 + 2.110 + if ( this->curr != nullptr ) { 2.111 + this->curr = this->curr->next; 2.112 + } 2.113 + return t; 2.114 + } 2.115 + 2.116 +template <typename T> 2.117 +T Bag<T>::iterator::operator*() { 2.118 + return this->curr->item; 2.119 + } 2.120 + 2.121 +template <typename T> 2.122 +bool Bag<T>::iterator::operator!=( typename Bag<T>::iterator other ) { 2.123 + return this->curr != other.curr; 2.124 + } 2.125 + 2.126 +//////////////////////////////////////////////////////////////////////////////// 2.127 + 2.128 + 2.129 +#ifdef EXERCISES 2.130 + 2.131 +// 1.3.19 2.132 +// Returns the item if entry was found. If the entry did not exist, then the returned value is undefined. 2.133 +template <typename T> 2.134 +T Bag<T>::delete_bottom( void ) { 2.135 + Node *prev, *curr; 2.136 + T item; 2.137 + 2.138 + prev = nullptr; 2.139 + curr = list; 2.140 + if ( curr ) { 2.141 + while ( curr->next ) { 2.142 + prev = curr; 2.143 + curr = curr->next; 2.144 + } 2.145 + 2.146 + item = curr->item; 2.147 + delete curr; 2.148 + if ( prev ) 2.149 + prev->next = nullptr; 2.150 + else 2.151 + list = nullptr; 2.152 + 2.153 + N--; 2.154 + } 2.155 + 2.156 + return item; 2.157 + } 2.158 + 2.159 + 2.160 +// 1.3.20 2.161 +// Returns the item if entry was found. If the entry did not exist, then the returned value is undefined. 2.162 +template <typename T> 2.163 +T Bag<T>::remove( size_t k ) { 2.164 + Node *prev, *curr; 2.165 + size_t i=0; 2.166 + T item; 2.167 + 2.168 + prev = nullptr; 2.169 + curr = list; 2.170 + while ( curr && (i < k) ) { 2.171 + prev = curr; 2.172 + curr = curr->next; 2.173 + ++i; 2.174 + } 2.175 + 2.176 + if ( curr &&( i == k) ) { 2.177 + item = curr->item; 2.178 + if ( prev ) 2.179 + prev->next = curr->next; 2.180 + else 2.181 + list = curr->next;; 2.182 + delete curr; 2.183 + N--; 2.184 + } 2.185 + 2.186 + return item; 2.187 + } 2.188 + 2.189 +// 1.3.21 2.190 +// Returns true if the specified key is in the bag. 2.191 +template <typename T> 2.192 +bool Bag<T>::find( T key ) { 2.193 + Node *curr = list; 2.194 + 2.195 + while ( curr ) { 2.196 + if ( curr->item == key ) 2.197 + return true; 2.198 + curr = curr->next; 2.199 + } 2.200 + 2.201 + return false; 2.202 + } 2.203 2.204 #endif 2.205 2.206 + 2.207 +#endif 2.208 +
3.1 --- a/algs4-c++/src/Deque.cpp Mon Jun 22 15:38:25 2015 -0500 3.2 +++ b/algs4-c++/src/Deque.cpp Tue Jun 23 10:17:43 2015 -0500 3.3 @@ -1,170 +1,8 @@ 3.4 -// g++ -D DEQUE_MAIN -std=c++0x Deque.cpp 3.5 -// g++ -D DEQUE_MAIN -std=c++11 Deque.cpp 3.6 +// g++ -std=c++11 Deque.cpp 3.7 3.8 3.9 #include "Deque.hpp" 3.10 3.11 -#include <cassert> 3.12 -#include <cstddef> 3.13 - 3.14 -#include <iostream> 3.15 - 3.16 -template <typename T> 3.17 -Deque<T>::Deque( void ) : 3.18 - N (0), 3.19 - first (nullptr), 3.20 - last (nullptr) 3.21 - { 3.22 - } 3.23 - 3.24 -template <typename T> 3.25 -Deque<T>::~Deque( void ) { 3.26 - assert( N == 0 ); // Catch the potential memory leak. 3.27 - while ( first ) { 3.28 - Node *next = first->next; 3.29 - delete first; 3.30 - first = next; 3.31 - } 3.32 - } 3.33 - 3.34 -template <typename T> 3.35 -void Deque<T>::push_right( T &item ) { 3.36 - Node * node = new Node(); 3.37 - node->item = item; 3.38 - node->next = nullptr; 3.39 - node->prev = nullptr; 3.40 - 3.41 - if ( last ) { 3.42 - last->next = node; 3.43 - node->prev = last; 3.44 - last = node; 3.45 - } 3.46 - else { 3.47 - last = first = node; 3.48 - } 3.49 - 3.50 - N++; 3.51 - } 3.52 - 3.53 -template <typename T> 3.54 -void Deque<T>::push_left( T &item ) { 3.55 - Node * node = new Node(); 3.56 - node->item = item; 3.57 - node->next = nullptr; 3.58 - node->prev = nullptr; 3.59 - 3.60 - if ( first ) { 3.61 - node->next = first; 3.62 - first->prev = node; 3.63 - first = node; 3.64 - } 3.65 - else { 3.66 - last = first = node; 3.67 - } 3.68 - 3.69 - N++; 3.70 - } 3.71 - 3.72 -template <typename T> 3.73 -T Deque<T>::pop_left( void ) { 3.74 - assert( N > 0 ); 3.75 - 3.76 - T item = first->item; 3.77 - 3.78 - Node *old = first; 3.79 - if ( first->next ) 3.80 - first->next->prev = nullptr; 3.81 - first = first->next; 3.82 - delete old; 3.83 - N--; 3.84 - 3.85 - if ( ! first ) 3.86 - last = nullptr; 3.87 - 3.88 - return item; 3.89 - } 3.90 - 3.91 -template <typename T> 3.92 -T Deque<T>::pop_right( void ) { 3.93 - assert( N > 0 ); 3.94 - 3.95 - T item = last->item; 3.96 - 3.97 - Node *old = last; 3.98 - if ( last->prev ) 3.99 - last->prev->next = nullptr; 3.100 - last = last->prev; 3.101 - delete old; 3.102 - N--; 3.103 - 3.104 - if ( ! last ) 3.105 - first = nullptr; 3.106 - 3.107 - return item; 3.108 - } 3.109 - 3.110 -template <typename T> 3.111 -bool Deque<T>::is_empty( void ) { 3.112 - return N == 0; 3.113 - } 3.114 - 3.115 -template <typename T> 3.116 -size_t Deque<T>::size( void ) { 3.117 - return N; 3.118 - } 3.119 - 3.120 -template <typename T> 3.121 -typename Deque<T>::iterator Deque<T>::begin( void ) { 3.122 - return Deque<T>::iterator( first ); 3.123 - } 3.124 - 3.125 -template <typename T> 3.126 -typename Deque<T>::iterator Deque<T>::end( void ) { 3.127 - return Deque<T>::iterator( nullptr ); 3.128 - } 3.129 - 3.130 - 3.131 -//////////////////////////////////////////////////////////////////////////////// 3.132 - 3.133 -template <typename T> 3.134 -Deque<T>::iterator::iterator( Node *c ) : 3.135 - curr (c) 3.136 - { 3.137 - } 3.138 - 3.139 -template <typename T> 3.140 -typename Deque<T>::iterator & Deque<T>::iterator::operator++() { 3.141 - if ( this->curr != nullptr ) { 3.142 - this->curr = this->curr->next; 3.143 - } 3.144 - return *this; 3.145 - } 3.146 - 3.147 -template <typename T> 3.148 -typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) { 3.149 - auto t = Deque<T>::iterator( *this ); 3.150 - 3.151 - if ( this->curr != nullptr ) { 3.152 - this->curr = this->curr->next; 3.153 - } 3.154 - return t; 3.155 - } 3.156 - 3.157 -template <typename T> 3.158 -T Deque<T>::iterator::operator*() { 3.159 - return this->curr->item; 3.160 - } 3.161 - 3.162 -template <typename T> 3.163 -bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) { 3.164 - return this->curr != other.curr; 3.165 - } 3.166 - 3.167 - 3.168 -//////////////////////////////////////////////////////////////////////////////// 3.169 - 3.170 -#ifdef DEQUE_MAIN 3.171 - 3.172 #include <iostream> 3.173 3.174 int main ( int argc, char **argv ) { 3.175 @@ -211,5 +49,3 @@ 3.176 std::cout << "Deque has " << deque.size() << " entries." << std::endl; 3.177 3.178 } 3.179 - 3.180 -#endif
4.1 --- a/algs4-c++/src/Deque.hpp Mon Jun 22 15:38:25 2015 -0500 4.2 +++ b/algs4-c++/src/Deque.hpp Tue Jun 23 10:17:43 2015 -0500 4.3 @@ -1,10 +1,11 @@ 4.4 +// Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3 4.5 + 4.6 #ifndef DEQUE_HPP 4.7 #define DEQUE_HPP 4.8 4.9 +#include <cassert> 4.10 #include <cstddef> 4.11 4.12 -// Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3 4.13 - 4.14 template <typename T> 4.15 class Deque { 4.16 4.17 @@ -66,6 +67,158 @@ 4.18 }; 4.19 4.20 4.21 +//////////////////////////////////////////////////////////////////////////////// 4.22 + 4.23 +template <typename T> 4.24 +Deque<T>::Deque( void ) : 4.25 + N (0), 4.26 + first (nullptr), 4.27 + last (nullptr) 4.28 + { 4.29 + } 4.30 + 4.31 +template <typename T> 4.32 +Deque<T>::~Deque( void ) { 4.33 + assert( N == 0 ); // Catch the potential memory leak. 4.34 + while ( first ) { 4.35 + Node *next = first->next; 4.36 + delete first; 4.37 + first = next; 4.38 + } 4.39 + } 4.40 + 4.41 +template <typename T> 4.42 +void Deque<T>::push_right( T &item ) { 4.43 + Node * node = new Node(); 4.44 + node->item = item; 4.45 + node->next = nullptr; 4.46 + node->prev = nullptr; 4.47 + 4.48 + if ( last ) { 4.49 + last->next = node; 4.50 + node->prev = last; 4.51 + last = node; 4.52 + } 4.53 + else { 4.54 + last = first = node; 4.55 + } 4.56 + 4.57 + N++; 4.58 + } 4.59 + 4.60 +template <typename T> 4.61 +void Deque<T>::push_left( T &item ) { 4.62 + Node * node = new Node(); 4.63 + node->item = item; 4.64 + node->next = nullptr; 4.65 + node->prev = nullptr; 4.66 + 4.67 + if ( first ) { 4.68 + node->next = first; 4.69 + first->prev = node; 4.70 + first = node; 4.71 + } 4.72 + else { 4.73 + last = first = node; 4.74 + } 4.75 + 4.76 + N++; 4.77 + } 4.78 + 4.79 +template <typename T> 4.80 +T Deque<T>::pop_left( void ) { 4.81 + assert( N > 0 ); 4.82 + 4.83 + T item = first->item; 4.84 + 4.85 + Node *old = first; 4.86 + if ( first->next ) 4.87 + first->next->prev = nullptr; 4.88 + first = first->next; 4.89 + delete old; 4.90 + N--; 4.91 + 4.92 + if ( ! first ) 4.93 + last = nullptr; 4.94 + 4.95 + return item; 4.96 + } 4.97 + 4.98 +template <typename T> 4.99 +T Deque<T>::pop_right( void ) { 4.100 + assert( N > 0 ); 4.101 + 4.102 + T item = last->item; 4.103 + 4.104 + Node *old = last; 4.105 + if ( last->prev ) 4.106 + last->prev->next = nullptr; 4.107 + last = last->prev; 4.108 + delete old; 4.109 + N--; 4.110 + 4.111 + if ( ! last ) 4.112 + first = nullptr; 4.113 + 4.114 + return item; 4.115 + } 4.116 + 4.117 +template <typename T> 4.118 +bool Deque<T>::is_empty( void ) { 4.119 + return N == 0; 4.120 + } 4.121 + 4.122 +template <typename T> 4.123 +size_t Deque<T>::size( void ) { 4.124 + return N; 4.125 + } 4.126 + 4.127 +template <typename T> 4.128 +typename Deque<T>::iterator Deque<T>::begin( void ) { 4.129 + return Deque<T>::iterator( first ); 4.130 + } 4.131 + 4.132 +template <typename T> 4.133 +typename Deque<T>::iterator Deque<T>::end( void ) { 4.134 + return Deque<T>::iterator( nullptr ); 4.135 + } 4.136 + 4.137 + 4.138 +//////////////////////////////////////////////////////////////////////////////// 4.139 + 4.140 +template <typename T> 4.141 +Deque<T>::iterator::iterator( Node *c ) : 4.142 + curr (c) 4.143 + { 4.144 + } 4.145 + 4.146 +template <typename T> 4.147 +typename Deque<T>::iterator & Deque<T>::iterator::operator++() { 4.148 + if ( this->curr != nullptr ) { 4.149 + this->curr = this->curr->next; 4.150 + } 4.151 + return *this; 4.152 + } 4.153 + 4.154 +template <typename T> 4.155 +typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) { 4.156 + auto t = Deque<T>::iterator( *this ); 4.157 + 4.158 + if ( this->curr != nullptr ) { 4.159 + this->curr = this->curr->next; 4.160 + } 4.161 + return t; 4.162 + } 4.163 + 4.164 +template <typename T> 4.165 +T Deque<T>::iterator::operator*() { 4.166 + return this->curr->item; 4.167 + } 4.168 + 4.169 +template <typename T> 4.170 +bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) { 4.171 + return this->curr != other.curr; 4.172 + } 4.173 4.174 #endif 4.175
5.1 --- a/algs4-c++/src/Queue.hpp Mon Jun 22 15:38:25 2015 -0500 5.2 +++ b/algs4-c++/src/Queue.hpp Tue Jun 23 10:17:43 2015 -0500 5.3 @@ -5,8 +5,6 @@ 5.4 5.5 #include <cstddef> 5.6 #include <cassert> 5.7 -#include <iostream> 5.8 - 5.9 5.10 template <typename T> 5.11 class Queue {
6.1 --- a/algs4-c++/src/RandomBag.cpp Mon Jun 22 15:38:25 2015 -0500 6.2 +++ b/algs4-c++/src/RandomBag.cpp Tue Jun 23 10:17:43 2015 -0500 6.3 @@ -1,122 +1,7 @@ 6.4 -// g++ -D RANDOMBAG_MAIN -std=c++11 RandomBag.cpp 6.5 - 6.6 +// g++ -std=c++11 RandomBag.cpp 6.7 6.8 #include "RandomBag.hpp" 6.9 6.10 -#include <algorithm> 6.11 -#include <cassert> 6.12 -#include <cstddef> 6.13 -#include <chrono> 6.14 -#include <iostream> 6.15 -#include <iterator> 6.16 -#include <random> 6.17 -#include <vector> 6.18 - 6.19 - 6.20 -template <typename T> 6.21 -RandomBag<T>::RandomBag( void ) : 6.22 - N (0), 6.23 - max(1) { 6.24 - data = new T[1]; 6.25 - } 6.26 - 6.27 -template <typename T> 6.28 -RandomBag<T>::~RandomBag( void ) { 6.29 - // May leak memory. 6.30 - if ( data ) 6.31 - delete[] data; 6.32 - } 6.33 - 6.34 -template <typename T> 6.35 -void RandomBag<T>::add( T &item ) { 6.36 - if ( max == N ) 6.37 - resize( 2 * max ); 6.38 - data[N++] = item; 6.39 - } 6.40 - 6.41 -template <typename T> 6.42 -bool RandomBag<T>::is_empty( void ) { 6.43 - return N == 0; 6.44 - } 6.45 - 6.46 -template <typename T> 6.47 -size_t RandomBag<T>::size( void ) { 6.48 - return N; 6.49 - } 6.50 - 6.51 -template <typename T> 6.52 -void RandomBag<T>::resize( size_t new_max ) { 6.53 - T *new_data = new T[new_max]; 6.54 - for ( size_t i = 0; i < N; ++i ) 6.55 - new_data[i] = data[i]; 6.56 - T *old_data = data; 6.57 - data = new_data; 6.58 - delete[] old_data; 6.59 - max = new_max; 6.60 - } 6.61 - 6.62 -template <typename T> 6.63 -typename RandomBag<T>::iterator RandomBag<T>::begin( void ) { 6.64 - return RandomBag<T>::iterator( data, data, data+N ); 6.65 - } 6.66 - 6.67 -template <typename T> 6.68 -typename RandomBag<T>::iterator RandomBag<T>::end( void ) { 6.69 - return RandomBag<T>::iterator( data, data+N, data+N ); 6.70 - } 6.71 - 6.72 - 6.73 -//////////////////////////////////////////////////////////////////////////////// 6.74 - 6.75 -template <typename T> 6.76 -RandomBag<T>::iterator::iterator( T *b, T *f, T *e ) : 6.77 - begin (b), 6.78 - first (f), 6.79 - end (e), 6.80 - curr (0) { 6.81 - size_t size = e - f; 6.82 - for ( size_t i = 0; i < size; ++i ) { 6.83 - order.push_back( (first - begin) + i ); 6.84 - } 6.85 - 6.86 - unsigned seed = std::chrono::system_clock::now().time_since_epoch().count(); 6.87 - shuffle (order.begin(), order.end(), std::default_random_engine(seed)); 6.88 - 6.89 - order.push_back( end - begin ); 6.90 - } 6.91 - 6.92 -template <typename T> 6.93 -typename RandomBag<T>::iterator & RandomBag<T>::iterator::operator++() { 6.94 - if ( this->curr < this->end - this->first ) { 6.95 - this->curr += 1; 6.96 - } 6.97 - return *this; 6.98 - } 6.99 - 6.100 -template <typename T> 6.101 -typename RandomBag<T>::iterator RandomBag<T>::iterator::operator++( int ) { 6.102 - auto t = RandomBag<T>::iterator( *this ); 6.103 - if ( this->curr < this->end - this->first ) { 6.104 - this->curr += 1; 6.105 - } 6.106 - return t; 6.107 - } 6.108 - 6.109 -template <typename T> 6.110 -T RandomBag<T>::iterator::operator*() { 6.111 - return *(this->begin + order[curr]); 6.112 - } 6.113 - 6.114 -template <typename T> 6.115 -bool RandomBag<T>::iterator::operator!=( typename RandomBag<T>::iterator other ) { 6.116 - return (this->begin + this->order[this->curr]) != (other.begin + other.order[other.curr]); 6.117 - } 6.118 - 6.119 - 6.120 -//////////////////////////////////////////////////////////////////////////////// 6.121 - 6.122 -#ifdef RANDOMBAG_MAIN 6.123 - 6.124 #include <iostream> 6.125 6.126 int main ( int argc, char **argv ) { 6.127 @@ -138,5 +23,3 @@ 6.128 6.129 6.130 } 6.131 - 6.132 -#endif
7.1 --- a/algs4-c++/src/RandomBag.hpp Mon Jun 22 15:38:25 2015 -0500 7.2 +++ b/algs4-c++/src/RandomBag.hpp Tue Jun 23 10:17:43 2015 -0500 7.3 @@ -1,7 +1,14 @@ 7.4 +// Bag class with random iteration order. 7.5 + 7.6 #ifndef RANDOMBAG_HPP 7.7 #define RANDOMBAG_HPP 7.8 7.9 +#include <algorithm> 7.10 #include <cstddef> 7.11 +#include <chrono> 7.12 +#include <iostream> 7.13 +#include <iterator> 7.14 +#include <random> 7.15 #include <vector> 7.16 7.17 template <typename T> 7.18 @@ -53,6 +60,108 @@ 7.19 }; 7.20 7.21 7.22 +//////////////////////////////////////////////////////////////////////////////// 7.23 + 7.24 +template <typename T> 7.25 +RandomBag<T>::RandomBag( void ) : 7.26 + N (0), 7.27 + max(1) { 7.28 + data = new T[1]; 7.29 + } 7.30 + 7.31 +template <typename T> 7.32 +RandomBag<T>::~RandomBag( void ) { 7.33 + // May leak memory. 7.34 + if ( data ) 7.35 + delete[] data; 7.36 + } 7.37 + 7.38 +template <typename T> 7.39 +void RandomBag<T>::add( T &item ) { 7.40 + if ( max == N ) 7.41 + resize( 2 * max ); 7.42 + data[N++] = item; 7.43 + } 7.44 + 7.45 +template <typename T> 7.46 +bool RandomBag<T>::is_empty( void ) { 7.47 + return N == 0; 7.48 + } 7.49 + 7.50 +template <typename T> 7.51 +size_t RandomBag<T>::size( void ) { 7.52 + return N; 7.53 + } 7.54 + 7.55 +template <typename T> 7.56 +void RandomBag<T>::resize( size_t new_max ) { 7.57 + T *new_data = new T[new_max]; 7.58 + for ( size_t i = 0; i < N; ++i ) 7.59 + new_data[i] = data[i]; 7.60 + T *old_data = data; 7.61 + data = new_data; 7.62 + delete[] old_data; 7.63 + max = new_max; 7.64 + } 7.65 + 7.66 +template <typename T> 7.67 +typename RandomBag<T>::iterator RandomBag<T>::begin( void ) { 7.68 + return RandomBag<T>::iterator( data, data, data+N ); 7.69 + } 7.70 + 7.71 +template <typename T> 7.72 +typename RandomBag<T>::iterator RandomBag<T>::end( void ) { 7.73 + return RandomBag<T>::iterator( data, data+N, data+N ); 7.74 + } 7.75 + 7.76 + 7.77 +//////////////////////////////////////////////////////////////////////////////// 7.78 + 7.79 +template <typename T> 7.80 +RandomBag<T>::iterator::iterator( T *b, T *f, T *e ) : 7.81 + begin (b), 7.82 + first (f), 7.83 + end (e), 7.84 + curr (0) { 7.85 + size_t size = e - f; 7.86 + for ( size_t i = 0; i < size; ++i ) { 7.87 + order.push_back( (first - begin) + i ); 7.88 + } 7.89 + 7.90 + unsigned seed = std::chrono::system_clock::now().time_since_epoch().count(); 7.91 + shuffle (order.begin(), order.end(), std::default_random_engine(seed)); 7.92 + 7.93 + order.push_back( end - begin ); 7.94 + } 7.95 + 7.96 +template <typename T> 7.97 +typename RandomBag<T>::iterator & RandomBag<T>::iterator::operator++() { 7.98 + if ( this->curr < this->end - this->first ) { 7.99 + this->curr += 1; 7.100 + } 7.101 + return *this; 7.102 + } 7.103 + 7.104 +template <typename T> 7.105 +typename RandomBag<T>::iterator RandomBag<T>::iterator::operator++( int ) { 7.106 + auto t = RandomBag<T>::iterator( *this ); 7.107 + if ( this->curr < this->end - this->first ) { 7.108 + this->curr += 1; 7.109 + } 7.110 + return t; 7.111 + } 7.112 + 7.113 +template <typename T> 7.114 +T RandomBag<T>::iterator::operator*() { 7.115 + return *(this->begin + order[curr]); 7.116 + } 7.117 + 7.118 +template <typename T> 7.119 +bool RandomBag<T>::iterator::operator!=( typename RandomBag<T>::iterator other ) { 7.120 + return (this->begin + this->order[this->curr]) != (other.begin + other.order[other.curr]); 7.121 + } 7.122 + 7.123 + 7.124 7.125 #endif 7.126
8.1 --- a/algs4-c++/src/ResizingArrayDeque.cpp Mon Jun 22 15:38:25 2015 -0500 8.2 +++ b/algs4-c++/src/ResizingArrayDeque.cpp Tue Jun 23 10:17:43 2015 -0500 8.3 @@ -1,216 +1,8 @@ 8.4 -// g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++0x ResizingArrayDeque.cpp 8.5 -// g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++11 ResizingArrayDeque.cpp 8.6 +// g++ -std=c++11 ResizingArrayDeque.cpp 8.7 8.8 8.9 #include "ResizingArrayDeque.hpp" 8.10 8.11 -#include <cassert> 8.12 -#include <cstddef> 8.13 - 8.14 -#include <iostream> 8.15 - 8.16 -template <typename T> 8.17 -ResizingArrayDeque<T>::ResizingArrayDeque( void ) : 8.18 - N (0), 8.19 - max(1), 8.20 - first(nullptr), 8.21 - last(nullptr) { 8.22 - data = new T[2]; 8.23 - } 8.24 - 8.25 -template <typename T> 8.26 -ResizingArrayDeque<T>::~ResizingArrayDeque( void ) { 8.27 - assert( N == 0 ); // Catch the potential memory leak. 8.28 - if ( data ) 8.29 - delete[] data; 8.30 - } 8.31 - 8.32 -template <typename T> 8.33 -void ResizingArrayDeque<T>::push_right( T &item ) { 8.34 - if ( N == max ) 8.35 - resize( 2 * max ); 8.36 - 8.37 - if ( last ) { 8.38 - if ( last == data ) 8.39 - last = data + max - 1; 8.40 - else 8.41 - ++last; 8.42 - } 8.43 - else { 8.44 - first = last = data; 8.45 - } 8.46 - 8.47 - *last = item; 8.48 - ++N; 8.49 - } 8.50 - 8.51 -template <typename T> 8.52 -void ResizingArrayDeque<T>::push_left( T &item ) { 8.53 - if ( N == max ) 8.54 - resize( 2 * max ); 8.55 - 8.56 - if ( first ) { 8.57 - if ( first == data ) 8.58 - first = data + max - 1; 8.59 - else 8.60 - --first; 8.61 - } 8.62 - else { 8.63 - first = last = data; 8.64 - } 8.65 - 8.66 - *first = item; 8.67 - ++N; 8.68 - } 8.69 - 8.70 -template <typename T> 8.71 -T ResizingArrayDeque<T>::pop_right( void ) { 8.72 - assert( N > 0 ); 8.73 - 8.74 - T item = *last; 8.75 - N--; 8.76 - 8.77 - if ( last == data ) { 8.78 - last = data + max - 1; 8.79 - } 8.80 - else { 8.81 - --last; 8.82 - } 8.83 - 8.84 - if ( N == 0 ) 8.85 - first = last = nullptr; 8.86 - 8.87 - // if ( N <= max/4 ) 8.88 - // resize( max/2 ); 8.89 - 8.90 - return item; 8.91 - } 8.92 - 8.93 -template <typename T> 8.94 -T ResizingArrayDeque<T>::pop_left( void ) { 8.95 - assert( N > 0 ); 8.96 - 8.97 - T item = *first; 8.98 - N--; 8.99 - 8.100 - if ( first == data + max - 1 ) { 8.101 - first = data; 8.102 - } 8.103 - else { 8.104 - ++first; 8.105 - } 8.106 - 8.107 - if ( N == 0 ) 8.108 - first = last = nullptr; 8.109 - 8.110 - // if ( N <= max/4 ) 8.111 - // resize( max/2 ); 8.112 - 8.113 - return item; 8.114 - } 8.115 - 8.116 -template <typename T> 8.117 -bool ResizingArrayDeque<T>::is_empty( void ) { 8.118 - return N == 0; 8.119 - } 8.120 - 8.121 -template <typename T> 8.122 -size_t ResizingArrayDeque<T>::size( void ) { 8.123 - return N; 8.124 - } 8.125 - 8.126 -template <typename T> 8.127 -void ResizingArrayDeque<T>::resize( size_t new_max ) { 8.128 - T *new_data = new T[new_max]; 8.129 - 8.130 - if ( N ) { 8.131 - size_t i = 0; 8.132 - T *curr = first; 8.133 - while ( i < N ) { 8.134 - new_data[i] = *curr; 8.135 - ++curr; 8.136 - if ( curr == data + max ) 8.137 - curr = data; 8.138 - ++i; 8.139 - } 8.140 - } 8.141 - first = new_data; 8.142 - last = new_data + N - 1; 8.143 - 8.144 - T *old_data = data; 8.145 - data = new_data; 8.146 - delete[] old_data; 8.147 - 8.148 - max = new_max; 8.149 - } 8.150 - 8.151 -template <typename T> 8.152 -typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::begin( void ) { 8.153 - return ResizingArrayDeque<T>::iterator( first, last, data, data + max - 1 ); 8.154 - } 8.155 - 8.156 -template <typename T> 8.157 -typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::end( void ) { 8.158 - return ResizingArrayDeque<T>::iterator( nullptr, nullptr, nullptr, nullptr ); 8.159 - } 8.160 - 8.161 - 8.162 -//////////////////////////////////////////////////////////////////////////////// 8.163 - 8.164 -template <typename T> 8.165 -ResizingArrayDeque<T>::iterator::iterator( T *c, T *l, T *b, T *m ) : 8.166 - curr (c), 8.167 - last (l), 8.168 - begin (b), 8.169 - max (m) 8.170 - { 8.171 - } 8.172 - 8.173 -template <typename T> 8.174 -typename ResizingArrayDeque<T>::iterator & ResizingArrayDeque<T>::iterator::operator++() { 8.175 - if ( this->curr == this->last ) { 8.176 - this->curr = nullptr; 8.177 - } 8.178 - else { 8.179 - this->curr += 1; 8.180 - if ( this->curr > this->max ) 8.181 - this->curr = this->begin; 8.182 - } 8.183 - 8.184 - return *this; 8.185 - } 8.186 - 8.187 -template <typename T> 8.188 -typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::iterator::operator++( int ) { 8.189 - auto t = ResizingArrayDeque<T>::iterator( *this ); 8.190 - 8.191 - if ( this->curr == this->last ) { 8.192 - this->curr = nullptr; 8.193 - } 8.194 - else { 8.195 - this->curr += 1; 8.196 - if ( this->curr > this->max ) 8.197 - this->curr = this->begin; 8.198 - } 8.199 - 8.200 - return t; 8.201 - } 8.202 - 8.203 -template <typename T> 8.204 -T ResizingArrayDeque<T>::iterator::operator*() { 8.205 - return *(this->curr); 8.206 - } 8.207 - 8.208 -template <typename T> 8.209 -bool ResizingArrayDeque<T>::iterator::operator!=( typename ResizingArrayDeque<T>::iterator other ) { 8.210 - return this->curr != other.curr; 8.211 - } 8.212 - 8.213 - 8.214 -//////////////////////////////////////////////////////////////////////////////// 8.215 - 8.216 -#ifdef RESIZINGARRAYDEQUE_MAIN 8.217 - 8.218 #include <iostream> 8.219 8.220 int main ( int argc, char **argv ) { 8.221 @@ -258,4 +50,3 @@ 8.222 8.223 } 8.224 8.225 -#endif
9.1 --- a/algs4-c++/src/ResizingArrayDeque.hpp Mon Jun 22 15:38:25 2015 -0500 9.2 +++ b/algs4-c++/src/ResizingArrayDeque.hpp Tue Jun 23 10:17:43 2015 -0500 9.3 @@ -1,6 +1,9 @@ 9.4 +// Double ended queue built on a resizing array. 9.5 + 9.6 #ifndef RESIZINGARRAYDEQUE_HPP 9.7 #define RESIZINGARRAYDEQUE_HPP 9.8 9.9 +#include <cassert> 9.10 #include <cstddef> 9.11 9.12 template <typename T> 9.13 @@ -54,6 +57,206 @@ 9.14 void resize( size_t new_max ); 9.15 }; 9.16 9.17 +//////////////////////////////////////////////////////////////////////////////// 9.18 + 9.19 +template <typename T> 9.20 +ResizingArrayDeque<T>::ResizingArrayDeque( void ) : 9.21 + N (0), 9.22 + max(1), 9.23 + first(nullptr), 9.24 + last(nullptr) { 9.25 + data = new T[2]; 9.26 + } 9.27 + 9.28 +template <typename T> 9.29 +ResizingArrayDeque<T>::~ResizingArrayDeque( void ) { 9.30 + assert( N == 0 ); // Catch the potential memory leak. 9.31 + if ( data ) 9.32 + delete[] data; 9.33 + } 9.34 + 9.35 +template <typename T> 9.36 +void ResizingArrayDeque<T>::push_right( T &item ) { 9.37 + if ( N == max ) 9.38 + resize( 2 * max ); 9.39 + 9.40 + if ( last ) { 9.41 + if ( last == data ) 9.42 + last = data + max - 1; 9.43 + else 9.44 + ++last; 9.45 + } 9.46 + else { 9.47 + first = last = data; 9.48 + } 9.49 + 9.50 + *last = item; 9.51 + ++N; 9.52 + } 9.53 + 9.54 +template <typename T> 9.55 +void ResizingArrayDeque<T>::push_left( T &item ) { 9.56 + if ( N == max ) 9.57 + resize( 2 * max ); 9.58 + 9.59 + if ( first ) { 9.60 + if ( first == data ) 9.61 + first = data + max - 1; 9.62 + else 9.63 + --first; 9.64 + } 9.65 + else { 9.66 + first = last = data; 9.67 + } 9.68 + 9.69 + *first = item; 9.70 + ++N; 9.71 + } 9.72 + 9.73 +template <typename T> 9.74 +T ResizingArrayDeque<T>::pop_right( void ) { 9.75 + assert( N > 0 ); 9.76 + 9.77 + T item = *last; 9.78 + N--; 9.79 + 9.80 + if ( last == data ) { 9.81 + last = data + max - 1; 9.82 + } 9.83 + else { 9.84 + --last; 9.85 + } 9.86 + 9.87 + if ( N == 0 ) 9.88 + first = last = nullptr; 9.89 + 9.90 + // if ( N <= max/4 ) 9.91 + // resize( max/2 ); 9.92 + 9.93 + return item; 9.94 + } 9.95 + 9.96 +template <typename T> 9.97 +T ResizingArrayDeque<T>::pop_left( void ) { 9.98 + assert( N > 0 ); 9.99 + 9.100 + T item = *first; 9.101 + N--; 9.102 + 9.103 + if ( first == data + max - 1 ) { 9.104 + first = data; 9.105 + } 9.106 + else { 9.107 + ++first; 9.108 + } 9.109 + 9.110 + if ( N == 0 ) 9.111 + first = last = nullptr; 9.112 + 9.113 + // if ( N <= max/4 ) 9.114 + // resize( max/2 ); 9.115 + 9.116 + return item; 9.117 + } 9.118 + 9.119 +template <typename T> 9.120 +bool ResizingArrayDeque<T>::is_empty( void ) { 9.121 + return N == 0; 9.122 + } 9.123 + 9.124 +template <typename T> 9.125 +size_t ResizingArrayDeque<T>::size( void ) { 9.126 + return N; 9.127 + } 9.128 + 9.129 +template <typename T> 9.130 +void ResizingArrayDeque<T>::resize( size_t new_max ) { 9.131 + T *new_data = new T[new_max]; 9.132 + 9.133 + if ( N ) { 9.134 + size_t i = 0; 9.135 + T *curr = first; 9.136 + while ( i < N ) { 9.137 + new_data[i] = *curr; 9.138 + ++curr; 9.139 + if ( curr == data + max ) 9.140 + curr = data; 9.141 + ++i; 9.142 + } 9.143 + } 9.144 + first = new_data; 9.145 + last = new_data + N - 1; 9.146 + 9.147 + T *old_data = data; 9.148 + data = new_data; 9.149 + delete[] old_data; 9.150 + 9.151 + max = new_max; 9.152 + } 9.153 + 9.154 +template <typename T> 9.155 +typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::begin( void ) { 9.156 + return ResizingArrayDeque<T>::iterator( first, last, data, data + max - 1 ); 9.157 + } 9.158 + 9.159 +template <typename T> 9.160 +typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::end( void ) { 9.161 + return ResizingArrayDeque<T>::iterator( nullptr, nullptr, nullptr, nullptr ); 9.162 + } 9.163 + 9.164 + 9.165 +//////////////////////////////////////////////////////////////////////////////// 9.166 + 9.167 +template <typename T> 9.168 +ResizingArrayDeque<T>::iterator::iterator( T *c, T *l, T *b, T *m ) : 9.169 + curr (c), 9.170 + last (l), 9.171 + begin (b), 9.172 + max (m) 9.173 + { 9.174 + } 9.175 + 9.176 +template <typename T> 9.177 +typename ResizingArrayDeque<T>::iterator & ResizingArrayDeque<T>::iterator::operator++() { 9.178 + if ( this->curr == this->last ) { 9.179 + this->curr = nullptr; 9.180 + } 9.181 + else { 9.182 + this->curr += 1; 9.183 + if ( this->curr > this->max ) 9.184 + this->curr = this->begin; 9.185 + } 9.186 + 9.187 + return *this; 9.188 + } 9.189 + 9.190 +template <typename T> 9.191 +typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::iterator::operator++( int ) { 9.192 + auto t = ResizingArrayDeque<T>::iterator( *this ); 9.193 + 9.194 + if ( this->curr == this->last ) { 9.195 + this->curr = nullptr; 9.196 + } 9.197 + else { 9.198 + this->curr += 1; 9.199 + if ( this->curr > this->max ) 9.200 + this->curr = this->begin; 9.201 + } 9.202 + 9.203 + return t; 9.204 + } 9.205 + 9.206 +template <typename T> 9.207 +T ResizingArrayDeque<T>::iterator::operator*() { 9.208 + return *(this->curr); 9.209 + } 9.210 + 9.211 +template <typename T> 9.212 +bool ResizingArrayDeque<T>::iterator::operator!=( typename ResizingArrayDeque<T>::iterator other ) { 9.213 + return this->curr != other.curr; 9.214 + } 9.215 + 9.216 + 9.217 9.218 9.219 #endif
10.1 --- a/algs4-c++/src/ResizingArrayStack.cpp Mon Jun 22 15:38:25 2015 -0500 10.2 +++ b/algs4-c++/src/ResizingArrayStack.cpp Tue Jun 23 10:17:43 2015 -0500 10.3 @@ -1,120 +1,8 @@ 10.4 -// g++ -D RESIZINGARRAYSTACK_MAIN -std=c++0x ResizingArrayStack.cpp 10.5 -// g++ -D RESIZINGARRAYSTACK_MAIN -std=c++11 ResizingArrayStack.cpp 10.6 +// g++ -std=c++11 ResizingArrayStack.cpp 10.7 10.8 10.9 #include "ResizingArrayStack.hpp" 10.10 10.11 -#include <cassert> 10.12 -#include <cstddef> 10.13 - 10.14 -#include <iostream> 10.15 - 10.16 -template <typename T> 10.17 -ResizingArrayStack<T>::ResizingArrayStack( void ) : 10.18 - N (0), 10.19 - max(1) { 10.20 - data = new T[1]; 10.21 - } 10.22 - 10.23 -template <typename T> 10.24 -ResizingArrayStack<T>::~ResizingArrayStack( void ) { 10.25 - assert( N == 0 ); // Catch the potential memory leak. 10.26 - if ( data ) 10.27 - delete[] data; 10.28 - } 10.29 - 10.30 -template <typename T> 10.31 -void ResizingArrayStack<T>::push( T &item ) { 10.32 - if ( max == N ) 10.33 - resize( 2 * max ); 10.34 - data[N++] = item; 10.35 - } 10.36 - 10.37 -template <typename T> 10.38 -T ResizingArrayStack<T>::pop( void ) { 10.39 - assert( N > 0 ); 10.40 - T item = data[N-1]; 10.41 - N--; 10.42 - 10.43 - if ( N <= max/4 ) 10.44 - resize( max/2 ); 10.45 - 10.46 - return item; 10.47 - } 10.48 - 10.49 -template <typename T> 10.50 -bool ResizingArrayStack<T>::is_empty( void ) { 10.51 - return N == 0; 10.52 - } 10.53 - 10.54 -template <typename T> 10.55 -size_t ResizingArrayStack<T>::size( void ) { 10.56 - return N; 10.57 - } 10.58 - 10.59 -template <typename T> 10.60 -void ResizingArrayStack<T>::resize( size_t new_max ) { 10.61 - T *new_data = new T[new_max]; 10.62 - for ( size_t i = 0; i < N; ++i ) 10.63 - new_data[i] = data[i]; 10.64 - T *old_data = data; 10.65 - data = new_data; 10.66 - delete[] old_data; 10.67 - max = new_max; 10.68 - } 10.69 - 10.70 -template <typename T> 10.71 -typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::begin( void ) { 10.72 - return ResizingArrayStack<T>::iterator( data+N-1, data-1 ); 10.73 - } 10.74 - 10.75 -template <typename T> 10.76 -typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::end( void ) { 10.77 - return ResizingArrayStack<T>::iterator( data-1, data-1 ); 10.78 - } 10.79 - 10.80 - 10.81 -//////////////////////////////////////////////////////////////////////////////// 10.82 - 10.83 -template <typename T> 10.84 -ResizingArrayStack<T>::iterator::iterator( T *c, T *e ) : 10.85 - curr (c), 10.86 - end (e) 10.87 - { 10.88 - } 10.89 - 10.90 -template <typename T> 10.91 -typename ResizingArrayStack<T>::iterator & ResizingArrayStack<T>::iterator::operator++() { 10.92 - if ( this->curr > this->end ) { 10.93 - this->curr -= 1; 10.94 - } 10.95 - return *this; 10.96 - } 10.97 - 10.98 -template <typename T> 10.99 -typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::iterator::operator++( int ) { 10.100 - auto t = ResizingArrayStack<T>::iterator( *this ); 10.101 - if ( this->curr > this->end ) { 10.102 - this->curr -= 1; 10.103 - } 10.104 - return t; 10.105 - } 10.106 - 10.107 -template <typename T> 10.108 -T ResizingArrayStack<T>::iterator::operator*() { 10.109 - return *(this->curr); 10.110 - } 10.111 - 10.112 -template <typename T> 10.113 -bool ResizingArrayStack<T>::iterator::operator!=( typename ResizingArrayStack<T>::iterator other ) { 10.114 - return this->curr != other.curr; 10.115 - } 10.116 - 10.117 - 10.118 -//////////////////////////////////////////////////////////////////////////////// 10.119 - 10.120 -#ifdef RESIZINGARRAYSTACK_MAIN 10.121 - 10.122 #include <iostream> 10.123 10.124 int main ( int argc, char **argv ) { 10.125 @@ -145,4 +33,3 @@ 10.126 10.127 } 10.128 10.129 -#endif
11.1 --- a/algs4-c++/src/ResizingArrayStack.hpp Mon Jun 22 15:38:25 2015 -0500 11.2 +++ b/algs4-c++/src/ResizingArrayStack.hpp Tue Jun 23 10:17:43 2015 -0500 11.3 @@ -1,6 +1,9 @@ 11.4 +// Stack built on a resizing array. 11.5 + 11.6 #ifndef RESIZINGARRAYSTACK_HPP 11.7 #define RESIZINGARRAYSTACK_HPP 11.8 11.9 +#include <cassert> 11.10 #include <cstddef> 11.11 11.12 template <typename T> 11.13 @@ -49,6 +52,109 @@ 11.14 void resize( size_t new_max ); 11.15 }; 11.16 11.17 +//////////////////////////////////////////////////////////////////////////////// 11.18 + 11.19 +template <typename T> 11.20 +ResizingArrayStack<T>::ResizingArrayStack( void ) : 11.21 + N (0), 11.22 + max(1) { 11.23 + data = new T[1]; 11.24 + } 11.25 + 11.26 +template <typename T> 11.27 +ResizingArrayStack<T>::~ResizingArrayStack( void ) { 11.28 + assert( N == 0 ); // Catch the potential memory leak. 11.29 + if ( data ) 11.30 + delete[] data; 11.31 + } 11.32 + 11.33 +template <typename T> 11.34 +void ResizingArrayStack<T>::push( T &item ) { 11.35 + if ( max == N ) 11.36 + resize( 2 * max ); 11.37 + data[N++] = item; 11.38 + } 11.39 + 11.40 +template <typename T> 11.41 +T ResizingArrayStack<T>::pop( void ) { 11.42 + assert( N > 0 ); 11.43 + T item = data[N-1]; 11.44 + N--; 11.45 + 11.46 + if ( N <= max/4 ) 11.47 + resize( max/2 ); 11.48 + 11.49 + return item; 11.50 + } 11.51 + 11.52 +template <typename T> 11.53 +bool ResizingArrayStack<T>::is_empty( void ) { 11.54 + return N == 0; 11.55 + } 11.56 + 11.57 +template <typename T> 11.58 +size_t ResizingArrayStack<T>::size( void ) { 11.59 + return N; 11.60 + } 11.61 + 11.62 +template <typename T> 11.63 +void ResizingArrayStack<T>::resize( size_t new_max ) { 11.64 + T *new_data = new T[new_max]; 11.65 + for ( size_t i = 0; i < N; ++i ) 11.66 + new_data[i] = data[i]; 11.67 + T *old_data = data; 11.68 + data = new_data; 11.69 + delete[] old_data; 11.70 + max = new_max; 11.71 + } 11.72 + 11.73 +template <typename T> 11.74 +typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::begin( void ) { 11.75 + return ResizingArrayStack<T>::iterator( data+N-1, data-1 ); 11.76 + } 11.77 + 11.78 +template <typename T> 11.79 +typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::end( void ) { 11.80 + return ResizingArrayStack<T>::iterator( data-1, data-1 ); 11.81 + } 11.82 + 11.83 + 11.84 +//////////////////////////////////////////////////////////////////////////////// 11.85 + 11.86 +template <typename T> 11.87 +ResizingArrayStack<T>::iterator::iterator( T *c, T *e ) : 11.88 + curr (c), 11.89 + end (e) 11.90 + { 11.91 + } 11.92 + 11.93 +template <typename T> 11.94 +typename ResizingArrayStack<T>::iterator & ResizingArrayStack<T>::iterator::operator++() { 11.95 + if ( this->curr > this->end ) { 11.96 + this->curr -= 1; 11.97 + } 11.98 + return *this; 11.99 + } 11.100 + 11.101 +template <typename T> 11.102 +typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::iterator::operator++( int ) { 11.103 + auto t = ResizingArrayStack<T>::iterator( *this ); 11.104 + if ( this->curr > this->end ) { 11.105 + this->curr -= 1; 11.106 + } 11.107 + return t; 11.108 + } 11.109 + 11.110 +template <typename T> 11.111 +T ResizingArrayStack<T>::iterator::operator*() { 11.112 + return *(this->curr); 11.113 + } 11.114 + 11.115 +template <typename T> 11.116 +bool ResizingArrayStack<T>::iterator::operator!=( typename ResizingArrayStack<T>::iterator other ) { 11.117 + return this->curr != other.curr; 11.118 + } 11.119 + 11.120 11.121 11.122 #endif
12.1 --- a/algs4-c++/src/Stack.cpp Mon Jun 22 15:38:25 2015 -0500 12.2 +++ b/algs4-c++/src/Stack.cpp Tue Jun 23 10:17:43 2015 -0500 12.3 @@ -1,196 +1,8 @@ 12.4 -// g++ -D STACK_MAIN -std=c++0x Stack.cpp 12.5 -// g++ -D STACK_MAIN -std=c++11 Stack.cpp 12.6 +// g++ -std=c++11 Stack.cpp 12.7 12.8 12.9 #include "Stack.hpp" 12.10 12.11 -#include <cassert> 12.12 -#include <cstddef> 12.13 - 12.14 -#include <iostream> 12.15 - 12.16 -template <typename T> 12.17 -Stack<T>::Stack( void ) : 12.18 - N (0), 12.19 - list (nullptr) 12.20 - { 12.21 - } 12.22 - 12.23 -template <typename T> 12.24 -Stack<T>::~Stack( void ) { 12.25 - assert( N == 0 ); // Catch the potential memory leak. 12.26 - while ( list ) { 12.27 - Node * next = list->next; 12.28 - delete list; 12.29 - list = next; 12.30 - } 12.31 - } 12.32 - 12.33 -template <typename T> 12.34 -void Stack<T>::push( T &item ) { 12.35 - Node * node = new Node(); 12.36 - node->item = item; 12.37 - node->next = list; 12.38 - list = node; 12.39 - N++; 12.40 - } 12.41 - 12.42 -template <typename T> 12.43 -T Stack<T>::pop( void ) { 12.44 - assert( N > 0 ); 12.45 - 12.46 - T item = list->item; 12.47 - 12.48 - Node *old = list; 12.49 - list = list->next; 12.50 - delete old; 12.51 - N--; 12.52 - 12.53 - return item; 12.54 - } 12.55 - 12.56 -template <typename T> 12.57 -bool Stack<T>::is_empty( void ) { 12.58 - return N == 0; 12.59 - } 12.60 - 12.61 -template <typename T> 12.62 -size_t Stack<T>::size( void ) { 12.63 - return N; 12.64 - } 12.65 - 12.66 -template <typename T> 12.67 -typename Stack<T>::iterator Stack<T>::begin( void ) { 12.68 - return Stack<T>::iterator( list ); 12.69 - } 12.70 - 12.71 -template <typename T> 12.72 -typename Stack<T>::iterator Stack<T>::end( void ) { 12.73 - return Stack<T>::iterator( nullptr ); 12.74 - } 12.75 - 12.76 - 12.77 -//////////////////////////////////////////////////////////////////////////////// 12.78 - 12.79 -template <typename T> 12.80 -Stack<T>::iterator::iterator( Node *c ) : 12.81 - curr (c) 12.82 - { 12.83 - } 12.84 - 12.85 -template <typename T> 12.86 -typename Stack<T>::iterator & Stack<T>::iterator::operator++() { 12.87 - if ( this->curr != nullptr ) { 12.88 - this->curr = this->curr->next; 12.89 - } 12.90 - return *this; 12.91 - } 12.92 - 12.93 -template <typename T> 12.94 -typename Stack<T>::iterator Stack<T>::iterator::operator++( int ) { 12.95 - auto t = Stack<T>::iterator( *this ); 12.96 - 12.97 - if ( this->curr != nullptr ) { 12.98 - this->curr = this->curr->next; 12.99 - } 12.100 - return t; 12.101 - } 12.102 - 12.103 -template <typename T> 12.104 -T Stack<T>::iterator::operator*() { 12.105 - return this->curr->item; 12.106 - } 12.107 - 12.108 -template <typename T> 12.109 -bool Stack<T>::iterator::operator!=( typename Stack<T>::iterator other ) { 12.110 - return this->curr != other.curr; 12.111 - } 12.112 - 12.113 -//////////////////////////////////////////////////////////////////////////////// 12.114 - 12.115 - 12.116 -#ifdef EXERCISES 12.117 - 12.118 -// 1.3.19 12.119 -// Returns the item if entry was found. If the entry did not exist, then the returned value is undefined. 12.120 -template <typename T> 12.121 -T Stack<T>::delete_bottom( void ) { 12.122 - Node *prev, *curr; 12.123 - T item; 12.124 - 12.125 - prev = nullptr; 12.126 - curr = list; 12.127 - if ( curr ) { 12.128 - while ( curr->next ) { 12.129 - prev = curr; 12.130 - curr = curr->next; 12.131 - } 12.132 - 12.133 - item = curr->item; 12.134 - delete curr; 12.135 - if ( prev ) 12.136 - prev->next = nullptr; 12.137 - else 12.138 - list = nullptr; 12.139 - 12.140 - N--; 12.141 - } 12.142 - 12.143 - return item; 12.144 - } 12.145 - 12.146 - 12.147 -// 1.3.20 12.148 -// Returns the item if entry was found. If the entry did not exist, then the returned value is undefined. 12.149 -template <typename T> 12.150 -T Stack<T>::remove( size_t k ) { 12.151 - Node *prev, *curr; 12.152 - size_t i=0; 12.153 - T item; 12.154 - 12.155 - prev = nullptr; 12.156 - curr = list; 12.157 - while ( curr && (i < k) ) { 12.158 - prev = curr; 12.159 - curr = curr->next; 12.160 - ++i; 12.161 - } 12.162 - 12.163 - if ( curr &&( i == k) ) { 12.164 - item = curr->item; 12.165 - if ( prev ) 12.166 - prev->next = curr->next; 12.167 - else 12.168 - list = curr->next;; 12.169 - delete curr; 12.170 - N--; 12.171 - } 12.172 - 12.173 - return item; 12.174 - } 12.175 - 12.176 -// 1.3.21 12.177 -// Returns true if the specified key is in the stack. 12.178 -template <typename T> 12.179 -bool Stack<T>::find( T key ) { 12.180 - Node *curr = list; 12.181 - 12.182 - while ( curr ) { 12.183 - if ( curr->item == key ) 12.184 - return true; 12.185 - curr = curr->next; 12.186 - } 12.187 - 12.188 - return false; 12.189 - } 12.190 - 12.191 -#endif 12.192 - 12.193 - 12.194 -//////////////////////////////////////////////////////////////////////////////// 12.195 - 12.196 -#ifdef STACK_MAIN 12.197 - 12.198 #include <iostream> 12.199 12.200 int main ( int argc, char **argv ) { 12.201 @@ -244,5 +56,3 @@ 12.202 std::cout << "Stack has " << stack.size() << " entries." << std::endl; 12.203 12.204 } 12.205 - 12.206 -#endif
13.1 --- a/algs4-c++/src/Stack.hpp Mon Jun 22 15:38:25 2015 -0500 13.2 +++ b/algs4-c++/src/Stack.hpp Tue Jun 23 10:17:43 2015 -0500 13.3 @@ -1,9 +1,11 @@ 13.4 +// Linked list based stack after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2 13.5 + 13.6 #ifndef STACK_HPP 13.7 #define STACK_HPP 13.8 13.9 +#include <cassert> 13.10 #include <cstddef> 13.11 13.12 -// Linked list based stack after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2 13.13 13.14 template <typename T> 13.15 class Stack { 13.16 @@ -70,6 +72,186 @@ 13.17 }; 13.18 13.19 13.20 +//////////////////////////////////////////////////////////////////////////////// 13.21 + 13.22 + 13.23 +template <typename T> 13.24 +Stack<T>::Stack( void ) : 13.25 + N (0), 13.26 + list (nullptr) 13.27 + { 13.28 + } 13.29 + 13.30 +template <typename T> 13.31 +Stack<T>::~Stack( void ) { 13.32 + assert( N == 0 ); // Catch the potential memory leak. 13.33 + while ( list ) { 13.34 + Node * next = list->next; 13.35 + delete list; 13.36 + list = next; 13.37 + } 13.38 + } 13.39 + 13.40 +template <typename T> 13.41 +void Stack<T>::push( T &item ) { 13.42 + Node * node = new Node(); 13.43 + node->item = item; 13.44 + node->next = list; 13.45 + list = node; 13.46 + N++; 13.47 + } 13.48 + 13.49 +template <typename T> 13.50 +T Stack<T>::pop( void ) { 13.51 + assert( N > 0 ); 13.52 + 13.53 + T item = list->item; 13.54 + 13.55 + Node *old = list; 13.56 + list = list->next; 13.57 + delete old; 13.58 + N--; 13.59 + 13.60 + return item; 13.61 + } 13.62 + 13.63 +template <typename T> 13.64 +bool Stack<T>::is_empty( void ) { 13.65 + return N == 0; 13.66 + } 13.67 + 13.68 +template <typename T> 13.69 +size_t Stack<T>::size( void ) { 13.70 + return N; 13.71 + } 13.72 + 13.73 +template <typename T> 13.74 +typename Stack<T>::iterator Stack<T>::begin( void ) { 13.75 + return Stack<T>::iterator( list ); 13.76 + } 13.77 + 13.78 +template <typename T> 13.79 +typename Stack<T>::iterator Stack<T>::end( void ) { 13.80 + return Stack<T>::iterator( nullptr ); 13.81 + } 13.82 + 13.83 + 13.84 +//////////////////////////////////////////////////////////////////////////////// 13.85 + 13.86 +template <typename T> 13.87 +Stack<T>::iterator::iterator( Node *c ) : 13.88 + curr (c) 13.89 + { 13.90 + } 13.91 + 13.92 +template <typename T> 13.93 +typename Stack<T>::iterator & Stack<T>::iterator::operator++() { 13.94 + if ( this->curr != nullptr ) { 13.95 + this->curr = this->curr->next; 13.96 + } 13.97 + return *this; 13.98 + } 13.99 + 13.100 +template <typename T> 13.101 +typename Stack<T>::iterator Stack<T>::iterator::operator++( int ) { 13.102 + auto t = Stack<T>::iterator( *this ); 13.103 + 13.104 + if ( this->curr != nullptr ) { 13.105 + this->curr = this->curr->next; 13.106 + } 13.107 + return t; 13.108 + } 13.109 + 13.110 +template <typename T> 13.111 +T Stack<T>::iterator::operator*() { 13.112 + return this->curr->item; 13.113 + } 13.114 + 13.115 +template <typename T> 13.116 +bool Stack<T>::iterator::operator!=( typename Stack<T>::iterator other ) { 13.117 + return this->curr != other.curr; 13.118 + } 13.119 + 13.120 +//////////////////////////////////////////////////////////////////////////////// 13.121 + 13.122 + 13.123 +#ifdef EXERCISES 13.124 + 13.125 +// 1.3.19 13.126 +// Returns the item if entry was found. If the entry did not exist, then the returned value is undefined. 13.127 +template <typename T> 13.128 +T Stack<T>::delete_bottom( void ) { 13.129 + Node *prev, *curr; 13.130 + T item; 13.131 + 13.132 + prev = nullptr; 13.133 + curr = list; 13.134 + if ( curr ) { 13.135 + while ( curr->next ) { 13.136 + prev = curr; 13.137 + curr = curr->next; 13.138 + } 13.139 + 13.140 + item = curr->item; 13.141 + delete curr; 13.142 + if ( prev ) 13.143 + prev->next = nullptr; 13.144 + else 13.145 + list = nullptr; 13.146 + 13.147 + N--; 13.148 + } 13.149 + 13.150 + return item; 13.151 + } 13.152 + 13.153 + 13.154 +// 1.3.20 13.155 +// Returns the item if entry was found. If the entry did not exist, then the returned value is undefined. 13.156 +template <typename T> 13.157 +T Stack<T>::remove( size_t k ) { 13.158 + Node *prev, *curr; 13.159 + size_t i=0; 13.160 + T item; 13.161 + 13.162 + prev = nullptr; 13.163 + curr = list; 13.164 + while ( curr && (i < k) ) { 13.165 + prev = curr; 13.166 + curr = curr->next; 13.167 + ++i; 13.168 + } 13.169 + 13.170 + if ( curr &&( i == k) ) { 13.171 + item = curr->item; 13.172 + if ( prev ) 13.173 + prev->next = curr->next; 13.174 + else 13.175 + list = curr->next;; 13.176 + delete curr; 13.177 + N--; 13.178 + } 13.179 + 13.180 + return item; 13.181 + } 13.182 + 13.183 +// 1.3.21 13.184 +// Returns true if the specified key is in the stack. 13.185 +template <typename T> 13.186 +bool Stack<T>::find( T key ) { 13.187 + Node *curr = list; 13.188 + 13.189 + while ( curr ) { 13.190 + if ( curr->item == key ) 13.191 + return true; 13.192 + curr = curr->next; 13.193 + } 13.194 + 13.195 + return false; 13.196 + } 13.197 13.198 #endif 13.199 13.200 + 13.201 +#endif 13.202 +
14.1 --- a/algs4-c++/src/Steque.cpp Mon Jun 22 15:38:25 2015 -0500 14.2 +++ b/algs4-c++/src/Steque.cpp Tue Jun 23 10:17:43 2015 -0500 14.3 @@ -1,141 +1,8 @@ 14.4 -// g++ -D STEQUE_MAIN -std=c++0x Steque.cpp 14.5 -// g++ -D STEQUE_MAIN -std=c++11 Steque.cpp 14.6 +// g++ -std=c++11 Steque.cpp 14.7 14.8 14.9 #include "Steque.hpp" 14.10 14.11 -#include <cassert> 14.12 -#include <cstddef> 14.13 - 14.14 -#include <iostream> 14.15 - 14.16 -template <typename T> 14.17 -Steque<T>::Steque( void ) : 14.18 - N (0), 14.19 - list (nullptr) 14.20 - { 14.21 - } 14.22 - 14.23 -template <typename T> 14.24 -Steque<T>::~Steque( void ) { 14.25 - assert( N == 0 ); // Catch the potential memory leak. 14.26 - while ( list ) { 14.27 - Node * next = list->next; 14.28 - delete list; 14.29 - list = next; 14.30 - } 14.31 - } 14.32 - 14.33 -template <typename T> 14.34 -void Steque<T>::push( T &item ) { 14.35 - Node * node = new Node(); 14.36 - node->item = item; 14.37 - node->next = list; 14.38 - list = node; 14.39 - N++; 14.40 - } 14.41 - 14.42 -template <typename T> 14.43 -T Steque<T>::pop( void ) { 14.44 - assert( N > 0 ); 14.45 - 14.46 - T item = list->item; 14.47 - 14.48 - Node *old = list; 14.49 - list = list->next; 14.50 - delete old; 14.51 - N--; 14.52 - 14.53 - return item; 14.54 - } 14.55 - 14.56 -template <typename T> 14.57 -void Steque<T>::enqueue( T &item ) { 14.58 - Node *curr = list; 14.59 - 14.60 - Node *node = new Node(); 14.61 - node->item = item; 14.62 - node->next = nullptr; 14.63 - 14.64 - if ( ! curr ) { 14.65 - list = node; 14.66 - N++; 14.67 - return; 14.68 - } 14.69 - 14.70 - while ( curr->next ) { 14.71 - curr = curr->next; 14.72 - } 14.73 - 14.74 - curr->next = node; 14.75 - N++; 14.76 - 14.77 - return; 14.78 - } 14.79 - 14.80 -template <typename T> 14.81 -bool Steque<T>::is_empty( void ) { 14.82 - return N == 0; 14.83 - } 14.84 - 14.85 -template <typename T> 14.86 -size_t Steque<T>::size( void ) { 14.87 - return N; 14.88 - } 14.89 - 14.90 -template <typename T> 14.91 -typename Steque<T>::iterator Steque<T>::begin( void ) { 14.92 - return Steque<T>::iterator( list ); 14.93 - } 14.94 - 14.95 -template <typename T> 14.96 -typename Steque<T>::iterator Steque<T>::end( void ) { 14.97 - return Steque<T>::iterator( nullptr ); 14.98 - } 14.99 - 14.100 - 14.101 -//////////////////////////////////////////////////////////////////////////////// 14.102 - 14.103 -template <typename T> 14.104 -Steque<T>::iterator::iterator( Node *c ) : 14.105 - curr (c) 14.106 - { 14.107 - } 14.108 - 14.109 -template <typename T> 14.110 -typename Steque<T>::iterator & Steque<T>::iterator::operator++() { 14.111 - if ( this->curr != nullptr ) { 14.112 - this->curr = this->curr->next; 14.113 - } 14.114 - return *this; 14.115 - } 14.116 - 14.117 -template <typename T> 14.118 -typename Steque<T>::iterator Steque<T>::iterator::operator++( int ) { 14.119 - auto t = Steque<T>::iterator( *this ); 14.120 - 14.121 - if ( this->curr != nullptr ) { 14.122 - this->curr = this->curr->next; 14.123 - } 14.124 - return t; 14.125 - } 14.126 - 14.127 -template <typename T> 14.128 -T Steque<T>::iterator::operator*() { 14.129 - return this->curr->item; 14.130 - } 14.131 - 14.132 -template <typename T> 14.133 -bool Steque<T>::iterator::operator!=( typename Steque<T>::iterator other ) { 14.134 - return this->curr != other.curr; 14.135 - } 14.136 - 14.137 -//////////////////////////////////////////////////////////////////////////////// 14.138 - 14.139 - 14.140 - 14.141 -#ifdef STEQUE_MAIN 14.142 - 14.143 #include <iostream> 14.144 14.145 int main ( int argc, char **argv ) { 14.146 @@ -174,5 +41,3 @@ 14.147 std::cout << "Steque has " << steque.size() << " entries." << std::endl; 14.148 14.149 } 14.150 - 14.151 -#endif
15.1 --- a/algs4-c++/src/Steque.hpp Mon Jun 22 15:38:25 2015 -0500 15.2 +++ b/algs4-c++/src/Steque.hpp Tue Jun 23 10:17:43 2015 -0500 15.3 @@ -1,10 +1,11 @@ 15.4 +// Linked list based steque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2 15.5 + 15.6 #ifndef STEQUE_HPP 15.7 #define STEQUE_HPP 15.8 15.9 +#include <cassert> 15.10 #include <cstddef> 15.11 15.12 -// Linked list based steque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2 15.13 - 15.14 template <typename T> 15.15 class Steque { 15.16 15.17 @@ -63,6 +64,129 @@ 15.18 }; 15.19 15.20 15.21 +//////////////////////////////////////////////////////////////////////////////// 15.22 + 15.23 +template <typename T> 15.24 +Steque<T>::Steque( void ) : 15.25 + N (0), 15.26 + list (nullptr) 15.27 + { 15.28 + } 15.29 + 15.30 +template <typename T> 15.31 +Steque<T>::~Steque( void ) { 15.32 + assert( N == 0 ); // Catch the potential memory leak. 15.33 + while ( list ) { 15.34 + Node * next = list->next; 15.35 + delete list; 15.36 + list = next; 15.37 + } 15.38 + } 15.39 + 15.40 +template <typename T> 15.41 +void Steque<T>::push( T &item ) { 15.42 + Node * node = new Node(); 15.43 + node->item = item; 15.44 + node->next = list; 15.45 + list = node; 15.46 + N++; 15.47 + } 15.48 + 15.49 +template <typename T> 15.50 +T Steque<T>::pop( void ) { 15.51 + assert( N > 0 ); 15.52 + 15.53 + T item = list->item; 15.54 + 15.55 + Node *old = list; 15.56 + list = list->next; 15.57 + delete old; 15.58 + N--; 15.59 + 15.60 + return item; 15.61 + } 15.62 + 15.63 +template <typename T> 15.64 +void Steque<T>::enqueue( T &item ) { 15.65 + Node *curr = list; 15.66 + 15.67 + Node *node = new Node(); 15.68 + node->item = item; 15.69 + node->next = nullptr; 15.70 + 15.71 + if ( ! curr ) { 15.72 + list = node; 15.73 + N++; 15.74 + return; 15.75 + } 15.76 + 15.77 + while ( curr->next ) { 15.78 + curr = curr->next; 15.79 + } 15.80 + 15.81 + curr->next = node; 15.82 + N++; 15.83 + 15.84 + return; 15.85 + } 15.86 + 15.87 +template <typename T> 15.88 +bool Steque<T>::is_empty( void ) { 15.89 + return N == 0; 15.90 + } 15.91 + 15.92 +template <typename T> 15.93 +size_t Steque<T>::size( void ) { 15.94 + return N; 15.95 + } 15.96 + 15.97 +template <typename T> 15.98 +typename Steque<T>::iterator Steque<T>::begin( void ) { 15.99 + return Steque<T>::iterator( list ); 15.100 + } 15.101 + 15.102 +template <typename T> 15.103 +typename Steque<T>::iterator Steque<T>::end( void ) { 15.104 + return Steque<T>::iterator( nullptr ); 15.105 + } 15.106 + 15.107 + 15.108 +//////////////////////////////////////////////////////////////////////////////// 15.109 + 15.110 +template <typename T> 15.111 +Steque<T>::iterator::iterator( Node *c ) : 15.112 + curr (c) 15.113 + { 15.114 + } 15.115 + 15.116 +template <typename T> 15.117 +typename Steque<T>::iterator & Steque<T>::iterator::operator++() { 15.118 + if ( this->curr != nullptr ) { 15.119 + this->curr = this->curr->next; 15.120 + } 15.121 + return *this; 15.122 + } 15.123 + 15.124 +template <typename T> 15.125 +typename Steque<T>::iterator Steque<T>::iterator::operator++( int ) { 15.126 + auto t = Steque<T>::iterator( *this ); 15.127 + 15.128 + if ( this->curr != nullptr ) { 15.129 + this->curr = this->curr->next; 15.130 + } 15.131 + return t; 15.132 + } 15.133 + 15.134 +template <typename T> 15.135 +T Steque<T>::iterator::operator*() { 15.136 + return this->curr->item; 15.137 + } 15.138 + 15.139 +template <typename T> 15.140 +bool Steque<T>::iterator::operator!=( typename Steque<T>::iterator other ) { 15.141 + return this->curr != other.curr; 15.142 + } 15.143 + 15.144 15.145 #endif 15.146