Mercurial > Algorithms__Sedgewick

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