From 2df06be1ce3b8693d50dbbadc4e47e2be2d6b0fd Mon Sep 17 00:00:00 2001
From: Zhongheng Liu <z.liu@outlook.com.gr>
Date: Fri, 24 Jan 2025 22:41:15 +0200
Subject: init: init project

---
 src/lib.rs   |  15 ++++++++
 src/tests.rs |  15 ++++++++
 src/tree.rs  | 122 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 152 insertions(+)
 create mode 100644 src/lib.rs
 create mode 100644 src/tests.rs
 create mode 100644 src/tree.rs

(limited to 'src')

diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..27ef0f6
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,15 @@
+//! Rust implementation of a binary tree.
+//!
+//! Work in progress.
+//!
+//! TODOS::
+//! - Understanding how complex borrows work
+//! - Apply correct value lifetime declarations
+//! - Make it efficient by implementing borrow 
+//! - Removing requirement for `Copy` trait
+
+mod tree;
+pub use tree::{Tree, TreeNode};
+
+#[cfg(test)]
+mod tests;
diff --git a/src/tests.rs b/src/tests.rs
new file mode 100644
index 0000000..3c029b9
--- /dev/null
+++ b/src/tests.rs
@@ -0,0 +1,15 @@
+use crate::tree;
+
+#[test]
+pub fn test_tree_init() {
+    let _ = tree::Tree::new(1);
+}
+
+#[test]
+pub fn test_tree_insert() {
+    let mut t = tree::Tree::new(1);
+    t.insert_left(12);
+    t.insert_right(13);
+    t.insert_left(15);
+    println!("{}", t);
+}
diff --git a/src/tree.rs b/src/tree.rs
new file mode 100644
index 0000000..e217b37
--- /dev/null
+++ b/src/tree.rs
@@ -0,0 +1,122 @@
+use std::fmt::Display;
+/// A binary tree structure used to parse and evaluate an expression into RPN.
+///
+/// Work in progress.
+///
+/// Type parameter must implement `Copy` trait until borrowing is implemented.
+pub struct Tree<T: Copy> {
+    pub root_node: TreeNode<T>,
+}
+impl<T: Copy> Tree<T> {
+    /// Takes reducer function input with following signature.
+    ///
+    /// The caller should ensure that reducer function returns same type as
+    /// the left- and right-hand side.
+    ///
+    /// Example: adding LHS: <i32>, Parent: <i32>, RHS: <i32> to sum values in tree.
+    pub fn reduce<R>(&self, reducer: fn(Option<R>, T, Option<R>) -> R) -> R {
+        self.root_node.reduce(reducer)
+    }
+
+    /// Initialises a new Tree struct.
+    ///
+    /// Needs a root value
+    pub fn new(root_val: T) -> Tree<T> {
+        Tree::<T> {
+            root_node: TreeNode::<T> {
+                value: root_val,
+                left: None,
+                right: None,
+            },
+        }
+    }
+
+    /// Inserts a node to the left of the root node.
+    pub fn insert_left(&mut self, v: T) {
+        self.root_node.insert_left(v);
+    }
+
+    /// Inserts a node to the right of the root node.
+    pub fn insert_right(&mut self, v: T) {
+        self.root_node.insert_right(v);
+    }
+}
+impl<T: Display + Copy> Display for Tree<T> {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        write!(f, "{}", self.root_node)
+    }
+}
+
+/// A node in a binary tree.
+///
+/// Can be used for many interesting algorithmic things.
+pub struct TreeNode<T: Copy> {
+    pub value: T,
+
+    /// The left node, may be `None`.
+    pub left: Option<Box<TreeNode<T>>>,
+
+    /// The right node, may be `None`.
+    pub right: Option<Box<TreeNode<T>>>,
+}
+impl<T: Copy + Display> Display for TreeNode<T> {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        write!(
+            f,
+            "{}{}{}",
+            match &self.left {
+                Some(v) => format!("({})<-", v),
+                None => "".to_string(),
+            },
+            format!("({})", self.value),
+            match &self.right {
+                Some(v) => format!("->({})", v),
+                None => "".to_string(),
+            }
+        )
+    }
+}
+impl<T: Copy> TreeNode<T> {
+
+    /// Initialises a new node for a Tree.
+    pub fn new(v: T) -> TreeNode<T> {
+        TreeNode {
+            value: v,
+            left: None,
+            right: None,
+        }
+    }
+
+    /// Recursively reduces each element in tree.
+    pub fn reduce<R>(&self, reducer: fn(Option<R>, T, Option<R>) -> R) -> R {
+        let left_val = match &self.left {
+            Some(node) => Some(node.reduce(reducer)),
+            None => None,
+        };
+        let right_val = match &self.right {
+            Some(node) => Some(node.reduce(reducer)),
+            None => None,
+        };
+        reducer(left_val, self.value, right_val)
+    }
+
+    /// Recursively inserts to the left of node until there is one empty space.
+    pub fn insert_left(&mut self, value: T) {
+        if let Some(node) = &mut self.left {
+            node.insert_left(value)
+        }
+        self.left = Some(Box::new(TreeNode {
+            value,
+            left: None,
+            right: None,
+        }));
+    }
+
+    /// Recursively inserts to the right of node until there is one empty space.
+    pub fn insert_right(&mut self, value: T) {
+        if let Some(node) = &mut self.right {
+            node.insert_right(value)
+        }
+        self.right = Some(Box::new(TreeNode::new(value)))
+    }
+}
-- 
cgit