algo-rs 0.1.0

Set of data structures and algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

use crate::data_structure::queue::Queue;

pub struct TwoStacksQueue<T> {
    s1: Vec<T>,
    s2: Vec<T>,
}

impl<T> TwoStacksQueue<T> {
    pub fn new() -> Self {
        Self {
            s1: Vec::<T>::new(),
            s2: Vec::<T>::new(),
        }
    }

    pub fn with_capacity(size: usize) -> Self {
        Self {
            s1: Vec::<T>::with_capacity(size),
            s2: Vec::<T>::with_capacity(size),
        }
    }

    fn rebalance(&mut self) {
        while self.s1.len() > 0 {
            self.s2.push(self.s1.pop().unwrap());
        }
    }
}

impl<T> Queue<T> for TwoStacksQueue<T> {
    fn push_back(&mut self, item: T) {
        self.s1.push(item)
    }

    fn pop_front(&mut self) -> Option<T> {
        if self.s2.is_empty() {
            self.rebalance();
        }

        self.s2.pop()
    }

    fn front(&self) -> Option<&T> {
        if !self.s2.is_empty() {
            return self.s2.last();
        }

        self.s1.first()
    }

    fn is_empty(&self) -> bool {
        self.s1.is_empty() && self.s2.is_empty()
    }
}

#[cfg(test)]
mod tests {
    use crate::data_structure::queue::two_stacks_queue::TwoStacksQueue;
    use crate::data_structure::queue::Queue;
    extern crate test;
    use test::Bencher;

    #[test]
    fn test_growable_queue_push_pop() {
        let mut queue = TwoStacksQueue::<i32>::new();
        for i in 0..33 {
            queue.push_back(i);
            queue.push_back(i + 1);
            queue.push_back(i + 2);
            assert_eq!(Some(i), queue.pop_front());
            assert_eq!(Some(i + 1), queue.pop_front());
            assert_eq!(Some(i + 2), queue.pop_front());
            assert_eq!(None, queue.pop_front());
        }
    }

    #[test]
    fn test_growable_queue_is_empty() {
        let mut queue = TwoStacksQueue::<i32>::new();
        assert_eq!(true, queue.is_empty());
        queue.push_back(1);
        assert_eq!(false, queue.is_empty());
        queue.pop_front();
        assert_eq!(true, queue.is_empty());
    }

    #[test]
    fn test_growable_queue_front() {
        let mut queue = TwoStacksQueue::<i32>::new();
        assert_eq!(None, queue.front());
        queue.push_back(1);
        assert_eq!(1, *queue.front().unwrap());
        queue.push_back(2);
        assert_eq!(1, *queue.front().unwrap());
        queue.pop_front();
        assert_eq!(2, *queue.front().unwrap());
        queue.pop_front();
        assert_eq!(None, queue.front());
    }

    #[bench]
    fn bench_growable_queue_push_pop(b: &mut Bencher) {
        b.iter(|| {
            let mut queue = TwoStacksQueue::<i32>::with_capacity(20);
            for i in 0..10000 {
                for _ in 0..10 {
                    queue.push_back(i);
                }

                for _ in 0..10 {
                    queue.pop_front();
                }
            }
        });
    }
}