Mercurial > Algorithms__Sedgewick

annotate algs4-c++/src/Deque.cpp @ 12:1e3c509b6ac4

find changesets by author, revision, files, or words in the commit message
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