Mercurial > Algorithms__Sedgewick

annotate algs4-c++/src/Deque.hpp @ 27:80ca1973e3bd

find changesets by author, revision, files, or words in the commit message
Fleshed out Queue::generic_iterator a bit more to make it a more or less complete example of implmenting an iterator.
author Eris Caffee <discordia@eldalin.com>
date Tue, 23 Jun 2015 17:14:09 -0500
parents 1e3c509b6ac4
children
rev   line source
discordia@18 1 // Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
discordia@18 2
discordia@12 3 #ifndef DEQUE_HPP
discordia@12 4 #define DEQUE_HPP
discordia@12 5
discordia@18 6 #include <cassert>
discordia@12 7 #include <cstddef>
discordia@12 8
discordia@12 9 template <typename T>
discordia@12 10 class Deque {
discordia@12 11
discordia@12 12 private:
discordia@12 13
discordia@12 14 ////////////////////////////////////
discordia@12 15 class Node {
discordia@12 16 public:
discordia@12 17 T item;
discordia@12 18 Node *next;
discordia@12 19 Node *prev;
discordia@12 20 };
discordia@12 21
discordia@12 22 public:
discordia@12 23
discordia@12 24 ////////////////////////////////////
discordia@12 25 class iterator;
discordia@12 26 friend class iterator;
discordia@12 27 class iterator {
discordia@12 28
discordia@12 29 public:
discordia@12 30
discordia@12 31 iterator( Node *c );
discordia@12 32
discordia@12 33 iterator& operator++();
discordia@12 34 iterator operator++(int);
discordia@12 35
discordia@12 36 T operator*();
discordia@12 37 bool operator!=( typename Deque<T>::iterator );
discordia@12 38
discordia@12 39 private:
discordia@12 40
discordia@12 41 Node *curr;
discordia@12 42 };
discordia@12 43
discordia@12 44 ////////////////////////////////////
discordia@12 45
discordia@12 46 Deque( void );
discordia@12 47 ~Deque( void );
discordia@12 48
discordia@12 49 void push_left( T &item );
discordia@12 50 void push_right( T &item );
discordia@12 51 T pop_left( void );
discordia@12 52 T pop_right( void );
discordia@12 53
discordia@12 54 bool is_empty( void );
discordia@12 55 size_t size( void );
discordia@12 56
discordia@12 57 iterator begin( void );
discordia@12 58 iterator end( void );
discordia@12 59
discordia@12 60
discordia@12 61 private:
discordia@12 62
discordia@12 63 size_t N;
discordia@12 64 Node *first;
discordia@12 65 Node *last;
discordia@12 66
discordia@12 67 };
discordia@12 68
discordia@12 69
discordia@18 70 ////////////////////////////////////////////////////////////////////////////////
discordia@18 71
discordia@18 72 template <typename T>
discordia@18 73 Deque<T>::Deque( void ) :
discordia@18 74 N (0),
discordia@18 75 first (nullptr),
discordia@18 76 last (nullptr)
discordia@18 77 {
discordia@18 78 }
discordia@18 79
discordia@18 80 template <typename T>
discordia@18 81 Deque<T>::~Deque( void ) {
discordia@18 82 assert( N == 0 ); // Catch the potential memory leak.
discordia@18 83 while ( first ) {
discordia@18 84 Node *next = first->next;
discordia@18 85 delete first;
discordia@18 86 first = next;
discordia@18 87 }
discordia@18 88 }
discordia@18 89
discordia@18 90 template <typename T>
discordia@18 91 void Deque<T>::push_right( T &item ) {
discordia@18 92 Node * node = new Node();
discordia@18 93 node->item = item;
discordia@18 94 node->next = nullptr;
discordia@18 95 node->prev = nullptr;
discordia@18 96
discordia@18 97 if ( last ) {
discordia@18 98 last->next = node;
discordia@18 99 node->prev = last;
discordia@18 100 last = node;
discordia@18 101 }
discordia@18 102 else {
discordia@18 103 last = first = node;
discordia@18 104 }
discordia@18 105
discordia@18 106 N++;
discordia@18 107 }
discordia@18 108
discordia@18 109 template <typename T>
discordia@18 110 void Deque<T>::push_left( T &item ) {
discordia@18 111 Node * node = new Node();
discordia@18 112 node->item = item;
discordia@18 113 node->next = nullptr;
discordia@18 114 node->prev = nullptr;
discordia@18 115
discordia@18 116 if ( first ) {
discordia@18 117 node->next = first;
discordia@18 118 first->prev = node;
discordia@18 119 first = node;
discordia@18 120 }
discordia@18 121 else {
discordia@18 122 last = first = node;
discordia@18 123 }
discordia@18 124
discordia@18 125 N++;
discordia@18 126 }
discordia@18 127
discordia@18 128 template <typename T>
discordia@18 129 T Deque<T>::pop_left( void ) {
discordia@18 130 assert( N > 0 );
discordia@18 131
discordia@18 132 T item = first->item;
discordia@18 133
discordia@18 134 Node *old = first;
discordia@18 135 if ( first->next )
discordia@18 136 first->next->prev = nullptr;
discordia@18 137 first = first->next;
discordia@18 138 delete old;
discordia@18 139 N--;
discordia@18 140
discordia@18 141 if ( ! first )
discordia@18 142 last = nullptr;
discordia@18 143
discordia@18 144 return item;
discordia@18 145 }
discordia@18 146
discordia@18 147 template <typename T>
discordia@18 148 T Deque<T>::pop_right( void ) {
discordia@18 149 assert( N > 0 );
discordia@18 150
discordia@18 151 T item = last->item;
discordia@18 152
discordia@18 153 Node *old = last;
discordia@18 154 if ( last->prev )
discordia@18 155 last->prev->next = nullptr;
discordia@18 156 last = last->prev;
discordia@18 157 delete old;
discordia@18 158 N--;
discordia@18 159
discordia@18 160 if ( ! last )
discordia@18 161 first = nullptr;
discordia@18 162
discordia@18 163 return item;
discordia@18 164 }
discordia@18 165
discordia@18 166 template <typename T>
discordia@18 167 bool Deque<T>::is_empty( void ) {
discordia@18 168 return N == 0;
discordia@18 169 }
discordia@18 170
discordia@18 171 template <typename T>
discordia@18 172 size_t Deque<T>::size( void ) {
discordia@18 173 return N;
discordia@18 174 }
discordia@18 175
discordia@18 176 template <typename T>
discordia@18 177 typename Deque<T>::iterator Deque<T>::begin( void ) {
discordia@18 178 return Deque<T>::iterator( first );
discordia@18 179 }
discordia@18 180
discordia@18 181 template <typename T>
discordia@18 182 typename Deque<T>::iterator Deque<T>::end( void ) {
discordia@18 183 return Deque<T>::iterator( nullptr );
discordia@18 184 }
discordia@18 185
discordia@18 186
discordia@18 187 ////////////////////////////////////////////////////////////////////////////////
discordia@18 188
discordia@18 189 template <typename T>
discordia@18 190 Deque<T>::iterator::iterator( Node *c ) :
discordia@18 191 curr (c)
discordia@18 192 {
discordia@18 193 }
discordia@18 194
discordia@18 195 template <typename T>
discordia@18 196 typename Deque<T>::iterator & Deque<T>::iterator::operator++() {
discordia@18 197 if ( this->curr != nullptr ) {
discordia@18 198 this->curr = this->curr->next;
discordia@18 199 }
discordia@18 200 return *this;
discordia@18 201 }
discordia@18 202
discordia@18 203 template <typename T>
discordia@18 204 typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) {
discordia@18 205 auto t = Deque<T>::iterator( *this );
discordia@18 206
discordia@18 207 if ( this->curr != nullptr ) {
discordia@18 208 this->curr = this->curr->next;
discordia@18 209 }
discordia@18 210 return t;
discordia@18 211 }
discordia@18 212
discordia@18 213 template <typename T>
discordia@18 214 T Deque<T>::iterator::operator*() {
discordia@18 215 return this->curr->item;
discordia@18 216 }
discordia@18 217
discordia@18 218 template <typename T>
discordia@18 219 bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) {
discordia@18 220 return this->curr != other.curr;
discordia@18 221 }
discordia@12 222
discordia@12 223 #endif
discordia@12 224