store-interval-tree 0.4.0

#![no_std]
#![warn(clippy::cargo)]
#![deny(rustdoc::broken_intra_doc_links)]
#![deny(clippy::all)]
#![warn(
    missing_debug_implementations,
    trivial_numeric_casts,
    unused_extern_crates,
    unused_import_braces,
    unused_qualifications,
    unused_must_use
)]
#![warn(clippy::pedantic)]
#![allow(clippy::comparison_chain)]
// TODO: check https://rust-lang.github.io/rust-clippy/master/index.html#derive_hash_xor_eq
#![allow(clippy::derive_hash_xor_eq)]
#![allow(clippy::missing_panics_doc)]

#[macro_use]
pub extern crate alloc;

use alloc::{boxed::Box, rc::Rc, vec::Vec};
use core::cmp::Ord;
use core::fmt::Debug;
use core::ops::Bound;

mod interval;
pub use interval::Interval;

mod node;
use node::Node;

mod iterators;
pub use iterators::{Entry, EntryMut, IntervalTreeIterator, IntervalTreeIteratorMut};

/// An interval tree is a tree data structure to hold intervals.
/// Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point.
///
/// This data structure is backed by a `store_interval_tree:IntervalTree`
///
/// # Examples
/// ```
/// use store_interval_tree::IntervalTree;
/// use store_interval_tree::Interval;
/// use std::ops::Bound::*;
///
/// // initialize an interval tree with end points of type usize
/// let mut interval_tree = IntervalTree::<usize, ()>::new();
///
/// // insert interval into the tree
/// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
/// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
/// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
/// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
/// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
/// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
/// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
/// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
/// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
///
/// let interval1 = Interval::new(Excluded(23), Included(26));
///
/// // interval (25, 30] is overlapped with interval (23,26]
/// assert!(interval_tree.find_overlap(&interval1).unwrap() == Interval::new(Excluded(25), Included(30)));
///
/// // there is no interval in the tree that has interval with (10,15)
/// assert!(interval_tree.find_overlap(&Interval::new(Excluded(10), Excluded(15))).is_none());
///
/// // find all overlaps with an interval
/// let interval = Interval::new(Included(8), Included(26));
/// // intervals are: (8,9], [6,10],(19,20], [16,21), (15,23), [17,19), (25,30], [26,26]
/// let intervals = interval_tree.find_overlaps(&interval);
///
/// // delete interval
/// let interval = Interval::new(Included(15), Included(18));
/// let overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
/// interval_tree.delete(&overlapped_interval);
///
/// // find all intervals between two intervals/points
/// let low = Interval::point(14);
/// let high = Interval::point(24);
/// // intervals are: (15,23), [16,21), [17,19), (19,20]
/// let intervals = interval_tree.intervals_between(&low, &high);
/// ```
#[derive(Clone, Default, Hash)]
pub struct IntervalTree<T: Ord, V> {
    root: Option<Box<Node<T, V>>>,
}

impl<T: Ord, V> IntervalTree<T, V> {
    /// Initialize an interval tree with end points of type usize
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    ///
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    /// ```
    #[must_use]
    pub fn new() -> IntervalTree<T, V> {
        IntervalTree { root: None }
    }

    /// Returns true if there are no intervals in the tree, false otherwise
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }

    /// Returns total number of intervals in the tree
    #[must_use]
    pub fn size(&self) -> usize {
        Node::size(&self.root)
    }

    /// Returns height of the tree
    #[must_use]
    pub fn height(&self) -> i64 {
        Node::height(&self.root)
    }

    /// Find overlapping intervals in the tree and returns an
    /// `IntervalTreeIterator` that allows access to the stored value
    ///
    /// # Arguments
    /// * `interval`: interval to be searched for any overlaps
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// // insert interval into the tree
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
    ///
    /// let interval1 = Interval::new(Excluded(23), Included(26));
    ///
    /// // interval (25, 30] is overlapped with interval (23,26]
    /// assert!(interval_tree.find_overlap(&interval1).unwrap() == Interval::new(Excluded(25), Included(30)));
    ///
    /// // there is no interval in the tree that has interval with (10,15)
    /// assert!(interval_tree.find_overlap(&Interval::new(Excluded(10), Excluded(15))).is_none());
    /// ```
    #[must_use]
    pub fn query<'a, 'v, 'i>(
        &'a self,
        interval: &'i Interval<T>,
    ) -> IntervalTreeIterator<'v, 'i, T, V>
    where
        'a: 'v,
        'a: 'i,
    {
        if let Some(ref n) = self.root {
            IntervalTreeIterator {
                nodes: vec![n],
                interval,
            }
        } else {
            let nodes = vec![];
            IntervalTreeIterator { nodes, interval }
        }
    }

    /// Find overlapping intervals in the tree and returns an
    /// `IntervalTreeIteratorMut` that allows mutable access to the stored value
    ///
    /// # Arguments
    /// * `interval`: interval to be searched for any overlaps
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// // insert interval into the tree
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
    ///
    /// let interval1 = Interval::new(Excluded(23), Included(26));
    ///
    /// // interval (25, 30] is overlapped with interval (23,26]
    /// assert!(interval_tree.find_overlap(&interval1).unwrap() == Interval::new(Excluded(25), Included(30)));
    ///
    /// // there is no interval in the tree that has interval with (10,15)
    /// assert!(interval_tree.find_overlap(&Interval::new(Excluded(10), Excluded(15))).is_none());
    /// ```
    pub fn query_mut<'a, 'v, 'i>(
        &'a mut self,
        interval: &'i Interval<T>,
    ) -> IntervalTreeIteratorMut<'v, 'i, T, V>
    where
        'a: 'v,
        'a: 'i,
    {
        if let Some(ref mut n) = self.root {
            IntervalTreeIteratorMut {
                nodes: vec![n],
                interval,
            }
        } else {
            let nodes = vec![];
            IntervalTreeIteratorMut { nodes, interval }
        }
    }

    /// Returns true if there exists an interval in the tree that overlaps with specified `interval`
    ///
    /// # Arguments
    /// * `interval`: interval to be searched for any overlaps
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    ///
    /// assert!(!interval_tree.overlaps(&Interval::new(Included(4), Excluded(6))));
    /// assert!(interval_tree.overlaps(&Interval::new(Included(4), Included(6))));
    /// ```
    #[must_use]
    pub fn overlaps(&self, interval: &Interval<T>) -> bool {
        self.find_overlap(interval).is_some()
    }

    /// Returns first interval that overlaps with specified `interval`
    ///
    /// # Arguments:
    /// * `interval`: interval to be searched for any overlaps
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// // initialize an interval tree with end points of type usize
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// // insert interval into the tree
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
    ///
    /// let interval1 = Interval::new(Excluded(23), Included(26));
    ///
    /// // interval (25, 30] is overlapped with interval (23,26]
    /// assert!(interval_tree.find_overlap(&interval1).unwrap() == Interval::new(Excluded(25), Included(30)));
    ///
    /// // there is no interval in the tree that has interval with (10,15)
    /// assert!(interval_tree.find_overlap(&Interval::new(Excluded(10), Excluded(15))).is_none());
    /// ```
    #[must_use]
    pub fn find_overlap(&self, interval: &Interval<T>) -> Option<Interval<T>> {
        IntervalTree::_find_overlap(&self.root, interval)
    }

    fn _find_overlap(
        node: &Option<Box<Node<T, V>>>,
        interval: &Interval<T>,
    ) -> Option<Interval<T>> {
        if node.is_none() {
            return None;
        }
        let mut current = node;
        while current.is_some() {
            let node_ref = current.as_ref().unwrap();
            if Interval::overlaps(node_ref.interval(), interval) {
                break;
            }

            if node_ref.left_child.is_some()
                && Node::<T, V>::is_ge(
                    &node_ref.left_child.as_ref().unwrap().get_max(),
                    &interval.get_low(),
                )
            {
                current = &node_ref.left_child;
            } else {
                current = &node_ref.right_child;
            }
        }

        if current.is_none() {
            None
        } else {
            Some(current.as_ref().unwrap().interval().duplicate())
        }
    }

    /// Returns all intervals that overlap with the specified `interval`
    ///
    /// # Arguments
    /// * `interval`: interval to be searched for any overlaps
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// // initialize an interval tree with end points of type usize
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// // insert interval into the tree
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
    ///
    /// // find all overlaps with an interval
    /// let interval = Interval::new(Included(8), Included(26));
    /// // intervals are: (8,9], [6,10],(19,20], [16,21), (15,23), [17,19), (25,30], [26,26]
    /// let intervals = interval_tree.find_overlaps(&interval);
    /// ```
    #[must_use]
    pub fn find_overlaps(&self, interval: &Interval<T>) -> Vec<Interval<T>> {
        let mut overlaps = Vec::<Interval<T>>::new();

        IntervalTree::_find_overlaps(&self.root, interval, &mut overlaps);

        overlaps
    }

    fn _find_overlaps(
        node: &Option<Box<Node<T, V>>>,
        interval: &Interval<T>,
        overlaps: &mut Vec<Interval<T>>,
    ) {
        if node.is_none() {
            return;
        }
        let node_ref = node.as_ref().unwrap();
        if Interval::overlaps(node_ref.interval(), interval) {
            overlaps.push(node_ref.interval().duplicate());
        }

        if node_ref.left_child.is_some()
            && Node::<T, V>::is_ge(
                &node_ref.left_child.as_ref().unwrap().get_max(),
                &interval.get_low(),
            )
        {
            IntervalTree::_find_overlaps(&node_ref.left_child, interval, overlaps);
        }
        IntervalTree::_find_overlaps(&node_ref.right_child, interval, overlaps);
    }

    /// Inserts an interval in the tree. if interval already exists, `interval` will be ignored
    ///
    /// # Arguments
    /// * `interval`: interval to be inserted in the tree
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// // initialize an interval tree with end points of type usize
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// // insert interval into the tree
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
    /// ```
    pub fn insert(&mut self, interval: Interval<T>, value: V) {
        let max = interval.get_high();

        self.root = Some(IntervalTree::_insert(
            self.root.take(),
            interval,
            value,
            max,
        ));
    }

    fn _insert(
        node: Option<Box<Node<T, V>>>,
        interval: Interval<T>,
        value: V,
        max: Rc<Bound<T>>,
    ) -> Box<Node<T, V>> {
        if node.is_none() {
            return Box::new(Node::init(interval, value, max, 0, 1));
        }

        let mut node_ref = node.unwrap();

        if interval < *node_ref.interval() {
            node_ref.left_child = Some(IntervalTree::_insert(
                node_ref.left_child,
                interval,
                value,
                max,
            ));
        } else if interval > *node_ref.interval() {
            node_ref.right_child = Some(IntervalTree::_insert(
                node_ref.right_child,
                interval,
                value,
                max,
            ));
        } else {
            return node_ref;
        }

        node_ref.update_height();
        node_ref.update_size();
        node_ref.update_max();

        IntervalTree::balance(node_ref)
    }

    fn balance(mut node: Box<Node<T, V>>) -> Box<Node<T, V>> {
        if Node::balance_factor(&node) < -1 {
            if Node::balance_factor(node.right_child.as_ref().unwrap()) > 0 {
                node.right_child = Some(IntervalTree::rotate_right(node.right_child.unwrap()));
            }
            node = IntervalTree::rotate_left(node);
        } else if Node::balance_factor(&node) > 1 {
            if Node::balance_factor(node.left_child.as_ref().unwrap()) < 0 {
                node.left_child = Some(IntervalTree::rotate_left(node.left_child.unwrap()));
            }
            node = IntervalTree::rotate_right(node);
        }
        node
    }

    fn rotate_right(mut node: Box<Node<T, V>>) -> Box<Node<T, V>> {
        let mut y = node.left_child.unwrap();
        node.left_child = y.right_child;
        y.size = node.size;
        node.update_height();
        node.update_size();
        node.update_max();

        y.right_child = Some(node);
        y.update_height();
        y.update_max();

        y
    }

    fn rotate_left(mut node: Box<Node<T, V>>) -> Box<Node<T, V>> {
        let mut y = node.right_child.unwrap();
        node.right_child = y.left_child;
        y.size = node.size;

        node.update_height();
        node.update_size();
        node.update_max();

        y.left_child = Some(node);
        y.update_height();
        y.update_max();

        y
    }

    /// Delete the specified `interval` if found
    ///
    /// # Arguments
    /// * `interval`: interval to be deleted
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// // initialize an interval tree with end points of type usize
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// // insert interval into the tree
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
    ///
    /// // delete interval
    /// let interval = Interval::new(Included(15), Included(18));
    /// let overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
    /// interval_tree.delete(&overlapped_interval);
    /// ```
    pub fn delete(&mut self, interval: &Interval<T>) {
        if !self.is_empty() {
            self.root = IntervalTree::_delete(self.root.take(), interval);
        }
    }

    fn _delete(node: Option<Box<Node<T, V>>>, interval: &Interval<T>) -> Option<Box<Node<T, V>>> {
        match node {
            None => None,
            Some(mut node) => {
                if *interval < *node.interval() {
                    node.left_child = IntervalTree::_delete(node.left_child.take(), interval);
                } else if *interval > *node.interval() {
                    node.right_child = IntervalTree::_delete(node.right_child.take(), interval);
                } else if node.left_child.is_none() {
                    return node.right_child;
                } else if node.right_child.is_none() {
                    return node.left_child;
                } else {
                    let mut y = node;
                    node = IntervalTree::_min(&mut y.right_child);
                    node.right_child = IntervalTree::_delete_min(y.right_child.unwrap());
                    node.left_child = y.left_child;
                }

                node.update_height();
                node.update_size();
                node.update_max();
                Some(IntervalTree::balance(node))
            }
        }
    }
    fn _min(node: &mut Option<Box<Node<T, V>>>) -> Box<Node<T, V>> {
        match node {
            Some(node) => {
                if node.left_child.is_none() {
                    Box::new(Node::init(
                        node.get_interval(),
                        node.get_value(),
                        node.get_max(),
                        0,
                        1,
                    ))
                } else {
                    IntervalTree::_min(&mut node.left_child)
                }
            }
            None => panic!("Called min on None node"),
        }
    }

    /// Deletes minimum interval in the tree
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
    ///
    /// interval_tree.delete_min();
    /// interval_tree.delete_min();
    ///
    /// assert!(interval_tree.find_overlap(&Interval::new(Included(1), Excluded(6))).is_none());
    /// ```
    pub fn delete_min(&mut self) {
        if !self.is_empty() {
            self.root = IntervalTree::_delete_min(self.root.take().unwrap());
        }
    }

    fn _delete_min(mut node: Box<Node<T, V>>) -> Option<Box<Node<T, V>>> {
        if node.left_child.is_none() {
            return node.right_child.take();
        }

        node.left_child = IntervalTree::_delete_min(node.left_child.unwrap());

        node.update_height();
        node.update_size();
        node.update_max();

        Some(IntervalTree::balance(node))
    }

    /// Deletes maximum interval in the tree
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
    ///
    /// interval_tree.delete_max();
    /// interval_tree.delete_max();
    ///
    /// assert!(interval_tree.find_overlap(&Interval::new(Included(25), Excluded(30))).is_none());
    pub fn delete_max(&mut self) {
        if !self.is_empty() {
            self.root = IntervalTree::_delete_max(self.root.take().unwrap());
        }
    }

    fn _delete_max(mut node: Box<Node<T, V>>) -> Option<Box<Node<T, V>>> {
        if node.right_child.is_none() {
            return node.left_child.take();
        }

        node.right_child = IntervalTree::_delete_max(node.right_child.unwrap());

        node.update_height();
        node.update_size();
        node.update_max();

        Some(IntervalTree::balance(node))
    }

    /// Returns the kth smallest interval
    ///
    /// # Arguments
    /// * `k`: the order statistic
    ///
    /// # Panics
    /// * panics if k is not in range: 0 <= k <= size - 1
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
    ///
    /// assert!(format!("{}", interval_tree.select(0).unwrap()) == String::from("[0,3)"));
    /// assert!(format!("{}", interval_tree.select(1).unwrap()) == String::from("(0,1]"));
    /// assert!(format!("{}", interval_tree.select(2).unwrap()) == String::from("[6,10]"));
    /// assert!(format!("{}", interval_tree.select(3).unwrap()) == String::from("(8,9]"));
    /// ```
    #[must_use]
    pub fn select(&self, k: usize) -> Option<Interval<T>> {
        assert!(k <= self.size(), "K must be in range 0 <= k <= size - 1");
        IntervalTree::_select(&self.root, k)
    }

    fn _select(node: &Option<Box<Node<T, V>>>, k: usize) -> Option<Interval<T>> {
        if node.is_none() {
            return None;
        }
        let node_ref = node.as_ref().unwrap();

        let t = Node::size(&node_ref.left_child);
        if t > k {
            IntervalTree::_select(&node_ref.left_child, k)
        } else if t < k {
            IntervalTree::_select(&node_ref.right_child, k - t - 1)
        } else {
            return Some(node_ref.interval().duplicate());
        }
    }

    /// Returns minimum interval in the tree
    #[must_use]
    pub fn min(&self) -> Option<Interval<T>> {
        self.select(0)
    }

    /// Returns maximum interval in the tree
    #[must_use]
    pub fn max(&self) -> Option<Interval<T>> {
        self.select(self.size() - 1)
    }

    /// Returns all intervals between two intervals/points
    ///
    /// # Arguments
    /// * `low_bound`: lowest interval of the range
    /// * `high_bound`: highest interval of the range
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
    ///
    /// let low = Interval::new(Included(14), Included(14));
    /// let high = Interval::new(Included(24), Included(24));
    /// let intervals = interval_tree.intervals_between(&low, &high);
    ///
    /// let accept = String::from("(15,23)[16,21)[17,19)(19,20]");
    ///
    /// let mut result = String::from("");
    /// for interval in intervals {
    ///     result.push_str(&format!("{}", interval))
    /// }
    ///
    /// assert_eq!(result, accept);
    /// ```
    #[must_use]
    pub fn intervals_between(
        &self,
        low_bound: &Interval<T>,
        high_bound: &Interval<T>,
    ) -> Vec<&Interval<T>> {
        let mut intervals: Vec<&Interval<T>> = Vec::new();

        IntervalTree::_intervals_between(&self.root, low_bound, high_bound, &mut intervals);

        intervals
    }

    fn _intervals_between<'a>(
        node: &'a Option<Box<Node<T, V>>>,
        low_bound: &Interval<T>,
        high_bound: &Interval<T>,
        intervals: &mut Vec<&'a Interval<T>>,
    ) {
        if node.is_none() {
            return;
        }

        let node_ref = node.as_ref().unwrap();
        if *low_bound < *node_ref.interval() {
            IntervalTree::_intervals_between(
                &node_ref.left_child,
                low_bound,
                high_bound,
                intervals,
            );
        }
        if *low_bound <= *node_ref.interval() && *node_ref.interval() <= *high_bound {
            intervals.push(node_ref.interval());
        }
        if *high_bound > *node_ref.interval() {
            IntervalTree::_intervals_between(
                &node_ref.right_child,
                low_bound,
                high_bound,
                intervals,
            );
        }
    }

    /// Returns all intervals in the tree following an in-order traversal.
    /// Therefore intervals are sorted from smallest to largest
    #[must_use]
    pub fn intervals(&self) -> Vec<Interval<T>> {
        let mut intervals: Vec<Interval<T>> = Vec::new();

        IntervalTree::_intervals_in_order(&self.root, &mut intervals);

        intervals
    }

    fn _intervals_in_order(node: &Option<Box<Node<T, V>>>, intervals: &mut Vec<Interval<T>>) {
        if node.is_none() {
            return;
        }

        let node_ref = node.as_ref().unwrap();
        IntervalTree::_intervals_in_order(&node_ref.left_child, intervals);
        intervals.push(node_ref.interval().duplicate());
        IntervalTree::_intervals_in_order(&node_ref.right_child, intervals);
    }

    /// Returns the number of intervals in the tree less than `interval`
    ///
    /// # Arguments
    /// * `interval`: interval to be searched for
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
    ///
    /// assert_eq!(interval_tree.rank(&Interval::point(5)), 1);
    /// ```
    #[must_use]
    pub fn rank(&self, interval: &Interval<T>) -> usize {
        IntervalTree::_rank(&self.root, interval)
    }
    fn _rank(node: &Option<Box<Node<T, V>>>, interval: &Interval<T>) -> usize {
        if node.is_none() {
            return 0;
        }
        let node_ref = node.as_ref().unwrap();
        if *interval < *node_ref.interval() {
            IntervalTree::_rank(&node_ref.left_child, interval)
        } else if *interval >= *node_ref.interval() {
            1 + Node::size(&node_ref.left_child)
                + IntervalTree::_rank(&node_ref.right_child, interval)
        } else {
            Node::size(&node_ref.left_child)
        }
    }

    /// Returns the number of intervals in the tree between `low_bound` and `high_bound`
    ///
    /// # Arguments
    /// * `low_bound`: lowest interval of the range
    /// * `high_bound`: highest interval of the range
    ///
    /// # Examples
    /// ```
    /// use store_interval_tree::IntervalTree;
    /// use store_interval_tree::Interval;
    /// use std::ops::Bound::*;
    ///
    /// let mut interval_tree = IntervalTree::<usize, ()>::new();
    ///
    /// interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
    /// interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
    /// interval_tree.insert(Interval::new(Included(6), Included(10)), ());
    /// interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
    /// interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
    /// interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
    /// interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
    /// interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
    /// interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
    /// interval_tree.insert(Interval::new(Included(26), Included(26)), ());
    ///
    /// let low = Interval::point(10);
    /// let high = Interval::point(25);
    /// assert_eq!(interval_tree.size_between(&low, &high), 5);
    /// ```
    #[must_use]
    pub fn size_between(&self, low_bound: &Interval<T>, high_bound: &Interval<T>) -> usize {
        if self.is_empty() {
            return 0;
        }
        if *low_bound > *high_bound {
            return 0;
        }

        self.rank(high_bound) - self.rank(low_bound) + 1
    }
}

impl<T: Debug + Ord, V: Debug> Debug for IntervalTree<T, V> {
    fn fmt(&self, fmt: &mut core::fmt::Formatter) -> core::fmt::Result {
        fmt.write_str("IntervalTree ")?;
        fmt.debug_set().entries(self.intervals().iter()).finish()
    }
}

#[cfg(test)]
mod tests {
    use alloc::string::String;

    use super::*;
    use core::ops::Bound::{Excluded, Included, Unbounded};

    #[test]
    fn tree_interval_init() {
        let interval_tree = IntervalTree::<usize, ()>::new();

        assert!(interval_tree.is_empty());
        assert_eq!(interval_tree.size(), 0);
    }

    #[test]
    fn tree_interval_insert() {
        let mut interval_tree = IntervalTree::<usize, ()>::new();

        interval_tree.insert(Interval::new(Included(0), Included(3)), ());
        interval_tree.insert(Interval::new(Included(5), Included(8)), ());
        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
        interval_tree.insert(Interval::new(Included(8), Included(9)), ());
        interval_tree.insert(Interval::new(Included(15), Included(23)), ());
        interval_tree.insert(Interval::new(Included(16), Included(21)), ());
        interval_tree.insert(Interval::new(Included(17), Included(19)), ());
        interval_tree.insert(Interval::new(Included(19), Included(20)), ());
        interval_tree.insert(Interval::new(Included(25), Included(30)), ());
        interval_tree.insert(Interval::new(Included(26), Included(26)), ());

        assert_eq!(interval_tree.size(), 10);
    }

    #[test]
    fn tree_interval_find_overlap_1() {
        let mut interval_tree = IntervalTree::<usize, ()>::new();

        interval_tree.insert(Interval::new(Included(0), Included(3)), ());
        interval_tree.insert(Interval::new(Included(5), Included(8)), ());
        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
        interval_tree.insert(Interval::new(Included(8), Included(9)), ());
        interval_tree.insert(Interval::new(Included(15), Included(23)), ());
        interval_tree.insert(Interval::new(Included(16), Included(21)), ());
        interval_tree.insert(Interval::new(Included(17), Included(19)), ());
        interval_tree.insert(Interval::new(Included(19), Included(20)), ());
        interval_tree.insert(Interval::new(Included(25), Included(30)), ());
        interval_tree.insert(Interval::new(Included(26), Included(26)), ());

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(1), Included(2)))
                    .unwrap()
            ) == *"[0,3]"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(4), Included(5)))
                    .unwrap()
            ) == *"[5,8]"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(10), Included(14)))
                    .unwrap()
            ) == *"[6,10]"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(14), Included(15)))
                    .unwrap()
            ) == *"[15,23]"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(15), Included(18)))
                    .unwrap()
            ) == *"[16,21]"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(19), Included(19)))
                    .unwrap()
            ) == *"[19,20]"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(23), Included(23)))
                    .unwrap()
            ) == *"[15,23]"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(24), Included(26)))
                    .unwrap()
            ) == *"[25,30]"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(26), Included(36)))
                    .unwrap()
            ) == *"[25,30]"
        );

        assert!(interval_tree
            .find_overlap(&Interval::new(Included(31), Included(36)))
            .is_none());
        assert!(interval_tree
            .find_overlap(&Interval::new(Included(12), Included(12)))
            .is_none());
        assert!(interval_tree
            .find_overlap(&Interval::new(Included(13), Included(13)))
            .is_none());
        assert!(interval_tree
            .find_overlap(&Interval::new(Included(12), Included(14)))
            .is_none());
    }

    #[test]
    fn tree_interval_find_overlap_2() {
        let mut interval_tree = IntervalTree::<usize, ()>::new();

        interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
        interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
        interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
        interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
        interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
        interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
        interval_tree.insert(Interval::new(Included(26), Included(26)), ());

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(1), Included(2)))
                    .unwrap()
            ) == *"[0,3)"
        );

        assert!(interval_tree
            .find_overlap(&Interval::new(Included(4), Included(5)))
            .is_none());

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(10), Included(14)))
                    .unwrap()
            ) == *"[6,10]"
        );

        assert!(interval_tree
            .find_overlap(&Interval::new(Included(14), Included(15)))
            .is_none());

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(15), Included(18)))
                    .unwrap()
            ) == *"[16,21)"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(19), Included(19)))
                    .unwrap()
            ) == *"[16,21)"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Excluded(23), Included(26)))
                    .unwrap()
            ) == *"(25,30]"
        );

        assert!(interval_tree
            .find_overlap(&Interval::new(Excluded(10), Excluded(15)))
            .is_none());

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Excluded(21), Included(23)))
                    .unwrap()
            ) == *"(15,23)"
        );

        assert!(interval_tree
            .find_overlap(&Interval::new(Included(31), Included(36)))
            .is_none());
        assert!(interval_tree
            .find_overlap(&Interval::new(Included(12), Included(12)))
            .is_none());
        assert!(interval_tree
            .find_overlap(&Interval::new(Included(13), Included(13)))
            .is_none());
        assert!(interval_tree
            .find_overlap(&Interval::new(Included(12), Included(14)))
            .is_none());
    }

    #[test]
    fn tree_interval_find_overlap_3() {
        let mut interval_tree = IntervalTree::<usize, ()>::new();

        interval_tree.insert(Interval::new(Unbounded, Excluded(3)), ());
        interval_tree.insert(Interval::new(Excluded(5), Included(8)), ());
        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
        interval_tree.insert(Interval::new(Unbounded, Included(9)), ());
        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
        interval_tree.insert(Interval::new(Unbounded, Excluded(21)), ());
        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
        interval_tree.insert(Interval::new(Excluded(19), Unbounded), ());
        interval_tree.insert(Interval::new(Unbounded, Included(30)), ());
        interval_tree.insert(Interval::new(Included(26), Unbounded), ());

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(1), Included(2)))
                    .unwrap()
            ) == *"(_,9]"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(4), Included(5)))
                    .unwrap()
            ) == *"(_,9]"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(10), Included(14)))
                    .unwrap()
            ) == *"(_,21)"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(14), Included(15)))
                    .unwrap()
            ) == *"(_,21)"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(15), Included(18)))
                    .unwrap()
            ) == *"(_,21)"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Included(19), Included(19)))
                    .unwrap()
            ) == *"(_,21)"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Excluded(23), Included(26)))
                    .unwrap()
            ) == *"(_,30]"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Excluded(21), Included(23)))
                    .unwrap()
            ) == *"(_,30]"
        );

        assert!(
            format!(
                "{}",
                interval_tree
                    .find_overlap(&Interval::new(Unbounded, Included(0)))
                    .unwrap()
            ) == *"(_,9]"
        );
    }

    #[test]
    fn tree_interval_delete_1() {
        let mut interval_tree = IntervalTree::<usize, ()>::new();

        interval_tree.insert(Interval::new(Included(0), Included(3)), ());
        interval_tree.insert(Interval::new(Included(5), Included(8)), ());
        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
        interval_tree.insert(Interval::new(Included(8), Included(9)), ());
        interval_tree.insert(Interval::new(Included(15), Included(23)), ());
        interval_tree.insert(Interval::new(Included(16), Included(21)), ());
        interval_tree.insert(Interval::new(Included(17), Included(19)), ());
        interval_tree.insert(Interval::new(Included(19), Included(20)), ());
        interval_tree.insert(Interval::new(Included(25), Included(30)), ());
        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
        let mut interval = Interval::new(Included(1), Included(2));
        let mut overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
        interval_tree.delete(&overlapped_interval);
        assert!(interval_tree.find_overlap(&interval).is_none());

        interval = Interval::new(Included(15), Included(18));
        overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
        interval_tree.delete(&overlapped_interval);
        overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
        interval_tree.delete(&overlapped_interval);
        overlapped_interval = interval_tree.find_overlap(&interval).unwrap();
        interval_tree.delete(&overlapped_interval);
        assert!(interval_tree.find_overlap(&interval).is_none());
    }

    #[test]
    fn tree_interval_delete_max_1() {
        let mut interval_tree = IntervalTree::<usize, ()>::new();

        interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
        interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
        interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
        interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
        interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
        interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
        interval_tree.delete_max();
        interval_tree.delete_max();

        assert!(interval_tree
            .find_overlap(&Interval::new(Included(23), Included(23)))
            .is_none());
    }

    #[test]
    fn tree_interval_delete_min_1() {
        let mut interval_tree = IntervalTree::<usize, ()>::new();

        interval_tree.insert(Interval::new(Included(0), Included(3)), ());
        interval_tree.insert(Interval::new(Included(5), Included(8)), ());
        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
        interval_tree.insert(Interval::new(Included(8), Included(9)), ());
        interval_tree.insert(Interval::new(Included(15), Included(23)), ());
        interval_tree.insert(Interval::new(Included(16), Included(21)), ());
        interval_tree.insert(Interval::new(Included(17), Included(19)), ());
        interval_tree.insert(Interval::new(Included(19), Included(20)), ());
        interval_tree.insert(Interval::new(Included(25), Included(30)), ());
        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
        interval_tree.delete_min();
        interval_tree.delete_min();

        assert!(interval_tree
            .find_overlap(&Interval::new(Included(1), Excluded(6)))
            .is_none());
    }

    #[test]
    fn tree_interval_select_1() {
        let mut interval_tree = IntervalTree::<usize, ()>::new();

        interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
        interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
        interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
        interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
        interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
        interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
        interval_tree.insert(Interval::new(Included(26), Included(26)), ());
        assert!(format!("{}", interval_tree.select(0).unwrap()) == *"[0,3)");
        assert!(format!("{}", interval_tree.select(1).unwrap()) == *"(0,1]");
        assert!(format!("{}", interval_tree.select(2).unwrap()) == *"[6,10]");
        assert!(format!("{}", interval_tree.select(3).unwrap()) == *"(8,9]");
        assert!(format!("{}", interval_tree.select(4).unwrap()) == *"(15,23)");
        assert!(format!("{}", interval_tree.select(5).unwrap()) == *"[16,21)");
        assert!(format!("{}", interval_tree.select(6).unwrap()) == *"[17,19)");
        assert!(format!("{}", interval_tree.select(7).unwrap()) == *"(19,20]");
        assert!(format!("{}", interval_tree.select(8).unwrap()) == *"(25,30]");
        assert!(format!("{}", interval_tree.select(9).unwrap()) == *"[26,26]");
    }

    #[test]
    fn tree_interval_intervals_between_1() {
        let mut interval_tree = IntervalTree::<usize, ()>::new();

        interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
        interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
        interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
        interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
        interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
        interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
        interval_tree.insert(Interval::new(Included(26), Included(26)), ());

        let low = Interval::new(Included(14), Included(14));
        let high = Interval::new(Included(24), Included(24));
        let intervals = interval_tree.intervals_between(&low, &high);

        let accept = String::from("(15,23)[16,21)[17,19)(19,20]");

        let mut result = String::from("");
        for interval in intervals {
            result.push_str(&format!("{}", interval));
        }

        assert_eq!(result, accept);
    }

    #[test]
    fn tree_interval_find_overlaps_1() {
        let mut interval_tree = IntervalTree::<usize, ()>::new();

        interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
        interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
        interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
        interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
        interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
        interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
        interval_tree.insert(Interval::new(Included(26), Included(26)), ());

        let interval = Interval::new(Included(8), Included(26));
        let intervals = interval_tree.find_overlaps(&interval);

        let accept = String::from("(8,9][6,10](19,20][16,21)(15,23)[17,19)(25,30][26,26]");

        let mut result = String::from("");
        for interval in intervals {
            result.push_str(&format!("{}", interval));
        }

        assert_eq!(result, accept);
    }

    #[test]
    fn tree_interval_query_1() {
        let mut interval_tree = IntervalTree::<usize, ()>::new();

        interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
        interval_tree.insert(Interval::new(Included(0), Excluded(3)), ());
        interval_tree.insert(Interval::new(Included(6), Included(10)), ());
        interval_tree.insert(Interval::new(Excluded(8), Included(9)), ());
        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), ());
        interval_tree.insert(Interval::new(Included(16), Excluded(21)), ());
        interval_tree.insert(Interval::new(Included(17), Excluded(19)), ());
        interval_tree.insert(Interval::new(Excluded(19), Included(20)), ());
        interval_tree.insert(Interval::new(Excluded(25), Included(30)), ());
        interval_tree.insert(Interval::new(Included(26), Included(26)), ());

        let interval = Interval::new(Included(8), Included(26));
        let iter = interval_tree.query(&interval);

        let accept = String::from("(8,9][6,10](19,20][16,21)(15,23)[17,19)(25,30][26,26]");

        let mut result = String::from("");
        for entry in iter {
            result.push_str(&format!("{}", entry.interval()));
        }

        assert_eq!(result, accept);
    }

    #[test]
    fn tree_interval_query_2() {
        let mut interval_tree = IntervalTree::<usize, bool>::new();

        interval_tree.insert(Interval::new(Excluded(0), Included(1)), true);
        interval_tree.insert(Interval::new(Included(0), Excluded(3)), true);
        interval_tree.insert(Interval::new(Included(6), Included(10)), true);
        interval_tree.insert(Interval::new(Excluded(8), Included(9)), true);
        interval_tree.insert(Interval::new(Excluded(15), Excluded(23)), true);
        interval_tree.insert(Interval::new(Included(16), Excluded(21)), true);
        interval_tree.insert(Interval::new(Included(17), Excluded(19)), true);
        interval_tree.insert(Interval::new(Excluded(19), Included(20)), true);
        interval_tree.insert(Interval::new(Excluded(25), Included(30)), true);
        interval_tree.insert(Interval::new(Included(26), Included(26)), true);

        let interval = Interval::new(Included(8), Included(26));
        let iter = interval_tree.query_mut(&interval);

        for mut entry in iter {
            *entry.value() = false;
        }

        let iter = interval_tree.query(&interval);
        for entry in iter {
            assert!(!*entry.value());
        }
    }

    #[test]
    fn tree_interval_debug() {
        let mut interval_tree = IntervalTree::<usize, ()>::new();
        assert_eq!(format!("{:?}", &interval_tree), "IntervalTree {}");
        interval_tree.insert(Interval::new(Excluded(0), Included(1)), ());
        assert_eq!(
            format!("{:?}", &interval_tree),
            "IntervalTree {Interval { low: Excluded(0), high: Included(1) }}"
        );
    }
}