Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Deque.cpp @ 15:63df3e6590e2

find changesets by author, revision, files, or words in the commit message
Bag and RandomBag (1.3.34) classes. There are not really robust enough to use as they will leak memory on destruction if you use them to store dynamically allocated objects.
author Eris Caffee <discordia@eldalin.com>
date Thu, 11 Jun 2015 16:30:14 -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