use derive_more::{From, Index, IndexMut};
use num_traits::Num;
use std::cmp::Ordering::Equal;
use std::ops::RangeBounds;

// A RankedWinner is a winner in an election, ranked ascending (starting from zero).
// A ranked-winner with a lower rank beats a ranked-winner with a higher rank.
// Ranked-winners with the same rank are tied.
type RankedWinner<T> = (T, u32);

/// `RankedWinners` is a ranked list of winning candidates, sorted according to rank.
/// Ranks are in ascending order. A `0` ranked winner is more significant than a `3` ranked winner.
/// Winners with the same rank are tied.
// TODO: implement Index, IndexMut
#[derive(Debug, Eq, PartialEq, From, Default)]
pub struct RankedWinners<T: Clone> {
    winners: Vec<RankedWinner<T>>,
    num_winners: u32,
}

impl<T: Clone + Eq> RankedWinners<T> {
    /// Get the number of winners.
    pub fn len(&self) -> usize {
        self.winners.len()
    }

    /// Check if it's empty
    pub fn is_empty(&self) -> bool {
        self.winners.is_empty()
    }

    /// Clears the winners, returning all winner-rank pairs as an iterator.
    pub fn drain<R>(&mut self, range: R) -> std::vec::Drain<'_, RankedWinner<T>>
    where
        R: RangeBounds<usize>,
    {
        self.winners.drain(range)
    }

    /// Transform winners into a vector of winner-rank pairs.
    pub fn into_vec(self) -> Vec<RankedWinner<T>> {
        self.winners
    }

    /// Get a list of all winners, without rank.
    pub fn all(&self) -> Vec<T> {
        let mut winners = Vec::<T>::with_capacity(self.len());
        for (winner, _) in self.winners.iter() {
            winners.push(winner.clone());
        }

        winners
    }

    /// Iterate over all winner->rank pairs.
    pub fn iter(&self) -> IterWinners<'_, T> {
        IterWinners { inner: self, pos: 0 }
    }

    /// Check if the given candidate exists in the set of ranked-winners.
    pub fn contains(&self, candidate: &T) -> bool {
        for (winner, _rank) in self.iter() {
            if candidate == winner {
                return true;
            }
        }

        false
    }

    /// Get the rank of a single winner.
    pub fn rank(&self, candidate: &T) -> Option<u32> {
        for (winner, rank) in self.iter() {
            if candidate == winner {
                return Some(*rank);
            }
        }

        None
    }

    /// Get an unranked list of all winners, this consumes the winner list.
    pub fn into_unranked(mut self) -> Vec<T> {
        let mut all = Vec::new();
        for (winner, _rank) in self.drain(0..) {
            all.push(winner);
        }

        all
    }

    /// Check if the actual number of winners is more than the wanted number of winners.
    /// This can happen if there is a tie.
    ///
    /// Not all ties result in an overflow. Only a tie of the least-significantly
    /// ranked winning candidates can result in an overflow. Consider an election
    /// that is trying to fill three seats. If only the top two candidates tie, then
    /// there is no overflow. However, if the 3rd place and 4th place candidates tie,
    /// then there will be an overflow with both candidates being equally ranked to
    /// fill the 3rd seat.
    pub fn check_overflow(&self) -> bool {
        self.len() > self.num_winners as usize
    }

    /// Get all tied least-significantly ranked winners that overflow the wanted number of winners.
    ///
    /// If there is a tie in the least-significantly ranked winning candidates,
    /// then the actual number of winners may "overflow" the wanted number of winners, in which case this
    /// method will return a list of overlow candidates (or `None` if there is no overflow).
    ///
    /// You should always check for an overflow so you can resolve this unfortunate situation.
    pub fn overflow(&self) -> Option<Vec<T>> {
        if self.check_overflow() {
            let mut overflow = Vec::<T>::new();
            let overflow_rank = self.winners[self.winners.len() - 1].1;
            for (candidate, rank) in self.iter() {
                if *rank == overflow_rank {
                    overflow.push(candidate.clone());
                }
            }
            Some(overflow)
        } else {
            None
        }
    }

    // New empty list of ranked winners
    pub(crate) fn new(num_winners: u32) -> Self {
        RankedWinners {
            winners: Vec::new(),
            num_winners: num_winners,
        }
    }

    // Push a new winner onto the end of of the list of winners
    // Make sure to call sort() before passing the Winners back to the user.
    pub(crate) fn push(&mut self, candidate: T, rank: u32) {
        self.winners.push((candidate, rank));
    }

    // Sort the winners by rank.
    pub(crate) fn sort(&mut self) {
        self.winners.sort_by(|a, b| a.1.cmp(&b.1));
    }

    // Create winners from a list of ranked candidates
    pub(crate) fn from_ranked(mut ranked: Vec<(T, u32)>, num_winners: u32) -> Self {
        let mut winners = Self::new(num_winners);
        let mut prev_rank = 0;
        for (candidate, rank) in ranked.drain(0..) {
            if winners.len() as u32 >= num_winners && rank != prev_rank {
                break;
            }
            winners.push(candidate, rank);
            prev_rank = rank;
        }
        winners.sort();

        winners
    }
}

// Iterator for Winners
// TODO: Use some sort of a macro to auto-generate this.
// ---------------------

/// Iterator for winners
pub struct IterWinners<'a, T: Clone> {
    inner: &'a RankedWinners<T>,
    pos: usize,
}

impl<'a, T: Clone> Iterator for IterWinners<'a, T> {
    type Item = &'a RankedWinner<T>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.pos >= self.inner.winners.len() {
            None
        } else {
            self.pos += 1;
            self.inner.winners.get(self.pos - 1)
        }
    }
}

#[derive(Debug, Eq, PartialEq, From, Index, IndexMut, Default)]
pub(crate) struct CountedCandidates<T: Clone + Eq, C: Copy + Num + PartialOrd>(Vec<(T, C)>);

impl<T: Clone + Eq, C: Copy + Num + PartialOrd> CountedCandidates<T, C> {
    // New empty list of counted candidates
    pub(crate) fn new() -> Self {
        CountedCandidates(Vec::new())
    }

    /// Get the number of winners.
    pub(crate) fn len(&self) -> usize {
        self.0.len()
    }

    /// Transform candidates into a vector of RankedWinners.
    /// Limit the number of winners by "num_winners", returned number may be over this if there is a tie
    /// Set num_winners to `0` for no limit.
    pub(crate) fn into_ranked(mut self, num_winners: u32) -> RankedWinners<T> {
        let mut ranked = RankedWinners::<T>::new(num_winners);

        if self.len() == 0 {
            return ranked;
        }

        self.sort();

        let mut rank = 0;
        let mut prev = self.0[0].1;
        for (candidate, score) in self.0.drain(0..) {
            if score != prev {
                if num_winners != 0 && ranked.len() as u32 >= num_winners {
                    return ranked;
                }
                rank += 1;
            }
            ranked.push(candidate, rank);
            prev = score;
        }

        ranked
    }

    // Transform into a vector
    pub(crate) fn into_vec(mut self) -> Vec<(T, C)> {
        self.sort();
        self.0
    }

    // Push a new winner onto the end of of the list of winners
    // Make sure to call sort() before passing the Winners back to the user.
    pub(crate) fn push(&mut self, candidate: T, count: C) {
        self.0.push((candidate, count));
    }

    /// Sort the candidates by tallied counts.
    // TODO: better handling of uncomparible (eg NaN) types
    //       one possibility is to check ordering against ::zero(), and order the offending value last.
    pub(crate) fn sort(&mut self) {
        self.0.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(Equal));
    }
}