Mercurial > Algorithms__Sedgewick
view algs4-c++/src/RandomBag.cpp @ 15:63df3e6590e2
Bag and RandomBag (1.3.34) classes.
There are not really robust enough to use as they will leak memory on
destruction if you use them to store dynamically allocated objects.
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Thu, 11 Jun 2015 16:30:14 -0500 |
| parents | |
| children | a149b424b4e2 |
line source
1 // g++ -D RANDOMBAG_MAIN -std=c++11 RandomBag.cpp
4 #include "RandomBag.hpp"
6 #include <algorithm>
7 #include <cassert>
8 #include <cstddef>
9 #include <chrono>
10 #include <iostream>
11 #include <iterator>
12 #include <random>
13 #include <vector>
16 template <typename T>
17 RandomBag<T>::RandomBag( void ) :
18 N (0),
19 max(1) {
20 data = new T[1];
21 }
23 template <typename T>
24 RandomBag<T>::~RandomBag( void ) {
25 // May leak memory.
26 if ( data )
27 delete[] data;
28 }
30 template <typename T>
31 void RandomBag<T>::add( T &item ) {
32 if ( max == N )
33 resize( 2 * max );
34 data[N++] = item;
35 }
37 template <typename T>
38 bool RandomBag<T>::is_empty( void ) {
39 return N == 0;
40 }
42 template <typename T>
43 size_t RandomBag<T>::size( void ) {
44 return N;
45 }
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 }
58 template <typename T>
59 typename RandomBag<T>::iterator RandomBag<T>::begin( void ) {
60 return RandomBag<T>::iterator( data, data, data+N );
61 }
63 template <typename T>
64 typename RandomBag<T>::iterator RandomBag<T>::end( void ) {
65 return RandomBag<T>::iterator( data, data+N, data+N );
66 }
69 ////////////////////////////////////////////////////////////////////////////////
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 }
82 unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
83 shuffle (order.begin(), order.end(), std::default_random_engine(seed));
85 order.push_back( end - begin );
86 }
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 }
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 }
105 template <typename T>
106 T RandomBag<T>::iterator::operator*() {
107 return *(this->begin + order[curr]);
108 }
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 }
116 ////////////////////////////////////////////////////////////////////////////////
118 #ifdef RANDOMBAG_MAIN
120 #include <iostream>
122 int main ( int argc, char **argv ) {
124 RandomBag<long> random_bag;
126 long i;
127 while ( ! std::cin.eof() ) {
128 std::cin >> i;
129 if ( std::cin.good() )
130 random_bag.add(i);
131 }
133 std::cout << "RandomBag has " << random_bag.size() << " entries." << std::endl;
135 for ( auto iter = random_bag.begin(); iter != random_bag.end(); ++iter ) {
136 std::cout << *iter << std::endl;
137 }
140 }
142 #endif