bintree 0.1.0

use crate::node::Node;
use std::cmp::Ordering;
use std::collections::VecDeque;

/// Перечисление (enumeration или enum) узел для нашего дерева.
/// Узел может быть либо пустым, либо не пустым.
/// Если он пуст, то принимает значение Empty, иначе
/// NonEmpty, которое хранит Box<Node<T>>.
/// Т.к. наша структура рекурсивна (Узлы хранят ветви,
/// а ветви хранят узлы), но наша структура должна иметь
/// некий размер, который можно вычислить в момент компиляции,
/// то я принял решение использовать Box<T>, который добавляет всё
/// содержимое в кучу, и хранит некий указатель на всё это,
/// который на стеке имеет константное значение.
///
/// Используются всё те же трейты Debug, Clone и PartialEq
/// плюс новый для нас трейт PartialOrd, который умеет сравнивать
/// на больше-меньше. Это сделанно для того, что бы мы могли выбирать
/// нужную нам ветвь, когда мы ходим по дереву.
///
/// Т.к. перечисление приватно, то советую изучить tests.rs
/// В котором для каждого метода есть тесты.

#[derive(Debug, Clone, PartialOrd, PartialEq)]
pub(crate) enum TreeKnot<T>
    where T: Copy + Clone + PartialOrd + PartialEq
{
    Empty,
    NonEmpty(Box<Node<T>>),
}

/// Трейт Default для узла. По-умолчанию наш узел пуст

impl<T> Default for TreeKnot<T>
    where T: Copy + Clone + PartialOrd + PartialEq
{

/// Дефолт-функция возвращает пустой узел
    #[inline]
    fn default() -> Self {
        TreeKnot::Empty
    }
}

/// Все методы для нашего узла.
/// Для ознакомления советую изучть tests.rs

#[allow(dead_code)]
impl<T> TreeKnot<T>
    where T: Copy + Clone + PartialOrd + PartialEq
{

/// Создаём новый узел
    
    #[inline]
    pub(crate) fn new() -> Self {
        TreeKnot::default()
    }

/// Метод конвертации узла в неизменяемую ветвь.
/// Т.к. узел может быть пуст, то может вызваться паника.
    
    #[inline]
    pub(crate) fn ignore(&self) -> &Box<Node<T>> {
        if let TreeKnot::NonEmpty(ref node) = *self {
            return node;
        } else {
            panic!("Empty tree");
        }
    }
    
/// Метод конвертации узла в изменяемую ветвь.
/// Т.к. узел может быть пуст, то может вызваться паника.

    #[inline]
    pub(crate) fn ignore_mut(&mut self) -> &mut Box<Node<T>> {
        if let TreeKnot::NonEmpty(ref mut node) = *self {
            return node;
        } else {
            panic!("Empty tree");
        }
    }

/// Получение ключа из ветви. Возможна паника.
    
    #[inline]
    pub(crate) fn get_key(&self) -> &T {
        &self.ignore().key
    }

/// Метод добавления значения в узел.
/// Добавление осуществляется рекурсивно
/// С помощью обхода в глубину
    
    pub(crate) fn insert(&mut self, val: &T) {
        match *self {
            TreeKnot::Empty => {
                *self = TreeKnot::NonEmpty(Box::new(Node {
                    key: (*val).clone(),
                    right: TreeKnot::Empty,
                    left: TreeKnot::Empty,
                }))
            }
            TreeKnot::NonEmpty(ref mut node) => {
                if node.key <= *val {
                    node.right.insert(val);
                } else {
                    node.left.insert(val);
                }
            }
        }
    }
    
/// Метод поиска значения в поддереве (не во всём дереве)
/// В случае, когда мы не находим значение, или поддерево пусто,
/// Вернётся пустой узел, иначе узел с эквивалентным значением.
   
    pub(crate) fn find(&self, val: &T) -> &Self {
        let mut find = self;
        while let TreeKnot::NonEmpty(ref node) = *find {
            match val.partial_cmp(find.get_key()) {
                Some(Ordering::Less) => find = &node.left,
                Some(Ordering::Greater) => find = &node.right,
                Some(Ordering::Equal) => return find,
                None => panic!("NAN value can't be used"),
            }
        }
        &TreeKnot::Empty
    }
   
/// Поиск минимального узла в ветви.
/// В случае, если поддерево, возвращаем пустой узел.
    
    pub(crate) fn min(&self) -> &Self {
        let mut min = self;
        while min.ignore().left != TreeKnot::Empty {
            min = &min.ignore().left;
        }
        min
    }
    
/// Поиск минимального узла в ветви.
/// В случае, если поддерево, возвращаем пустой узел.
    
    pub(crate) fn max(&self) -> &Self {
        let mut max = self;
        while max.ignore().right != TreeKnot::Empty {
            max = &max.ignore().right;
        }
        max
    }
    
/// Обход поддерева в глубину.
/// Возвращаем дек со значениями из поддерева.
    
    pub(crate) fn walk(&self) -> VecDeque<T> {
        return match *self {
            TreeKnot::Empty => VecDeque::new(),
            TreeKnot::NonEmpty(ref node) => {
                let mut result = node.left.walk();
                result.push_back(node.key.clone());
                result.extend(node.right.walk());
                result
            }
        }
    }
}