Mercurial > Algorithms__Sedgewick
view algs4-c++/src/RandomBag.hpp @ 18:a149b424b4e2
Updated all template classes to have the implementaiton in the header file.
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Sat, 20 Jun 2015 19:36:11 -0500 |
| parents | 63df3e6590e2 |
| children |
line source
1 // Bag class with random iteration order.
3 #ifndef RANDOMBAG_HPP
4 #define RANDOMBAG_HPP
6 #include <algorithm>
7 #include <cstddef>
8 #include <chrono>
9 #include <iostream>
10 #include <iterator>
11 #include <random>
12 #include <vector>
14 template <typename T>
15 class RandomBag {
17 public:
19 ////////////////////////////////////////
20 class iterator {
22 public:
24 iterator( T *b, T *f, T *e );
26 iterator& operator++();
27 iterator operator++(int);
29 T operator*();
30 bool operator!=( typename RandomBag<T>::iterator other );
32 private:
34 T *begin;
35 T *first;
36 T *end;
37 size_t curr;
38 std::vector<size_t> order;
39 };
41 ////////////////////////////////////////
42 RandomBag( void );
43 ~RandomBag( void );
45 void add( T &item );
47 bool is_empty( void );
48 size_t size( void );
50 iterator begin( void );
51 iterator end( void );
53 private:
55 size_t N;
56 size_t max;
57 T *data;
59 void resize( size_t new_max );
60 };
63 ////////////////////////////////////////////////////////////////////////////////
65 template <typename T>
66 RandomBag<T>::RandomBag( void ) :
67 N (0),
68 max(1) {
69 data = new T[1];
70 }
72 template <typename T>
73 RandomBag<T>::~RandomBag( void ) {
74 // May leak memory.
75 if ( data )
76 delete[] data;
77 }
79 template <typename T>
80 void RandomBag<T>::add( T &item ) {
81 if ( max == N )
82 resize( 2 * max );
83 data[N++] = item;
84 }
86 template <typename T>
87 bool RandomBag<T>::is_empty( void ) {
88 return N == 0;
89 }
91 template <typename T>
92 size_t RandomBag<T>::size( void ) {
93 return N;
94 }
96 template <typename T>
97 void RandomBag<T>::resize( size_t new_max ) {
98 T *new_data = new T[new_max];
99 for ( size_t i = 0; i < N; ++i )
100 new_data[i] = data[i];
101 T *old_data = data;
102 data = new_data;
103 delete[] old_data;
104 max = new_max;
105 }
107 template <typename T>
108 typename RandomBag<T>::iterator RandomBag<T>::begin( void ) {
109 return RandomBag<T>::iterator( data, data, data+N );
110 }
112 template <typename T>
113 typename RandomBag<T>::iterator RandomBag<T>::end( void ) {
114 return RandomBag<T>::iterator( data, data+N, data+N );
115 }
118 ////////////////////////////////////////////////////////////////////////////////
120 template <typename T>
121 RandomBag<T>::iterator::iterator( T *b, T *f, T *e ) :
122 begin (b),
123 first (f),
124 end (e),
125 curr (0) {
126 size_t size = e - f;
127 for ( size_t i = 0; i < size; ++i ) {
128 order.push_back( (first - begin) + i );
129 }
131 unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
132 shuffle (order.begin(), order.end(), std::default_random_engine(seed));
134 order.push_back( end - begin );
135 }
137 template <typename T>
138 typename RandomBag<T>::iterator & RandomBag<T>::iterator::operator++() {
139 if ( this->curr < this->end - this->first ) {
140 this->curr += 1;
141 }
142 return *this;
143 }
145 template <typename T>
146 typename RandomBag<T>::iterator RandomBag<T>::iterator::operator++( int ) {
147 auto t = RandomBag<T>::iterator( *this );
148 if ( this->curr < this->end - this->first ) {
149 this->curr += 1;
150 }
151 return t;
152 }
154 template <typename T>
155 T RandomBag<T>::iterator::operator*() {
156 return *(this->begin + order[curr]);
157 }
159 template <typename T>
160 bool RandomBag<T>::iterator::operator!=( typename RandomBag<T>::iterator other ) {
161 return (this->begin + this->order[this->curr]) != (other.begin + other.order[other.curr]);
162 }
166 #endif