summaryrefslogtreecommitdiff
path: root/week_1
diff options
context:
space:
mode:
Diffstat (limited to 'week_1')
-rw-r--r--week_1/bagFns1_static/Tupfile2
-rw-r--r--week_1/bagFns1_static/bag.cxx154
-rw-r--r--week_1/bagFns1_static/bag.h90
-rw-r--r--week_1/bagFns1_static/testBag.cxx120
4 files changed, 366 insertions, 0 deletions
diff --git a/week_1/bagFns1_static/Tupfile b/week_1/bagFns1_static/Tupfile
new file mode 100644
index 0000000..b6fe5c5
--- /dev/null
+++ b/week_1/bagFns1_static/Tupfile
@@ -0,0 +1,2 @@
+: foreach *.cxx |> clang++ -Weverything -Wno-c++98-compat -c %f -o %o |> %B.o
+: *.o |> clang++ %f -o %o |> bag
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
diff --git a/week_1/bagFns1_static/bag.h b/week_1/bagFns1_static/bag.h
new file mode 100644
index 0000000..64c6ef8
--- /dev/null
+++ b/week_1/bagFns1_static/bag.h
@@ -0,0 +1,90 @@
+// FILE: bag1.h
+// CLASS PROVIDED: bag (part of the namespace main_savitch_3)
+//
+// TYPEDEF and MEMBER CONSTANTS for the bag class:
+// typedef ____ value_type
+// bag::value_type is the data type of the items in the bag. It may be any
+// of the C++ built-in types (int, char, etc.), or a class with a default
+// constructor, an assignment operator, and operators to
+// test for equality (x == y) and non-equality (x != y).
+//
+// typedef ____ size_type
+// bag::size_type is the data type of any variable that keeps track of how
+// many items are in a bag.
+//
+// static const size_type CAPACITY = _____
+// bag::CAPACITY is the maximum number of items that a bag can hold.
+//
+// CONSTRUCTOR for the bag class:
+// bag( )
+// Postcondition: The bag has been initialized as an empty bag.
+//
+// MODIFICATION MEMBER FUNCTIONS for the bag class:
+// size_type erase(const value_type& target);
+// Postcondition: All copies of target have been removed from the bag.
+// The return value is the number of copies removed (which could be zero).
+//
+// void erase_one(const value_type& target)
+// Postcondition: If target was in the bag, then one copy has been removed;
+// otherwise the bag is unchanged. A true return value indicates that one
+// copy was removed; false indicates that nothing was removed.
+//
+// void insert(const value_type& entry)
+// Precondition: size( ) < CAPACITY.
+// Postcondition: A new copy of entry has been added to the bag.
+//
+// void operator +=(const bag& addend)
+// Precondition: size( ) + addend.size( ) <= CAPACITY.
+// Postcondition: Each item in addend has been added to this bag.
+//
+// CONSTANT MEMBER FUNCTIONS for the bag class:
+// size_type size( ) const
+// Postcondition: The return value is the total number of items in the bag.
+//
+// size_type count(const value_type& target) const
+// Postcondition: The return value is number of times target is in the bag.
+//
+// NONMEMBER FUNCTIONS for the bag class:
+// bag operator +(const bag& b1, const bag& b2)
+// Precondition: b1.size( ) + b2.size( ) <= bag::CAPACITY.
+// Postcondition: The bag returned is the union of b1 and b2.
+//
+// VALUE SEMANTICS for the bag class:
+// Assignments and the copy constructor may be used with bag objects.
+
+#ifndef MAIN_SAVITCH_BAG1_H
+#define MAIN_SAVITCH_BAG1_H
+#include <cstdlib> // Provides size_t
+
+namespace main_savitch_3 {
+class bag {
+public:
+ // TYPEDEFS and MEMBER CONSTANTS
+ typedef int value_type;
+ typedef std::size_t size_type;
+ static const size_type CAPACITY = 30;
+ // CONSTRUCTOR
+ bag() { used = 0; }
+ // MODIFICATION MEMBER FUNCTIONS
+ size_type erase(const value_type &target);
+ bool erase_one(const value_type &target);
+ void insert(const value_type &entry);
+ void operator+=(const bag &addend);
+ // CONSTANT MEMBER FUNCTIONS
+ size_type size() const { return used; }
+ size_type count(const value_type &target) const;
+ value_type smallest() const;
+ value_type average() const;
+ void sort() const;
+ bool operator==(const bag &);
+
+private:
+ value_type data[CAPACITY]; // The array to store items
+ size_type used; // How much of array is used
+};
+
+// NONMEMBER FUNCTIONS for the bag class
+bag operator+(const bag &b1, const bag &b2);
+} // namespace main_savitch_3
+
+#endif
diff --git a/week_1/bagFns1_static/testBag.cxx b/week_1/bagFns1_static/testBag.cxx
new file mode 100644
index 0000000..bd42f95
--- /dev/null
+++ b/week_1/bagFns1_static/testBag.cxx
@@ -0,0 +1,120 @@
+#include <cmath>
+#include <functional>
+#include <iostream>
+#include <sstream>
+
+#include "bag.h"
+
+template <typename T>
+void test(std::string, std::function<T()>, T, bool = false);
+
+int main() {
+ main_savitch_3::bag bag;
+ main_savitch_3::bag bag_2;
+
+ test<int>(
+ "size", [&bag]() { return bag.size(); }, 0);
+ test<int>(
+ "insert",
+ [&bag, &bag_2]() {
+ bag.insert(1);
+ bag_2.insert(3);
+ bag_2.insert(3);
+ bag_2.insert(7);
+
+ return bag.size();
+ },
+ 1);
+ test<int>(
+ "+=",
+ [&bag, &bag_2]() {
+ bag += bag_2;
+
+ return bag.size();
+ },
+ 4);
+ test<int>(
+ "count", [&bag]() { return bag.count(3); }, 2);
+ test<int>(
+ "erase_one",
+ [&bag]() {
+ bag.erase_one(3);
+
+ return bag.count(3);
+ },
+ 1);
+ test<int>(
+ "erase",
+ [&bag]() {
+ bag.insert(3);
+ bag.erase(3);
+
+ return bag.count(3);
+ },
+ 0);
+ test<int>(
+ "smallest", [&bag]() { return bag.smallest(); }, 1);
+ test<int>(
+ "average", [&bag]() { return bag.average(); },
+ static_cast<int>((1 + 7) / 2));
+ test<int>(
+ "sort",
+ [&bag]() {
+ std::stringstream sort_buffer;
+ std::streambuf *original_cout_buffer = std::cout.rdbuf();
+ std::cout.rdbuf(sort_buffer.rdbuf());
+
+ bag.insert(3);
+ bag.sort();
+
+ std::cout.rdbuf(original_cout_buffer);
+
+ return sort_buffer.str() == "1\n3\n7\n";
+ },
+ true);
+ test<int>(
+ "==",
+ [&bag]() {
+ main_savitch_3::bag bag_test;
+
+ bag_test.insert(7);
+ bag_test.insert(1);
+ bag_test.insert(3);
+
+ return bag == bag_test;
+ },
+ true);
+ test<int>(
+ "==",
+ [&bag]() {
+ main_savitch_3::bag bag_test;
+
+ // Slightly different test values that fail, as to prove validity of
+ // test suite.
+ // I mark the expected value as `false` for this `test` to treat an
+ // intentional fail expectation as a pass.
+ bag_test.insert(7);
+ bag_test.insert(1);
+ bag_test.insert(9);
+
+ return bag == bag_test;
+ },
+ false);
+ // This test is purposefully set to fail as to prove the validity of `test`.
+ test<int>(
+ "test", [&bag]() { return bag.smallest(); }, 0, true);
+
+ return 0;
+}
+
+template <typename T>
+void test(std::string name, std::function<T()> evaluate, T expected,
+ bool should_fail) {
+ T evaluated = evaluate();
+
+ if (should_fail)
+ evaluated = !evaluated;
+
+ std::cout << (evaluated == expected ? "pass(" : "FAIL(") << name
+ << "): expected " << expected << ", got " << evaluated << std::endl;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-11 09:58:11 +0000