From d80c10626712eff3b94fdd26345efaa8fc520c5e Mon Sep 17 00:00:00 2001 From: Fuwn Date: Mon, 8 Apr 2024 01:20:21 -0700 Subject: feat(week_1): wk1_bagFns1_static --- week_1/bagFns1_static/Tupfile | 2 + week_1/bagFns1_static/bag.cxx | 154 ++++++++++++++++++++++++++++++++++++++ week_1/bagFns1_static/bag.h | 90 ++++++++++++++++++++++ week_1/bagFns1_static/testBag.cxx | 120 +++++++++++++++++++++++++++++ 4 files changed, 366 insertions(+) create mode 100644 week_1/bagFns1_static/Tupfile create mode 100644 week_1/bagFns1_static/bag.cxx create mode 100644 week_1/bagFns1_static/bag.h create mode 100644 week_1/bagFns1_static/testBag.cxx (limited to 'week_1') 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 // Provides copy function +#include // Provides assert function +#include +#include +#include +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 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 // 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 +#include +#include +#include + +#include "bag.h" + +template +void test(std::string, std::function, T, bool = false); + +int main() { + main_savitch_3::bag bag; + main_savitch_3::bag bag_2; + + test( + "size", [&bag]() { return bag.size(); }, 0); + test( + "insert", + [&bag, &bag_2]() { + bag.insert(1); + bag_2.insert(3); + bag_2.insert(3); + bag_2.insert(7); + + return bag.size(); + }, + 1); + test( + "+=", + [&bag, &bag_2]() { + bag += bag_2; + + return bag.size(); + }, + 4); + test( + "count", [&bag]() { return bag.count(3); }, 2); + test( + "erase_one", + [&bag]() { + bag.erase_one(3); + + return bag.count(3); + }, + 1); + test( + "erase", + [&bag]() { + bag.insert(3); + bag.erase(3); + + return bag.count(3); + }, + 0); + test( + "smallest", [&bag]() { return bag.smallest(); }, 1); + test( + "average", [&bag]() { return bag.average(); }, + static_cast((1 + 7) / 2)); + test( + "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( + "==", + [&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( + "==", + [&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( + "test", [&bag]() { return bag.smallest(); }, 0, true); + + return 0; +} + +template +void test(std::string name, std::function 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; +} -- cgit v1.2.3