bmatcher_core/
stack.rs

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
117
118
119
120
121
122
123
124
125
126
use alloc::vec::Vec;

pub trait Stack<T> {
    fn len(&self) -> usize;
    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    fn reserve(&mut self, _size: usize) {}
    fn truncate(&mut self, size: usize);

    fn push_value(&mut self, value: T) -> bool;
    fn pop_value(&mut self) -> Option<T>;

    fn stack_mut(&mut self) -> &mut [T];
}

impl<T, I: Stack<T>> Stack<T> for &mut I {
    fn len(&self) -> usize {
        I::len(self)
    }

    fn reserve(&mut self, size: usize) {
        I::reserve(self, size)
    }
    fn truncate(&mut self, size: usize) {
        I::truncate(self, size)
    }

    fn push_value(&mut self, value: T) -> bool {
        I::push_value(self, value)
    }
    fn pop_value(&mut self) -> Option<T> {
        I::pop_value(self)
    }

    fn stack_mut(&mut self) -> &mut [T] {
        I::stack_mut(self)
    }
}

pub struct StaticStack<const N: usize, T> {
    stack: [T; N],
    length: usize,
}

impl<const N: usize, T: Default + Copy> StaticStack<N, T> {
    pub fn new() -> Self {
        Self {
            stack: [Default::default(); N],
            length: 0,
        }
    }
}

impl<const N: usize, T: Copy> Stack<T> for StaticStack<N, T> {
    fn len(&self) -> usize {
        self.length
    }

    fn stack_mut(&mut self) -> &mut [T] {
        &mut self.stack[0..self.length]
    }

    fn truncate(&mut self, size: usize) {
        self.length = size;
        assert!(size <= self.stack.len());
    }

    fn push_value(&mut self, value: T) -> bool {
        if self.length == self.stack.len() {
            return false;
        }

        self.stack[self.length] = value;
        self.length += 1;
        true
    }

    fn pop_value(&mut self) -> Option<T> {
        if self.length > 0 {
            self.length -= 1;
            let value = self.stack[self.length];
            Some(value)
        } else {
            None
        }
    }
}

pub struct HeapStack<T> {
    stack: Vec<T>,
}

impl<T> HeapStack<T> {
    pub fn new() -> Self {
        Self { stack: Vec::new() }
    }
}

impl<T> Stack<T> for HeapStack<T> {
    fn len(&self) -> usize {
        self.stack.len()
    }

    fn stack_mut(&mut self) -> &mut [T] {
        &mut self.stack
    }

    fn reserve(&mut self, size: usize) {
        self.stack.reserve(size);
    }

    fn truncate(&mut self, size: usize) {
        self.stack.truncate(size);
    }

    fn push_value(&mut self, value: T) -> bool {
        self.stack.push(value);
        true
    }

    fn pop_value(&mut self) -> Option<T> {
        self.stack.pop()
    }
}