Mercurial > Algorithms__Sedgewick

comparison algs4-c++/src/RandomBag.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 63df3e6590e2
children
comparison
equal deleted inserted replaced
0:787aa5a39b9b 1:0ce8bd091b3a
1 // g++ -D RANDOMBAG_MAIN -std=c++11 RandomBag.cpp 1 // g++ -std=c++11 RandomBag.cpp
2
3 2
4 #include "RandomBag.hpp" 3 #include "RandomBag.hpp"
5
6 #include <algorithm>
7 #include <cassert>
8 #include <cstddef>
9 #include <chrono>
10 #include <iostream>
11 #include <iterator>
12 #include <random>
13 #include <vector>
14
15
16 template <typename T>
17 RandomBag<T>::RandomBag( void ) :
18 N (0),
19 max(1) {
20 data = new T[1];
21 }
22
23 template <typename T>
24 RandomBag<T>::~RandomBag( void ) {
25 // May leak memory.
26 if ( data )
27 delete[] data;
28 }
29
30 template <typename T>
31 void RandomBag<T>::add( T &item ) {
32 if ( max == N )
33 resize( 2 * max );
34 data[N++] = item;
35 }
36
37 template <typename T>
38 bool RandomBag<T>::is_empty( void ) {
39 return N == 0;
40 }
41
42 template <typename T>
43 size_t RandomBag<T>::size( void ) {
44 return N;
45 }
46
47 template <typename T>
48 void RandomBag<T>::resize( size_t new_max ) {
49 T *new_data = new T[new_max];
50 for ( size_t i = 0; i < N; ++i )
51 new_data[i] = data[i];
52 T *old_data = data;
53 data = new_data;
54 delete[] old_data;
55 max = new_max;
56 }
57
58 template <typename T>
59 typename RandomBag<T>::iterator RandomBag<T>::begin( void ) {
60 return RandomBag<T>::iterator( data, data, data+N );
61 }
62
63 template <typename T>
64 typename RandomBag<T>::iterator RandomBag<T>::end( void ) {
65 return RandomBag<T>::iterator( data, data+N, data+N );
66 }
67
68
69 ////////////////////////////////////////////////////////////////////////////////
70
71 template <typename T>
72 RandomBag<T>::iterator::iterator( T *b, T *f, T *e ) :
73 begin (b),
74 first (f),
75 end (e),
76 curr (0) {
77 size_t size = e - f;
78 for ( size_t i = 0; i < size; ++i ) {
79 order.push_back( (first - begin) + i );
80 }
81
82 unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
83 shuffle (order.begin(), order.end(), std::default_random_engine(seed));
84
85 order.push_back( end - begin );
86 }
87
88 template <typename T>
89 typename RandomBag<T>::iterator & RandomBag<T>::iterator::operator++() {
90 if ( this->curr < this->end - this->first ) {
91 this->curr += 1;
92 }
93 return *this;
94 }
95
96 template <typename T>
97 typename RandomBag<T>::iterator RandomBag<T>::iterator::operator++( int ) {
98 auto t = RandomBag<T>::iterator( *this );
99 if ( this->curr < this->end - this->first ) {
100 this->curr += 1;
101 }
102 return t;
103 }
104
105 template <typename T>
106 T RandomBag<T>::iterator::operator*() {
107 return *(this->begin + order[curr]);
108 }
109
110 template <typename T>
111 bool RandomBag<T>::iterator::operator!=( typename RandomBag<T>::iterator other ) {
112 return (this->begin + this->order[this->curr]) != (other.begin + other.order[other.curr]);
113 }
114
115
116 ////////////////////////////////////////////////////////////////////////////////
117
118 #ifdef RANDOMBAG_MAIN
119 4
120 #include <iostream> 5 #include <iostream>
121 6
122 int main ( int argc, char **argv ) { 7 int main ( int argc, char **argv ) {
123 8
136 std::cout << *iter << std::endl; 21 std::cout << *iter << std::endl;
137 } 22 }
138 23
139 24
140 } 25 }
141
142 #endif