Mercurial > Algorithms__Sedgewick

comparison 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
comparison
equal deleted inserted replaced
0:1e815ab35362 1:e914eacc98b5
1 // Linked list based steque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
2
1 #ifndef STEQUE_HPP 3 #ifndef STEQUE_HPP
2 #define STEQUE_HPP 4 #define STEQUE_HPP
3 5
6 #include <cassert>
4 #include <cstddef> 7 #include <cstddef>
5
6 // Linked list based steque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
7 8
8 template <typename T> 9 template <typename T>
9 class Steque { 10 class Steque {
10 11
11 private: 12 private:
61 Node *list; 62 Node *list;
62 63
63 }; 64 };
64 65
65 66
67 ////////////////////////////////////////////////////////////////////////////////
68
69 template <typename T>
70 Steque<T>::Steque( void ) :
71 N (0),
72 list (nullptr)
73 {
74 }
75
76 template <typename T>
77 Steque<T>::~Steque( void ) {
78 assert( N == 0 ); // Catch the potential memory leak.
79 while ( list ) {
80 Node * next = list->next;
81 delete list;
82 list = next;
83 }
84 }
85
86 template <typename T>
87 void Steque<T>::push( T &item ) {
88 Node * node = new Node();
89 node->item = item;
90 node->next = list;
91 list = node;
92 N++;
93 }
94
95 template <typename T>
96 T Steque<T>::pop( void ) {
97 assert( N > 0 );
98
99 T item = list->item;
100
101 Node *old = list;
102 list = list->next;
103 delete old;
104 N--;
105
106 return item;
107 }
108
109 template <typename T>
110 void Steque<T>::enqueue( T &item ) {
111 Node *curr = list;
112
113 Node *node = new Node();
114 node->item = item;
115 node->next = nullptr;
116
117 if ( ! curr ) {
118 list = node;
119 N++;
120 return;
121 }
122
123 while ( curr->next ) {
124 curr = curr->next;
125 }
126
127 curr->next = node;
128 N++;
129
130 return;
131 }
132
133 template <typename T>
134 bool Steque<T>::is_empty( void ) {
135 return N == 0;
136 }
137
138 template <typename T>
139 size_t Steque<T>::size( void ) {
140 return N;
141 }
142
143 template <typename T>
144 typename Steque<T>::iterator Steque<T>::begin( void ) {
145 return Steque<T>::iterator( list );
146 }
147
148 template <typename T>
149 typename Steque<T>::iterator Steque<T>::end( void ) {
150 return Steque<T>::iterator( nullptr );
151 }
152
153
154 ////////////////////////////////////////////////////////////////////////////////
155
156 template <typename T>
157 Steque<T>::iterator::iterator( Node *c ) :
158 curr (c)
159 {
160 }
161
162 template <typename T>
163 typename Steque<T>::iterator & Steque<T>::iterator::operator++() {
164 if ( this->curr != nullptr ) {
165 this->curr = this->curr->next;
166 }
167 return *this;
168 }
169
170 template <typename T>
171 typename Steque<T>::iterator Steque<T>::iterator::operator++( int ) {
172 auto t = Steque<T>::iterator( *this );
173
174 if ( this->curr != nullptr ) {
175 this->curr = this->curr->next;
176 }
177 return t;
178 }
179
180 template <typename T>
181 T Steque<T>::iterator::operator*() {
182 return this->curr->item;
183 }
184
185 template <typename T>
186 bool Steque<T>::iterator::operator!=( typename Steque<T>::iterator other ) {
187 return this->curr != other.curr;
188 }
189
66 190
67 #endif 191 #endif
68 192