diff options
| -rw-r--r-- | .gitignore | 6 | ||||
| -rw-r--r-- | week_1/bagFns1_static/Tupfile | 2 | ||||
| -rw-r--r-- | week_1/bagFns1_static/bag.cxx | 154 | ||||
| -rw-r--r-- | week_1/bagFns1_static/bag.h | 90 | ||||
| -rw-r--r-- | week_1/bagFns1_static/testBag.cxx | 120 |
5 files changed, 372 insertions, 0 deletions
@@ -1,8 +1,14 @@ +* +!/**/ +!*.* +!Tupfile + # Ninja .ninja_* # Build Artifacts out +*.o # Visual Studio Code .vscode 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; +} |