Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Deque.cpp @ 12:1e3c509b6ac4

find changesets by author, revision, files, or words in the commit message
Added Deque (exercise 1.3.33)
author Eris Caffee <discordia@eldalin.com>
date Wed, 10 Jun 2015 15:44:42 -0500
parents
children a149b424b4e2
line source
1 // g++ -D DEQUE_MAIN -std=c++0x Deque.cpp
2 // g++ -D DEQUE_MAIN -std=c++11 Deque.cpp
3
4
5 #include "Deque.hpp"
6
7 #include <cassert>
8 #include <cstddef>
9
10 #include <iostream>
11
12 template <typename T>
13 Deque<T>::Deque( void ) :
14 N (0),
15 first (nullptr),
16 last (nullptr)
17 {
18 }
19
20 template <typename T>
21 Deque<T>::~Deque( void ) {
22 assert( N == 0 ); // Catch the potential memory leak.
23 while ( first ) {
24 Node *next = first->next;
25 delete first;
26 first = next;
27 }
28 }
29
30 template <typename T>
31 void Deque<T>::push_right( T &item ) {
32 Node * node = new Node();
33 node->item = item;
34 node->next = nullptr;
35 node->prev = nullptr;
36
37 if ( last ) {
38 last->next = node;
39 node->prev = last;
40 last = node;
41 }
42 else {
43 last = first = node;
44 }
45
46 N++;
47 }
48
49 template <typename T>
50 void Deque<T>::push_left( T &item ) {
51 Node * node = new Node();
52 node->item = item;
53 node->next = nullptr;
54 node->prev = nullptr;
55
56 if ( first ) {
57 node->next = first;
58 first->prev = node;
59 first = node;
60 }
61 else {
62 last = first = node;
63 }
64
65 N++;
66 }
67
68 template <typename T>
69 T Deque<T>::pop_left( void ) {
70 assert( N > 0 );
71
72 T item = first->item;
73
74 Node *old = first;
75 if ( first->next )
76 first->next->prev = nullptr;
77 first = first->next;
78 delete old;
79 N--;
80
81 if ( ! first )
82 last = nullptr;
83
84 return item;
85 }
86
87 template <typename T>
88 T Deque<T>::pop_right( void ) {
89 assert( N > 0 );
90
91 T item = last->item;
92
93 Node *old = last;
94 if ( last->prev )
95 last->prev->next = nullptr;
96 last = last->prev;
97 delete old;
98 N--;
99
100 if ( ! last )
101 first = nullptr;
102
103 return item;
104 }
105
106 template <typename T>
107 bool Deque<T>::is_empty( void ) {
108 return N == 0;
109 }
110
111 template <typename T>
112 size_t Deque<T>::size( void ) {
113 return N;
114 }
115
116 template <typename T>
117 typename Deque<T>::iterator Deque<T>::begin( void ) {
118 return Deque<T>::iterator( first );
119 }
120
121 template <typename T>
122 typename Deque<T>::iterator Deque<T>::end( void ) {
123 return Deque<T>::iterator( nullptr );
124 }
125
126
127 ////////////////////////////////////////////////////////////////////////////////
128
129 template <typename T>
130 Deque<T>::iterator::iterator( Node *c ) :
131 curr (c)
132 {
133 }
134
135 template <typename T>
136 typename Deque<T>::iterator & Deque<T>::iterator::operator++() {
137 if ( this->curr != nullptr ) {
138 this->curr = this->curr->next;
139 }
140 return *this;
141 }
142
143 template <typename T>
144 typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) {
145 auto t = Deque<T>::iterator( *this );
146
147 if ( this->curr != nullptr ) {
148 this->curr = this->curr->next;
149 }
150 return t;
151 }
152
153 template <typename T>
154 T Deque<T>::iterator::operator*() {
155 return this->curr->item;
156 }
157
158 template <typename T>
159 bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) {
160 return this->curr != other.curr;
161 }
162
163
164 ////////////////////////////////////////////////////////////////////////////////
165
166 #ifdef DEQUE_MAIN
167
168 #include <iostream>
169
170 int main ( int argc, char **argv ) {
171
172 Deque<long> deque;
173 bool left = true;
174
175 long i;
176 while ( ! std::cin.eof() ) {
177 std::cin >> i;
178 if ( std::cin.good() ) {
179 if ( left ) {
180 deque.push_left( i );
181 left = false;
182 }
183 else {
184 deque.push_right( i );
185 left = true;
186 }
187 }
188 }
189
190 std::cout << "Deque has " << deque.size() << " entries." << std::endl;
191
192 for ( auto iter = deque.begin(); iter != deque.end(); ++iter ) {
193 std::cout << *iter << std::endl;
194 }
195
196 std::cout << "Dequeuing entries..." << std::endl;
197
198 left = true;
199 while ( ! deque.is_empty() ) {
200 if ( left ) {
201 i = deque.pop_left();
202 left = false;
203 }
204 else {
205 i = deque.pop_right();
206 left = true;
207 }
208 std::cout << i << std::endl;
209 }
210
211 std::cout << "Deque has " << deque.size() << " entries." << std::endl;
212
213 }
214
215 #endif