stacktools 0.1.0

use std::cmp::Ord;
use std::collections::{BinaryHeap, VecDeque};
use std::collections::binary_heap;
use std::collections::vec_deque;

pub struct Queue<T> {
    inner: VecDeque<T>,
}

pub struct Stack<T> {
    inner: VecDeque<T>,
}

pub struct PriorityQueue<T: Ord> {
    inner: BinaryHeap<T>,
}

impl<T> Queue<T> {
    pub fn new() -> Self {
        Self {
            inner: VecDeque::new(),
        }
    }

    fn len(&self) -> usize {
        self.inner.len()
    }

    fn push(&mut self, v: T) {
        self.inner.push_back(v);
    }

    fn iter(&self) -> vec_deque::Iter<T> {
        self.inner.iter()
    }
}

impl<T> Stack<T> {
    pub fn new() -> Self {
        Self {
            inner: VecDeque::new(),
        }
    }

    fn len(&self) -> usize {
        self.inner.len()
    }

    fn push(&mut self, v: T) {
        self.inner.push_front(v);
    }

    fn iter(&self) -> vec_deque::Iter<T> {
        self.inner.iter()
    }
}

impl<T> Iterator for Queue<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.inner.pop_front()
    }
}
impl<T> Iterator for Stack<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.inner.pop_front()
    }
}
impl<T: Ord> Iterator for PriorityQueue<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.inner.pop()
    }
}
impl<T> PriorityQueue<T>
where
    T: Ord,
{
    pub fn new() -> Self {
        Self {
            inner: BinaryHeap::new(),
        }
    }

    fn len(&self) -> usize {
        self.inner.len()
    }

    fn push(&mut self, v: T) {
        self.inner.push(v);
    }

    fn iter(&self) -> binary_heap::Iter<T> {
        self.inner.iter()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::cmp::Ord;
    use std::cmp::Ordering;

    #[test]
    fn fifo_instantiate() {
        let mut fifo: Queue<i32> = Queue::new();

        assert!(fifo.len() == 0);
        fifo.push(1);
        fifo.push(2);
        fifo.push(3);
        assert!(fifo.len() == 3);

        {
            let mut iter = fifo.iter();

            assert_eq!(Some(&1), iter.next());
            assert_eq!(Some(&2), iter.next());
            assert_eq!(Some(&3), iter.next());
        }

        assert_eq!(Some(1), fifo.next());
        assert!(fifo.len() == 2);

        assert_eq!(Some(2), fifo.next());
        assert!(fifo.len() == 1);

        assert_eq!(Some(3), fifo.next());
        assert!(fifo.len() == 0);

        assert_eq!(None, fifo.next());
    }

    #[test]
    fn lifo_instantiate() {
        let mut lifo: Stack<i32> = Stack::new();

        assert!(lifo.len() == 0);
        lifo.push(1);
        lifo.push(2);
        lifo.push(3);
        assert!(lifo.len() == 3);

        {
            let mut iter = lifo.iter();

            assert_eq!(Some(&3), iter.next());
            assert_eq!(Some(&2), iter.next());
            assert_eq!(Some(&1), iter.next());
        }

        assert_eq!(Some(3), lifo.next());
        assert!(lifo.len() == 2);

        assert_eq!(Some(2), lifo.next());
        assert!(lifo.len() == 1);

        assert_eq!(Some(1), lifo.next());
        assert!(lifo.len() == 0);

        assert_eq!(None, lifo.next());
    }

    #[derive(Copy, Eq, Debug, PartialOrd, PartialEq)]
    enum Priority {
        Trivial = 1,
        Normal,
        Critical,
    }

    impl Clone for Priority {
        #[inline]
        fn clone(&self) -> Priority {
            *self
        }
    }

    impl Ord for Priority {
        #[inline]
        fn cmp(&self, other: &Priority) -> Ordering {
            (*self as usize).cmp(&(*other as usize))
        }
    }

    #[derive(Eq, PartialEq, Debug)]
    struct PriorityMessage {
        priority: Priority,
        value: i32,
    }

    impl Ord for PriorityMessage {
        fn cmp(&self, other: &PriorityMessage) -> Ordering {
            self.priority.cmp(&other.priority)
        }
    }

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

    #[test]
    fn priority_instantiate() {
        let mut prio: PriorityQueue<PriorityMessage> = PriorityQueue::new();

        assert!(prio.len() == 0);
        prio.push(PriorityMessage {
            priority: Priority::Trivial,
            value: 1,
        });
        prio.push(PriorityMessage {
            priority: Priority::Normal,
            value: 2,
        });
        prio.push(PriorityMessage {
            priority: Priority::Critical,
            value: 3,
        });
        prio.push(PriorityMessage {
            priority: Priority::Critical,
            value: 4,
        });

        assert!(prio.len() == 4);

        {
            let mut iter = prio.iter();

            assert_eq!(
                Some(&PriorityMessage {
                    priority: Priority::Critical,
                    value: 3,
                }),
                iter.next()
            );
            assert_eq!(
                Some(&PriorityMessage {
                    priority: Priority::Critical,
                    value: 4,
                }),
                iter.next()
            );
            assert_eq!(
                Some(&PriorityMessage {
                    priority: Priority::Normal,
                    value: 2,
                }),
                iter.next()
            );
            assert_eq!(
                Some(&PriorityMessage {
                    priority: Priority::Trivial,
                    value: 1,
                }),
                iter.next()
            );
        }

        assert_eq!(
            Some(PriorityMessage {
                priority: Priority::Critical,
                value: 3,
            }),
            prio.next()
        );
        assert!(prio.len() == 3);

        assert_eq!(
            Some(PriorityMessage {
                priority: Priority::Critical,
                value: 4,
            }),
            prio.next()
        );
        assert!(prio.len() == 2);

        assert_eq!(
            Some(PriorityMessage {
                priority: Priority::Normal,
                value: 2,
            }),
            prio.next()
        );
        assert!(prio.len() == 1);

        assert_eq!(
            Some(PriorityMessage {
                priority: Priority::Trivial,
                value: 1,
            }),
            prio.next()
        );
        assert!(prio.len() == 0);

        assert_eq!(None, prio.next());
    }
}