discordia@15: // g++ -D RANDOMBAG_MAIN -std=c++11 RandomBag.cpp
discordia@15: 
discordia@15: 
discordia@15: #include "RandomBag.hpp"
discordia@15: 
discordia@15: #include <algorithm>
discordia@15: #include <cassert>
discordia@15: #include <cstddef>
discordia@15: #include <chrono>
discordia@15: #include <iostream>
discordia@15: #include <iterator>
discordia@15: #include <random> 
discordia@15: #include <vector>
discordia@15: 
discordia@15: 
discordia@15: template <typename T>
discordia@15: RandomBag<T>::RandomBag( void ) :
discordia@15:     N (0),
discordia@15:     max(1) {
discordia@15:     data = new T[1];
discordia@15:     }
discordia@15:     
discordia@15: template <typename T>
discordia@15: RandomBag<T>::~RandomBag( void ) {
discordia@15:     // May leak memory.
discordia@15:     if ( data )
discordia@15:         delete[] data;
discordia@15:     }
discordia@15: 
discordia@15: template <typename T>
discordia@15: void RandomBag<T>::add( T &item ) {
discordia@15:     if ( max == N )
discordia@15:         resize( 2 * max );
discordia@15:     data[N++] = item;
discordia@15:     }
discordia@15: 
discordia@15: template <typename T>
discordia@15: bool RandomBag<T>::is_empty( void ) {
discordia@15:     return N == 0;
discordia@15:     }
discordia@15: 
discordia@15: template <typename T>
discordia@15: size_t RandomBag<T>::size( void ) {
discordia@15:     return N;
discordia@15:     }
discordia@15: 
discordia@15: template <typename T>
discordia@15: void RandomBag<T>::resize( size_t new_max ) {
discordia@15:     T *new_data = new T[new_max];
discordia@15:     for ( size_t i = 0; i < N; ++i )
discordia@15:         new_data[i] = data[i];
discordia@15:     T *old_data = data;
discordia@15:     data = new_data;
discordia@15:     delete[] old_data;
discordia@15:     max = new_max;
discordia@15:     }
discordia@15: 
discordia@15: template <typename T>
discordia@15: typename RandomBag<T>::iterator RandomBag<T>::begin( void ) {
discordia@15:     return RandomBag<T>::iterator( data, data, data+N );
discordia@15:     }
discordia@15: 
discordia@15: template <typename T>
discordia@15: typename RandomBag<T>::iterator RandomBag<T>::end( void ) {
discordia@15:     return RandomBag<T>::iterator( data, data+N, data+N );
discordia@15:     }
discordia@15: 
discordia@15: 
discordia@15: ////////////////////////////////////////////////////////////////////////////////
discordia@15: 
discordia@15: template <typename T>
discordia@15: RandomBag<T>::iterator::iterator( T *b, T *f, T *e ) :
discordia@15:     begin (b),
discordia@15:     first (f),
discordia@15:     end (e),
discordia@15:     curr (0) {
discordia@15:     size_t size = e - f;
discordia@15:     for ( size_t i = 0; i < size; ++i ) {
discordia@15:         order.push_back( (first - begin) + i );
discordia@15:         }
discordia@15: 
discordia@15:     unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
discordia@15:     shuffle (order.begin(), order.end(), std::default_random_engine(seed));
discordia@15: 
discordia@15:     order.push_back( end - begin );
discordia@15:     }
discordia@15: 
discordia@15: template <typename T>
discordia@15: typename RandomBag<T>::iterator & RandomBag<T>::iterator::operator++() {
discordia@15:     if ( this->curr < this->end - this->first ) {
discordia@15:         this->curr += 1;
discordia@15:         }
discordia@15:     return *this;
discordia@15:     }
discordia@15: 
discordia@15: template <typename T>
discordia@15: typename RandomBag<T>::iterator RandomBag<T>::iterator::operator++( int ) {
discordia@15:     auto t = RandomBag<T>::iterator( *this );
discordia@15:     if ( this->curr < this->end - this->first ) {
discordia@15:         this->curr += 1;
discordia@15:         }
discordia@15:     return t;
discordia@15:     }
discordia@15: 
discordia@15: template <typename T>
discordia@15: T RandomBag<T>::iterator::operator*() {
discordia@15:     return *(this->begin + order[curr]);
discordia@15:     }
discordia@15: 
discordia@15: template <typename T>
discordia@15: bool RandomBag<T>::iterator::operator!=( typename RandomBag<T>::iterator other ) {
discordia@15:     return (this->begin + this->order[this->curr]) != (other.begin + other.order[other.curr]);
discordia@15:     }
discordia@15: 
discordia@15: 
discordia@15: ////////////////////////////////////////////////////////////////////////////////
discordia@15: 
discordia@15: #ifdef RANDOMBAG_MAIN
discordia@15: 
discordia@15: #include <iostream>
discordia@15: 
discordia@15: int main ( int argc, char **argv ) {
discordia@15: 
discordia@15:     RandomBag<long> random_bag;
discordia@15: 
discordia@15:     long i;
discordia@15:     while ( ! std::cin.eof() ) {
discordia@15:         std::cin >> i;
discordia@15:         if ( std::cin.good() ) 
discordia@15:             random_bag.add(i);
discordia@15:         }
discordia@15: 
discordia@15:     std::cout << "RandomBag has " << random_bag.size() << " entries." << std::endl;
discordia@15: 
discordia@15:     for ( auto iter = random_bag.begin(); iter != random_bag.end(); ++iter ) {
discordia@15:         std::cout << *iter << std::endl;
discordia@15:         }
discordia@15: 
discordia@15: 
discordia@15:     }
discordia@15: 
discordia@15: #endif