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