aboutsummaryrefslogtreecommitdiff
path: root/src/numerics.cpp
diff options
context:
space:
mode:
authorAryadev Chavali <aryadev@aryadevchavali.com>2024-07-26 02:59:14 +0100
committerAryadev Chavali <aryadev@aryadevchavali.com>2024-07-26 02:59:31 +0100
commit8207d49211bddfa8005a63e941824e09a342b015 (patch)
tree5650d547c1c7987afa7cd52d05b3fa33251e2741 /src/numerics.cpp
parent139f2e9e5a6db38095f9ba4b006e5867e251458e (diff)
downloadcw_tree-8207d49211bddfa8005a63e941824e09a342b015.tar.gz
cw_tree-8207d49211bddfa8005a63e941824e09a342b015.tar.bz2
cw_tree-8207d49211bddfa8005a63e941824e09a342b015.zip
Implemented numerics in numerics.cpp
Simple implementation, few refactors from the main.cpp version based on API changes.
Diffstat (limited to 'src/numerics.cpp')
-rw-r--r--src/numerics.cpp120
1 files changed, 120 insertions, 0 deletions
diff --git a/src/numerics.cpp b/src/numerics.cpp
new file mode 100644
index 0000000..ddf7187
--- /dev/null
+++ b/src/numerics.cpp
@@ -0,0 +1,120 @@
+/* Copyright (C) 2024 Aryadev Chavali
+
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License Version 2 for
+ * details.
+
+ * You may distribute and modify this code under the terms of the GNU General
+ * Public License Version 2, which you should have received a copy of along with
+ * this program. If not, please go to <https://www.gnu.org/licenses/>.
+
+ * Created: 2024-07-26
+ * Author: Aryadev Chavali
+ * Description: Implementation of numerics
+ */
+
+#include "./numerics.hpp"
+
+#include <sstream>
+
+Fraction::Fraction(word_t numerator, word_t denominator)
+ : numerator{numerator}, denominator{denominator}
+{
+ word_t hcf = gcd(MIN(numerator, denominator), MAX(numerator, denominator));
+ numerator /= hcf;
+ denominator /= hcf;
+}
+
+bool Fraction::operator<(const Fraction other)
+{
+ if (other.denominator == denominator)
+ return numerator < other.numerator;
+ // TODO: Is it better to use the GCD?
+ return (numerator * other.denominator) < (other.numerator * denominator);
+}
+
+bool Fraction::operator==(const Fraction &other)
+{
+ return numerator == other.numerator && denominator == other.denominator;
+}
+
+Node::Node(Fraction val, int64_t left, int64_t right)
+ : value{val}, left{left}, right{right}
+{
+}
+
+NodeAllocator::NodeAllocator(word_t capacity) : vec{capacity}
+{
+}
+
+word_t NodeAllocator::alloc_node(Node n)
+{
+ vec.push_back(n);
+ return vec.size() - 1;
+}
+
+word_t gcd(word_t a, word_t b)
+{
+ if (a == b)
+ return a;
+ else if (a <= 1 || b <= 1)
+ return 1;
+ for (word_t r = b % a; r != 0; b = a, a = r, r = b % a)
+ continue;
+ return a;
+}
+
+void iterate(std::queue<word_t> &queue, NodeAllocator &allocator)
+{
+ if (queue.empty())
+ return;
+ word_t index = queue.front();
+ Node node = allocator.vec[index];
+ if (node.left == -1)
+ {
+ allocator.vec[index].left = allocator.alloc_node(Fraction{
+ node.value.numerator, node.value.numerator + node.value.denominator});
+ }
+ if (node.right == -1)
+ {
+ allocator.vec[index].right = allocator.alloc_node(Fraction{
+ node.value.numerator + node.value.denominator, node.value.denominator});
+ }
+ queue.pop();
+ queue.push(allocator.vec[index].left);
+ queue.push(allocator.vec[index].right);
+}
+
+std::string to_string(const Fraction &f)
+{
+ std::stringstream ss;
+ ss << f.numerator << "/" << f.denominator;
+ return ss.str();
+}
+
+void indent_depth(int depth, std::stringstream &ss)
+{
+ for (int i = 0; i < depth; ++i)
+ ss << " ";
+}
+
+std::string to_string(const NodeAllocator &allocator, const word_t n, int depth)
+{
+ std::stringstream ss;
+ Node x = allocator.vec[n];
+ ss << "(" << to_string(x.value) << "\n";
+ indent_depth(depth, ss);
+ if (x.left == -1)
+ ss << "NIL";
+ else
+ ss << to_string(allocator, x.left, depth + 1);
+ ss << "\n";
+ indent_depth(depth, ss);
+ if (x.right == -1)
+ ss << "NIL";
+ else
+ ss << to_string(allocator, x.right, depth + 1);
+ ss << ")";
+ return ss.str();
+}