bintree 0.1.0

use crate::knot::TreeKnot;
use crate::node::Node;
use crate::iter::TreeIter;
use std::iter::FromIterator;

/// Реализация бинарного дерева поиска на языке Rust.
/// О СТРУКТУРЕ:
/// Бинарное дерево поиска (Binary Search Tree) - условно направленный граф,
/// каждый узел котрого имеет ключ - некое значение, которое можно сравнивать
/// и две ветви - правую и левую.
/// (будем считать, что ветви есть всегда, просто они могут быть
/// либо пустыми, либо содержать значение).
/// В левой ветви хранятся узлы, ключи (значения) которых меньше ключа текущего
/// узла. В классической реализации бинарное дерево не хранит одинаковые ключи.
/// В моей реализации это возможно, узлы, ключи которых больше или равны текущему
/// хранятся в левой ветви.
///
/// В текущей реализации удалять ключи ПОКА ЧТО нельзя из-за сложностей реализации,
/// но это временно. Реализована система добавления и поиска ключа, а также ряд
/// других полезных фич, упрощающих жизнь.
///
/// Дерево можно сравнивать с себе подобными деревьями по принципу "равно-неравно".
/// От трейта PartialOrd решил отказаться во избежание недопонимания пользователя.
/// Если вы хотите сравнить размер, то это возможно сделать с помощью методов
/// len() и is_empty(). Если вы хотите сравнивать ещё что-то, то можете написать свою
/// функцию или реализовать полноценный трейт.
///
/// Также дерево можно вывести на экран с помощью форматного вывода
/// (т.е. print!("{:?}" ...). Трейт Debug также упрощает работу с тестами,
/// т.е. вы можете использовать дерево для тестирования моих или ваших функций.
///
/// Так же к дереву подключён трейт Clone, позволяющий полностью копировать
/// экземпляр дерева, если в этом есть необходимость.
///
/// Дерево может импользовать все те типы, которые поддерживают трейты
/// Copy, Clone, PartialOrd, PartialEq. Иными словами их можно переносить, копировать,
/// сравнивать между собой по типу больше-меньше и равно-неравно. Если типы, которые
/// вы хотите использовать, не поддерживают этих трейтов (а именно: сложные структуры, которые хранят
/// свои значения в куче (Vec, LinkedList, HashMap и т.д.), срезы, статические массивы, NAN и т.д.),
/// то вы не сможете импользовать дерево по техническим причинам :(
///
/// Если вы хотите полностью ознакомится с кодом, то переходите по ссылке ниже:
/// https://github.com/dinaraparanid/Structures/tree/master/src
/// Это репозиторий на GitHub с полной версией кода.
/// Если есть предложения, то не стесняйтесь, предлагайте :)

#[derive(PartialEq, Debug, Clone)]
pub struct BinaryTree<T>
    where T: Copy + Clone + PartialOrd + PartialEq
{
    pub(crate) top: TreeKnot<T>,
    pub(crate) size: usize,
}

/// Головная структура дерево хранит 2 поля: вершину дерева и размер дерева.
/// Вершина дерева представлена структурой TreeKnot<T> - узел дерева (см knot.rs)

impl<T> Default for BinaryTree<T>
    where T: Copy + Clone + PartialOrd + PartialEq
{
	#[inline]
    fn default() -> Self {
        BinaryTree {
            top: TreeKnot::Empty,
            size: 0,
        }
    }
}

/// Реализация трейта Default для дерева. Трейт Default отвечает за значение по-умолчанию.
/// По умолчанию дерево абсолютно пусто.
/// Высокой цели это не преследовало, так что можно идти дальше.


/// Реализуем методы для дерева.
impl<T> BinaryTree<T>
    where T: Copy + Clone + PartialOrd,
{

/// Метод new() делает всё то же, что и default()
/// По сути является конструктором для дерева.
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
///
/// let new_tree = BinaryTree::<i32>::new();
/// let def_tree = BinaryTree::<i32>::default();
///
/// assert_eq!(new_tree.len(), 0); // размер дерева
/// assert_eq!(def_tree.len(), 0); // см. len() ниже
/// ```

	#[inline]
    pub fn new() -> Self {
        BinaryTree::default()
    }

/// Метод len возвращает размер дерева как беззнаковое 64 битное
/// Если вдруг размер оказался отрицательным, то вам немедленно
/// нужно обратиться к врачу или перестать ломать чужой код :)
///
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
///
/// let mut tree = BinaryTree::new();
/// tree.insert(&1); // добавление в дерево
/// tree.insert(&2); // об этом поговорим
/// tree.insert(&3); // позже
///
/// assert_eq!(tree.len(), 3);
/// ```

	#[inline]
    pub fn len(&self) -> usize {
        self.size
    }
    
/// Метод is_empty() отвечает на вопрос: "пусто ли наше дерево?"
/// Если пусто, то возвращается true, иначе false;
///
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
///
/// let empty_tree = BinaryTree::<i32>::new();
/// let mut not_empty_tree = BinaryTree::new();
///
/// not_empty_tree.insert(&1);
/// not_empty_tree.insert(&2);
/// not_empty_tree.insert(&3);
///
/// assert_eq!(empty_tree.len(), 0);
/// assert_eq!(empty_tree.is_empty(), true);
///
/// assert_eq!(not_empty_tree.len(), 3);
/// assert_eq!(not_empty_tree.is_empty(), false);
/// ```
    
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.size == 0
    }
    
/// Метод insert() добавляет значение в дерево.
/// Значение берётся по неизменяемой ссылке, так что
/// смело юзайте, хотя я бы не рекомендовал использовать
/// типы, которые не хранятся на стеке или неразмерные типы.
/// Ах, да, их и нельзя импользовать)
///
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
/// 
/// let mut tree = BinaryTree::new();
/// tree.insert(&1);
/// tree.insert(&2);
/// tree.insert(&3);
///
/// assert_eq!(tree.contains(&1), true); // проверка на наличие значения в дереве.
/// assert_eq!(tree.contains(&2), true); // для лучшего понимания см tests.rs
/// assert_eq!(tree.contains(&3), true); // метод contains() рассмотрен ниже
/// ```

    pub fn insert(&mut self, val: &T) {
        if let TreeKnot::Empty = self.top {
            self.top = TreeKnot::NonEmpty(Box::new(Node {
                key: (*val).clone(),
                right: TreeKnot::Empty,
                left: TreeKnot::Empty,
            }));
            self.size = 1;
        } else {
            self.top.insert(val);
            self.size += 1;
        }
    }
    
/// Метод contains() проверяет наличие значения в дереве
/// Если оно есть, то возвращает true, иначе false
///
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
///
/// let mut tree = BinaryTree::new();
/// tree.insert(&1);
/// tree.insert(&2);
/// tree.insert(&3);
///
/// assert_eq!(tree.contains(&1), true);
/// assert_eq!(tree.contains(&2), true);
/// assert_eq!(tree.contains(&3), true);
/// ```
    
    #[inline]
    pub fn contains(&self, val: &T) -> bool {
        *self.top.find(&val) != TreeKnot::Empty
    }
    
/// Метод first() возвращает минимальное значение,
/// которое хранится в дереве. Если дерево пустое,
/// то пудет вызвана паника, сообщающая о том, что
/// дерево пусто, так что будьте осторожны.
///
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
///
/// let mut tree = BinaryTree::new();
///
/// tree.insert(&3);
/// assert_eq!(tree.first(), &3);
///
/// tree.insert(&2);
///  assert_eq!(tree.first(), &2);
///
/// tree.insert(&1);
///  assert_eq!(tree.first(), &1);
/// ```
    
    #[inline]
    pub fn first(&self) -> &T {
        self.top.min().get_key()
    }
    
/// Метод last() возвращает наибольший элемент дерва.
/// В случае, когда дерево пусто, вызывается паника.
///
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
///
/// let mut tree = BinaryTree::new();
///
/// tree.insert(&1);
/// assert_eq!(tree.last(), &1);
///
/// tree.insert(&2);
/// assert_eq!(tree.last(), &2);
///
/// tree.insert(&3);
/// assert_eq!(tree.last(), &3);
/// ```
    
    #[inline]
    pub fn last(&self) -> &T {
        self.top.max().get_key()
    }
    
/// Метод iter() превращает дерево в итератор,
/// который хранит элементы по-возрастанию.
/// Метод приватный, вместо этого используется
/// into_iter() из трейта IntoIterator (см. ниже)
/// Само дерево остаётся, так что смело используйте.
/// Для лучшего понимания см iter.rs
///
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
///
/// let mut tree = BinaryTree::new();
/// tree.insert(&1);
/// tree.insert(&2);
/// tree.insert(&3);
///
/// assert_eq!(tree.into_iter().collect::<Vec<i32>>(), vec![1, 2, 3]);
/// ```
    
    #[inline]
    pub(crate)fn iter(&self) -> TreeIter<T> {
        TreeIter {
            iter: self.top.walk()
        }
    }
    
/// Метод append() передаёт элементы из 1 дерева
/// в другое. Используемое дерево остаётся неизменным,
/// так что его можно также использовать.
/// Здесь мы создаём итератор из второго дерева
/// и перемещаем по ссылкам элементы в первое дерево.
///
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
///
/// let mut tree1 = BinaryTree::new();
/// let mut tree2 = BinaryTree::new();
///
/// tree1.insert(&1);
/// tree2.insert(&2);
/// tree2.insert(&3);
///
/// tree1.append(&tree2);
///
/// assert_eq!(tree1.into_iter().collect::<Vec<i32>>(), vec![1, 2, 3]);
/// ```
    
    pub fn append(&mut self, other: &BinaryTree<T>) {
        let collect = other.iter().iter;
        for elem in collect.iter() {
            self.insert(elem);
        }
    }
}

/// Добавляем дереву трейт IntoIterator.
/// Теперь мы можем итерироваться (ходить) по дереву.
/// Типом, который хранит наш итератор является пользовательский тип,
/// который должен соответствовать правилам, описанным выше.
/// В качестве итератора используем свою структуру TreeIter (см. iter.rs)
///
/// Т.к. мы добавили трейт и реализовали все необходимые методы
/// для точной имплементации трейта, то можем юзать и другие методы
/// из трейта Iterator, например:
///
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
///
/// let mut tree = BinaryTree::new();
///
/// tree.insert(&1);
/// tree.insert(&2);
/// tree.insert(&3);
///
/// let test1 = tree.clone().into_iter().collect::<Vec<i32>>();
/// let test2 = tree.clone().into_iter().min().unwrap();
/// let test3 = tree.clone().into_iter().sum::<i32>();
///
/// assert_eq!(test1, vec![1, 2, 3]);
/// assert_eq!(test2, 1);
/// assert_eq!(test3, 6);
/// ```
///
impl<T> IntoIterator for BinaryTree<T>
    where T: Copy + Clone + PartialOrd + PartialEq
{
    type Item = T;
    type IntoIter = TreeIter<T>;
    
/// Метод into_iter() превращает наше дерево в TreeIter.
///
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
///
/// let mut tree1 = BinaryTree::new();
/// let mut tree2 = BinaryTree::new();
///
/// tree1.insert(&1);
/// tree2.insert(&2);
/// tree2.insert(&3);
///
/// tree1.append(&tree2);
///
/// assert_eq!(tree1.into_iter().collect::<Vec<i32>>(), vec![1, 2, 3]);
/// ```
    
    fn into_iter(self) -> TreeIter<T> {
        self.iter()
    }
}

/// Добавление трейта FromIterator<T> для дерева
/// Теперь мы можем построить целое дерево из итератора.
///
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
/// use std::iter::FromIterator;
///
/// let range = (0..11).step_by(2);
/// let mut new_tree = BinaryTree::from_iter(range);
///
/// assert_eq!(new_tree.into_iter().collect::<Vec<i32>>(), vec![0, 2, 4, 6, 8, 10]);
/// ```

impl<T> FromIterator<T> for BinaryTree<T>
    where T: Copy + Clone + PartialOrd + PartialEq
{
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let it = iter.into_iter();
        let mut tree = BinaryTree::<T>::new();
        for elem in it {
            tree.insert(&elem);
        }
        return tree;
    }
}