From 2df06be1ce3b8693d50dbbadc4e47e2be2d6b0fd Mon Sep 17 00:00:00 2001 From: Zhongheng Liu Date: Fri, 24 Jan 2025 22:41:15 +0200 Subject: init: init project --- .envrc | 3 ++ .gitignore | 21 ++++++++++ Cargo.lock | 7 ++++ Cargo.toml | 10 +++++ devenv.lock | 100 ++++++++++++++++++++++++++++++++++++++++++++++++ devenv.nix | 45 ++++++++++++++++++++++ devenv.yaml | 15 ++++++++ src/lib.rs | 15 ++++++++ src/tests.rs | 15 ++++++++ src/tree.rs | 122 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 10 files changed, 353 insertions(+) create mode 100644 .envrc create mode 100644 .gitignore create mode 100644 Cargo.lock create mode 100644 Cargo.toml create mode 100644 devenv.lock create mode 100644 devenv.nix create mode 100644 devenv.yaml create mode 100644 src/lib.rs create mode 100644 src/tests.rs create mode 100644 src/tree.rs 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 "] +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 { + pub root_node: TreeNode, +} +impl Tree { + /// 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: , Parent: , RHS: to sum values in tree. + pub fn reduce(&self, reducer: fn(Option, T, Option) -> R) -> R { + self.root_node.reduce(reducer) + } + + /// Initialises a new Tree struct. + /// + /// Needs a root value + pub fn new(root_val: T) -> Tree { + Tree:: { + root_node: TreeNode:: { + 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 Display for Tree { + 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 { + pub value: T, + + /// The left node, may be `None`. + pub left: Option>>, + + /// The right node, may be `None`. + pub right: Option>>, +} +impl Display for TreeNode { + 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 TreeNode { + + /// Initialises a new node for a Tree. + pub fn new(v: T) -> TreeNode { + TreeNode { + value: v, + left: None, + right: None, + } + } + + /// Recursively reduces each element in tree. + pub fn reduce(&self, reducer: fn(Option, T, Option) -> 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