diff options
| -rw-r--r-- | .gitignore | 6 | ||||
| -rw-r--r-- | Tupfile | 22 | ||||
| -rw-r--r-- | bst.cc | 189 |
3 files changed, 217 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..195601d --- /dev/null +++ b/.gitignore @@ -0,0 +1,6 @@ +# Build Artifacts +build + +# tup +.tup + @@ -0,0 +1,22 @@ +# Input & Output Directories +SOURCE_DIRECTORY = . +INCLUDE_DIRECTORY = . +BUILD_DIRECTORY = build + +# Compiler Configuration +CC = clang++ +CC_EXTENSION = cc +# CC_FLAGS = -std=c++23 -I $(INCLUDE_DIRECTORY) -Weverything -Wno-padded -Wno-c++98-compat -MMD -Wno-c++98-compat-pedantic +CC_FLAGS = -MMD + +# Clang-tidy Configuration +CLANG_TIDY_CHECKS = '-*,bugprone-*,clang-analyzer-*,concurrency-*,cppcoreguildelines-*,llvm-*,misc-*,modernize-*,performance-*,portability-*,readability-*,-readability-magic-numbers,-llvm-header-guard,-bugprone-suspicious-include,-readability-function-cognitive-complexity,-bugprone-exception-escape,-misc-no-recursion,-llvm-else-after-return,-readability-else-after-return' +CLANG_TIDY_FLAGS = -checks=$(CLANG_TIDY_CHECKS) -warnings-as-errors=* -quiet + +NAME = bst + +# : foreach $(SOURCE_DIRECTORY)/*.$(CC_EXTENSION) $(INCLUDE_DIRECTORY)/*.hh |> clang-format -i %f |> +# : foreach $(SOURCE_DIRECTORY)/*.$(CC_EXTENSION) |> clang-tidy $(CLANG_TIDY_FLAGS) %f -- $(CC_FLAGS) |> +: foreach $(SOURCE_DIRECTORY)/*.$(CC_EXTENSION) |> ^j^ $(CC) $(CC_FLAGS) -MF $(BUILD_DIRECTORY)/%B.d -c %f -o %o |> $(BUILD_DIRECTORY)/%B.o | $(BUILD_DIRECTORY)/%B.d +: $(BUILD_DIRECTORY)/*.o ^test.o |> $(CC) %f -o %o |> $(BUILD_DIRECTORY)/$(NAME) +: $(BUILD_DIRECTORY)/*.o ^main.o |> $(CC) %f -o %o |> $(BUILD_DIRECTORY)/$(NAME)_test @@ -0,0 +1,189 @@ +#include <cstddef> +#include <iostream> +#include <memory> +#include <optional> + +template <typename T> class bst { +public: + using size_type = std::size_t; + +private: + T _key; + std::optional<std::shared_ptr<bst>> _left; + std::optional<std::shared_ptr<bst>> _right; + +public: + bst(T key) : _key(key) {} + + auto key() -> T { return this->_key; } + auto key(T key) -> void { this->_key = key; } + + auto left() -> std::optional<T> { return this->_left; } + auto left(T left) -> void { this->_left = left; } + + auto right() -> std::optional<T> { return this->_right; } + auto right(T right) -> void { this->_right = right; } + + auto insert(T key) -> void { + // A BST is structured in a way that values larger than the root node sit + // right of the node, while values smaller sit left of it. + // + // If the key is greater than than this node's key, it will sit to the right + // of it. + if (key > this->_key) { + // If this node already has a right value, we must tack it onto the end of + // that node ... + if (this->_right.has_value()) { + std::cout << "inserting as right: " << key << "\n"; + + // or keep trying until an empty branch is found. + this->_right.value()->insert(key); + } else { + // If this branch was hit, that must mean that an empty right branch was + // found, so we set it. + this->_right = std::make_shared<bst<T>>(bst(key)); + + std::cout << "set as right: " << key << "\n"; + } + } else { + // This is the same operation is above, but for values smaller than the + // current BST node. + if (this->_left.has_value()) { + std::cout << "inserting as left: " << key << "\n"; + + this->_left.value()->insert(key); + } else { + this->_left = std::make_shared<bst<T>>(bst(key)); + + std::cout << "set as left: " << key << "\n"; + } + } + } + + auto size() -> bst::size_type { + return + // If the left value of the current node has a value, add one to + // the accumulator (the +1 below), and continue down the branch + (this->_left.has_value() ? this->_left.value()->size() : 0) + + // The same as above, but for the right branch + (this->_right.has_value() ? this->_right.value()->size() : 0) + + // Additionally account for the root node itself + 1; + } + + auto depth() -> bst::size_type { + // Account for the root node, but also serve as the accumulator for the + // below `depth` calls, similar as to the above `size` function + return 1 + + std::max(this->_left.has_value() ? this->_left.value()->depth() : 0, + this->_right.has_value() ? this->_right.value()->depth() + : 0); + } + + auto minimum() -> T { + // Start with the root key as the base minimum, since the left branch may be + // empty + T minimum = this->_key; + + // If the left branch has a value, and the value is smaller than the root + // node, consider it as a minimum + if (this->_left.has_value() && this->_key > this->_left.value()->key()) { + // Attempt to obtain the valid left branch value's left branch, otherwise, + // minimum will return the top-level minimum of the left branch + minimum = this->_left.value()->minimum(); + } + + return minimum; + } + + auto maximum() -> T { + // Identical to the `minimum` implementation, but considers the right-hand + // branch + T maximum = this->_key; + + if (this->_right.has_value() && this->_key < this->_right.value()->key()) { + maximum = this->_right.value()->maximum(); + } + + return maximum; + } + + auto _remove(std::optional<std::shared_ptr<bst>> bst, + T key) -> std::optional<std::shared_ptr<class bst>> { + // If the current BST being evaluated has no value, it could not possibly be + // considering for child removal + if (!bst.has_value()) { + return std::nullopt; + } + + // If the current BST's key is smaller than the target key, it must be on + // the right-hand side, this additionally means that it is not the target + // value + if (bst.value()->_key < key) { + bst.value()->_right = this->_remove(bst.value()->_right, key); + + return bst; + } else if (bst.value()->_key > key) { + bst.value()->_left = this->_remove(bst.value()->_left, key); + + return bst; + } + + // At this point, the BST value has been found if available through a series + // of greater than, less than evaluations + + if (!bst.value()->_left.has_value()) { + auto temporary_bst = bst.value()->_right; + + bst.value().reset(); + + return temporary_bst; + } else if (!bst.value()->_right.has_value()) { + auto temporary_bst = bst.value()->_left; + + bst.value().reset(); + + return temporary_bst; + } + + auto next_parent = bst.value()->_right; + auto next = bst.value()->_right; + + while (next.value()->_left.has_value()) { + next_parent = next; + next = next.value()->_left; + } + + next_parent.value()->_left = next.value()->_right; + bst.value()->_key = next.value()->_key; + + next.value().reset(); + + return bst; + } + + auto remove(T key) -> void { + // `remove` is easier with recursion, so its wrapped + this->_remove(std::make_shared<bst<T>>(*this), key); + } +}; + +auto main() -> int { + bst<int> bst(2); + + bst.insert(3); + bst.insert(4); + bst.insert(5); + bst.insert(1); + + std::cout << "size: " << bst.size() << '\n'; + std::cout << "depth: " << bst.depth() << '\n'; + std::cout << "minimum: " << bst.minimum() << '\n'; + std::cout << "maximum: " << bst.maximum() << '\n'; + + bst.remove(5); + + std::cout << "size: " << bst.size() << '\n'; + + return 0; +} |