Mercurial > Algorithms__Sedgewick

view algs4-c++/src/RandomQueue.hpp @ 19:60fb85712482

find changesets by author, revision, files, or words in the commit message
Problems 1.3.35 and 36
author Eris Caffee <discordia@eldalin.com>
date Mon, 22 Jun 2015 14:07:01 -0500
parents
children
line source
1 #ifndef RANDOMQUEUE_HPP
2 #define RANDOMQUEUE_HPP
3
4 #include <algorithm>
5 #include <cassert>
6 #include <cstddef>
7 #include <chrono>
8 #include <random>
9 #include <vector>
10
11 template <typename T>
12 class RandomQueue {
13
14 public:
15
16 ////////////////////////////////////////
17 class iterator {
18
19 public:
20
21 iterator( RandomQueue<T> *q, size_t c, size_t e );
22
23 iterator& operator++();
24 iterator operator++(int);
25
26 T operator*();
27 bool operator!=( typename RandomQueue<T>::iterator );
28
29 private:
30
31 RandomQueue<T> *queue;
32 size_t curr;
33 size_t end;
34 };
35
36 ////////////////////////////////////////
37 RandomQueue( void );
38 ~RandomQueue( void );
39
40 void enqueue( T &item );
41 T dequeue( void );
42 T sample( void );
43
44 bool is_empty( void );
45 size_t size( void );
46
47 iterator begin( void );
48 iterator end( void );
49
50 private:
51
52 size_t N;
53 size_t max;
54 T *data;
55 std::vector<size_t> order;
56
57 void resize( size_t new_max );
58 size_t sample_index( void );
59 void get_order( void );
60 };
61
62
63 ////////////////////////////////////////////////////////////////////////////////
64
65 template <typename T>
66 RandomQueue<T>::RandomQueue( void ) :
67 N (0),
68 max(1) {
69 data = new T[2];
70 }
71
72 template <typename T>
73 RandomQueue<T>::~RandomQueue( void ) {
74 assert( N == 0 ); // Catch the potential memory leak.
75 if ( data )
76 delete[] data;
77 }
78
79 template <typename T>
80 void RandomQueue<T>::enqueue( T &item ) {
81 if ( N == max )
82 resize( 2 * max );
83
84 data[N] = item;
85 ++N;
86 }
87
88 template <typename T>
89 size_t RandomQueue<T>::sample_index( void ) {
90 unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
91 std::default_random_engine generator ( seed );
92 std::uniform_int_distribution<size_t> distribution( 0, N-1 );
93 return distribution(generator);
94 }
95
96 template <typename T>
97 T RandomQueue<T>::dequeue( void ) {
98 assert( N > 0 );
99
100 size_t i = sample_index();
101
102 T tmp = data[N-1];
103 data[N-1] = data[i];
104 data[i] = tmp;
105
106 T item = data[N-1];
107
108 --N;
109
110 return item;
111 }
112
113 template <typename T>
114 T RandomQueue<T>::sample( void ) {
115 assert( N > 0 );
116
117 size_t i = sample_index();
118 return data[i];
119 }
120
121 template <typename T>
122 bool RandomQueue<T>::is_empty( void ) {
123 return N == 0;
124 }
125
126 template <typename T>
127 size_t RandomQueue<T>::size( void ) {
128 return N;
129 }
130
131 template <typename T>
132 void RandomQueue<T>::resize( size_t new_max ) {
133 T *new_data = new T[new_max];
134 for ( size_t i = 0; i < N; ++i )
135 new_data[i] = data[i];
136 T *old_data = data;
137 data = new_data;
138 delete[] old_data;
139 max = new_max;
140 }
141
142 template <typename T>
143 void RandomQueue<T>::get_order( void ) {
144 for ( size_t i = 0; i < N; ++i )
145 order.push_back( i );
146
147 unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
148 shuffle (order.begin(), order.end(), std::default_random_engine(seed));
149 }
150
151 template <typename T>
152 typename RandomQueue<T>::iterator RandomQueue<T>::begin( void ) {
153 if ( order.size() != N )
154 get_order();
155
156 return RandomQueue<T>::iterator( this, 0, order.size() );
157 }
158
159 template <typename T>
160 typename RandomQueue<T>::iterator RandomQueue<T>::end( void ) {
161 if ( order.size() != N )
162 get_order();
163
164 return RandomQueue<T>::iterator( this, order.size(), order.size() );
165 }
166
167
168 ////////////////////////////////////////////////////////////////////////////////
169
170 template <typename T>
171 RandomQueue<T>::iterator::iterator( RandomQueue<T> *q, size_t c, size_t e ) :
172 queue (q),
173 curr (c),
174 end (e)
175 {
176 }
177
178 template <typename T>
179 typename RandomQueue<T>::iterator & RandomQueue<T>::iterator::operator++() {
180 if ( this->curr != this->end )
181 ++(this->curr);
182 return *this;
183 }
184
185 template <typename T>
186 typename RandomQueue<T>::iterator RandomQueue<T>::iterator::operator++( int ) {
187 auto t = RandomQueue<T>::iterator( *this );
188
189 if ( this->curr != this->end )
190 ++(this->curr);
191
192 return t;
193 }
194
195 template <typename T>
196 T RandomQueue<T>::iterator::operator*() {
197
198 return this->queue->data[ this->queue->order[ this->curr ] ];
199 }
200
201 template <typename T>
202 bool RandomQueue<T>::iterator::operator!=( typename RandomQueue<T>::iterator other ) {
203 return this->curr != other.curr;
204 }
205
206
207 #endif
208