1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/algs4-c++/1.3.34	Thu Jun 11 16:30:14 2015 -0500
     1.3 @@ -0,0 +1,1 @@
     1.4 +src/RandomBag.hpp
     1.5 \ No newline at end of file

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/algs4-c++/src/Bag.cpp	Thu Jun 11 16:30:14 2015 -0500
     2.3 @@ -0,0 +1,201 @@
     2.4 +// g++ -D BAG_MAIN -std=c++0x Bag.cpp
     2.5 +// g++ -D BAG_MAIN -std=c++11 Bag.cpp
     2.6 +
     2.7 +
     2.8 +#include "Bag.hpp"
     2.9 +
    2.10 +#include <cassert>
    2.11 +#include <cstddef>
    2.12 +
    2.13 +#include <iostream>
    2.14 +
    2.15 +template <typename T>
    2.16 +Bag<T>::Bag( void ) :
    2.17 +    N (0),
    2.18 +    list (nullptr)
    2.19 +    {
    2.20 +    }
    2.21 +    
    2.22 +template <typename T>
    2.23 +Bag<T>::~Bag( void ) {
    2.24 +    // This will leak memory, won't it?
    2.25 +    while ( list ) {
    2.26 +        Node * next = list->next;
    2.27 +        delete list;
    2.28 +        list = next;
    2.29 +        }
    2.30 +    }
    2.31 +
    2.32 +template <typename T>
    2.33 +void Bag<T>::add( T &item ) {
    2.34 +    Node * node = new Node();
    2.35 +    node->item = item;
    2.36 +    node->next = list;
    2.37 +    list = node;
    2.38 +    N++;
    2.39 +    }
    2.40 +
    2.41 +template <typename T>
    2.42 +bool Bag<T>::is_empty( void ) {
    2.43 +    return N == 0;
    2.44 +    }
    2.45 +
    2.46 +template <typename T>
    2.47 +size_t Bag<T>::size( void ) {
    2.48 +    return N;
    2.49 +    }
    2.50 +
    2.51 +template <typename T>
    2.52 +typename Bag<T>::iterator Bag<T>::begin( void ) {
    2.53 +    return Bag<T>::iterator( list );
    2.54 +    }
    2.55 +
    2.56 +template <typename T>
    2.57 +typename Bag<T>::iterator Bag<T>::end( void ) {
    2.58 +    return Bag<T>::iterator( nullptr );
    2.59 +    }
    2.60 +
    2.61 +
    2.62 +////////////////////////////////////////////////////////////////////////////////
    2.63 +
    2.64 +template <typename T>
    2.65 +Bag<T>::iterator::iterator( Node *c ) :
    2.66 +    curr (c)
    2.67 +    {
    2.68 +    }
    2.69 +
    2.70 +template <typename T>
    2.71 +typename Bag<T>::iterator & Bag<T>::iterator::operator++() {
    2.72 +    if ( this->curr != nullptr ) {
    2.73 +        this->curr = this->curr->next;
    2.74 +        }
    2.75 +    return *this;
    2.76 +    }
    2.77 +
    2.78 +template <typename T>
    2.79 +typename Bag<T>::iterator Bag<T>::iterator::operator++( int ) {
    2.80 +    auto t = Bag<T>::iterator( *this );
    2.81 +
    2.82 +    if ( this->curr != nullptr ) {
    2.83 +        this->curr = this->curr->next;
    2.84 +        }
    2.85 +    return t;
    2.86 +    }
    2.87 +
    2.88 +template <typename T>
    2.89 +T Bag<T>::iterator::operator*() {
    2.90 +    return this->curr->item;
    2.91 +    }
    2.92 +
    2.93 +template <typename T>
    2.94 +bool Bag<T>::iterator::operator!=( typename Bag<T>::iterator other ) {
    2.95 +    return this->curr != other.curr;
    2.96 +    }
    2.97 +
    2.98 +////////////////////////////////////////////////////////////////////////////////
    2.99 +
   2.100 +
   2.101 +#ifdef EXERCISES
   2.102 +
   2.103 +// 1.3.19
   2.104 +// Returns the item if entry was found.  If the entry did not exist, then the returned value is undefined.
   2.105 +template <typename T>
   2.106 +T Bag<T>::delete_bottom( void ) {
   2.107 +    Node *prev, *curr;
   2.108 +    T item;
   2.109 +
   2.110 +    prev = nullptr;
   2.111 +    curr = list;
   2.112 +    if ( curr ) {
   2.113 +        while ( curr->next ) {
   2.114 +            prev = curr;
   2.115 +            curr = curr->next;
   2.116 +            }
   2.117 +
   2.118 +        item = curr->item;
   2.119 +        delete curr;
   2.120 +        if ( prev )
   2.121 +            prev->next = nullptr;
   2.122 +        else
   2.123 +            list = nullptr;
   2.124 +
   2.125 +        N--;
   2.126 +        }
   2.127 +
   2.128 +    return item;
   2.129 +    }
   2.130 +
   2.131 +
   2.132 +// 1.3.20
   2.133 +// Returns the item if entry was found.  If the entry did not exist, then the returned value is undefined.
   2.134 +template <typename T>
   2.135 +T Bag<T>::remove( size_t k ) {
   2.136 +    Node *prev, *curr;
   2.137 +    size_t i=0;
   2.138 +    T item;
   2.139 +
   2.140 +    prev = nullptr;
   2.141 +    curr = list;
   2.142 +    while ( curr && (i < k) ) {
   2.143 +        prev = curr;
   2.144 +        curr = curr->next;
   2.145 +        ++i;
   2.146 +        }
   2.147 +
   2.148 +    if ( curr &&( i == k) ) {
   2.149 +        item = curr->item;
   2.150 +        if ( prev )
   2.151 +            prev->next = curr->next;
   2.152 +        else
   2.153 +            list = curr->next;;
   2.154 +        delete curr;
   2.155 +        N--;
   2.156 +        }
   2.157 +
   2.158 +    return item;
   2.159 +    }
   2.160 +
   2.161 +// 1.3.21
   2.162 +// Returns true if the specified key is in the bag.
   2.163 +template <typename T>
   2.164 +bool Bag<T>::find( T key ) {
   2.165 +    Node *curr = list;
   2.166 +
   2.167 +    while ( curr ) {
   2.168 +        if ( curr->item == key )
   2.169 +            return true;
   2.170 +        curr = curr->next;
   2.171 +        }
   2.172 +
   2.173 +    return false;
   2.174 +    }
   2.175 +
   2.176 +#endif
   2.177 +
   2.178 +
   2.179 +////////////////////////////////////////////////////////////////////////////////
   2.180 +
   2.181 +#ifdef BAG_MAIN
   2.182 +
   2.183 +#include <iostream>
   2.184 +
   2.185 +int main ( int argc, char **argv ) {
   2.186 +
   2.187 +    Bag<long> bag;
   2.188 +
   2.189 +    long i;
   2.190 +    while ( ! std::cin.eof() ) {
   2.191 +        std::cin >> i;
   2.192 +        if ( std::cin.good() ) 
   2.193 +            bag.add(i);
   2.194 +        }
   2.195 +
   2.196 +    std::cout << "Bag has " << bag.size() << " entries." << std::endl;
   2.197 +
   2.198 +    for ( auto iter = bag.begin(); iter != bag.end(); ++iter ) {
   2.199 +        std::cout << *iter << std::endl;
   2.200 +        }
   2.201 +
   2.202 +    }
   2.203 +
   2.204 +#endif

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/algs4-c++/src/Bag.hpp	Thu Jun 11 16:30:14 2015 -0500
     3.3 @@ -0,0 +1,66 @@
     3.4 +#ifndef BAG_HPP
     3.5 +#define BAG_HPP
     3.6 +
     3.7 +#include <cstddef>
     3.8 +
     3.9 +// Linked list based bag after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
    3.10 +
    3.11 +template <typename T>
    3.12 +class Bag {
    3.13 +
    3.14 +private:
    3.15 +
    3.16 +    ////////////////////////////////////
    3.17 +    class Node {
    3.18 +    public:
    3.19 +        T item;
    3.20 +        Node *next;
    3.21 +        };
    3.22 +
    3.23 +
    3.24 +public:
    3.25 +
    3.26 +    ////////////////////////////////////
    3.27 +    class iterator;
    3.28 +    friend class iterator;
    3.29 +    class iterator {
    3.30 +
    3.31 +    public:
    3.32 +
    3.33 +        iterator( Node *c );
    3.34 +
    3.35 +        iterator& operator++();
    3.36 +        iterator operator++(int);
    3.37 +
    3.38 +        T operator*();
    3.39 +        bool operator!=( typename Bag<T>::iterator );
    3.40 +
    3.41 +    private:
    3.42 +
    3.43 +        Node *curr;
    3.44 +        };
    3.45 +
    3.46 +    ////////////////////////////////////
    3.47 +
    3.48 +    Bag( void );
    3.49 +    ~Bag( void );
    3.50 +
    3.51 +    void add( T &item );
    3.52 +
    3.53 +    bool is_empty( void );
    3.54 +    size_t size( void );
    3.55 +
    3.56 +    iterator begin( void );
    3.57 +    iterator end( void );
    3.58 +
    3.59 +private:
    3.60 +
    3.61 +    size_t N;
    3.62 +    Node *list;
    3.63 +
    3.64 +    };
    3.65 +
    3.66 +
    3.67 +
    3.68 +#endif
    3.69 +

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/algs4-c++/src/RandomBag.cpp	Thu Jun 11 16:30:14 2015 -0500
     4.3 @@ -0,0 +1,142 @@
     4.4 +// g++ -D RANDOMBAG_MAIN -std=c++11 RandomBag.cpp
     4.5 +
     4.6 +
     4.7 +#include "RandomBag.hpp"
     4.8 +
     4.9 +#include <algorithm>
    4.10 +#include <cassert>
    4.11 +#include <cstddef>
    4.12 +#include <chrono>
    4.13 +#include <iostream>
    4.14 +#include <iterator>
    4.15 +#include <random> 
    4.16 +#include <vector>
    4.17 +
    4.18 +
    4.19 +template <typename T>
    4.20 +RandomBag<T>::RandomBag( void ) :
    4.21 +    N (0),
    4.22 +    max(1) {
    4.23 +    data = new T[1];
    4.24 +    }
    4.25 +    
    4.26 +template <typename T>
    4.27 +RandomBag<T>::~RandomBag( void ) {
    4.28 +    // May leak memory.
    4.29 +    if ( data )
    4.30 +        delete[] data;
    4.31 +    }
    4.32 +
    4.33 +template <typename T>
    4.34 +void RandomBag<T>::add( T &item ) {
    4.35 +    if ( max == N )
    4.36 +        resize( 2 * max );
    4.37 +    data[N++] = item;
    4.38 +    }
    4.39 +
    4.40 +template <typename T>
    4.41 +bool RandomBag<T>::is_empty( void ) {
    4.42 +    return N == 0;
    4.43 +    }
    4.44 +
    4.45 +template <typename T>
    4.46 +size_t RandomBag<T>::size( void ) {
    4.47 +    return N;
    4.48 +    }
    4.49 +
    4.50 +template <typename T>
    4.51 +void RandomBag<T>::resize( size_t new_max ) {
    4.52 +    T *new_data = new T[new_max];
    4.53 +    for ( size_t i = 0; i < N; ++i )
    4.54 +        new_data[i] = data[i];
    4.55 +    T *old_data = data;
    4.56 +    data = new_data;
    4.57 +    delete[] old_data;
    4.58 +    max = new_max;
    4.59 +    }
    4.60 +
    4.61 +template <typename T>
    4.62 +typename RandomBag<T>::iterator RandomBag<T>::begin( void ) {
    4.63 +    return RandomBag<T>::iterator( data, data, data+N );
    4.64 +    }
    4.65 +
    4.66 +template <typename T>
    4.67 +typename RandomBag<T>::iterator RandomBag<T>::end( void ) {
    4.68 +    return RandomBag<T>::iterator( data, data+N, data+N );
    4.69 +    }
    4.70 +
    4.71 +
    4.72 +////////////////////////////////////////////////////////////////////////////////
    4.73 +
    4.74 +template <typename T>
    4.75 +RandomBag<T>::iterator::iterator( T *b, T *f, T *e ) :
    4.76 +    begin (b),
    4.77 +    first (f),
    4.78 +    end (e),
    4.79 +    curr (0) {
    4.80 +    size_t size = e - f;
    4.81 +    for ( size_t i = 0; i < size; ++i ) {
    4.82 +        order.push_back( (first - begin) + i );
    4.83 +        }
    4.84 +
    4.85 +    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    4.86 +    shuffle (order.begin(), order.end(), std::default_random_engine(seed));
    4.87 +
    4.88 +    order.push_back( end - begin );
    4.89 +    }
    4.90 +
    4.91 +template <typename T>
    4.92 +typename RandomBag<T>::iterator & RandomBag<T>::iterator::operator++() {
    4.93 +    if ( this->curr < this->end - this->first ) {
    4.94 +        this->curr += 1;
    4.95 +        }
    4.96 +    return *this;
    4.97 +    }
    4.98 +
    4.99 +template <typename T>
   4.100 +typename RandomBag<T>::iterator RandomBag<T>::iterator::operator++( int ) {
   4.101 +    auto t = RandomBag<T>::iterator( *this );
   4.102 +    if ( this->curr < this->end - this->first ) {
   4.103 +        this->curr += 1;
   4.104 +        }
   4.105 +    return t;
   4.106 +    }
   4.107 +
   4.108 +template <typename T>
   4.109 +T RandomBag<T>::iterator::operator*() {
   4.110 +    return *(this->begin + order[curr]);
   4.111 +    }
   4.112 +
   4.113 +template <typename T>
   4.114 +bool RandomBag<T>::iterator::operator!=( typename RandomBag<T>::iterator other ) {
   4.115 +    return (this->begin + this->order[this->curr]) != (other.begin + other.order[other.curr]);
   4.116 +    }
   4.117 +
   4.118 +
   4.119 +////////////////////////////////////////////////////////////////////////////////
   4.120 +
   4.121 +#ifdef RANDOMBAG_MAIN
   4.122 +
   4.123 +#include <iostream>
   4.124 +
   4.125 +int main ( int argc, char **argv ) {
   4.126 +
   4.127 +    RandomBag<long> random_bag;
   4.128 +
   4.129 +    long i;
   4.130 +    while ( ! std::cin.eof() ) {
   4.131 +        std::cin >> i;
   4.132 +        if ( std::cin.good() ) 
   4.133 +            random_bag.add(i);
   4.134 +        }
   4.135 +
   4.136 +    std::cout << "RandomBag has " << random_bag.size() << " entries." << std::endl;
   4.137 +
   4.138 +    for ( auto iter = random_bag.begin(); iter != random_bag.end(); ++iter ) {
   4.139 +        std::cout << *iter << std::endl;
   4.140 +        }
   4.141 +
   4.142 +
   4.143 +    }
   4.144 +
   4.145 +#endif

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/algs4-c++/src/RandomBag.hpp	Thu Jun 11 16:30:14 2015 -0500
     5.3 @@ -0,0 +1,58 @@
     5.4 +#ifndef RANDOMBAG_HPP
     5.5 +#define RANDOMBAG_HPP
     5.6 +
     5.7 +#include <cstddef>
     5.8 +#include <vector>
     5.9 +
    5.10 +template <typename T>
    5.11 +class RandomBag {
    5.12 +
    5.13 +public:
    5.14 +
    5.15 +    ////////////////////////////////////////
    5.16 +    class iterator {
    5.17 +
    5.18 +    public:
    5.19 +
    5.20 +        iterator( T *b, T *f, T *e );
    5.21 +
    5.22 +        iterator& operator++();
    5.23 +        iterator operator++(int);
    5.24 +
    5.25 +        T operator*();
    5.26 +        bool operator!=( typename RandomBag<T>::iterator other );
    5.27 +
    5.28 +    private:
    5.29 +
    5.30 +        T *begin;
    5.31 +        T *first;
    5.32 +        T *end;
    5.33 +        size_t curr;
    5.34 +        std::vector<size_t> order;
    5.35 +        };
    5.36 +
    5.37 +    ////////////////////////////////////////
    5.38 +    RandomBag( void );
    5.39 +    ~RandomBag( void );
    5.40 +
    5.41 +    void add( T &item );
    5.42 +
    5.43 +    bool is_empty( void );
    5.44 +    size_t size( void );
    5.45 +
    5.46 +    iterator begin( void );
    5.47 +    iterator end( void );
    5.48 +
    5.49 +private:
    5.50 +
    5.51 +    size_t N;
    5.52 +    size_t max;
    5.53 +    T *data;
    5.54 +
    5.55 +    void resize( size_t new_max );
    5.56 +    };
    5.57 +
    5.58 +
    5.59 +
    5.60 +#endif
    5.61 +