Mercurial > Algorithms__Sedgewick
annotate algs4-c++/src/Deque.cpp @ 12:1e3c509b6ac4
Added Deque (exercise 1.3.33)
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Wed, 10 Jun 2015 15:44:42 -0500 |
parents | |
children | a149b424b4e2 |
rev | line source |
---|---|
discordia@12 | 1 // g++ -D DEQUE_MAIN -std=c++0x Deque.cpp |
discordia@12 | 2 // g++ -D DEQUE_MAIN -std=c++11 Deque.cpp |
discordia@12 | 3 |
discordia@12 | 4 |
discordia@12 | 5 #include "Deque.hpp" |
discordia@12 | 6 |
discordia@12 | 7 #include <cassert> |
discordia@12 | 8 #include <cstddef> |
discordia@12 | 9 |
discordia@12 | 10 #include <iostream> |
discordia@12 | 11 |
discordia@12 | 12 template <typename T> |
discordia@12 | 13 Deque<T>::Deque( void ) : |
discordia@12 | 14 N (0), |
discordia@12 | 15 first (nullptr), |
discordia@12 | 16 last (nullptr) |
discordia@12 | 17 { |
discordia@12 | 18 } |
discordia@12 | 19 |
discordia@12 | 20 template <typename T> |
discordia@12 | 21 Deque<T>::~Deque( void ) { |
discordia@12 | 22 assert( N == 0 ); // Catch the potential memory leak. |
discordia@12 | 23 while ( first ) { |
discordia@12 | 24 Node *next = first->next; |
discordia@12 | 25 delete first; |
discordia@12 | 26 first = next; |
discordia@12 | 27 } |
discordia@12 | 28 } |
discordia@12 | 29 |
discordia@12 | 30 template <typename T> |
discordia@12 | 31 void Deque<T>::push_right( T &item ) { |
discordia@12 | 32 Node * node = new Node(); |
discordia@12 | 33 node->item = item; |
discordia@12 | 34 node->next = nullptr; |
discordia@12 | 35 node->prev = nullptr; |
discordia@12 | 36 |
discordia@12 | 37 if ( last ) { |
discordia@12 | 38 last->next = node; |
discordia@12 | 39 node->prev = last; |
discordia@12 | 40 last = node; |
discordia@12 | 41 } |
discordia@12 | 42 else { |
discordia@12 | 43 last = first = node; |
discordia@12 | 44 } |
discordia@12 | 45 |
discordia@12 | 46 N++; |
discordia@12 | 47 } |
discordia@12 | 48 |
discordia@12 | 49 template <typename T> |
discordia@12 | 50 void Deque<T>::push_left( T &item ) { |
discordia@12 | 51 Node * node = new Node(); |
discordia@12 | 52 node->item = item; |
discordia@12 | 53 node->next = nullptr; |
discordia@12 | 54 node->prev = nullptr; |
discordia@12 | 55 |
discordia@12 | 56 if ( first ) { |
discordia@12 | 57 node->next = first; |
discordia@12 | 58 first->prev = node; |
discordia@12 | 59 first = node; |
discordia@12 | 60 } |
discordia@12 | 61 else { |
discordia@12 | 62 last = first = node; |
discordia@12 | 63 } |
discordia@12 | 64 |
discordia@12 | 65 N++; |
discordia@12 | 66 } |
discordia@12 | 67 |
discordia@12 | 68 template <typename T> |
discordia@12 | 69 T Deque<T>::pop_left( void ) { |
discordia@12 | 70 assert( N > 0 ); |
discordia@12 | 71 |
discordia@12 | 72 T item = first->item; |
discordia@12 | 73 |
discordia@12 | 74 Node *old = first; |
discordia@12 | 75 if ( first->next ) |
discordia@12 | 76 first->next->prev = nullptr; |
discordia@12 | 77 first = first->next; |
discordia@12 | 78 delete old; |
discordia@12 | 79 N--; |
discordia@12 | 80 |
discordia@12 | 81 if ( ! first ) |
discordia@12 | 82 last = nullptr; |
discordia@12 | 83 |
discordia@12 | 84 return item; |
discordia@12 | 85 } |
discordia@12 | 86 |
discordia@12 | 87 template <typename T> |
discordia@12 | 88 T Deque<T>::pop_right( void ) { |
discordia@12 | 89 assert( N > 0 ); |
discordia@12 | 90 |
discordia@12 | 91 T item = last->item; |
discordia@12 | 92 |
discordia@12 | 93 Node *old = last; |
discordia@12 | 94 if ( last->prev ) |
discordia@12 | 95 last->prev->next = nullptr; |
discordia@12 | 96 last = last->prev; |
discordia@12 | 97 delete old; |
discordia@12 | 98 N--; |
discordia@12 | 99 |
discordia@12 | 100 if ( ! last ) |
discordia@12 | 101 first = nullptr; |
discordia@12 | 102 |
discordia@12 | 103 return item; |
discordia@12 | 104 } |
discordia@12 | 105 |
discordia@12 | 106 template <typename T> |
discordia@12 | 107 bool Deque<T>::is_empty( void ) { |
discordia@12 | 108 return N == 0; |
discordia@12 | 109 } |
discordia@12 | 110 |
discordia@12 | 111 template <typename T> |
discordia@12 | 112 size_t Deque<T>::size( void ) { |
discordia@12 | 113 return N; |
discordia@12 | 114 } |
discordia@12 | 115 |
discordia@12 | 116 template <typename T> |
discordia@12 | 117 typename Deque<T>::iterator Deque<T>::begin( void ) { |
discordia@12 | 118 return Deque<T>::iterator( first ); |
discordia@12 | 119 } |
discordia@12 | 120 |
discordia@12 | 121 template <typename T> |
discordia@12 | 122 typename Deque<T>::iterator Deque<T>::end( void ) { |
discordia@12 | 123 return Deque<T>::iterator( nullptr ); |
discordia@12 | 124 } |
discordia@12 | 125 |
discordia@12 | 126 |
discordia@12 | 127 //////////////////////////////////////////////////////////////////////////////// |
discordia@12 | 128 |
discordia@12 | 129 template <typename T> |
discordia@12 | 130 Deque<T>::iterator::iterator( Node *c ) : |
discordia@12 | 131 curr (c) |
discordia@12 | 132 { |
discordia@12 | 133 } |
discordia@12 | 134 |
discordia@12 | 135 template <typename T> |
discordia@12 | 136 typename Deque<T>::iterator & Deque<T>::iterator::operator++() { |
discordia@12 | 137 if ( this->curr != nullptr ) { |
discordia@12 | 138 this->curr = this->curr->next; |
discordia@12 | 139 } |
discordia@12 | 140 return *this; |
discordia@12 | 141 } |
discordia@12 | 142 |
discordia@12 | 143 template <typename T> |
discordia@12 | 144 typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) { |
discordia@12 | 145 auto t = Deque<T>::iterator( *this ); |
discordia@12 | 146 |
discordia@12 | 147 if ( this->curr != nullptr ) { |
discordia@12 | 148 this->curr = this->curr->next; |
discordia@12 | 149 } |
discordia@12 | 150 return t; |
discordia@12 | 151 } |
discordia@12 | 152 |
discordia@12 | 153 template <typename T> |
discordia@12 | 154 T Deque<T>::iterator::operator*() { |
discordia@12 | 155 return this->curr->item; |
discordia@12 | 156 } |
discordia@12 | 157 |
discordia@12 | 158 template <typename T> |
discordia@12 | 159 bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) { |
discordia@12 | 160 return this->curr != other.curr; |
discordia@12 | 161 } |
discordia@12 | 162 |
discordia@12 | 163 |
discordia@12 | 164 //////////////////////////////////////////////////////////////////////////////// |
discordia@12 | 165 |
discordia@12 | 166 #ifdef DEQUE_MAIN |
discordia@12 | 167 |
discordia@12 | 168 #include <iostream> |
discordia@12 | 169 |
discordia@12 | 170 int main ( int argc, char **argv ) { |
discordia@12 | 171 |
discordia@12 | 172 Deque<long> deque; |
discordia@12 | 173 bool left = true; |
discordia@12 | 174 |
discordia@12 | 175 long i; |
discordia@12 | 176 while ( ! std::cin.eof() ) { |
discordia@12 | 177 std::cin >> i; |
discordia@12 | 178 if ( std::cin.good() ) { |
discordia@12 | 179 if ( left ) { |
discordia@12 | 180 deque.push_left( i ); |
discordia@12 | 181 left = false; |
discordia@12 | 182 } |
discordia@12 | 183 else { |
discordia@12 | 184 deque.push_right( i ); |
discordia@12 | 185 left = true; |
discordia@12 | 186 } |
discordia@12 | 187 } |
discordia@12 | 188 } |
discordia@12 | 189 |
discordia@12 | 190 std::cout << "Deque has " << deque.size() << " entries." << std::endl; |
discordia@12 | 191 |
discordia@12 | 192 for ( auto iter = deque.begin(); iter != deque.end(); ++iter ) { |
discordia@12 | 193 std::cout << *iter << std::endl; |
discordia@12 | 194 } |
discordia@12 | 195 |
discordia@12 | 196 std::cout << "Dequeuing entries..." << std::endl; |
discordia@12 | 197 |
discordia@12 | 198 left = true; |
discordia@12 | 199 while ( ! deque.is_empty() ) { |
discordia@12 | 200 if ( left ) { |
discordia@12 | 201 i = deque.pop_left(); |
discordia@12 | 202 left = false; |
discordia@12 | 203 } |
discordia@12 | 204 else { |
discordia@12 | 205 i = deque.pop_right(); |
discordia@12 | 206 left = true; |
discordia@12 | 207 } |
discordia@12 | 208 std::cout << i << std::endl; |
discordia@12 | 209 } |
discordia@12 | 210 |
discordia@12 | 211 std::cout << "Deque has " << deque.size() << " entries." << std::endl; |
discordia@12 | 212 |
discordia@12 | 213 } |
discordia@12 | 214 |
discordia@12 | 215 #endif |