Mercurial > Algorithms__Sedgewick

annotate algs4-c++/src/Deque.cpp @ 15:63df3e6590e2

find changesets by author, revision, files, or words in the commit message
Bag and RandomBag (1.3.34) classes. There are not really robust enough to use as they will leak memory on destruction if you use them to store dynamically allocated objects.
author Eris Caffee <discordia@eldalin.com>
date Thu, 11 Jun 2015 16:30:14 -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