feat: first commit

devanbenz · Nov 16, 2024 · be2093a · be2093a
commit be2093a
Show file tree

Hide file tree

Showing 10 changed files with 409 additions and 0 deletions.
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,37 @@
+# Prerequisites
+*.d
+
+# Compiled Object files
+*.slo
+*.lo
+*.o
+*.obj
+
+# Precompiled Headers
+*.gch
+*.pch
+
+# Compiled Dynamic libraries
+*.so
+*.dylib
+*.dll
+
+# Fortran module files
+*.mod
+*.smod
+
+# Compiled Static libraries
+*.lai
+*.la
+*.a
+*.lib
+
+# Executables
+*.exe
+*.out
+*.app
+
+.idea/
+cmake-build*/
+135-0.txt
+
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -0,0 +1,33 @@
+cmake_minimum_required(VERSION 3.29)
+project(spray_paint)
+
+set(CMAKE_CXX_STANDARD 26)
+
+include(FetchContent)
+FetchContent_Declare(
+        googletest
+        URL https://github.com/google/googletest/archive/03597a01ee50ed33e9dfd640b249b4be3799d395.zip
+)
+
+set(gtest_force_shared_crt ON CACHE BOOL "" FORCE)
+FetchContent_MakeAvailable(googletest)
+enable_testing()
+
+add_library(spray_paint_lib
+    src/huffman.cpp src/huffman.h
+        src/heap/heap.h
+        src/heap/min_heap.h
+)
+add_executable(spray_paint_test
+    tests/sp_test.cpp
+)
+target_link_libraries(spray_paint_test
+        GTest::gtest_main
+        spray_paint_lib
+)
+
+add_executable(spray_paint main.cpp)
+target_link_libraries(spray_paint spray_paint_lib)
+
+include(GoogleTest)
+gtest_discover_tests(spray_paint_test)
diff --git a/README.md b/README.md
@@ -0,0 +1,2 @@
+# Spray Paint
+
diff --git a/main.cpp b/main.cpp
@@ -0,0 +1,23 @@
+#include <iostream>
+
+#include "src/huffman.h"
+
+// Huffman encoding
+// lossless data compression algorithm
+
+// Read the text and determine the frequency of each character occurring.
+// Build the binary tree from the frequencies.
+// Generate the prefix-code table from the tree.
+// Encode the text using the code table.
+// Encode the tree - we’ll need to include this in the output file so we can decode it.
+// Write the encoded tree and text to an output field
+
+int main() {
+    std::ifstream input_file("/Users/devan/Documents/Projects/spray-paint/135-0.txt");
+    assert(input_file.is_open());
+    assert(input_file.good());
+
+    auto char_map = build_char_map(std::move(input_file));
+
+    return 0;
+}
diff --git a/src/heap/heap.h b/src/heap/heap.h
@@ -0,0 +1,57 @@
+#pragma once
+
+#include <vector>
+#include <optional>
+#include <cassert>
+
+///The formulae for calculating the array indices of the various relatives of a node are as follows.
+// The total number of nodes in the tree is n.
+// The index of the node in question is r, which must fall in the range 0 to n−1
+
+//Parent(r) =⌊(r−1)/2⌋ if r≠0
+//Left child(r) =2r+1 if 2r+1<n
+//Right child(r) =2r+2 if 2r+2<n
+//Left sibling(r) =r−1 if r is even and r≠0
+//Right sibling(r) =r+1; if r is odd and r+1<n
+
+template <typename T>
+class BaseHeap {
+public:
+    virtual void put(T value) = 0;
+
+    virtual T pop() = 0;
+
+    virtual bool is_leaf(int idx) = 0;
+
+    virtual void sift_down(T value) = 0;
+protected:
+    std::optional<int> parent_node(int);
+
+    std::optional<int> left_child_node(int, int);
+
+    std::optional<int> right_child_node(int, int);
+};
+
+template <typename T>
+std::optional<int> BaseHeap<T>::parent_node(int idx) {
+    assert(idx >= 0);
+    if (idx == 0) {
+        return {};
+    }
+    return ((idx - 1)/2);
+}
+
+template <typename T>
+std::optional<int> BaseHeap<T>::left_child_node(int idx, int cap) {
+    assert(idx >= 0);
+    if ((2 * idx) + 1 < cap) {
+        return (2 * idx) + 1;
+    }
+    return {};
+}
+
+template <typename T>
+std::optional<int> BaseHeap<T>::right_child_node(int idx, int cap) {
+    assert(idx >= 0);
+    return 0;
+}
diff --git a/src/heap/min_heap.h b/src/heap/min_heap.h
@@ -0,0 +1,72 @@
+#include "heap.h"
+
+#include <cassert>
+#include <concepts>
+
+template <typename T>
+concept Comparable = requires (T a, T b) {
+    {a > b} -> std::convertible_to<bool>;
+    {a < b} -> std::convertible_to<bool>;
+    {a == b} -> std::convertible_to<bool>;
+};
+
+template <typename T>
+class MinHeap : public BaseHeap<T> {
+public:
+    explicit MinHeap(int cap);
+
+    void put(T value) requires Comparable<T>;
+
+    T pop() override;
+
+    bool is_leaf(int idx) override;
+private:
+    int cap_;
+
+    std::vector<T> heap_;
+
+    void sift_down(T) requires Comparable<T>;
+
+    void sift_up(T) requires Comparable<T>;
+};
+
+template <typename T>
+MinHeap<T>::MinHeap(int cap): cap_(cap) {
+    std::vector<T> vec(cap);
+    heap_ = vec;
+}
+
+template <typename T>
+void MinHeap<T>::put(T value) requires Comparable<T> {
+    if (heap_.size() == cap_) {
+        throw std::runtime_error("min_heap is already at max capacity");
+    }
+
+}
+
+template <typename T>
+T MinHeap<T>::pop() {
+    return heap_.front();
+}
+
+template<typename T>
+bool MinHeap<T>::is_leaf(int idx) {
+    assert(idx >= 0);
+    auto lc = this->left_child_node(idx, heap_.capacity());
+    auto rc = this->right_child_node(idx, heap_.capacity());
+    if (!rc.has_value() && !lc.has_value()) {
+        return false;
+    }
+
+    return true;
+}
+
+template<typename T>
+void MinHeap<T>::sift_up(T) requires Comparable<T> {
+
+}
+
+template<typename T>
+void MinHeap<T>::sift_down(T) requires Comparable<T> {
+
+}
diff --git a/src/huffman.cpp b/src/huffman.cpp
@@ -0,0 +1,54 @@
+#include "huffman.h"
+
+std::unordered_map<char, int> build_char_map(std::ifstream is) {
+    std::unordered_map<char, int> char_map;
+    char c;
+    while (is.get(static_cast<char &>(c))) {
+        auto it = char_map.find(c);
+        if (it == char_map.end()) {
+            char_map.insert(std::make_pair(c, 1));
+        } else {
+            it->second = ++it->second;
+        }
+    }
+
+    assert(!char_map.empty());
+    is.close();
+    assert(!is.is_open());
+
+    return char_map;
+}
+
+std::vector<std::pair<char, int>> build_set(std::unordered_map<char, int> &src) {
+    std::vector<std::pair<char, int>> pairs;
+    pairs.reserve(src.size());
+
+    for (auto i : src) {
+        pairs.emplace_back(i);
+    }
+
+    std::sort(pairs.begin(), pairs.end(), [=](std::pair<char, int> &a, std::pair<char, int> &b){
+        return a.second < b.second;
+    });
+
+    return pairs;
+}
+
+void SprayPaintNode::insert_node(SprayPaintNode *node) {
+    if (node == nullptr) {
+        throw std::runtime_error("failed to insert node; cannot insert nil value.");
+    }
+
+    auto head = (*this);
+    auto tail = (*this);
+
+    if (head.weight_ < node->weight_) {
+        // swap nodes - head will become the incoming node and the tail is now the head
+
+
+        // Since the source node's weight is less than the new node it will need to become an arm of the new node.
+        // Binary trees require that the left arm is lesser so the source node will need to become the left arm.
+
+        // Traverse tree if node is less than
+    }
+}
diff --git a/src/huffman.h b/src/huffman.h
@@ -0,0 +1,43 @@
+#pragma once
+
+#include <unordered_map>
+#include <fstream>
+#include <cassert>
+#include <algorithm>
+#include <stdexcept>
+#include <iostream>
+#include <optional>
+
+std::unordered_map<char, int> build_char_map(std::ifstream);
+
+std::vector<std::pair<char, int>> build_set(std::unordered_map<char, int> &src);
+
+class SprayPaintNode {
+public:
+    SprayPaintNode(int weight, std::optional<char> val, bool leaf) :
+        weight_(weight), val_(val), leaf_(leaf), left_(nullptr), right_(nullptr) {};
+
+    void insert_node(SprayPaintNode* node);
+
+    [[nodiscard]] bool is_leaf() const {
+        return leaf_;
+    };
+
+    [[nodiscard]] char value() const {
+        if (val_.has_value()) {
+            return val_.value();
+        }
+
+        throw std::runtime_error("attempting to access a None value");
+    }
+
+    [[nodiscard]] int weight() const {
+        return weight_;
+    }
+private:
+    int weight_;
+    std::optional<char> val_;
+    bool leaf_;
+    SprayPaintNode* left_;
+    SprayPaintNode* right_;
+};