min_stack/
min_stack.rs

1#![allow(dead_code)]
2
3use hegel::TestCase;
4use hegel::generators as gs;
5use std::cmp::Ord;
6use std::marker::Copy;
7
8struct MinStack<T> {
9    stack: Vec<T>,
10    minimums: Vec<T>,
11}
12
13impl<T: Copy + Ord> MinStack<T> {
14    fn new() -> Self {
15        MinStack {
16            stack: Vec::new(),
17            minimums: Vec::new(),
18        }
19    }
20
21    fn push(&mut self, element: T) {
22        self.stack.push(element);
23        if self.minimums.is_empty() || self.minimum().is_some_and(|m| element < m) {
24            self.minimums.push(element);
25        }
26    }
27
28    fn pop(&mut self) -> Option<T> {
29        let element = self.stack.pop();
30        if element.is_some_and(|e| self.minimum().unwrap() == e) {
31            self.minimums.pop();
32        }
33        element
34    }
35
36    fn minimum(&self) -> Option<T> {
37        let length = self.minimums.len();
38        if length > 0 {
39            Some(self.minimums[length - 1])
40        } else {
41            None
42        }
43    }
44
45    fn reference(&self) -> Option<T> {
46        let mut minimum = None;
47        for element in &self.stack {
48            if minimum.is_none_or(|m| m > *element) {
49                minimum = Some(*element);
50            }
51        }
52        minimum
53    }
54}
55
56struct MinStackTest {
57    stack: MinStack<i32>,
58}
59
60#[hegel::state_machine]
61impl MinStackTest {
62    #[rule]
63    fn push(&mut self, tc: TestCase) {
64        let element = tc.draw(gs::integers::<i32>());
65        self.stack.push(element);
66    }
67
68    #[rule]
69    fn pop(&mut self, tc: TestCase) {
70        let element = self.stack.pop();
71        match element {
72            Some(element) => {
73                tc.note(&format!("pop {}", element));
74            }
75            _ => {
76                tc.note("pop nothing");
77            }
78        }
79    }
80
81    #[invariant]
82    fn minimums_agree(&mut self, _: TestCase) {
83        assert_eq!(self.stack.minimum(), self.stack.reference());
84    }
85}
86
87#[hegel::test]
88fn test_min_stack(tc: TestCase) {
89    let test = MinStackTest {
90        stack: MinStack::new(),
91    };
92    hegel::stateful::run(test, tc);
93}
94
95fn main() {}
min_stack/min_stack.rs

min_stack/
min_stack.rs
