//! A library implementing a tournament tree data structure.
//!
//! Tournament trees are, conceptually, complete binary trees holding the result
//! of comparisons between each element of the tree. They can be used as a fixed
//! size priority queue for applications like out-of-core sorting, or
//! implementing many way joins.
//!
//! ```
//! use tournament_tree::TournamentTree;
//! # use std::cmp::Reverse;
//! let mut data1 = vec![3, 1, 4, 1, 5, 2, 6, 5];
//! let tourney_tree = TournamentTree::from(data1.clone());
//! data1.sort_by_key(|&e| Reverse(e));
//! let data2: Vec<_> = tourney_tree.into_iter().collect();
//! assert_eq!(data1, data2);
//! ```
use std::{iter::FromIterator, ops::Deref};

/// A tournament tree. See the module documentation for more details.
///
/// This is a max tree.
#[derive(Debug, Clone)]
pub struct TournamentTree<T> {
    data: Vec<T>,
    tree: Vec<usize>,
}

/// Immutable tournament tree iterator.
#[derive(Debug, Clone)]
pub struct Iter<'tree, T> {
    data: &'tree TournamentTree<T>,
    tree: Vec<usize>,
}

/// An iterator that moves out of the tournament
/// tree.
#[derive(Debug, Clone)]
pub struct IntoIter<T> {
    data: Vec<Option<T>>,
    tree: Vec<usize>,
}

impl<T: Ord> TournamentTree<T> {
    /// Returns the winner.
    ///
    /// # Panics
    /// If the tree is empty.
    pub fn winner(&self) -> &T {
        &self[self.winner_idx()]
    }

    /// The Index of the winner.
    ///
    /// # Panics
    /// If the tree is empty.
    pub fn winner_idx(&self) -> usize {
        self.tree[0]
    }

    fn build(data: Vec<T>) -> Self {
        let mut tree = vec![usize::MAX; data.len()];
        let k = data.len();
        for i in 0..data.len() {
            let mut winner = i;
            let mut j = (i + k) / 2;
            while j != 0 && tree[j] != usize::MAX {
                let challenger = tree[j];
                if data[challenger] > data[winner] {
                    tree[j] = winner;
                    winner = challenger;
                }
                j = j / 2;
            }
            tree[j] = winner;
        }

        Self { data, tree }
    }

    pub fn iter(&self) -> Iter<T> {
        Iter {
            data: self,
            tree: self.tree.clone(),
        }
    }
}

impl<T: Ord> Deref for TournamentTree<T> {
    type Target = [T];

    fn deref(&self) -> &Self::Target {
        &self.data
    }
}

impl<T: Ord> From<Vec<T>> for TournamentTree<T> {
    fn from(data: Vec<T>) -> Self {
        Self::build(data)
    }
}

impl<T: Ord> Into<Vec<T>> for TournamentTree<T> {
    fn into(self) -> Vec<T> {
        self.data
    }
}

impl<T: Ord> AsRef<[T]> for TournamentTree<T> {
    fn as_ref(&self) -> &[T] {
        &self.data
    }
}

impl<T: Ord> FromIterator<T> for TournamentTree<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let data = Vec::from_iter(iter);
        Self::build(data)
    }
}

impl<T: Ord> IntoIterator for TournamentTree<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;
    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            data: self.data.into_iter().map(Some).collect(),
            tree: self.tree,
        }
    }
}

impl<'tree, T: Ord> IntoIterator for &'tree TournamentTree<T> {
    type Item = &'tree T;
    type IntoIter = Iter<'tree, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl<T: Ord> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        let k = self.data.len();
        if self.tree[0] == k {
            return None;
        }

        let i = self.tree[0];
        let mut winner = k;
        let mut j = (i + k) / 2;
        while j != 0 {
            let challenger = self.tree[j];
            if challenger != k && (winner == k || self.data[challenger] > self.data[winner]) {
                self.tree[j] = winner;
                winner = challenger;
            }
            j = j / 2;
        }
        self.tree[j] = winner;

        self.data[i].take()
    }
}

impl<'tree, T: Ord> Iterator for Iter<'tree, T> {
    type Item = &'tree T;

    fn next(&mut self) -> Option<Self::Item> {
        let k = self.data.len();
        if self.tree[0] == k {
            return None;
        }

        let i = self.tree[0];
        let mut winner = k;
        let mut j = (i + k) / 2;
        while j != 0 {
            let challenger = self.tree[j];
            if challenger != k
                && (winner == k || self.data.data[challenger] > self.data.data[winner])
            {
                self.tree[j] = winner;
                winner = challenger;
            }
            j = j / 2;
        }
        self.tree[j] = winner;

        Some(&self.data.data[i])
    }
}

/// A bounded priority queue using a `TournamentTree` for a backing structure.
///
/// Will replace each element removed with the next one from it's iterator until
/// all iterators are exhausted. If the iterators iterate in reverse sorted order, the
/// output will be in sorted order.
pub struct TournamentTreeIterator<T> {
    tt: TournamentTree<Option<T>>,
    its: Vec<Box<dyn Iterator<Item = T>>>,
}

pub struct TournamentTreeIteratorBuilder<T> {
    its: Vec<Box<dyn Iterator<Item = T>>>,
}

impl<T: Ord> TournamentTreeIterator<T> {
    /// Creates a new `TournamentTreeIteratorBuilder` for constructing a
    /// `TournamentTreeIterator`
    pub fn builder() -> TournamentTreeIteratorBuilder<T> {
        TournamentTreeIteratorBuilder { its: Vec::new() }
    }
}

impl<T: Ord> TournamentTreeIterator<T> {
    fn adv(&mut self) -> Option<T> {
        let i = self.tt.winner_idx();
        let k = self.tt.data.len();
        let ret = self.tt.data[i].take();
        self.tt.data[i] = self.its[i].next();
        let mut winner = i;
        let mut j = (i + k) / 2;
        while j != 0 {
            let challenger = self.tt.tree[j];
            if self.tt[challenger] > self.tt[winner] {
                self.tt.tree[j] = winner;
                winner = challenger;
            }
            j = j / 2;
        }
        self.tt.tree[j] = winner;

        ret
    }
}

impl<T: Ord> Iterator for TournamentTreeIterator<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.tt.winner().is_none() {
            return None;
        }
        self.adv()
    }
}

impl<T: Ord> TournamentTreeIteratorBuilder<T> {
    /// Add an iterator to the eventual `TournamentTreeIterator`
    pub fn add(&mut self, it: impl Iterator<Item = T> + 'static) -> &mut Self {
        self.its.push(Box::new(it));
        self
    }

    /// Consumes the builder, returning the `TournamentTreeIterator`.
    pub fn build(mut self) -> TournamentTreeIterator<T> {
        let mut data = Vec::with_capacity(self.its.len());
        for it in self.its.iter_mut() {
            data.push(it.next());
        }

        TournamentTreeIterator {
            tt: TournamentTree::from(data),
            its: self.its,
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn basic() {
        let data = vec![3, 1, 4, 1, 5, 2, 6, 5];
        let tourney_tree = TournamentTree::build(data);
        assert_eq!(*tourney_tree.winner(), 6);
    }

    #[test]
    fn iter() {
        use std::cmp::Reverse;
        let mut data1 = vec![3, 1, 4, 1, 5, 2, 6, 5];
        let tourney_tree = TournamentTree::build(data1.clone());
        data1.sort_by_key(|&e| Reverse(e));
        let data2: Vec<_> = tourney_tree.iter().copied().collect();
        assert_eq!(data1, data2);
    }

    #[test]
    fn into_iter() {
        use std::cmp::Reverse;
        let mut data1 = vec![3, 1, 4, 1, 5, 2, 6, 5];
        let tourney_tree = TournamentTree::build(data1.clone());
        data1.sort_by_key(|&e| Reverse(e));
        let data2: Vec<_> = tourney_tree.into_iter().collect();
        assert_eq!(data1, data2);
    }

    #[test]
    fn iterator() {
        let mut ttib = TournamentTreeIterator::builder();
        ttib.add(vec![7, 5, 3, 1].into_iter())
            .add(vec![16, 8, 4, 2, 1].into_iter())
            .add(vec![11, 7, 5, 3, 2].into_iter())
            .add(vec![25, 16, 9, 4, 1, 0].into_iter());
        let v: Vec<_> = ttib.build().collect();
        assert_eq!(
            v,
            [25, 16, 16, 11, 9, 8, 7, 7, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 0]
        );
    }
}