incomplete data structures implemented in Rust for academy purposes

binary_tree.rs

use std::fmt;
use std::any::Any;

// Implements Binary Trees
#[derive(Clone)]
struct BruteBinaryTree<T> {
    info: T,
    left: BinaryTree<T>,
    right: BinaryTree<T>,
}

#[derive(Clone)]
enum BinaryTree<T> {
    Empty,
    Just(Box<BruteBinaryTree<T>>),
}

impl<T: Any> BinaryTree<T> {
    pub fn new(info_: T) -> BinaryTree<T> {
        BinaryTree::Just(Box::new(BruteBinaryTree {
            info: info_,
            left: BinaryTree::Empty,
            right: BinaryTree::Empty,
        }))
    }
}

impl<T: Any + fmt::Display> fmt::Display for BinaryTree<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            BinaryTree::Just(ref r) => {
                return write!(f, "[{}](L: {}, R: {})", r.info, r.left, r.right);
            }
            BinaryTree::Empty => {
                return write!(f, "-");
            }
        }
    }
}

// Implements Searchable Binary Trees
// T: Any + Ord
impl<T: Any + Ord> BinaryTree<T> {
    pub fn insert(&mut self, info_: T) -> bool {
        match *self {
            BinaryTree::Just(ref mut r) => {
                if r.info == info_ {
                    return false;
                } else if info_ > r.info {
                    return r.right.insert(info_);
                } else {
                    return r.left.insert(info_);
                }
            }
            BinaryTree::Empty => {
                *self = BinaryTree::new(info_);
                return true;
            }
        }
    }
}

// Implements Searchable Binary Trees as IMMUTABLEs
impl<T: Any + Ord + Clone> BinaryTree<T> {
    pub fn insert_(&self, info_: T) -> BinaryTree<T> {
        match *self {
            BinaryTree::Just(ref r) => {
                if r.info == info_ {
                    return (*self).clone();
                } else if info_ > r.info {
                    return BinaryTree::Just(Box::new(BruteBinaryTree {
                        info: r.info.clone(),
                        left: r.left.clone(),
                        right: BinaryTree::insert_(&r.right.clone(), info_),
                    }));
                } else {
                    return BinaryTree::Just(Box::new(BruteBinaryTree {
                        info: r.info.clone(),
                        left: BinaryTree::insert_(&r.left.clone(), info_),
                        right: r.right.clone(),
                    }));
                }
            }
            BinaryTree::Empty => {
                return BinaryTree::new(info_);
            }
        }
    }
}

// Main Func

fn main() {
    let mut mut_bt = BinaryTree::new(64);
    mut_bt.insert(32);
    mut_bt.insert(48);
    mut_bt.insert(96);
    mut_bt.insert(16);

    let let_bt = mut_bt;
    println!("{:?}", let_bt.insert_(128).to_string());
}

doublelinked_list.rs

use std::any::Any;
use std::ptr;
use std::mem::size_of;
use std::slice;

#[derive(Clone, PartialEq)]
struct BruteListNode<T> {
    info: T,
    prev: *mut BruteListNode<T>,
    next: ListNode<T>,
}

type ListNode<T> = Option<Box<BruteListNode<T>>>;

#[derive(Clone)]
struct List<T> {
    head: ListNode<T>,
    limit: Option<usize>,
}

impl<T: Any> List<T> {
    pub fn new(limit_: Option<usize>) -> List<T> {
        List {
            head: None,
            limit: limit_,
        }
    }

    pub fn is_empty(&self) -> bool {
        match self.head {
            Some(_) => false,
            None => true,
        }
    }

    pub fn len(&self) -> usize {
        match self.head {
            Some(ref head_val) => head_val.len(),
            None => 0,
        }
    }

    pub fn append(&mut self, info_: T) -> bool {
        match self.limit {
            Some(ref limit_val) => {
                if self.len() >= *limit_val {
                    return false;
                }
            }
            None => {}
        }
        match self.head {
            None => {
                self.head = Some(Box::new(BruteListNode {
                    info: info_,
                    prev: ptr::null_mut(),
                    next: None,
                }))
            }
            Some(ref mut head) => head.add_last(info_),
        }
        return true;
    }

    pub fn take(&mut self) -> Result<T, &'static str> {
        match self.head.take() {
            Some(mut head_val) => {
                self.head = head_val.next.take();
                return Ok(head_val.info);
            }
            None => {
                return Err("nothing to take");
            }
        }
    }
}

impl<T: Any> BruteListNode<T> {
    pub fn len(&self) -> usize {
        match self.next {
            Some(ref next_val) => 1 + next_val.len(),
            None => 1,
        }
    }

    pub fn add_last(&mut self, new_last_info: T) {
        match self.next {
            None => {
                self.next = Some(Box::new(BruteListNode {
                    info: new_last_info,
                    prev: self as *mut BruteListNode<T>,
                    next: None,
                }))
            }
            Some(ref mut next) => next.add_last(new_last_info),
        }
    }

    pub fn get_prev(&self) -> ListNode<T> {
        if self.prev == ptr::null_mut() {
            None
        } else {
            unsafe {
                Some(Box::from_raw(
                    slice::from_raw_parts_mut(
                        self.prev,
                        size_of::<BruteListNode<T>>(),
                    ).as_mut_ptr(),
                ))
            }
        }
    }
}

fn main() {
    let mut test: List<u64> = List::new(Some(2));
    test.append(40);
    test.append(60);
    test.append(80);
    println!("{:?}", test.len());
    match test.pop() {
        Ok(ref poped) => println!("{:?}", poped),
        Err(ref msg) => println!("{:?}", msg),
    }
    match test.pop() {
        Ok(ref poped) => println!("{:?}", poped),
        Err(ref msg) => println!("{:?}", msg),
    }
    match test.pop() {
        Ok(ref poped) => println!("{:?}", poped),
        Err(ref msg) => println!("{:?}", msg),
    }
    println!("{:?}", test.is_empty());
}

queue.rs

use std::any::Any;

#[derive(Clone, PartialEq)]
struct BruteQueueNode<T> {
    info: T,
    next: QueueNode<T>,
}

type QueueNode<T> = Option<Box<BruteQueueNode<T>>>;

#[derive(Clone)]
struct Queue<T> {
    first: QueueNode<T>,
    limit: Option<usize>,
}

impl<T: Any> Queue<T> {
    pub fn new(limit_: Option<usize>) -> Queue<T> {
        Queue {
            first: None,
            limit: limit_,
        }
    }

    pub fn is_empty(&self) -> bool {
        match self.first {
            Some(_) => false,
            None => true,
        }
    }

    pub fn len(&self) -> usize {
        match self.first {
            Some(ref first_val) => first_val.len(),
            None => 0,
        }
    }

    pub fn enqueue(&mut self, info_: T) -> bool {
        match self.limit {
            Some(ref limit_val) => {
                if self.len() >= *limit_val {
                    return false;
                }
            }
            None => {}
        }
        let new_last = Some(Box::new(BruteQueueNode {
            info: info_,
            next: None,
        }));
        match self.first {
            None => self.first = new_last,
            Some(ref mut first) => first.add_last(new_last),
        }
        return true;
    }

    pub fn dequeue(&mut self) -> Result<T, &'static str> {
        match self.first.take() {
            Some(mut first_val) => {
                self.first = first_val.next.take();
                return Ok(first_val.info);
            }
            None => {
                return Err("nothing to take");
            }
        }
    }
}

impl<T: Any> BruteQueueNode<T> {
    pub fn len(&self) -> usize {
        match self.next {
            Some(ref next_val) => 1 + next_val.len(),
            None => 1,
        }
    }

    pub fn add_last(&mut self, new_last: QueueNode<T>) {
        match self.next {
            None => self.next = new_last,
            Some(ref mut next) => next.add_last(new_last),
        }
    }
}

fn main() {
    let mut test: Queue<u64> = Queue::new(Some(2));
    test.enqueue(40);
    test.enqueue(60);
    test.enqueue(80);
    println!("{:?}", test.len());
    match test.dequeue() {
        Ok(ref dequeued) => println!("{:?}", dequeued),
        Err(ref msg) => println!("{:?}", msg),
    }
    match test.dequeue() {
        Ok(ref dequeued) => println!("{:?}", dequeued),
        Err(ref msg) => println!("{:?}", msg),
    }
    match test.dequeue() {
        Ok(ref dequeued) => println!("{:?}", dequeued),
        Err(ref msg) => println!("{:?}", msg),
    }
    println!("{:?}", test.is_empty());
}

stack.rs

use std::any::Any;

#[derive(Clone, PartialEq)]
struct BruteStackNode<T> {
    info: T,
    next: StackNode<T>,
}

type StackNode<T> = Option<Box<BruteStackNode<T>>>;

#[derive(Clone)]
struct Stack<T> {
    first: StackNode<T>,
    limit: Option<usize>,
}

impl<T: Any> Stack<T> {
    pub fn new(limit_: Option<usize>) -> Stack<T> {
        Stack {
            first: None,
            limit: limit_,
        }
    }

    pub fn is_empty(&self) -> bool {
        match self.first {
            Some(_) => false,
            None => true,
        }
    }

    pub fn len(&self) -> usize {
        match self.first {
            Some(ref first_val) => first_val.len(),
            None => 0,
        }
    }

    pub fn push(&mut self, info_: T) -> bool {
        self.first = Some(Box::new(BrutePileNode {
            info: info_,
            next: self.first.take(),
        }));
    }

    pub fn pop(&mut self) -> Result<T, &'static str> {
        match self.first.take() {
            Some(mut first_val) => {
                self.first = first_val.next.take();
                return Ok(first_val.info);
            }
            None => {
                return Err("nothing to take");
            }
        }
    }
}

impl<T: Any> BruteStackNode<T> {
    pub fn len(&self) -> usize {
        match self.next {
            Some(ref next_val) => 1 + next_val.len(),
            None => 1,
        }
    }

    pub fn add_last(&mut self, new_last: StackNode<T>) {
        match self.next {
            None => self.next = new_last,
            Some(ref mut next) => next.add_last(new_last),
        }
    }
}

fn main() {
    let mut test: Stack<u64> = Stack::new(None);
    test.push(40);
    test.push(60);
    test.push(80);
    println!("{:?}", test.len());
    match test.pop() {
        Ok(ref poped) => println!("{:?}", poped),
        Err(ref msg) => println!("{:?}", msg),
    }
    println!("{:?}", test.is_empty());
}

TODO list:

• Binary Tree
  • Add balance function
  • Add limit
• Double-linked list
  • Add tail
  • Add ways to interact (in both ways).