lib.rs

#![feature(box_syntax, box_patterns, nll)]

extern crate rayon;

use std::{
    borrow::{Borrow, BorrowMut},
    cmp::Ordering,
};

type Stem<T> = Option<Box<Node<T>>>;

#[derive(Debug)]
pub struct Node<T>(Stem<T>, Stem<T>, T);

impl<T> Node<T> {
    fn new(value: T) -> Self {
        Node(None, None, value)
    }

    pub fn take(self) -> (Option<Node<T>>, Option<Node<T>>, T) {
        let Node(left, right, node_value) = self;
        let deref_move = |box node| node;

        (
            left .map(deref_move),
            right.map(deref_move),
            node_value
        )
    }

    pub fn subtree_eq<U>(&self, rhs: &Node<U>) -> bool where T: PartialEq<U> + Sync, U: Sync {
        let stem_eq = |lhs: &Stem<T>, rhs: &Stem<U>| match (lhs, rhs) {
            (None,    None   ) => true,
            (Some(l), Some(r)) => l.subtree_eq(r.borrow()),
            _ => false,
        };

        let Node(lhs_l, lhs_r, lhs_v) = self;
        let Node(rhs_l, rhs_r, rhs_v) = rhs;

        let (left, right) = rayon::join(
            || stem_eq(lhs_l, rhs_l),
            || stem_eq(lhs_r, rhs_r),
        );
        lhs_v == rhs_v && left && right
    }
}

impl<T, U> PartialEq<Node<U>> for Node<T> where T: PartialEq<U> {
    fn eq(&self, rhs: &Node<U>) -> bool {
        let Node(_, _, lhs_value) = self;
        let Node(_, _, rhs_value) = rhs;

        lhs_value == rhs_value
    }
}

#[derive(Debug)]
pub struct BinaryTree<T> {
    root: Stem<T>,
    size: usize,
}

impl<T> BinaryTree<T> {
    pub fn new() -> Self {
        BinaryTree {
            root: None,
            size: 0,
        }
    }
    
    pub fn len(&self) -> usize { self.size }
    
    pub fn insert(&mut self, value: T) where T: Ord {
        use self::Ordering::*;
        
        self.size += 1;
        
        let mut current_node: &mut Node<T> = match &mut self.root {
            Some(root) => root.borrow_mut(),
            None       => return self.root = Some(box Node::new(value)),
        };
        
        loop {
            let side = {
                let Node(left, right, node_value) = current_node;

                match value.cmp(node_value) {
                    Less | Equal => left,
                    Greater      => right,
                }
            };
            
            match side {
                Some(node) => current_node = node.borrow_mut(),
                None       => return *side = Some(box Node::new(value)),
            }
        }
    }
    
    pub fn get_by<'a, F>(&'a self, predicate: F) -> Option<&'a Node<T>>
    where
        T: Ord,
        F: Fn(&T) -> Ordering,
    {
        use self::Ordering::*;
        
        let mut current_node = match self.root.borrow() {
            Some(node) => node,
            None       => return None,
        };
        
        loop {
            let side = {
                let Node(left, right, node_value) = current_node.borrow();

                match predicate(node_value) {
                    Equal   => return Some(current_node),
                    Less    => left .as_ref(),
                    Greater => right.as_ref(),
                }
            };
            
            match side {
                Some(node) => current_node = node.borrow(),
                None       => return None,
            }
        }
    }

    pub fn get<'a>(&'a self, value: &T) -> Option<&'a Node<T>> where T: Ord {
        self.get_by(|x| value.cmp(x))
    }
}

impl<T, U> PartialEq<BinaryTree<U>> for BinaryTree<T> where T: PartialEq<U> + Sync, U: Sync {
    fn eq(&self, rhs: &BinaryTree<U>) -> bool {
        match (&self.root, &rhs.root) {
            (None, None) => true,
            (Some(lhs), Some(rhs)) => lhs.subtree_eq(rhs.borrow()),
            _ => false,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn count() {
        let mut tree = BinaryTree::<i32>::new();
        tree.insert(5);
        tree.insert(5);
        tree.insert(5);
        
        assert_eq!(3, tree.len())
    }

    #[test]
    fn equality() {
        let t1: BinaryTree<i32> = BinaryTree {
            root: Some(box Node(
                Some(box Node(None, None, 1)),
                Some(box Node(
                    Some(box Node(None, None, 4)),
                    None,
                    3,
                )),
                2,
            )),
            size: 4,
        };

        let t2: BinaryTree<i32> = BinaryTree {
            root: Some(box Node(
                Some(box Node(None, None, 1)),
                Some(box Node(
                    Some(box Node(None, None, 5)),
                    None,
                    3,
                )),
                2,
            )),
            size: 4,
        };

        let t3: BinaryTree<i32> = BinaryTree {
            root: Some(box Node(
                Some(box Node(None, None, 1)),
                None,
                2,
            )),
            size: 2,
        };

        assert_eq!(t1, t1);
        assert_ne!(t1, t2);
        assert_ne!(t1, t3);
    }

    #[test]
    fn contents() {
        let correct: BinaryTree<i32> = BinaryTree {
            root: Some(box Node(
                Some(box Node(
                    Some(box Node(None, None, 1)),
                    Some(box Node(None, None, 4)),
                    3
                )),
                Some(box Node(None, None, 8)),
                6
            )),
            size: 5,
        };

        let mut tree = BinaryTree::<i32>::new();
        tree.insert(6);
        tree.insert(3);
        tree.insert(4);
        tree.insert(8);
        tree.insert(1);

        assert_eq!(correct, tree);
    }
}