Mercurial > Algorithms__Sedgewick

comparison algs4-c++/src/RandomBag.cpp @ 15:63df3e6590e2

find changesets by author, revision, files, or words in the commit message
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
comparison
equal deleted inserted replaced
-1:000000000000 0:787aa5a39b9b
1 // g++ -D RANDOMBAG_MAIN -std=c++11 RandomBag.cpp
2
3
4 #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
120 #include <iostream>
121
122 int main ( int argc, char **argv ) {
123
124 RandomBag<long> random_bag;
125
126 long i;
127 while ( ! std::cin.eof() ) {
128 std::cin >> i;
129 if ( std::cin.good() )
130 random_bag.add(i);
131 }
132
133 std::cout << "RandomBag has " << random_bag.size() << " entries." << std::endl;
134
135 for ( auto iter = random_bag.begin(); iter != random_bag.end(); ++iter ) {
136 std::cout << *iter << std::endl;
137 }
138
139
140 }
141
142 #endif