1 files changed, 154 insertions, 0 deletions
diff --git a/week_1/bagFns1_static/bag.cxx b/week_1/bagFns1_static/bag.cxx
new file mode 100644
index 0000000..e1e6b5f
--- /dev/null
+++ b/week_1/bagFns1_static/bag.cxx
@@ -0,0 +1,154 @@
+// FILE: bag1.cxx
+// CLASS IMPLEMENTED: bag (see bag1.h for documentation)
+// INVARIANT for the bag class:
+//   1. The number of items in the bag is in the member variable used;
+//   2. For an empty bag, we do not care what is stored in any of data; for a
+//      non-empty bag the items in the bag are stored in data[0] through
+//      data[used-1], and we don't care what's in the rest of data.
+
+#include "bag.h"
+#include <algorithm> // Provides copy function
+#include <cassert>   // Provides assert function
+#include <functional>
+#include <iostream>
+#include <limits>
+using namespace std;
+
+namespace main_savitch_3 {
+const bag::size_type bag::CAPACITY;
+
+bag::size_type bag::erase(const value_type &target) {
+  size_type index = 0;
+  size_type many_removed = 0;
+
+  while (index < used) {
+    if (data[index] == target) {
+      --used;
+      data[index] = data[used];
+      ++many_removed;
+    } else
+      ++index;
+  }
+
+  return many_removed;
+}
+
+bool bag::erase_one(const value_type &target) {
+  size_type index; // The location of target in the data array
+
+  // First, set index to the location of target in the data array,
+  // which could be as small as 0 or as large as used-1. If target is not
+  // in the array, then index will be set equal to used.
+  index = 0;
+  while ((index < used) && (data[index] != target))
+    ++index;
+
+  if (index == used)
+    return false; // target isn't in the bag, so no work to do.
+
+  // When execution reaches here, target is in the bag at data[index].
+  // So, reduce used by 1 and copy the last item onto data[index].
+  --used;
+  data[index] = data[used];
+  return true;
+}
+
+void bag::insert(const value_type &entry)
+// Library facilities used: cassert
+{
+  assert(size() < CAPACITY);
+
+  data[used] = entry;
+  ++used;
+}
+
+void bag::operator+=(const bag &addend)
+// Library facilities used: algorithm, cassert
+{
+  assert(size() + addend.size() <= CAPACITY);
+
+  copy(addend.data, addend.data + addend.used, data + used);
+  used += addend.used;
+}
+
+bag::size_type bag::count(const value_type &target) const {
+  size_type answer;
+  size_type i;
+
+  answer = 0;
+  for (i = 0; i < used; ++i)
+    if (target == data[i])
+      ++answer;
+  return answer;
+}
+
+bag::value_type bag::smallest() const {
+  bag::value_type smallest = this->data[0];
+
+  for (int i = 1; i < used; ++i)
+    if (this->data[i] < smallest)
+      smallest = this->data[i];
+
+  return smallest;
+}
+
+bag::value_type bag::average() const {
+  bag::value_type sum = 0;
+
+  for (int i = 0; i < this->used; ++i)
+    sum += this->data[i];
+
+  // I'll use an arithmetic average since once isn't specified. This
+  // self-rounds since `value_type` is `int`.
+  return sum / this->used;
+}
+
+void bag::sort() const {
+  bag bag;
+
+  for (int i = 0; i < this->size(); ++i)
+    bag.insert(this->data[i]);
+
+  for (int i = 0; i < bag.used - 1; ++i)
+    for (int j = 0; j < bag.used - i - 1; ++j)
+      if (bag.data[j] > bag.data[j + 1])
+        std::swap(bag.data[j], bag.data[j + 1]);
+
+  for (int i = 0; i < bag.size(); ++i)
+    std::cout << bag.data[i] << std::endl;
+}
+
+bool bag::operator==(const bag &bag_2) {
+  bag bag_this_sorted = *this;
+  bag bag_2_sorted = bag_2;
+  // Typically I'd make this a member function since it could be reused in
+  // `sort`, but it seems out of the scope of what's asked.
+  std::function<void(bag &)> sort_bag = [](bag &bag) {
+    for (int i = 0; i < bag.used - 1; ++i)
+      for (int j = 0; j < bag.used - i - 1; ++j)
+        if (bag.data[j] > bag.data[j + 1])
+          std::swap(bag.data[j], bag.data[j + 1]);
+  };
+
+  sort_bag(bag_this_sorted);
+  sort_bag(bag_2_sorted);
+
+  for (int i = 0; i < this->used; ++i)
+    if (bag_this_sorted.data[i] != bag_2_sorted.data[i])
+      return false;
+
+  return true;
+}
+
+bag operator+(const bag &b1, const bag &b2)
+// Library facilities used: cassert
+{
+  bag answer;
+
+  assert(b1.size() + b2.size() <= bag::CAPACITY);
+
+  answer += b1;
+  answer += b2;
+  return answer;
+}
+} // namespace main_savitch_3