bintree 0.1.0

use std::collections::VecDeque;

/// Реализация итератора для нашего дерева.
/// Для полного понимания советую ознакомится с реализацией
/// самого дерева, если вы этого ещё не сделали.
///
/// Для итератора я принял решение использовать
/// std::collections::VecDeque, т.к. он шустрее двусвязного
/// списка (std::collections::LinkedList), а также он может удалять
/// элементы как с конца, так и с начала.
/// В деке мы храним сами элементы, однако менять содержимое
/// итератора нельзя, т.к. может нарушиться логика дерева.
///
/// Для нашего итератора мы используем те же трейты, что и
/// для дерева, а именно:
/// Debug (для вывода на консоль или в файл),
/// Clone (для полного клонирования экземпляра),
/// PartialEq (для сравнения на равенство-неравенство).

#[derive(Debug, Clone, PartialEq)]
pub struct TreeIter<T>
	where T: Copy + Clone + PartialOrd + PartialEq
{
	pub(crate)iter: VecDeque<T>
}

/// Добавляем трейт Default для реализации дефолтного
/// итератора. По-умолчанию наш итератор - пустой дек.

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

/// Создаём пустой итератор
///
/// # Example
///
/// ```
/// use bintree::iter::TreeIter;
///
/// let def_iter = TreeIter::<i32>::default();
/// assert_eq!(def_iter.into_iter(), TreeIter::new());
/// ```

	fn default() -> Self {
		return TreeIter { iter: VecDeque::new() };
	}
}


/// Добавляем метод new() для нашего итератора.
/// Если честно, то просто по фану :D

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

/// Метод new() делает всё то же, что и метод default().
/// Если очень надо, то можно использовать его.
///
/// # Example
///
/// ```
/// use bintree::iter::TreeIter;
/// use std::collections::VecDeque;
///
/// let new_iter = TreeIter::new();
/// assert_eq!(new_iter.collect::<VecDeque<i32>>(), VecDeque::<i32>::new());
/// ```
 
	pub fn new() -> Self {
		TreeIter::default()
	}
}

/// Делаем наш итератор итератором, а точнее добавляем
/// реализацию трейта Iterator для нашего итератора.
/// Это значит, что наш итератор имеет те же методы,
/// что и все итераторы.
///
///  # Example
/// ```
/// use bintree::iter::TreeIter;
/// use bintree::tree::BinaryTree;
/// use std::iter::FromIterator;
///
/// let mut tree = BinaryTree::from_iter((1..11).step_by(2));
/// let mut tree_iter = tree.into_iter();
///
/// assert_eq!(tree_iter.clone().min().unwrap(), 1);
/// assert_eq!(tree_iter.clone().max().unwrap(), 9);
/// assert_eq!(tree_iter.clone().collect::<Vec<i32>>(), vec![1, 3, 5, 7, 9]);
/// assert_eq!(tree_iter.clone().filter(|x| x % 3 == 0).collect::<Vec<i32>>(), vec![3, 9]);
/// ```

impl<T> Iterator for TreeIter<T>
	where T: Copy + Clone + PartialOrd + PartialEq
{

/// Тип итератора соответствует типу дерева.
/// О том, какой тип может находится в дереве подробно
/// описано в tree.rs
	
	type Item = T;
	
/// Метод next() позволяет передвигаться по нашему итератору
/// поэлементно. Так как мы когда-нибудь дойдём до конца,
/// то это нужно как-то обозначить. Для этого используем
/// перечисление (enumeration или enum) Option.
/// Если мы дошли до конца, то вернётяс None,
/// Иначе Some(T).
/// Здесь мы опустошаем наш итератор, так что
/// ПОВТОРНОЕ ИСПОЛЬЗОВАНИЕ ОДНОГО И ТОГО ЖЕ
/// ИТЕРАТОРА ЗАПРЕЩЕНО (не рекомендуется).
///
/// # Example
///
/// ```
/// use bintree::tree::BinaryTree;
/// use std::iter::FromIterator;
///
/// let mut tree_iter = BinaryTree::from_iter((0..5).step_by(2)).into_iter();
///
/// assert_eq!(tree_iter.next(), Some(0));
/// assert_eq!(tree_iter.next(), Some(2));
/// assert_eq!(tree_iter.next(), Some(4));
/// assert_eq!(tree_iter.next(), None);
/// ```
	
	fn next(&mut self) -> Option<T> {
		return self.iter.pop_front();
	}
}