Mercurial > Algorithms__Sedgewick

annotate 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
rev   line source
discordia@15 1 // g++ -D RANDOMBAG_MAIN -std=c++11 RandomBag.cpp
discordia@15 2
discordia@15 3
discordia@15 4 #include "RandomBag.hpp"
discordia@15 5
discordia@15 6 #include <algorithm>
discordia@15 7 #include <cassert>
discordia@15 8 #include <cstddef>
discordia@15 9 #include <chrono>
discordia@15 10 #include <iostream>
discordia@15 11 #include <iterator>
discordia@15 12 #include <random>
discordia@15 13 #include <vector>
discordia@15 14
discordia@15 15
discordia@15 16 template <typename T>
discordia@15 17 RandomBag<T>::RandomBag( void ) :
discordia@15 18 N (0),
discordia@15 19 max(1) {
discordia@15 20 data = new T[1];
discordia@15 21 }
discordia@15 22
discordia@15 23 template <typename T>
discordia@15 24 RandomBag<T>::~RandomBag( void ) {
discordia@15 25 // May leak memory.
discordia@15 26 if ( data )
discordia@15 27 delete[] data;
discordia@15 28 }
discordia@15 29
discordia@15 30 template <typename T>
discordia@15 31 void RandomBag<T>::add( T &item ) {
discordia@15 32 if ( max == N )
discordia@15 33 resize( 2 * max );
discordia@15 34 data[N++] = item;
discordia@15 35 }
discordia@15 36
discordia@15 37 template <typename T>
discordia@15 38 bool RandomBag<T>::is_empty( void ) {
discordia@15 39 return N == 0;
discordia@15 40 }
discordia@15 41
discordia@15 42 template <typename T>
discordia@15 43 size_t RandomBag<T>::size( void ) {
discordia@15 44 return N;
discordia@15 45 }
discordia@15 46
discordia@15 47 template <typename T>
discordia@15 48 void RandomBag<T>::resize( size_t new_max ) {
discordia@15 49 T *new_data = new T[new_max];
discordia@15 50 for ( size_t i = 0; i < N; ++i )
discordia@15 51 new_data[i] = data[i];
discordia@15 52 T *old_data = data;
discordia@15 53 data = new_data;
discordia@15 54 delete[] old_data;
discordia@15 55 max = new_max;
discordia@15 56 }
discordia@15 57
discordia@15 58 template <typename T>
discordia@15 59 typename RandomBag<T>::iterator RandomBag<T>::begin( void ) {
discordia@15 60 return RandomBag<T>::iterator( data, data, data+N );
discordia@15 61 }
discordia@15 62
discordia@15 63 template <typename T>
discordia@15 64 typename RandomBag<T>::iterator RandomBag<T>::end( void ) {
discordia@15 65 return RandomBag<T>::iterator( data, data+N, data+N );
discordia@15 66 }
discordia@15 67
discordia@15 68
discordia@15 69 ////////////////////////////////////////////////////////////////////////////////
discordia@15 70
discordia@15 71 template <typename T>
discordia@15 72 RandomBag<T>::iterator::iterator( T *b, T *f, T *e ) :
discordia@15 73 begin (b),
discordia@15 74 first (f),
discordia@15 75 end (e),
discordia@15 76 curr (0) {
discordia@15 77 size_t size = e - f;
discordia@15 78 for ( size_t i = 0; i < size; ++i ) {
discordia@15 79 order.push_back( (first - begin) + i );
discordia@15 80 }
discordia@15 81
discordia@15 82 unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
discordia@15 83 shuffle (order.begin(), order.end(), std::default_random_engine(seed));
discordia@15 84
discordia@15 85 order.push_back( end - begin );
discordia@15 86 }
discordia@15 87
discordia@15 88 template <typename T>
discordia@15 89 typename RandomBag<T>::iterator & RandomBag<T>::iterator::operator++() {
discordia@15 90 if ( this->curr < this->end - this->first ) {
discordia@15 91 this->curr += 1;
discordia@15 92 }
discordia@15 93 return *this;
discordia@15 94 }
discordia@15 95
discordia@15 96 template <typename T>
discordia@15 97 typename RandomBag<T>::iterator RandomBag<T>::iterator::operator++( int ) {
discordia@15 98 auto t = RandomBag<T>::iterator( *this );
discordia@15 99 if ( this->curr < this->end - this->first ) {
discordia@15 100 this->curr += 1;
discordia@15 101 }
discordia@15 102 return t;
discordia@15 103 }
discordia@15 104
discordia@15 105 template <typename T>
discordia@15 106 T RandomBag<T>::iterator::operator*() {
discordia@15 107 return *(this->begin + order[curr]);
discordia@15 108 }
discordia@15 109
discordia@15 110 template <typename T>
discordia@15 111 bool RandomBag<T>::iterator::operator!=( typename RandomBag<T>::iterator other ) {
discordia@15 112 return (this->begin + this->order[this->curr]) != (other.begin + other.order[other.curr]);
discordia@15 113 }
discordia@15 114
discordia@15 115
discordia@15 116 ////////////////////////////////////////////////////////////////////////////////
discordia@15 117
discordia@15 118 #ifdef RANDOMBAG_MAIN
discordia@15 119
discordia@15 120 #include <iostream>
discordia@15 121
discordia@15 122 int main ( int argc, char **argv ) {
discordia@15 123
discordia@15 124 RandomBag<long> random_bag;
discordia@15 125
discordia@15 126 long i;
discordia@15 127 while ( ! std::cin.eof() ) {
discordia@15 128 std::cin >> i;
discordia@15 129 if ( std::cin.good() )
discordia@15 130 random_bag.add(i);
discordia@15 131 }
discordia@15 132
discordia@15 133 std::cout << "RandomBag has " << random_bag.size() << " entries." << std::endl;
discordia@15 134
discordia@15 135 for ( auto iter = random_bag.begin(); iter != random_bag.end(); ++iter ) {
discordia@15 136 std::cout << *iter << std::endl;
discordia@15 137 }
discordia@15 138
discordia@15 139
discordia@15 140 }
discordia@15 141
discordia@15 142 #endif