Mercurial > Algorithms__Sedgewick

comparison algs4-c++/src/Deque.cpp @ 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 1e3c509b6ac4
children
comparison
equal deleted inserted replaced
0:c41347541319 1:a12aa9be8f23
1 // g++ -D DEQUE_MAIN -std=c++0x Deque.cpp 1 // g++ -std=c++11 Deque.cpp
2 // g++ -D DEQUE_MAIN -std=c++11 Deque.cpp
3 2
4 3
5 #include "Deque.hpp" 4 #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 5
168 #include <iostream> 6 #include <iostream>
169 7
170 int main ( int argc, char **argv ) { 8 int main ( int argc, char **argv ) {
171 9
209 } 47 }
210 48
211 std::cout << "Deque has " << deque.size() << " entries." << std::endl; 49 std::cout << "Deque has " << deque.size() << " entries." << std::endl;
212 50
213 } 51 }
214
215 #endif