Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Steque.hpp @ 18:a149b424b4e2

find changesets by author, revision, files, or words in the commit message
Updated all template classes to have the implementaiton in the header file.
author Eris Caffee <discordia@eldalin.com>
date Sat, 20 Jun 2015 19:36:11 -0500
parents 846aeab17939
children
line source
1 // Linked list based steque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
2
3 #ifndef STEQUE_HPP
4 #define STEQUE_HPP
5
6 #include <cassert>
7 #include <cstddef>
8
9 template <typename T>
10 class Steque {
11
12 private:
13
14 ////////////////////////////////////
15 class Node {
16 public:
17 T item;
18 Node *next;
19 };
20
21
22 public:
23
24 ////////////////////////////////////
25 class iterator;
26 friend class iterator;
27 class iterator {
28
29 public:
30
31 iterator( Node *c );
32
33 iterator& operator++();
34 iterator operator++(int);
35
36 T operator*();
37 bool operator!=( typename Steque<T>::iterator );
38
39 private:
40
41 Node *curr;
42 };
43
44 ////////////////////////////////////
45
46 Steque( void );
47 ~Steque( void );
48
49 void push( T &item );
50 T pop( void );
51 void enqueue( T &item );
52
53 bool is_empty( void );
54 size_t size( void );
55
56 iterator begin( void );
57 iterator end( void );
58
59 private:
60
61 size_t N;
62 Node *list;
63
64 };
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
190
191 #endif
192