Mercurial > Algorithms__Sedgewick

annotate algs4-c++/src/Steque.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 846aeab17939
children
rev   line source
discordia@18 1 // Linked list based steque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
discordia@18 2
discordia@11 3 #ifndef STEQUE_HPP
discordia@11 4 #define STEQUE_HPP
discordia@11 5
discordia@18 6 #include <cassert>
discordia@11 7 #include <cstddef>
discordia@11 8
discordia@11 9 template <typename T>
discordia@11 10 class Steque {
discordia@11 11
discordia@11 12 private:
discordia@11 13
discordia@11 14 ////////////////////////////////////
discordia@11 15 class Node {
discordia@11 16 public:
discordia@11 17 T item;
discordia@11 18 Node *next;
discordia@11 19 };
discordia@11 20
discordia@11 21
discordia@11 22 public:
discordia@11 23
discordia@11 24 ////////////////////////////////////
discordia@11 25 class iterator;
discordia@11 26 friend class iterator;
discordia@11 27 class iterator {
discordia@11 28
discordia@11 29 public:
discordia@11 30
discordia@11 31 iterator( Node *c );
discordia@11 32
discordia@11 33 iterator& operator++();
discordia@11 34 iterator operator++(int);
discordia@11 35
discordia@11 36 T operator*();
discordia@11 37 bool operator!=( typename Steque<T>::iterator );
discordia@11 38
discordia@11 39 private:
discordia@11 40
discordia@11 41 Node *curr;
discordia@11 42 };
discordia@11 43
discordia@11 44 ////////////////////////////////////
discordia@11 45
discordia@11 46 Steque( void );
discordia@11 47 ~Steque( void );
discordia@11 48
discordia@11 49 void push( T &item );
discordia@11 50 T pop( void );
discordia@11 51 void enqueue( T &item );
discordia@11 52
discordia@11 53 bool is_empty( void );
discordia@11 54 size_t size( void );
discordia@11 55
discordia@11 56 iterator begin( void );
discordia@11 57 iterator end( void );
discordia@11 58
discordia@11 59 private:
discordia@11 60
discordia@11 61 size_t N;
discordia@11 62 Node *list;
discordia@11 63
discordia@11 64 };
discordia@11 65
discordia@11 66
discordia@18 67 ////////////////////////////////////////////////////////////////////////////////
discordia@18 68
discordia@18 69 template <typename T>
discordia@18 70 Steque<T>::Steque( void ) :
discordia@18 71 N (0),
discordia@18 72 list (nullptr)
discordia@18 73 {
discordia@18 74 }
discordia@18 75
discordia@18 76 template <typename T>
discordia@18 77 Steque<T>::~Steque( void ) {
discordia@18 78 assert( N == 0 ); // Catch the potential memory leak.
discordia@18 79 while ( list ) {
discordia@18 80 Node * next = list->next;
discordia@18 81 delete list;
discordia@18 82 list = next;
discordia@18 83 }
discordia@18 84 }
discordia@18 85
discordia@18 86 template <typename T>
discordia@18 87 void Steque<T>::push( T &item ) {
discordia@18 88 Node * node = new Node();
discordia@18 89 node->item = item;
discordia@18 90 node->next = list;
discordia@18 91 list = node;
discordia@18 92 N++;
discordia@18 93 }
discordia@18 94
discordia@18 95 template <typename T>
discordia@18 96 T Steque<T>::pop( void ) {
discordia@18 97 assert( N > 0 );
discordia@18 98
discordia@18 99 T item = list->item;
discordia@18 100
discordia@18 101 Node *old = list;
discordia@18 102 list = list->next;
discordia@18 103 delete old;
discordia@18 104 N--;
discordia@18 105
discordia@18 106 return item;
discordia@18 107 }
discordia@18 108
discordia@18 109 template <typename T>
discordia@18 110 void Steque<T>::enqueue( T &item ) {
discordia@18 111 Node *curr = list;
discordia@18 112
discordia@18 113 Node *node = new Node();
discordia@18 114 node->item = item;
discordia@18 115 node->next = nullptr;
discordia@18 116
discordia@18 117 if ( ! curr ) {
discordia@18 118 list = node;
discordia@18 119 N++;
discordia@18 120 return;
discordia@18 121 }
discordia@18 122
discordia@18 123 while ( curr->next ) {
discordia@18 124 curr = curr->next;
discordia@18 125 }
discordia@18 126
discordia@18 127 curr->next = node;
discordia@18 128 N++;
discordia@18 129
discordia@18 130 return;
discordia@18 131 }
discordia@18 132
discordia@18 133 template <typename T>
discordia@18 134 bool Steque<T>::is_empty( void ) {
discordia@18 135 return N == 0;
discordia@18 136 }
discordia@18 137
discordia@18 138 template <typename T>
discordia@18 139 size_t Steque<T>::size( void ) {
discordia@18 140 return N;
discordia@18 141 }
discordia@18 142
discordia@18 143 template <typename T>
discordia@18 144 typename Steque<T>::iterator Steque<T>::begin( void ) {
discordia@18 145 return Steque<T>::iterator( list );
discordia@18 146 }
discordia@18 147
discordia@18 148 template <typename T>
discordia@18 149 typename Steque<T>::iterator Steque<T>::end( void ) {
discordia@18 150 return Steque<T>::iterator( nullptr );
discordia@18 151 }
discordia@18 152
discordia@18 153
discordia@18 154 ////////////////////////////////////////////////////////////////////////////////
discordia@18 155
discordia@18 156 template <typename T>
discordia@18 157 Steque<T>::iterator::iterator( Node *c ) :
discordia@18 158 curr (c)
discordia@18 159 {
discordia@18 160 }
discordia@18 161
discordia@18 162 template <typename T>
discordia@18 163 typename Steque<T>::iterator & Steque<T>::iterator::operator++() {
discordia@18 164 if ( this->curr != nullptr ) {
discordia@18 165 this->curr = this->curr->next;
discordia@18 166 }
discordia@18 167 return *this;
discordia@18 168 }
discordia@18 169
discordia@18 170 template <typename T>
discordia@18 171 typename Steque<T>::iterator Steque<T>::iterator::operator++( int ) {
discordia@18 172 auto t = Steque<T>::iterator( *this );
discordia@18 173
discordia@18 174 if ( this->curr != nullptr ) {
discordia@18 175 this->curr = this->curr->next;
discordia@18 176 }
discordia@18 177 return t;
discordia@18 178 }
discordia@18 179
discordia@18 180 template <typename T>
discordia@18 181 T Steque<T>::iterator::operator*() {
discordia@18 182 return this->curr->item;
discordia@18 183 }
discordia@18 184
discordia@18 185 template <typename T>
discordia@18 186 bool Steque<T>::iterator::operator!=( typename Steque<T>::iterator other ) {
discordia@18 187 return this->curr != other.curr;
discordia@18 188 }
discordia@18 189
discordia@11 190
discordia@11 191 #endif
discordia@11 192