# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1433803974 18000
# Node ID 8af1a61be7c11e2fc719beda49221d5038fc174b
# Parent  0f99a5ae6cd45ea3bd5954bcbf474f53209755d1
Added some of the exercises from chapter 1

diff -r 0f99a5ae6cd4 -r 8af1a61be7c1 algs4-c++/src/Stack.cpp
--- a/algs4-c++/src/Stack.cpp	Fri May 29 21:34:18 2015 -0500
+++ b/algs4-c++/src/Stack.cpp	Mon Jun 08 17:52:54 2015 -0500
@@ -106,6 +106,86 @@
     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
+
 
 ////////////////////////////////////////////////////////////////////////////////
 
@@ -130,6 +210,30 @@
         std::cout << *iter << std::endl;
         }
 
+#ifdef EXERCISES
+    std::cout << "Looking for 3: " << ( stack.find( 3 ) ? "found" : "not found" ) << std::endl;
+    std::cout << "Looking for 9999: " << ( stack.find( 9999 ) ? "found" : "not found" ) << std::endl;
+
+    std::cout << "Removing bottom entry: ";
+    i = stack.delete_bottom();
+    std::cout << i << std::endl;
+    std::cout << "Stack has " << stack.size() << " entries." << std::endl;
+
+    for ( auto iter = stack.begin(); iter != stack.end(); ++iter ) {
+        std::cout << *iter << std::endl;
+        }
+
+    std::cout << "Removing entry 2: ";
+    i = stack.remove( 2 );
+    std::cout << i << std::endl;
+    std::cout << "Stack has " << stack.size() << " entries." << std::endl;
+
+    for ( auto iter = stack.begin(); iter != stack.end(); ++iter ) {
+        std::cout << *iter << std::endl;
+        }
+
+#endif
+
     std::cout << "Popping entries..." << std::endl;
 
     while ( ! stack.is_empty() ) {
diff -r 0f99a5ae6cd4 -r 8af1a61be7c1 algs4-c++/src/Stack.hpp
--- a/algs4-c++/src/Stack.hpp	Fri May 29 21:34:18 2015 -0500
+++ b/algs4-c++/src/Stack.hpp	Mon Jun 08 17:52:54 2015 -0500
@@ -54,6 +54,14 @@
     iterator begin( void );
     iterator end( void );
 
+#ifdef EXERCISES
+
+    T delete_bottom( void );    // 1.3.19
+    T remove( size_t k );       // 1.3.20
+    bool find( T key );         // 1.3.21
+
+#endif
+
 private:
 
     size_t N;