# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1435072663 18000
# Node ID ec700842d1825440aab04aee89a7f692afb35ff4
# Parent  86281e8f24ba8e17985b8ba90468f85118da5e26# Parent  a149b424b4e26bf33298657c83f8c61f95d0ce46
MErged changes from home and server.

diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/Bag.cpp
--- a/algs4-c++/src/Bag.cpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/Bag.cpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,182 +1,7 @@
-// g++ -D BAG_MAIN -std=c++0x Bag.cpp
-// g++ -D BAG_MAIN -std=c++11 Bag.cpp
-
+// g++ -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 ) {
@@ -197,5 +22,3 @@
         }
 
     }
-
-#endif
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/Bag.hpp
--- a/algs4-c++/src/Bag.hpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/Bag.hpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,16 +1,16 @@
+// Linked list based bag after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
+
 #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;
@@ -53,6 +53,12 @@
     iterator begin( void );
     iterator end( void );
 
+#ifdef EXERCISES
+    T delete_bottom( void );
+    T remove( size_t k );
+    bool find( T key );
+#endif
+
 private:
 
     size_t N;
@@ -61,6 +67,172 @@
     };
 
 
+////////////////////////////////////////////////////////////////////////////////
+
+
+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
 
+
+#endif
+
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/Deque.cpp
--- a/algs4-c++/src/Deque.cpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/Deque.cpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,170 +1,8 @@
-// g++ -D DEQUE_MAIN -std=c++0x Deque.cpp
-// g++ -D DEQUE_MAIN -std=c++11 Deque.cpp
+// g++ -std=c++11 Deque.cpp
 
 
 #include "Deque.hpp"
 
-#include <cassert>
-#include <cstddef>
-
-#include <iostream>
-
-template <typename T>
-Deque<T>::Deque( void ) :
-    N (0),
-    first (nullptr),
-    last (nullptr)
-    {
-    }
-    
-template <typename T>
-Deque<T>::~Deque( void ) {
-    assert( N == 0 );  // Catch the potential memory leak.
-    while ( first ) {
-        Node *next = first->next;
-        delete first;
-        first = next;
-        }
-    }
-
-template <typename T>
-void Deque<T>::push_right( T &item ) {
-    Node * node = new Node();
-    node->item = item;
-    node->next = nullptr;
-    node->prev = nullptr;
-
-    if ( last ) {
-        last->next = node;
-        node->prev = last;
-        last = node;
-        }
-    else {
-        last = first = node;
-        }
-
-    N++;
-    }
-
-template <typename T>
-void Deque<T>::push_left( T &item ) {
-    Node * node = new Node();
-    node->item = item;
-    node->next = nullptr;
-    node->prev = nullptr;
-
-    if ( first ) {
-        node->next = first;
-        first->prev = node;
-        first = node;
-        }
-    else {
-        last = first = node;
-        }
-
-    N++;
-    }
-
-template <typename T>
-T Deque<T>::pop_left( void ) {
-    assert( N > 0 );
-
-    T item = first->item;
-
-    Node *old = first;
-    if ( first->next )
-        first->next->prev = nullptr;
-    first = first->next;
-    delete old;
-    N--;
-
-    if ( ! first )
-        last = nullptr;
-
-    return item;
-    }
-
-template <typename T>
-T Deque<T>::pop_right( void ) {
-    assert( N > 0 );
-
-    T item = last->item;
-
-    Node *old = last;
-    if ( last->prev )
-        last->prev->next = nullptr;
-    last = last->prev;
-    delete old;
-    N--;
-
-    if ( ! last )
-        first = nullptr;
-
-    return item;
-    }
-
-template <typename T>
-bool Deque<T>::is_empty( void ) {
-    return N == 0;
-    }
-
-template <typename T>
-size_t Deque<T>::size( void ) {
-    return N;
-    }
-
-template <typename T>
-typename Deque<T>::iterator Deque<T>::begin( void ) {
-    return Deque<T>::iterator( first );
-    }
-
-template <typename T>
-typename Deque<T>::iterator Deque<T>::end( void ) {
-    return Deque<T>::iterator( nullptr );
-    }
-
-
-////////////////////////////////////////////////////////////////////////////////
-
-template <typename T>
-Deque<T>::iterator::iterator( Node *c ) :
-    curr (c)
-    {
-    }
-
-template <typename T>
-typename Deque<T>::iterator & Deque<T>::iterator::operator++() {
-    if ( this->curr != nullptr ) {
-        this->curr = this->curr->next;
-        }
-    return *this;
-    }
-
-template <typename T>
-typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) {
-    auto t = Deque<T>::iterator( *this );
-
-    if ( this->curr != nullptr ) {
-        this->curr = this->curr->next;
-        }
-    return t;
-    }
-
-template <typename T>
-T Deque<T>::iterator::operator*() {
-    return this->curr->item;
-    }
-
-template <typename T>
-bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) {
-    return this->curr != other.curr;
-    }
-
-
-////////////////////////////////////////////////////////////////////////////////
-
-#ifdef DEQUE_MAIN
-
 #include <iostream>
 
 int main ( int argc, char **argv ) {
@@ -211,5 +49,3 @@
     std::cout << "Deque has " << deque.size() << " entries." << std::endl;
 
     }
-
-#endif
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/Deque.hpp
--- a/algs4-c++/src/Deque.hpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/Deque.hpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,10 +1,11 @@
+// Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
+
 #ifndef DEQUE_HPP
 #define DEQUE_HPP
 
+#include <cassert>
 #include <cstddef>
 
-// Linked list based deque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.3
-
 template <typename T>
 class Deque {
 
@@ -66,6 +67,158 @@
     };
 
 
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+Deque<T>::Deque( void ) :
+    N (0),
+    first (nullptr),
+    last (nullptr)
+    {
+    }
+    
+template <typename T>
+Deque<T>::~Deque( void ) {
+    assert( N == 0 );  // Catch the potential memory leak.
+    while ( first ) {
+        Node *next = first->next;
+        delete first;
+        first = next;
+        }
+    }
+
+template <typename T>
+void Deque<T>::push_right( T &item ) {
+    Node * node = new Node();
+    node->item = item;
+    node->next = nullptr;
+    node->prev = nullptr;
+
+    if ( last ) {
+        last->next = node;
+        node->prev = last;
+        last = node;
+        }
+    else {
+        last = first = node;
+        }
+
+    N++;
+    }
+
+template <typename T>
+void Deque<T>::push_left( T &item ) {
+    Node * node = new Node();
+    node->item = item;
+    node->next = nullptr;
+    node->prev = nullptr;
+
+    if ( first ) {
+        node->next = first;
+        first->prev = node;
+        first = node;
+        }
+    else {
+        last = first = node;
+        }
+
+    N++;
+    }
+
+template <typename T>
+T Deque<T>::pop_left( void ) {
+    assert( N > 0 );
+
+    T item = first->item;
+
+    Node *old = first;
+    if ( first->next )
+        first->next->prev = nullptr;
+    first = first->next;
+    delete old;
+    N--;
+
+    if ( ! first )
+        last = nullptr;
+
+    return item;
+    }
+
+template <typename T>
+T Deque<T>::pop_right( void ) {
+    assert( N > 0 );
+
+    T item = last->item;
+
+    Node *old = last;
+    if ( last->prev )
+        last->prev->next = nullptr;
+    last = last->prev;
+    delete old;
+    N--;
+
+    if ( ! last )
+        first = nullptr;
+
+    return item;
+    }
+
+template <typename T>
+bool Deque<T>::is_empty( void ) {
+    return N == 0;
+    }
+
+template <typename T>
+size_t Deque<T>::size( void ) {
+    return N;
+    }
+
+template <typename T>
+typename Deque<T>::iterator Deque<T>::begin( void ) {
+    return Deque<T>::iterator( first );
+    }
+
+template <typename T>
+typename Deque<T>::iterator Deque<T>::end( void ) {
+    return Deque<T>::iterator( nullptr );
+    }
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+Deque<T>::iterator::iterator( Node *c ) :
+    curr (c)
+    {
+    }
+
+template <typename T>
+typename Deque<T>::iterator & Deque<T>::iterator::operator++() {
+    if ( this->curr != nullptr ) {
+        this->curr = this->curr->next;
+        }
+    return *this;
+    }
+
+template <typename T>
+typename Deque<T>::iterator Deque<T>::iterator::operator++( int ) {
+    auto t = Deque<T>::iterator( *this );
+
+    if ( this->curr != nullptr ) {
+        this->curr = this->curr->next;
+        }
+    return t;
+    }
+
+template <typename T>
+T Deque<T>::iterator::operator*() {
+    return this->curr->item;
+    }
+
+template <typename T>
+bool Deque<T>::iterator::operator!=( typename Deque<T>::iterator other ) {
+    return this->curr != other.curr;
+    }
 
 #endif
 
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/Queue.hpp
--- a/algs4-c++/src/Queue.hpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/Queue.hpp	Tue Jun 23 10:17:43 2015 -0500
@@ -5,8 +5,6 @@
 
 #include <cstddef>
 #include <cassert>
-#include <iostream>
-
 
 template <typename T>
 class Queue {
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/RandomBag.cpp
--- a/algs4-c++/src/RandomBag.cpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/RandomBag.cpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,122 +1,7 @@
-// g++ -D RANDOMBAG_MAIN -std=c++11 RandomBag.cpp
-
+// g++ -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 ) {
@@ -138,5 +23,3 @@
 
 
     }
-
-#endif
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/RandomBag.hpp
--- a/algs4-c++/src/RandomBag.hpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/RandomBag.hpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,7 +1,14 @@
+// Bag class with random iteration order.
+
 #ifndef RANDOMBAG_HPP
 #define RANDOMBAG_HPP
 
+#include <algorithm>
 #include <cstddef>
+#include <chrono>
+#include <iostream>
+#include <iterator>
+#include <random> 
 #include <vector>
 
 template <typename T>
@@ -53,6 +60,108 @@
     };
 
 
+////////////////////////////////////////////////////////////////////////////////
+
+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]);
+    }
+
+
 
 #endif
 
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/ResizingArrayDeque.cpp
--- a/algs4-c++/src/ResizingArrayDeque.cpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/ResizingArrayDeque.cpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,216 +1,8 @@
-// g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++0x ResizingArrayDeque.cpp
-// g++ -D RESIZINGARRAYDEQUE_MAIN -std=c++11 ResizingArrayDeque.cpp
+// g++ -std=c++11 ResizingArrayDeque.cpp
 
 
 #include "ResizingArrayDeque.hpp"
 
-#include <cassert>
-#include <cstddef>
-
-#include <iostream>
-
-template <typename T>
-ResizingArrayDeque<T>::ResizingArrayDeque( void ) :
-    N (0),
-    max(1),
-    first(nullptr),
-    last(nullptr) {
-    data = new T[2];
-    }
-    
-template <typename T>
-ResizingArrayDeque<T>::~ResizingArrayDeque( void ) {
-    assert( N == 0 );  // Catch the potential memory leak.
-    if ( data )
-        delete[] data;
-    }
-
-template <typename T>
-void ResizingArrayDeque<T>::push_right( T &item ) {
-    if ( N == max )
-        resize( 2 * max );
-
-    if ( last ) {
-        if ( last == data )
-            last = data + max - 1;
-        else
-            ++last;
-        }
-    else {
-        first = last = data;
-        }
-
-    *last = item;
-    ++N;
-    }
-
-template <typename T>
-void ResizingArrayDeque<T>::push_left( T &item ) {
-    if ( N == max )
-        resize( 2 * max );
-
-    if ( first ) {
-        if ( first == data )
-            first = data + max - 1;
-        else
-            --first;
-        }
-    else {
-        first = last = data;
-        }
-
-    *first = item;
-    ++N;
-    }
-
-template <typename T>
-T ResizingArrayDeque<T>::pop_right( void ) {
-    assert( N > 0 );
-
-    T item = *last;
-    N--;
-
-    if ( last == data ) {
-        last = data + max - 1;
-        }
-    else {
-        --last;
-        }
-
-    if ( N == 0 )
-        first = last = nullptr;
-
-    // if ( N <= max/4 )
-    //     resize( max/2 );
-
-    return item;
-    }
-
-template <typename T>
-T ResizingArrayDeque<T>::pop_left( void ) {
-    assert( N > 0 );
-
-    T item = *first;
-    N--;
-
-    if ( first == data + max - 1 ) {
-        first = data;
-        }
-    else {
-        ++first;
-        }
-
-    if ( N == 0 )
-        first = last = nullptr;
-
-    // if ( N <= max/4 )
-    //     resize( max/2 );
-
-    return item;
-    }
-
-template <typename T>
-bool ResizingArrayDeque<T>::is_empty( void ) {
-    return N == 0;
-    }
-
-template <typename T>
-size_t ResizingArrayDeque<T>::size( void ) {
-    return N;
-    }
-
-template <typename T>
-void ResizingArrayDeque<T>::resize( size_t new_max ) {
-    T *new_data = new T[new_max];
-
-    if ( N ) {
-        size_t i = 0;
-        T *curr = first;
-        while ( i < N ) {
-            new_data[i] = *curr;
-            ++curr;
-            if ( curr == data + max )
-                curr = data;
-            ++i;
-            }
-        }
-    first = new_data;
-    last = new_data + N - 1;
-
-    T *old_data = data;
-    data = new_data;
-    delete[] old_data;
-
-    max = new_max;
-    }
-
-template <typename T>
-typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::begin( void ) {
-    return ResizingArrayDeque<T>::iterator( first, last, data, data + max - 1 );
-    }
-
-template <typename T>
-typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::end( void ) {
-    return ResizingArrayDeque<T>::iterator( nullptr, nullptr, nullptr, nullptr );
-    }
-
-
-////////////////////////////////////////////////////////////////////////////////
-
-template <typename T>
-ResizingArrayDeque<T>::iterator::iterator( T *c, T *l, T *b, T *m ) :
-    curr (c),
-    last (l),
-    begin (b),
-    max (m)
-    {
-    }
-
-template <typename T>
-typename ResizingArrayDeque<T>::iterator & ResizingArrayDeque<T>::iterator::operator++() {
-    if ( this->curr == this->last ) {
-        this->curr = nullptr;
-        }
-    else {
-        this->curr += 1;
-        if ( this->curr > this->max )
-            this->curr = this->begin;
-        }
-
-    return *this;
-    }
-
-template <typename T>
-typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::iterator::operator++( int ) {
-    auto t = ResizingArrayDeque<T>::iterator( *this );
-
-    if ( this->curr == this->last ) {
-        this->curr = nullptr;
-        }
-    else {
-        this->curr += 1;
-        if ( this->curr > this->max )
-            this->curr = this->begin;
-        }
-
-    return t;
-    }
-
-template <typename T>
-T ResizingArrayDeque<T>::iterator::operator*() {
-    return *(this->curr);
-    }
-
-template <typename T>
-bool ResizingArrayDeque<T>::iterator::operator!=( typename ResizingArrayDeque<T>::iterator other ) {
-    return this->curr != other.curr;
-    }
-
-
-////////////////////////////////////////////////////////////////////////////////
-
-#ifdef RESIZINGARRAYDEQUE_MAIN
-
 #include <iostream>
 
 int main ( int argc, char **argv ) {
@@ -258,4 +50,3 @@
 
     }
 
-#endif
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/ResizingArrayDeque.hpp
--- a/algs4-c++/src/ResizingArrayDeque.hpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/ResizingArrayDeque.hpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,6 +1,9 @@
+// Double ended queue built on a resizing array.
+
 #ifndef RESIZINGARRAYDEQUE_HPP
 #define RESIZINGARRAYDEQUE_HPP
 
+#include <cassert>
 #include <cstddef>
 
 template <typename T>
@@ -54,6 +57,206 @@
     void resize( size_t new_max );
     };
 
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+ResizingArrayDeque<T>::ResizingArrayDeque( void ) :
+    N (0),
+    max(1),
+    first(nullptr),
+    last(nullptr) {
+    data = new T[2];
+    }
+    
+template <typename T>
+ResizingArrayDeque<T>::~ResizingArrayDeque( void ) {
+    assert( N == 0 );  // Catch the potential memory leak.
+    if ( data )
+        delete[] data;
+    }
+
+template <typename T>
+void ResizingArrayDeque<T>::push_right( T &item ) {
+    if ( N == max )
+        resize( 2 * max );
+
+    if ( last ) {
+        if ( last == data )
+            last = data + max - 1;
+        else
+            ++last;
+        }
+    else {
+        first = last = data;
+        }
+
+    *last = item;
+    ++N;
+    }
+
+template <typename T>
+void ResizingArrayDeque<T>::push_left( T &item ) {
+    if ( N == max )
+        resize( 2 * max );
+
+    if ( first ) {
+        if ( first == data )
+            first = data + max - 1;
+        else
+            --first;
+        }
+    else {
+        first = last = data;
+        }
+
+    *first = item;
+    ++N;
+    }
+
+template <typename T>
+T ResizingArrayDeque<T>::pop_right( void ) {
+    assert( N > 0 );
+
+    T item = *last;
+    N--;
+
+    if ( last == data ) {
+        last = data + max - 1;
+        }
+    else {
+        --last;
+        }
+
+    if ( N == 0 )
+        first = last = nullptr;
+
+    // if ( N <= max/4 )
+    //     resize( max/2 );
+
+    return item;
+    }
+
+template <typename T>
+T ResizingArrayDeque<T>::pop_left( void ) {
+    assert( N > 0 );
+
+    T item = *first;
+    N--;
+
+    if ( first == data + max - 1 ) {
+        first = data;
+        }
+    else {
+        ++first;
+        }
+
+    if ( N == 0 )
+        first = last = nullptr;
+
+    // if ( N <= max/4 )
+    //     resize( max/2 );
+
+    return item;
+    }
+
+template <typename T>
+bool ResizingArrayDeque<T>::is_empty( void ) {
+    return N == 0;
+    }
+
+template <typename T>
+size_t ResizingArrayDeque<T>::size( void ) {
+    return N;
+    }
+
+template <typename T>
+void ResizingArrayDeque<T>::resize( size_t new_max ) {
+    T *new_data = new T[new_max];
+
+    if ( N ) {
+        size_t i = 0;
+        T *curr = first;
+        while ( i < N ) {
+            new_data[i] = *curr;
+            ++curr;
+            if ( curr == data + max )
+                curr = data;
+            ++i;
+            }
+        }
+    first = new_data;
+    last = new_data + N - 1;
+
+    T *old_data = data;
+    data = new_data;
+    delete[] old_data;
+
+    max = new_max;
+    }
+
+template <typename T>
+typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::begin( void ) {
+    return ResizingArrayDeque<T>::iterator( first, last, data, data + max - 1 );
+    }
+
+template <typename T>
+typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::end( void ) {
+    return ResizingArrayDeque<T>::iterator( nullptr, nullptr, nullptr, nullptr );
+    }
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+ResizingArrayDeque<T>::iterator::iterator( T *c, T *l, T *b, T *m ) :
+    curr (c),
+    last (l),
+    begin (b),
+    max (m)
+    {
+    }
+
+template <typename T>
+typename ResizingArrayDeque<T>::iterator & ResizingArrayDeque<T>::iterator::operator++() {
+    if ( this->curr == this->last ) {
+        this->curr = nullptr;
+        }
+    else {
+        this->curr += 1;
+        if ( this->curr > this->max )
+            this->curr = this->begin;
+        }
+
+    return *this;
+    }
+
+template <typename T>
+typename ResizingArrayDeque<T>::iterator ResizingArrayDeque<T>::iterator::operator++( int ) {
+    auto t = ResizingArrayDeque<T>::iterator( *this );
+
+    if ( this->curr == this->last ) {
+        this->curr = nullptr;
+        }
+    else {
+        this->curr += 1;
+        if ( this->curr > this->max )
+            this->curr = this->begin;
+        }
+
+    return t;
+    }
+
+template <typename T>
+T ResizingArrayDeque<T>::iterator::operator*() {
+    return *(this->curr);
+    }
+
+template <typename T>
+bool ResizingArrayDeque<T>::iterator::operator!=( typename ResizingArrayDeque<T>::iterator other ) {
+    return this->curr != other.curr;
+    }
+
+
 
 
 #endif
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/ResizingArrayStack.cpp
--- a/algs4-c++/src/ResizingArrayStack.cpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/ResizingArrayStack.cpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,120 +1,8 @@
-// g++ -D RESIZINGARRAYSTACK_MAIN -std=c++0x ResizingArrayStack.cpp
-// g++ -D RESIZINGARRAYSTACK_MAIN -std=c++11 ResizingArrayStack.cpp
+// g++ -std=c++11 ResizingArrayStack.cpp
 
 
 #include "ResizingArrayStack.hpp"
 
-#include <cassert>
-#include <cstddef>
-
-#include <iostream>
-
-template <typename T>
-ResizingArrayStack<T>::ResizingArrayStack( void ) :
-    N (0),
-    max(1) {
-    data = new T[1];
-    }
-    
-template <typename T>
-ResizingArrayStack<T>::~ResizingArrayStack( void ) {
-    assert( N == 0 );  // Catch the potential memory leak.
-    if ( data )
-        delete[] data;
-    }
-
-template <typename T>
-void ResizingArrayStack<T>::push( T &item ) {
-    if ( max == N )
-        resize( 2 * max );
-    data[N++] = item;
-    }
-
-template <typename T>
-T ResizingArrayStack<T>::pop( void ) {
-    assert( N > 0 );
-    T item = data[N-1];
-    N--;
-
-    if ( N <= max/4 )
-        resize( max/2 );
-
-    return item;
-    }
-
-template <typename T>
-bool ResizingArrayStack<T>::is_empty( void ) {
-    return N == 0;
-    }
-
-template <typename T>
-size_t ResizingArrayStack<T>::size( void ) {
-    return N;
-    }
-
-template <typename T>
-void ResizingArrayStack<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 ResizingArrayStack<T>::iterator ResizingArrayStack<T>::begin( void ) {
-    return ResizingArrayStack<T>::iterator( data+N-1, data-1 );
-    }
-
-template <typename T>
-typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::end( void ) {
-    return ResizingArrayStack<T>::iterator( data-1, data-1 );
-    }
-
-
-////////////////////////////////////////////////////////////////////////////////
-
-template <typename T>
-ResizingArrayStack<T>::iterator::iterator( T *c, T *e ) :
-    curr (c),
-    end (e)
-    {
-    }
-
-template <typename T>
-typename ResizingArrayStack<T>::iterator & ResizingArrayStack<T>::iterator::operator++() {
-    if ( this->curr > this->end ) {
-        this->curr -= 1;
-        }
-    return *this;
-    }
-
-template <typename T>
-typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::iterator::operator++( int ) {
-    auto t = ResizingArrayStack<T>::iterator( *this );
-    if ( this->curr > this->end ) {
-        this->curr -= 1;
-        }
-    return t;
-    }
-
-template <typename T>
-T ResizingArrayStack<T>::iterator::operator*() {
-    return *(this->curr);
-    }
-
-template <typename T>
-bool ResizingArrayStack<T>::iterator::operator!=( typename ResizingArrayStack<T>::iterator other ) {
-    return this->curr != other.curr;
-    }
-
-
-////////////////////////////////////////////////////////////////////////////////
-
-#ifdef RESIZINGARRAYSTACK_MAIN
-
 #include <iostream>
 
 int main ( int argc, char **argv ) {
@@ -145,4 +33,3 @@
 
     }
 
-#endif
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/ResizingArrayStack.hpp
--- a/algs4-c++/src/ResizingArrayStack.hpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/ResizingArrayStack.hpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,6 +1,9 @@
+// Stack built on a resizing array.
+
 #ifndef RESIZINGARRAYSTACK_HPP
 #define RESIZINGARRAYSTACK_HPP
 
+#include <cassert>
 #include <cstddef>
 
 template <typename T>
@@ -49,6 +52,109 @@
     void resize( size_t new_max );
     };
 
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+ResizingArrayStack<T>::ResizingArrayStack( void ) :
+    N (0),
+    max(1) {
+    data = new T[1];
+    }
+    
+template <typename T>
+ResizingArrayStack<T>::~ResizingArrayStack( void ) {
+    assert( N == 0 );  // Catch the potential memory leak.
+    if ( data )
+        delete[] data;
+    }
+
+template <typename T>
+void ResizingArrayStack<T>::push( T &item ) {
+    if ( max == N )
+        resize( 2 * max );
+    data[N++] = item;
+    }
+
+template <typename T>
+T ResizingArrayStack<T>::pop( void ) {
+    assert( N > 0 );
+    T item = data[N-1];
+    N--;
+
+    if ( N <= max/4 )
+        resize( max/2 );
+
+    return item;
+    }
+
+template <typename T>
+bool ResizingArrayStack<T>::is_empty( void ) {
+    return N == 0;
+    }
+
+template <typename T>
+size_t ResizingArrayStack<T>::size( void ) {
+    return N;
+    }
+
+template <typename T>
+void ResizingArrayStack<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 ResizingArrayStack<T>::iterator ResizingArrayStack<T>::begin( void ) {
+    return ResizingArrayStack<T>::iterator( data+N-1, data-1 );
+    }
+
+template <typename T>
+typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::end( void ) {
+    return ResizingArrayStack<T>::iterator( data-1, data-1 );
+    }
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+ResizingArrayStack<T>::iterator::iterator( T *c, T *e ) :
+    curr (c),
+    end (e)
+    {
+    }
+
+template <typename T>
+typename ResizingArrayStack<T>::iterator & ResizingArrayStack<T>::iterator::operator++() {
+    if ( this->curr > this->end ) {
+        this->curr -= 1;
+        }
+    return *this;
+    }
+
+template <typename T>
+typename ResizingArrayStack<T>::iterator ResizingArrayStack<T>::iterator::operator++( int ) {
+    auto t = ResizingArrayStack<T>::iterator( *this );
+    if ( this->curr > this->end ) {
+        this->curr -= 1;
+        }
+    return t;
+    }
+
+template <typename T>
+T ResizingArrayStack<T>::iterator::operator*() {
+    return *(this->curr);
+    }
+
+template <typename T>
+bool ResizingArrayStack<T>::iterator::operator!=( typename ResizingArrayStack<T>::iterator other ) {
+    return this->curr != other.curr;
+    }
+
 
 
 #endif
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/Stack.cpp
--- a/algs4-c++/src/Stack.cpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/Stack.cpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,196 +1,8 @@
-// g++ -D STACK_MAIN -std=c++0x Stack.cpp
-// g++ -D STACK_MAIN -std=c++11 Stack.cpp
+// g++ -std=c++11 Stack.cpp
 
 
 #include "Stack.hpp"
 
-#include <cassert>
-#include <cstddef>
-
-#include <iostream>
-
-template <typename T>
-Stack<T>::Stack( void ) :
-    N (0),
-    list (nullptr)
-    {
-    }
-    
-template <typename T>
-Stack<T>::~Stack( void ) {
-    assert( N == 0 );  // Catch the potential memory leak.
-    while ( list ) {
-        Node * next = list->next;
-        delete list;
-        list = next;
-        }
-    }
-
-template <typename T>
-void Stack<T>::push( T &item ) {
-    Node * node = new Node();
-    node->item = item;
-    node->next = list;
-    list = node;
-    N++;
-    }
-
-template <typename T>
-T Stack<T>::pop( void ) {
-    assert( N > 0 );
-
-    T item = list->item;
-
-    Node *old = list;
-    list = list->next;
-    delete old;
-    N--;
-
-    return item;
-    }
-
-template <typename T>
-bool Stack<T>::is_empty( void ) {
-    return N == 0;
-    }
-
-template <typename T>
-size_t Stack<T>::size( void ) {
-    return N;
-    }
-
-template <typename T>
-typename Stack<T>::iterator Stack<T>::begin( void ) {
-    return Stack<T>::iterator( list );
-    }
-
-template <typename T>
-typename Stack<T>::iterator Stack<T>::end( void ) {
-    return Stack<T>::iterator( nullptr );
-    }
-
-
-////////////////////////////////////////////////////////////////////////////////
-
-template <typename T>
-Stack<T>::iterator::iterator( Node *c ) :
-    curr (c)
-    {
-    }
-
-template <typename T>
-typename Stack<T>::iterator & Stack<T>::iterator::operator++() {
-    if ( this->curr != nullptr ) {
-        this->curr = this->curr->next;
-        }
-    return *this;
-    }
-
-template <typename T>
-typename Stack<T>::iterator Stack<T>::iterator::operator++( int ) {
-    auto t = Stack<T>::iterator( *this );
-
-    if ( this->curr != nullptr ) {
-        this->curr = this->curr->next;
-        }
-    return t;
-    }
-
-template <typename T>
-T Stack<T>::iterator::operator*() {
-    return this->curr->item;
-    }
-
-template <typename T>
-bool Stack<T>::iterator::operator!=( typename Stack<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 Stack<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 Stack<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 stack.
-template <typename T>
-bool Stack<T>::find( T key ) {
-    Node *curr = list;
-
-    while ( curr ) {
-        if ( curr->item == key )
-            return true;
-        curr = curr->next;
-        }
-
-    return false;
-    }
-
-#endif
-
-
-////////////////////////////////////////////////////////////////////////////////
-
-#ifdef STACK_MAIN
-
 #include <iostream>
 
 int main ( int argc, char **argv ) {
@@ -244,5 +56,3 @@
     std::cout << "Stack has " << stack.size() << " entries." << std::endl;
 
     }
-
-#endif
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/Stack.hpp
--- a/algs4-c++/src/Stack.hpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/Stack.hpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,9 +1,11 @@
+// Linked list based stack after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
+
 #ifndef STACK_HPP
 #define STACK_HPP
 
+#include <cassert>
 #include <cstddef>
 
-// Linked list based stack after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
 
 template <typename T>
 class Stack {
@@ -70,6 +72,186 @@
     };
 
 
+////////////////////////////////////////////////////////////////////////////////
+
+
+template <typename T>
+Stack<T>::Stack( void ) :
+    N (0),
+    list (nullptr)
+    {
+    }
+    
+template <typename T>
+Stack<T>::~Stack( void ) {
+    assert( N == 0 );  // Catch the potential memory leak.
+    while ( list ) {
+        Node * next = list->next;
+        delete list;
+        list = next;
+        }
+    }
+
+template <typename T>
+void Stack<T>::push( T &item ) {
+    Node * node = new Node();
+    node->item = item;
+    node->next = list;
+    list = node;
+    N++;
+    }
+
+template <typename T>
+T Stack<T>::pop( void ) {
+    assert( N > 0 );
+
+    T item = list->item;
+
+    Node *old = list;
+    list = list->next;
+    delete old;
+    N--;
+
+    return item;
+    }
+
+template <typename T>
+bool Stack<T>::is_empty( void ) {
+    return N == 0;
+    }
+
+template <typename T>
+size_t Stack<T>::size( void ) {
+    return N;
+    }
+
+template <typename T>
+typename Stack<T>::iterator Stack<T>::begin( void ) {
+    return Stack<T>::iterator( list );
+    }
+
+template <typename T>
+typename Stack<T>::iterator Stack<T>::end( void ) {
+    return Stack<T>::iterator( nullptr );
+    }
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+Stack<T>::iterator::iterator( Node *c ) :
+    curr (c)
+    {
+    }
+
+template <typename T>
+typename Stack<T>::iterator & Stack<T>::iterator::operator++() {
+    if ( this->curr != nullptr ) {
+        this->curr = this->curr->next;
+        }
+    return *this;
+    }
+
+template <typename T>
+typename Stack<T>::iterator Stack<T>::iterator::operator++( int ) {
+    auto t = Stack<T>::iterator( *this );
+
+    if ( this->curr != nullptr ) {
+        this->curr = this->curr->next;
+        }
+    return t;
+    }
+
+template <typename T>
+T Stack<T>::iterator::operator*() {
+    return this->curr->item;
+    }
+
+template <typename T>
+bool Stack<T>::iterator::operator!=( typename Stack<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 Stack<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 Stack<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 stack.
+template <typename T>
+bool Stack<T>::find( T key ) {
+    Node *curr = list;
+
+    while ( curr ) {
+        if ( curr->item == key )
+            return true;
+        curr = curr->next;
+        }
+
+    return false;
+    }
 
 #endif
 
+
+#endif
+
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/Steque.cpp
--- a/algs4-c++/src/Steque.cpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/Steque.cpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,141 +1,8 @@
-// g++ -D STEQUE_MAIN -std=c++0x Steque.cpp
-// g++ -D STEQUE_MAIN -std=c++11 Steque.cpp
+// g++ -std=c++11 Steque.cpp
 
 
 #include "Steque.hpp"
 
-#include <cassert>
-#include <cstddef>
-
-#include <iostream>
-
-template <typename T>
-Steque<T>::Steque( void ) :
-    N (0),
-    list (nullptr)
-    {
-    }
-    
-template <typename T>
-Steque<T>::~Steque( void ) {
-    assert( N == 0 );  // Catch the potential memory leak.
-    while ( list ) {
-        Node * next = list->next;
-        delete list;
-        list = next;
-        }
-    }
-
-template <typename T>
-void Steque<T>::push( T &item ) {
-    Node * node = new Node();
-    node->item = item;
-    node->next = list;
-    list = node;
-    N++;
-    }
-
-template <typename T>
-T Steque<T>::pop( void ) {
-    assert( N > 0 );
-
-    T item = list->item;
-
-    Node *old = list;
-    list = list->next;
-    delete old;
-    N--;
-
-    return item;
-    }
-
-template <typename T>
-void Steque<T>::enqueue( T &item ) {
-    Node *curr = list;
-
-    Node *node = new Node();
-    node->item = item;
-    node->next = nullptr;
-
-    if ( ! curr ) {
-        list = node;
-        N++;
-        return;
-        }
-
-    while ( curr->next ) {
-        curr = curr->next;
-        }
-
-    curr->next = node;
-    N++;
-
-    return;
-    }
-
-template <typename T>
-bool Steque<T>::is_empty( void ) {
-    return N == 0;
-    }
-
-template <typename T>
-size_t Steque<T>::size( void ) {
-    return N;
-    }
-
-template <typename T>
-typename Steque<T>::iterator Steque<T>::begin( void ) {
-    return Steque<T>::iterator( list );
-    }
-
-template <typename T>
-typename Steque<T>::iterator Steque<T>::end( void ) {
-    return Steque<T>::iterator( nullptr );
-    }
-
-
-////////////////////////////////////////////////////////////////////////////////
-
-template <typename T>
-Steque<T>::iterator::iterator( Node *c ) :
-    curr (c)
-    {
-    }
-
-template <typename T>
-typename Steque<T>::iterator & Steque<T>::iterator::operator++() {
-    if ( this->curr != nullptr ) {
-        this->curr = this->curr->next;
-        }
-    return *this;
-    }
-
-template <typename T>
-typename Steque<T>::iterator Steque<T>::iterator::operator++( int ) {
-    auto t = Steque<T>::iterator( *this );
-
-    if ( this->curr != nullptr ) {
-        this->curr = this->curr->next;
-        }
-    return t;
-    }
-
-template <typename T>
-T Steque<T>::iterator::operator*() {
-    return this->curr->item;
-    }
-
-template <typename T>
-bool Steque<T>::iterator::operator!=( typename Steque<T>::iterator other ) {
-    return this->curr != other.curr;
-    }
-
-////////////////////////////////////////////////////////////////////////////////
-
-
-
-#ifdef STEQUE_MAIN
-
 #include <iostream>
 
 int main ( int argc, char **argv ) {
@@ -174,5 +41,3 @@
     std::cout << "Steque has " << steque.size() << " entries." << std::endl;
 
     }
-
-#endif
diff -r 86281e8f24ba -r ec700842d182 algs4-c++/src/Steque.hpp
--- a/algs4-c++/src/Steque.hpp	Mon Jun 22 15:38:25 2015 -0500
+++ b/algs4-c++/src/Steque.hpp	Tue Jun 23 10:17:43 2015 -0500
@@ -1,10 +1,11 @@
+// Linked list based steque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
+
 #ifndef STEQUE_HPP
 #define STEQUE_HPP
 
+#include <cassert>
 #include <cstddef>
 
-// Linked list based steque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
-
 template <typename T>
 class Steque {
 
@@ -63,6 +64,129 @@
     };
 
 
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+Steque<T>::Steque( void ) :
+    N (0),
+    list (nullptr)
+    {
+    }
+    
+template <typename T>
+Steque<T>::~Steque( void ) {
+    assert( N == 0 );  // Catch the potential memory leak.
+    while ( list ) {
+        Node * next = list->next;
+        delete list;
+        list = next;
+        }
+    }
+
+template <typename T>
+void Steque<T>::push( T &item ) {
+    Node * node = new Node();
+    node->item = item;
+    node->next = list;
+    list = node;
+    N++;
+    }
+
+template <typename T>
+T Steque<T>::pop( void ) {
+    assert( N > 0 );
+
+    T item = list->item;
+
+    Node *old = list;
+    list = list->next;
+    delete old;
+    N--;
+
+    return item;
+    }
+
+template <typename T>
+void Steque<T>::enqueue( T &item ) {
+    Node *curr = list;
+
+    Node *node = new Node();
+    node->item = item;
+    node->next = nullptr;
+
+    if ( ! curr ) {
+        list = node;
+        N++;
+        return;
+        }
+
+    while ( curr->next ) {
+        curr = curr->next;
+        }
+
+    curr->next = node;
+    N++;
+
+    return;
+    }
+
+template <typename T>
+bool Steque<T>::is_empty( void ) {
+    return N == 0;
+    }
+
+template <typename T>
+size_t Steque<T>::size( void ) {
+    return N;
+    }
+
+template <typename T>
+typename Steque<T>::iterator Steque<T>::begin( void ) {
+    return Steque<T>::iterator( list );
+    }
+
+template <typename T>
+typename Steque<T>::iterator Steque<T>::end( void ) {
+    return Steque<T>::iterator( nullptr );
+    }
+
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+Steque<T>::iterator::iterator( Node *c ) :
+    curr (c)
+    {
+    }
+
+template <typename T>
+typename Steque<T>::iterator & Steque<T>::iterator::operator++() {
+    if ( this->curr != nullptr ) {
+        this->curr = this->curr->next;
+        }
+    return *this;
+    }
+
+template <typename T>
+typename Steque<T>::iterator Steque<T>::iterator::operator++( int ) {
+    auto t = Steque<T>::iterator( *this );
+
+    if ( this->curr != nullptr ) {
+        this->curr = this->curr->next;
+        }
+    return t;
+    }
+
+template <typename T>
+T Steque<T>::iterator::operator*() {
+    return this->curr->item;
+    }
+
+template <typename T>
+bool Steque<T>::iterator::operator!=( typename Steque<T>::iterator other ) {
+    return this->curr != other.curr;
+    }
+
 
 #endif