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