BTree (Rust)

/**
 *   _____________________________________
 *  |                                    |
 * | О СТРУКТУРЕ И КАК ЕЙ ПОЛЬЗОВАТЬСЯ  |
 *|____________________________________|
 *
 *-------------------------О СТРУКТУРЕ----------------------------------------------------------------
 *
 * Бинарное дерево - это структура данных,
 * которая имеет корень, значение и две ветви - правую и левую,
 * которые, в свою очередь, также хранят значения и две ветви.
 * Ветви могут быть как пустыми, так и непустыми.
 * Так же ветвь хранит ссылку на отцовскую ветвь,
 * если та не является родителем (т.е. инициализированна через Empty)
 * Значение представленно дженериком T (аналог шаблона С++)
 *
 * --------------ПРАВИЛА ХРАНЕНИЯ И ИСПОЛЬЗОВАНИЯ-------------------------------------------------
 *
 * В БИНАРНОМ ДЕРЕВЕ КЛЮЧИ ПРАВОГО ПОДДЕРЕВА БОЛЬШЕ КЛЮЧЕЙ ЛЕВОГО ПОДДЕРЕВА
 * Это освновополагающее правило размещения в дереве. Рассмотрим его подробнее:
 * Допустим, у нас есть ключ с неким значением и дерево (непустое)
 * Мы будем идти вглубь дерева, и на каждом вхождении проверять ключи ветвей
 * Если ключ меньше ключа ветви, то отправляемся в правую ветвь,
 * иначе идём в левую ветвь. Так идём, пока не дойдём то конца всей корневой системы
 * Когда дошли, то проверяем наш ключ и ключ ветви, выбираем нужную ветвь
 * и определяем родителя для новой ветви по указателю, тем самым мы можем ходить по дереву
 */

//---------------------------------------------------------------------------------------------------------

/*
* Будем хранить всё в enum (перечисление)
* В случае, когда ветвь пуста, то мы определяем её как Empty,
* иначе определяем её как NonEmpty. Перечисления в Rust позволяют
* хранить данные для параметров перечислений. Здесь мы храним всё
* как Box<TreeNode<T>>. Box - указатель на кучу, который
* задаёт размер структуре.
*
* TreeNode<T> - универсальная структура, которая основана на типе T.
* Тип T - дженерик (или шаблон С++), для использования которого Rust
* требует определения трейтов (если говорить коротко - аналогов
* интерфейсов). Для типа T мы определили трейты PartialEq (сравнение
* на равенство или неравенство), PartialOrd (сравнения >, <, <=, >=),
* Clone и Copy (для копирования. Кстати, трейты также, как и интерфейсы
* умеют "наследовать" друг друга. Так, например, Clone - дочерний трейт
* для Copy. Т.к. Clone наследует Copy, то реализуя трейт Clone, мы обязаны
* реализовывать Copy)
*/

pub enum BTree<T>
// Храним всё дерево как перечисление
where
    T: PartialOrd + PartialEq + Clone + Copy, // определяем трейты для дженерика T
{
    Empty,                      // Пусто
    NonEmpty(Box<TreeNode<T>>), // Не пусто
}

pub struct TreeNode<T>
// Структура ветвь, с помощью которой
where
    // мы можем передвигаться по дереву
    T: PartialOrd + PartialEq + Clone + Copy, // Для T используем те же трейты
{
    key: T,           // Значение, которое мы храним на ветви
    right: BTree<T>,  // Правая ветвь
    left: BTree<T>,   // Левая ветвь
    parent: BTree<T>, // Родительская ветвь
}

//-------------------------------------------------------------------------------------------------------

impl<T> BTree<T>
// Реализация всех методов для дерева
where
    BTree<T>: PartialOrd + PartialEq + Clone + Copy, // Дерево также обязано иметь свои трейты,
    T: PartialOrd + PartialEq + Clone + Copy,        // при том те же, что и T
{
    /*
     * Метод new() - конструктор, который создаёт новый
     * экземпляр дерева. По умолчанию наше дерево пустое,
     * чтобы пользователю было удобно им пользоваться,
     * а не утруждать себя добавлениями-удалениями
     */

    pub fn new() -> Self {
        BTree::Empty
    }

    //----------------------------------------------------------------------------------------------------------

    /*
     * Методы ignore() и ignore_mut() конвертирует BTree<T> в &Box<TreeNode<T>>.
     * Т.к. наше дерево может быть пусто, то вызываем панику,
     * иначе всё корректно и возвращаем ссылку
     */

    fn ignore(&self) -> &Box<TreeNode<T>> {
        if let BTree::NonEmpty(ref node) = *self {
            return node;
        } else {
            panic!("Empty tree");
        }
    }

    fn ignore_mut(&mut self) -> &mut Box<TreeNode<T>> {
        if let BTree::NonEmpty(ref mut node) = *self {
            return node;
        } else {
            panic!("Empty tree");
        }
    }

    //----------------------------------------------------------------------------------------------------------

    /*
     * Метод insert() добавляет в дерево новую ветвь,
     * значение которой устанавливает пользователь
     * Моя реализация дерева поддерживает хранение ветвей,
     * которые имеют одинаковые значения.
     */

    pub fn insert(&mut self, val: &T) {
        let mut new_node = TreeNode {
            key: (*val).clone(),
            right: BTree::Empty,
            left: BTree::Empty,
            parent: BTree::Empty,
        };

        let mut root2 = *self;
        let mut root3 = BTree::Empty;

        while root2 != BTree::Empty {
            root3 = root2;
            if val < &root2.ignore().key {
                root2 = root2.ignore().left;
            } else {
                root2 = root2.ignore().right;
            }
        }

        new_node.parent = root3;

        if val < &root3.ignore().key {
            root3.ignore_mut().left = BTree::NonEmpty(Box::new(new_node));
        } else {
            root3.ignore_mut().right = BTree::NonEmpty(Box::new(new_node));
        }
    }

    //----------------------------------------------------------------------------------------------------------

    /*
     * Метод find() ищет ветвь,
     * значение которой равно заданному пользователю.
     * Т.к. дерево может хранить ветви с повторяющимися значениями
     * то мы находим ту ветвь, которая находится ближе всего
     * к макушке (началу) дерева.
     *
     * Входной параметр - искомое значение.
     * В случае успеха мы возвращаем непустую ветвь (BTree<T>),
     * Иначе мы возвращаем совершенно пустую ветвь (Empty).
     */

    pub fn find(&self, val: &T) -> BTree<T> {
        let mut root2 = *self;

        while root2 != BTree::Empty {
            if val < &root2.ignore().key {
                root2 = root2.ignore().left
            } else if val < &root2.ignore().key {
                root2 = root2.ignore().right;
            } else {
                return root2;
            }
        }

        BTree::Empty
    }

    //----------------------------------------------------------------------------------------------------------

    /*
     * Методы min_key() и max_key() ищет минимальную/максимальную ветвь поддерева.
     * Т.к. дерево может хранить ветви с одинаковыми значениями,
     * то мы вернём последнее наименьшее/наибольшее вхождение.
     *
     * Т.к. дерево может быть пустым, то мы вернём пустое дерево (Empty).
     * Иначе мы найдём хоть что-то, и ветвь с этим мы и вернём
     */

    pub fn min_key(&self) -> BTree<T> {
        let mut min = *self;

        while min.ignore().left != BTree::Empty {
            min = min.ignore().left;
        }

        min
    }

    pub fn max_key(&self) -> BTree<T> {
        let mut max = *self;

        while max.ignore().right != BTree::Empty {
            max = max.ignore().right;
        }

        max
    }

    //----------------------------------------------------------------------------------------------------------

    /*
     * Метод next() находит ветвь, значение которой является следующим
     * для текущего т.е. минимальным, но большим или равным текущему.
     *
     * Т.к. всё, что больше, хранится в дереве справа, то если наше дерево
     * имеет правую ветвь, то мы пользуемся методом min_key() и находим
     * такую ветвь, что её значение будет минимальным.
     * Если же дерево не имеет правую ветвь, то мы идём вверх по дереву
     * и ищем такую родительскую ветвь, у которой есть правая, а дальше
     * используем min_key() и находим нужную ветвь.
     *
     * Т.к. дерево может быть пустым, то мы возвращаем пустое дерево,
     * иначе возвращаем непустое дерево с нужным значением.
     */

    pub fn next(&self) -> BTree<T> {
        let node = *self;
        return if node.ignore().right != BTree::Empty {
            node.ignore().right.min_key()
        } else {
            let mut l = node.ignore().parent;
            let mut p = *self;
            let mut check = node.ignore().parent;

            if let BTree::NonEmpty(ref mut node_l) = check {
                while l != BTree::Empty && p == node_l.right {
                    p = l;
                    l = node_l.parent;
                }
            }
            l
        };
    }

    //----------------------------------------------------------------------------------------------------------

    /*
     * Метод remove() очищает ветвь по значению.
     * Возможны 3 случая размещения удаляемой ветки:
     *
     * 1) Когда у ветви нет дочерних ветвей.
     * В этом случае мы просто удаляем ветвь,
     * предварительно обнулив её для родителей
     *
     * 2) Когда у ветви есть 1 дочерняя ветвь.
     * В этом случае просто удаляем узел,
     *  и на его место ставим дочернюю ветвь
     *
     * 3) Когда у ветви есть обе дочерние ветви.
     * В этом случае ищем такую ветвь,
     * что она будет следующей для текущей.
     * Ставим этот узел на место удаляемой.
     *
     * Возвращаем удалённую ветвь, возможно
     * она ещё пригодится пользователю.
     * Если же дерево было пусто, то
     * возвращаем пустое дерево.
     */

    pub fn remove(&mut self, val: &T) -> BTree<T> {
        let p = *self;
        let mut l = BTree::Empty;

        l = p.find(val);

        if l == BTree::Empty {
            return BTree::Empty;
        }

        if l.ignore().left == BTree::Empty && l.ignore().right == BTree::Empty {
            let mut m = l.ignore().parent;
            if l == m.ignore().right {
                m.ignore_mut().right = BTree::Empty;
            } else {
                m.ignore_mut().left = BTree::Empty;
            }
            drop(l);
        }

        if l.ignore().left == BTree::Empty && l.ignore().right != BTree::Empty {
            let mut m = l.ignore().parent;
            if l == m.ignore().right {
                m.ignore_mut().right = l.ignore().left;
            } else {
                m.ignore_mut().left = l.ignore().left;
            }
            drop(l);
        }

        if l.ignore().left != BTree::Empty && l.ignore().right != BTree::Empty {
            let mut m = l.next();
            l.ignore_mut().key = m.ignore().key;
            if m.ignore().right == BTree::Empty {
                if m.ignore().parent.ignore().right == BTree::Empty {
                    m.ignore_mut().parent.ignore_mut().left = BTree::Empty;
                } else {
                    m.ignore_mut().parent.ignore_mut().left = m.ignore().right;
                }
            }

            drop(m);
        }
        *self
    }
    //----------------------------------------------------------------------------------------------------------

    /*
     * Методы get_key() и get_key_mut() возвращают значение ветви
     * Т.к. дерево может быть пустым,
     * то методы ignore() и ignore_mut() будут вызывать панику
     */

    pub fn get_key(&self) -> &T {
        &(*self).ignore().key
    }

    pub fn get_key_mut(&mut self) -> &mut T {
        &mut (*self).ignore_mut().key
    }

    //----------------------------------------------------------------------------------------------------------

    /*
     * Метод first() макушку дерева.
     * Метод призван помочь пользователю передвигаться по дереву
     * В случае, когда дерево пусто, вызывается паника
     */

    fn first(&self) -> Self {
        let mut root = *self;
        while root.ignore().parent != BTree::Empty {
            root = root.ignore().parent;
        }
        root
    }

    //-----------------------------------------------------------------------------------------------------------

    /*
     * Методы begin() и end() позволяют пользователю
     * передвигаться по дереву.
     * Т.к. дерево может быть пустым,
     * то будет вызвана паника
     */

    pub fn begin(&self) -> Self {
        let mut root = (*self).first();
        while root.ignore().left != BTree::Empty {
            root = root.ignore().left;
        }
        root
    }

    pub fn end(&self) -> Self {
        let mut root = (*self).first();
        while root.ignore().right != BTree::Empty {
            root = root.ignore().right;
        }
        root
    }

    //-----------------------------------------------------------------------------------------------------------
}