init: init project

10 files changed, 353 insertions, 0 deletions

diff --git a/.envrc b/.envrc
new file mode 100644
index 0000000..894571b
--- /dev/null
+++ b/.envrc
@@ -0,0 +1,3 @@
+source_url "https://raw.githubusercontent.com/cachix/devenv/82c0147677e510b247d8b9165c54f73d32dfd899/direnvrc" "sha256-7u4iDd1nZpxL4tCzmPG0dQgC5V+/44Ba+tHkPob1v2k="
+
+use devenv
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..4271aa1
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,21 @@
+# Devenv
+.devenv*
+devenv.local.nix
+
+# direnv
+.direnv
+
+# pre-commit
+.pre-commit-config.yaml
+
+
+# Added by cargo
+
+/target
+
+
+# Added by cargo
+#
+# already existing elements were commented out
+
+#/target
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644
index 0000000..de963e3
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "tree-rs"
+version = "0.1.0"
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..09c5232
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+name = "tree"
+version = "0.0.1"
+edition = "2021"
+authors = ["Zhongheng Liu <z.liu@outlook.com.gr>"]
+description = "Rust implementation of a binary tree data structure. Unstable and a work in progress."
+[lib]
+name = "tree"
+path = "src/lib.rs"
+[dependencies]
diff --git a/devenv.lock b/devenv.lock
new file mode 100644
index 0000000..c37b5d8
--- /dev/null
+++ b/devenv.lock
@@ -0,0 +1,100 @@
+{
+  "nodes": {
+    "devenv": {
+      "locked": {
+        "dir": "src/modules",
+        "lastModified": 1737729971,
+        "owner": "cachix",
+        "repo": "devenv",
+        "rev": "68a6d54dbeb5622b8435d7f1acf9ce239a075635",
+        "type": "github"
+      },
+      "original": {
+        "dir": "src/modules",
+        "owner": "cachix",
+        "repo": "devenv",
+        "type": "github"
+      }
+    },
+    "flake-compat": {
+      "flake": false,
+      "locked": {
+        "lastModified": 1733328505,
+        "owner": "edolstra",
+        "repo": "flake-compat",
+        "rev": "ff81ac966bb2cae68946d5ed5fc4994f96d0ffec",
+        "type": "github"
+      },
+      "original": {
+        "owner": "edolstra",
+        "repo": "flake-compat",
+        "type": "github"
+      }
+    },
+    "gitignore": {
+      "inputs": {
+        "nixpkgs": [
+          "pre-commit-hooks",
+          "nixpkgs"
+        ]
+      },
+      "locked": {
+        "lastModified": 1709087332,
+        "owner": "hercules-ci",
+        "repo": "gitignore.nix",
+        "rev": "637db329424fd7e46cf4185293b9cc8c88c95394",
+        "type": "github"
+      },
+      "original": {
+        "owner": "hercules-ci",
+        "repo": "gitignore.nix",
+        "type": "github"
+      }
+    },
+    "nixpkgs": {
+      "locked": {
+        "lastModified": 1733477122,
+        "owner": "cachix",
+        "repo": "devenv-nixpkgs",
+        "rev": "7bd9e84d0452f6d2e63b6e6da29fe73fac951857",
+        "type": "github"
+      },
+      "original": {
+        "owner": "cachix",
+        "ref": "rolling",
+        "repo": "devenv-nixpkgs",
+        "type": "github"
+      }
+    },
+    "pre-commit-hooks": {
+      "inputs": {
+        "flake-compat": "flake-compat",
+        "gitignore": "gitignore",
+        "nixpkgs": [
+          "nixpkgs"
+        ]
+      },
+      "locked": {
+        "lastModified": 1737465171,
+        "owner": "cachix",
+        "repo": "pre-commit-hooks.nix",
+        "rev": "9364dc02281ce2d37a1f55b6e51f7c0f65a75f17",
+        "type": "github"
+      },
+      "original": {
+        "owner": "cachix",
+        "repo": "pre-commit-hooks.nix",
+        "type": "github"
+      }
+    },
+    "root": {
+      "inputs": {
+        "devenv": "devenv",
+        "nixpkgs": "nixpkgs",
+        "pre-commit-hooks": "pre-commit-hooks"
+      }
+    }
+  },
+  "root": "root",
+  "version": 7
+}
diff --git a/devenv.nix b/devenv.nix
new file mode 100644
index 0000000..2c8b05f
--- /dev/null
+++ b/devenv.nix
@@ -0,0 +1,45 @@
+{ pkgs, lib, config, inputs, ... }:
+
+{
+  # https://devenv.sh/basics/
+  env.GREET = "devenv";
+
+  # https://devenv.sh/packages/
+  packages = [ pkgs.git ];
+
+  # https://devenv.sh/languages/
+  languages.rust.enable = true;
+
+  # https://devenv.sh/processes/
+  processes.cargo-watch.exec = "cargo-watch";
+
+  # https://devenv.sh/services/
+  # services.postgres.enable = true;
+
+  # https://devenv.sh/scripts/
+  scripts.hello.exec = ''
+    echo hello from $GREET
+  '';
+
+  enterShell = ''
+    hello
+    git --version
+  '';
+
+  # https://devenv.sh/tasks/
+  # tasks = {
+  #   "myproj:setup".exec = "mytool build";
+  #   "devenv:enterShell".after = [ "myproj:setup" ];
+  # };
+
+  # https://devenv.sh/tests/
+  enterTest = ''
+    echo "Running tests"
+    git --version | grep --color=auto "${pkgs.git.version}"
+  '';
+
+  # https://devenv.sh/pre-commit-hooks/
+  # pre-commit.hooks.shellcheck.enable = true;
+
+  # See full reference at https://devenv.sh/reference/options/
+}
diff --git a/devenv.yaml b/devenv.yaml
new file mode 100644
index 0000000..116a2ad
--- /dev/null
+++ b/devenv.yaml
@@ -0,0 +1,15 @@
+# yaml-language-server: $schema=https://devenv.sh/devenv.schema.json
+inputs:
+  nixpkgs:
+    url: github:cachix/devenv-nixpkgs/rolling
+
+# If you're using non-OSS software, you can set allowUnfree to true.
+# allowUnfree: true
+
+# If you're willing to use a package that's vulnerable
+# permittedInsecurePackages:
+#  - "openssl-1.1.1w"
+
+# If you have more than one devenv you can merge them
+#imports:
+# - ./backend
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)))
+    }
+}