Mercurial > Algorithms__Sedgewick
diff 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 diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/algs4-c++/src/RandomBag.cpp Thu Jun 11 16:30:14 2015 -0500 1.3 @@ -0,0 +1,142 @@ 1.4 +// g++ -D RANDOMBAG_MAIN -std=c++11 RandomBag.cpp 1.5 + 1.6 + 1.7 +#include "RandomBag.hpp" 1.8 + 1.9 +#include <algorithm> 1.10 +#include <cassert> 1.11 +#include <cstddef> 1.12 +#include <chrono> 1.13 +#include <iostream> 1.14 +#include <iterator> 1.15 +#include <random> 1.16 +#include <vector> 1.17 + 1.18 + 1.19 +template <typename T> 1.20 +RandomBag<T>::RandomBag( void ) : 1.21 + N (0), 1.22 + max(1) { 1.23 + data = new T[1]; 1.24 + } 1.25 + 1.26 +template <typename T> 1.27 +RandomBag<T>::~RandomBag( void ) { 1.28 + // May leak memory. 1.29 + if ( data ) 1.30 + delete[] data; 1.31 + } 1.32 + 1.33 +template <typename T> 1.34 +void RandomBag<T>::add( T &item ) { 1.35 + if ( max == N ) 1.36 + resize( 2 * max ); 1.37 + data[N++] = item; 1.38 + } 1.39 + 1.40 +template <typename T> 1.41 +bool RandomBag<T>::is_empty( void ) { 1.42 + return N == 0; 1.43 + } 1.44 + 1.45 +template <typename T> 1.46 +size_t RandomBag<T>::size( void ) { 1.47 + return N; 1.48 + } 1.49 + 1.50 +template <typename T> 1.51 +void RandomBag<T>::resize( size_t new_max ) { 1.52 + T *new_data = new T[new_max]; 1.53 + for ( size_t i = 0; i < N; ++i ) 1.54 + new_data[i] = data[i]; 1.55 + T *old_data = data; 1.56 + data = new_data; 1.57 + delete[] old_data; 1.58 + max = new_max; 1.59 + } 1.60 + 1.61 +template <typename T> 1.62 +typename RandomBag<T>::iterator RandomBag<T>::begin( void ) { 1.63 + return RandomBag<T>::iterator( data, data, data+N ); 1.64 + } 1.65 + 1.66 +template <typename T> 1.67 +typename RandomBag<T>::iterator RandomBag<T>::end( void ) { 1.68 + return RandomBag<T>::iterator( data, data+N, data+N ); 1.69 + } 1.70 + 1.71 + 1.72 +//////////////////////////////////////////////////////////////////////////////// 1.73 + 1.74 +template <typename T> 1.75 +RandomBag<T>::iterator::iterator( T *b, T *f, T *e ) : 1.76 + begin (b), 1.77 + first (f), 1.78 + end (e), 1.79 + curr (0) { 1.80 + size_t size = e - f; 1.81 + for ( size_t i = 0; i < size; ++i ) { 1.82 + order.push_back( (first - begin) + i ); 1.83 + } 1.84 + 1.85 + unsigned seed = std::chrono::system_clock::now().time_since_epoch().count(); 1.86 + shuffle (order.begin(), order.end(), std::default_random_engine(seed)); 1.87 + 1.88 + order.push_back( end - begin ); 1.89 + } 1.90 + 1.91 +template <typename T> 1.92 +typename RandomBag<T>::iterator & RandomBag<T>::iterator::operator++() { 1.93 + if ( this->curr < this->end - this->first ) { 1.94 + this->curr += 1; 1.95 + } 1.96 + return *this; 1.97 + } 1.98 + 1.99 +template <typename T> 1.100 +typename RandomBag<T>::iterator RandomBag<T>::iterator::operator++( int ) { 1.101 + auto t = RandomBag<T>::iterator( *this ); 1.102 + if ( this->curr < this->end - this->first ) { 1.103 + this->curr += 1; 1.104 + } 1.105 + return t; 1.106 + } 1.107 + 1.108 +template <typename T> 1.109 +T RandomBag<T>::iterator::operator*() { 1.110 + return *(this->begin + order[curr]); 1.111 + } 1.112 + 1.113 +template <typename T> 1.114 +bool RandomBag<T>::iterator::operator!=( typename RandomBag<T>::iterator other ) { 1.115 + return (this->begin + this->order[this->curr]) != (other.begin + other.order[other.curr]); 1.116 + } 1.117 + 1.118 + 1.119 +//////////////////////////////////////////////////////////////////////////////// 1.120 + 1.121 +#ifdef RANDOMBAG_MAIN 1.122 + 1.123 +#include <iostream> 1.124 + 1.125 +int main ( int argc, char **argv ) { 1.126 + 1.127 + RandomBag<long> random_bag; 1.128 + 1.129 + long i; 1.130 + while ( ! std::cin.eof() ) { 1.131 + std::cin >> i; 1.132 + if ( std::cin.good() ) 1.133 + random_bag.add(i); 1.134 + } 1.135 + 1.136 + std::cout << "RandomBag has " << random_bag.size() << " entries." << std::endl; 1.137 + 1.138 + for ( auto iter = random_bag.begin(); iter != random_bag.end(); ++iter ) { 1.139 + std::cout << *iter << std::endl; 1.140 + } 1.141 + 1.142 + 1.143 + } 1.144 + 1.145 +#endif