use std::cmp::Ordering;
use std::collections::{BinaryHeap, VecDeque};
use std::time::{Duration, Instant};

#[derive(Debug, PartialEq, Eq)]
struct Event<T> {
    item: T,
    release_at: Instant,
}

impl<T: Eq> Ord for Event<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        other.release_at.cmp(&self.release_at) // reverse ordering for min-heap
    }
}

impl<T: Eq> PartialOrd for Event<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

/// Current state of the debouncing buffer returned from `.get()`:
///
/// - `Ready(T)` when the event is ready to be delivered after the timeout
///   (moves data out of the buffer)
/// - `Wait(Duration)` indicates how much time is left until `Ready`
/// - `Empty` means the buffer is empty
#[derive(Debug, PartialEq)]
pub enum State<T> {
    Ready(T),
    Wait(Duration),
    Empty,
}

pub trait BufferGet<T> {
    fn get(&mut self) -> State<T>;
}

/// Debouncing buffer with a common delay for all events. Accepts events via
/// `.put()` which tracks the time of the event and de-duplicates them against
/// the current buffer content. Subsequent call to `.get()` which returns the
/// `State` of the buffer.
///
/// Implemented on top of a `VecDeque` and should be slightly more preformant
/// than `MixedEventBuffer`.
pub struct EventBuffer<T> {
    delay: Duration,
    events: VecDeque<Event<T>>,
}

impl<T: PartialEq> EventBuffer<T> {
    pub fn new(delay: Duration) -> EventBuffer<T> {
        EventBuffer {
            delay,
            events: VecDeque::new(),
        }
    }

    pub fn put(&mut self, item: T) {
        let time = Instant::now();
        self.events
            .retain(|e| e.release_at <= time || e.item != item);
        self.events.push_back(Event {
            item,
            release_at: time + self.delay,
        });
    }
}

impl<T> BufferGet<T> for EventBuffer<T> {
    fn get(&mut self) -> State<T> {
        let time = Instant::now();
        match self.events.get(0) {
            None => State::Empty,
            Some(e) if e.release_at > time => State::Wait(e.release_at - time),
            Some(_) => State::Ready(self.events.pop_front().unwrap().item),
        }
    }
}

/// Debouncing buffer with per-event delays. Accepts events via `.put(T, delay)`
/// which tracks the time of the event and de-duplicates them against the
/// current buffer content. Subsequent call to `.get()` which returns the
/// `State` of the buffer.
///
/// Implemented on top of a `BinaryHeap` and should be slightly less preformant
/// than `EventBuffer`.
pub struct MixedEventBuffer<T> {
    events: BinaryHeap<Event<T>>,
}

impl<T: Eq> MixedEventBuffer<T> {
    pub fn new() -> MixedEventBuffer<T> {
        MixedEventBuffer {
            events: BinaryHeap::new(),
        }
    }

    pub fn put(&mut self, item: T, delay: Duration) {
        let time = Instant::now();
        self.events
            .retain(|e| e.release_at <= time || e.item != item);
        self.events.push(Event {
            item,
            release_at: time + delay,
        });
    }
}

impl<T: Eq> BufferGet<T> for MixedEventBuffer<T> {
    fn get(&mut self) -> State<T> {
        let time = Instant::now();
        match self.events.peek() {
            None => State::Empty,
            Some(e) if e.release_at > time => State::Wait(e.release_at - time),
            Some(_) => State::Ready(self.events.pop().unwrap().item),
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::thread::sleep;
    use std::time::Duration;

    mod event_buffer {
        use super::*;

        #[test]
        fn wait() {
            let mut debouncer = EventBuffer::new(Duration::from_millis(20));
            debouncer.put(1);
            assert!(matches!(debouncer.get(), State::Wait(_)));
            sleep(Duration::from_millis(10));
            assert!(matches!(debouncer.get(), State::Wait(_)));
            sleep(Duration::from_millis(10));
            assert!(matches!(debouncer.get(), State::Ready(_)));
        }

        #[test]
        fn deduplication() {
            let mut debouncer = EventBuffer::new(Duration::from_millis(20));
            debouncer.put(1);
            debouncer.put(2);
            sleep(Duration::from_millis(10));
            debouncer.put(1);
            sleep(Duration::from_millis(20));
            assert_eq!(
                vec![debouncer.get(), debouncer.get(), debouncer.get()],
                vec![State::Ready(2), State::Ready(1), State::Empty]
            );
        }
    }

    mod mixed_event_buffer {
        use super::*;

        #[test]
        fn wait() {
            let mut debouncer = MixedEventBuffer::new();
            debouncer.put(1, Duration::from_millis(20));
            assert!(matches!(debouncer.get(), State::Wait(_)));
            sleep(Duration::from_millis(10));
            assert!(matches!(debouncer.get(), State::Wait(_)));
            sleep(Duration::from_millis(10));
            assert!(matches!(debouncer.get(), State::Ready(_)));
        }

        #[test]
        fn deduplication() {
            let mut debouncer = MixedEventBuffer::new();
            debouncer.put(1, Duration::from_millis(20));
            debouncer.put(2, Duration::from_millis(30));
            sleep(Duration::from_millis(10));
            debouncer.put(1, Duration::from_millis(10));
            sleep(Duration::from_millis(20));
            assert_eq!(
                vec![debouncer.get(), debouncer.get(), debouncer.get()],
                vec![State::Ready(1), State::Ready(2), State::Empty]
            );
        }

        #[test]
        fn event_order() {
            let mut debouncer = MixedEventBuffer::new();
            debouncer.put(2, Duration::from_millis(20));
            debouncer.put(1, Duration::from_millis(10));
            sleep(Duration::from_millis(30));
            assert_eq!(
                vec![debouncer.get(), debouncer.get()],
                vec![State::Ready(1), State::Ready(2)]
            );
        }
    }
}