Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Queue.hpp @ 16:eb159ea69f33

find changesets by author, revision, files, or words in the commit message
Updated Queue to have the implementation in the header file. I forgot that templates need the implementation visible to the copmiler in the place where the code is generated - it can't be properly generated if it's in a separate file.
author Eris Caffee <discordia@eldalin.com>
date Fri, 19 Jun 2015 18:17:46 -0500
parents 0f99a5ae6cd4
children a149b424b4e2
line source
1 // Linked list based queue after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
2
3 #ifndef QUEUE_HPP
4 #define QUEUE_HPP
5
6 #include <cstddef>
7 #include <cassert>
8 #include <iostream>
9
10
11 template <typename T>
12 class Queue {
13
14 private:
15
16 ////////////////////////////////////
17 class Node {
18 public:
19 T item;
20 Node *next;
21 };
22
23 public:
24
25 ////////////////////////////////////
26 class iterator;
27 friend class iterator;
28 class iterator {
29
30 public:
31
32 iterator( Node *c );
33
34 iterator& operator++();
35 iterator operator++(int);
36
37 T operator*();
38 bool operator!=( typename Queue<T>::iterator );
39
40 private:
41
42 Node *curr;
43 };
44
45 ////////////////////////////////////
46
47 Queue( void );
48 ~Queue( void );
49
50 void enqueue( T &item );
51 T dequeue( void );
52
53 bool is_empty( void );
54 size_t size( void );
55
56 iterator begin( void );
57 iterator end( void );
58
59
60 private:
61
62 size_t N;
63 Node *first;
64 Node *last;
65
66 };
67
68
69 template <typename T>
70 Queue<T>::Queue( void ) :
71 N (0),
72 first (nullptr),
73 last (nullptr)
74 {
75 }
76
77 template <typename T>
78 Queue<T>::~Queue( void ) {
79 assert( N == 0 ); // Catch the potential memory leak.
80 while ( first ) {
81 Node *next = first->next;
82 delete first;
83 first = next;
84 }
85 }
86
87 template <typename T>
88 void Queue<T>::enqueue( T &item ) {
89 Node * node = new Node();
90 node->item = item;
91 node->next = nullptr;
92
93 if ( last ) {
94 last->next = node;
95 last = node;
96 }
97 else {
98 last = first = node;
99 }
100
101 N++;
102 }
103
104 template <typename T>
105 T Queue<T>::dequeue( void ) {
106 assert( N > 0 );
107
108 T item = first->item;
109
110 Node *old = first;
111 first = first->next;
112 delete old;
113 N--;
114
115 if ( ! first )
116 last = nullptr;
117
118 return item;
119 }
120
121 template <typename T>
122 bool Queue<T>::is_empty( void ) {
123 return N == 0;
124 }
125
126 template <typename T>
127 size_t Queue<T>::size( void ) {
128 return N;
129 }
130
131 template <typename T>
132 typename Queue<T>::iterator Queue<T>::begin( void ) {
133 return Queue<T>::iterator( first );
134 }
135
136 template <typename T>
137 typename Queue<T>::iterator Queue<T>::end( void ) {
138 return Queue<T>::iterator( nullptr );
139 }
140
141
142 ////////////////////////////////////////////////////////////////////////////////
143
144 template <typename T>
145 Queue<T>::iterator::iterator( Node *c ) :
146 curr (c)
147 {
148 }
149
150 template <typename T>
151 typename Queue<T>::iterator & Queue<T>::iterator::operator++() {
152 if ( this->curr != nullptr ) {
153 this->curr = this->curr->next;
154 }
155 return *this;
156 }
157
158 template <typename T>
159 typename Queue<T>::iterator Queue<T>::iterator::operator++( int ) {
160 auto t = Queue<T>::iterator( *this );
161
162 if ( this->curr != nullptr ) {
163 this->curr = this->curr->next;
164 }
165 return t;
166 }
167
168 template <typename T>
169 T Queue<T>::iterator::operator*() {
170 return this->curr->item;
171 }
172
173 template <typename T>
174 bool Queue<T>::iterator::operator!=( typename Queue<T>::iterator other ) {
175 return this->curr != other.curr;
176 }
177
178
179 #endif
180