# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1434058214 18000
# Node ID 63df3e6590e27e9624180b0df1ff1eb2922ca704
# Parent  2f87e582d91a18e976338d03ea0f16320e09e62f
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.

diff -r 2f87e582d91a -r 63df3e6590e2 algs4-c++/1.3.34
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/1.3.34	Thu Jun 11 16:30:14 2015 -0500
@@ -0,0 +1,1 @@
+src/RandomBag.hpp
\ No newline at end of file
diff -r 2f87e582d91a -r 63df3e6590e2 algs4-c++/src/Bag.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/src/Bag.cpp	Thu Jun 11 16:30:14 2015 -0500
@@ -0,0 +1,201 @@
+// g++ -D BAG_MAIN -std=c++0x Bag.cpp
+// g++ -D BAG_MAIN -std=c++11 Bag.cpp
+
+
+#include "Bag.hpp"
+
+#include <cassert>
+#include <cstddef>
+
+#include <iostream>
+
+template <typename T>
+Bag<T>::Bag( void ) :
+    N (0),
+    list (nullptr)
+    {
+    }
+    
+template <typename T>
+Bag<T>::~Bag( void ) {
+    // This will leak memory, won't it?
+    while ( list ) {
+        Node * next = list->next;
+        delete list;
+        list = next;
+        }
+    }
+
+template <typename T>
+void Bag<T>::add( T &item ) {
+    Node * node = new Node();
+    node->item = item;
+    node->next = list;
+    list = node;
+    N++;
+    }
+
+template <typename T>
+bool Bag<T>::is_empty( void ) {
+    return N == 0;
+    }
+
+template <typename T>
+size_t Bag<T>::size( void ) {
+    return N;
+    }
+
+template <typename T>
+typename Bag<T>::iterator Bag<T>::begin( void ) {
+    return Bag<T>::iterator( list );
+    }
+
+template <typename T>
+typename Bag<T>::iterator Bag<T>::end( void ) {
+    return Bag<T>::iterator( nullptr );
+    }
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+Bag<T>::iterator::iterator( Node *c ) :
+    curr (c)
+    {
+    }
+
+template <typename T>
+typename Bag<T>::iterator & Bag<T>::iterator::operator++() {
+    if ( this->curr != nullptr ) {
+        this->curr = this->curr->next;
+        }
+    return *this;
+    }
+
+template <typename T>
+typename Bag<T>::iterator Bag<T>::iterator::operator++( int ) {
+    auto t = Bag<T>::iterator( *this );
+
+    if ( this->curr != nullptr ) {
+        this->curr = this->curr->next;
+        }
+    return t;
+    }
+
+template <typename T>
+T Bag<T>::iterator::operator*() {
+    return this->curr->item;
+    }
+
+template <typename T>
+bool Bag<T>::iterator::operator!=( typename Bag<T>::iterator other ) {
+    return this->curr != other.curr;
+    }
+
+////////////////////////////////////////////////////////////////////////////////
+
+
+#ifdef EXERCISES
+
+// 1.3.19
+// Returns the item if entry was found.  If the entry did not exist, then the returned value is undefined.
+template <typename T>
+T Bag<T>::delete_bottom( void ) {
+    Node *prev, *curr;
+    T item;
+
+    prev = nullptr;
+    curr = list;
+    if ( curr ) {
+        while ( curr->next ) {
+            prev = curr;
+            curr = curr->next;
+            }
+
+        item = curr->item;
+        delete curr;
+        if ( prev )
+            prev->next = nullptr;
+        else
+            list = nullptr;
+
+        N--;
+        }
+
+    return item;
+    }
+
+
+// 1.3.20
+// Returns the item if entry was found.  If the entry did not exist, then the returned value is undefined.
+template <typename T>
+T Bag<T>::remove( size_t k ) {
+    Node *prev, *curr;
+    size_t i=0;
+    T item;
+
+    prev = nullptr;
+    curr = list;
+    while ( curr && (i < k) ) {
+        prev = curr;
+        curr = curr->next;
+        ++i;
+        }
+
+    if ( curr &&( i == k) ) {
+        item = curr->item;
+        if ( prev )
+            prev->next = curr->next;
+        else
+            list = curr->next;;
+        delete curr;
+        N--;
+        }
+
+    return item;
+    }
+
+// 1.3.21
+// Returns true if the specified key is in the bag.
+template <typename T>
+bool Bag<T>::find( T key ) {
+    Node *curr = list;
+
+    while ( curr ) {
+        if ( curr->item == key )
+            return true;
+        curr = curr->next;
+        }
+
+    return false;
+    }
+
+#endif
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+#ifdef BAG_MAIN
+
+#include <iostream>
+
+int main ( int argc, char **argv ) {
+
+    Bag<long> bag;
+
+    long i;
+    while ( ! std::cin.eof() ) {
+        std::cin >> i;
+        if ( std::cin.good() ) 
+            bag.add(i);
+        }
+
+    std::cout << "Bag has " << bag.size() << " entries." << std::endl;
+
+    for ( auto iter = bag.begin(); iter != bag.end(); ++iter ) {
+        std::cout << *iter << std::endl;
+        }
+
+    }
+
+#endif
diff -r 2f87e582d91a -r 63df3e6590e2 algs4-c++/src/Bag.hpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/src/Bag.hpp	Thu Jun 11 16:30:14 2015 -0500
@@ -0,0 +1,66 @@
+#ifndef BAG_HPP
+#define BAG_HPP
+
+#include <cstddef>
+
+// Linked list based bag after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
+
+template <typename T>
+class Bag {
+
+private:
+
+    ////////////////////////////////////
+    class Node {
+    public:
+        T item;
+        Node *next;
+        };
+
+
+public:
+
+    ////////////////////////////////////
+    class iterator;
+    friend class iterator;
+    class iterator {
+
+    public:
+
+        iterator( Node *c );
+
+        iterator& operator++();
+        iterator operator++(int);
+
+        T operator*();
+        bool operator!=( typename Bag<T>::iterator );
+
+    private:
+
+        Node *curr;
+        };
+
+    ////////////////////////////////////
+
+    Bag( void );
+    ~Bag( void );
+
+    void add( T &item );
+
+    bool is_empty( void );
+    size_t size( void );
+
+    iterator begin( void );
+    iterator end( void );
+
+private:
+
+    size_t N;
+    Node *list;
+
+    };
+
+
+
+#endif
+
diff -r 2f87e582d91a -r 63df3e6590e2 algs4-c++/src/RandomBag.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/src/RandomBag.cpp	Thu Jun 11 16:30:14 2015 -0500
@@ -0,0 +1,142 @@
+// g++ -D RANDOMBAG_MAIN -std=c++11 RandomBag.cpp
+
+
+#include "RandomBag.hpp"
+
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <chrono>
+#include <iostream>
+#include <iterator>
+#include <random> 
+#include <vector>
+
+
+template <typename T>
+RandomBag<T>::RandomBag( void ) :
+    N (0),
+    max(1) {
+    data = new T[1];
+    }
+    
+template <typename T>
+RandomBag<T>::~RandomBag( void ) {
+    // May leak memory.
+    if ( data )
+        delete[] data;
+    }
+
+template <typename T>
+void RandomBag<T>::add( T &item ) {
+    if ( max == N )
+        resize( 2 * max );
+    data[N++] = item;
+    }
+
+template <typename T>
+bool RandomBag<T>::is_empty( void ) {
+    return N == 0;
+    }
+
+template <typename T>
+size_t RandomBag<T>::size( void ) {
+    return N;
+    }
+
+template <typename T>
+void RandomBag<T>::resize( size_t new_max ) {
+    T *new_data = new T[new_max];
+    for ( size_t i = 0; i < N; ++i )
+        new_data[i] = data[i];
+    T *old_data = data;
+    data = new_data;
+    delete[] old_data;
+    max = new_max;
+    }
+
+template <typename T>
+typename RandomBag<T>::iterator RandomBag<T>::begin( void ) {
+    return RandomBag<T>::iterator( data, data, data+N );
+    }
+
+template <typename T>
+typename RandomBag<T>::iterator RandomBag<T>::end( void ) {
+    return RandomBag<T>::iterator( data, data+N, data+N );
+    }
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+RandomBag<T>::iterator::iterator( T *b, T *f, T *e ) :
+    begin (b),
+    first (f),
+    end (e),
+    curr (0) {
+    size_t size = e - f;
+    for ( size_t i = 0; i < size; ++i ) {
+        order.push_back( (first - begin) + i );
+        }
+
+    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
+    shuffle (order.begin(), order.end(), std::default_random_engine(seed));
+
+    order.push_back( end - begin );
+    }
+
+template <typename T>
+typename RandomBag<T>::iterator & RandomBag<T>::iterator::operator++() {
+    if ( this->curr < this->end - this->first ) {
+        this->curr += 1;
+        }
+    return *this;
+    }
+
+template <typename T>
+typename RandomBag<T>::iterator RandomBag<T>::iterator::operator++( int ) {
+    auto t = RandomBag<T>::iterator( *this );
+    if ( this->curr < this->end - this->first ) {
+        this->curr += 1;
+        }
+    return t;
+    }
+
+template <typename T>
+T RandomBag<T>::iterator::operator*() {
+    return *(this->begin + order[curr]);
+    }
+
+template <typename T>
+bool RandomBag<T>::iterator::operator!=( typename RandomBag<T>::iterator other ) {
+    return (this->begin + this->order[this->curr]) != (other.begin + other.order[other.curr]);
+    }
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+#ifdef RANDOMBAG_MAIN
+
+#include <iostream>
+
+int main ( int argc, char **argv ) {
+
+    RandomBag<long> random_bag;
+
+    long i;
+    while ( ! std::cin.eof() ) {
+        std::cin >> i;
+        if ( std::cin.good() ) 
+            random_bag.add(i);
+        }
+
+    std::cout << "RandomBag has " << random_bag.size() << " entries." << std::endl;
+
+    for ( auto iter = random_bag.begin(); iter != random_bag.end(); ++iter ) {
+        std::cout << *iter << std::endl;
+        }
+
+
+    }
+
+#endif
diff -r 2f87e582d91a -r 63df3e6590e2 algs4-c++/src/RandomBag.hpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/src/RandomBag.hpp	Thu Jun 11 16:30:14 2015 -0500
@@ -0,0 +1,58 @@
+#ifndef RANDOMBAG_HPP
+#define RANDOMBAG_HPP
+
+#include <cstddef>
+#include <vector>
+
+template <typename T>
+class RandomBag {
+
+public:
+
+    ////////////////////////////////////////
+    class iterator {
+
+    public:
+
+        iterator( T *b, T *f, T *e );
+
+        iterator& operator++();
+        iterator operator++(int);
+
+        T operator*();
+        bool operator!=( typename RandomBag<T>::iterator other );
+
+    private:
+
+        T *begin;
+        T *first;
+        T *end;
+        size_t curr;
+        std::vector<size_t> order;
+        };
+
+    ////////////////////////////////////////
+    RandomBag( void );
+    ~RandomBag( void );
+
+    void add( T &item );
+
+    bool is_empty( void );
+    size_t size( void );
+
+    iterator begin( void );
+    iterator end( void );
+
+private:
+
+    size_t N;
+    size_t max;
+    T *data;
+
+    void resize( size_t new_max );
+    };
+
+
+
+#endif
+