snarkvm_r1cs/
optional_vec.rs

1// Copyright (C) 2019-2023 Aleo Systems Inc.
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7// http://www.apache.org/licenses/LICENSE-2.0
8
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15// A helper object containing a list of values that, when removed, leave a "hole" in their
16// place; this allows all the following indices to remain unperturbed; the holes take priority
17// when inserting new objects.
18pub struct OptionalVec<T> {
19    // a list of optional values
20    values: Vec<Option<T>>,
21    // a list of indices of the Nones in the values vector
22    holes: Vec<usize>,
23}
24
25impl<T> Default for OptionalVec<T> {
26    fn default() -> Self {
27        Self { values: Default::default(), holes: Default::default() }
28    }
29}
30
31impl<T> OptionalVec<T> {
32    /// Creates a new `OptionalVec` with the given underlying capacity.
33    #[inline]
34    pub fn with_capacity(cap: usize) -> Self {
35        Self { values: Vec::with_capacity(cap), holes: Default::default() }
36    }
37
38    /// Inserts a new value either into the first existing hole or extending the vector
39    /// of values, i.e. pushing it to its end.
40    #[inline]
41    pub fn insert(&mut self, elem: T) -> usize {
42        let idx = self.holes.pop().unwrap_or(self.values.len());
43        if idx < self.values.len() {
44            self.values[idx] = Some(elem);
45        } else {
46            self.values.push(Some(elem));
47        }
48        idx
49    }
50
51    /// Returns the index of the next value inserted into the `OptionalVec`.
52    #[inline]
53    pub fn next_idx(&self) -> usize {
54        self.holes.last().copied().unwrap_or(self.values.len())
55    }
56
57    /// Removes a value at the specified index; assumes that the index points to
58    /// an existing value that is a `Some(T)` (i.e. not a hole).
59    #[inline]
60    pub fn remove(&mut self, idx: usize) -> T {
61        let val = self.values[idx].take();
62        self.holes.push(idx);
63        val.unwrap()
64    }
65
66    /// Iterates over all the `Some(T)` values in the list.
67    #[inline]
68    pub fn iter(&self) -> impl Iterator<Item = &T> {
69        self.values.iter().filter_map(|v| v.as_ref())
70    }
71
72    /// Returns the number of `Some(T)` values.
73    #[inline]
74    pub fn len(&self) -> usize {
75        self.values.len() - self.holes.len()
76    }
77
78    #[inline]
79    /// Returns `true` if there are no `Some(T)` values
80    pub fn is_empty(&self) -> bool {
81        self.len() == 0
82    }
83}
84
85impl<T> std::ops::Index<usize> for OptionalVec<T> {
86    type Output = T;
87
88    fn index(&self, idx: usize) -> &Self::Output {
89        self.values[idx].as_ref().unwrap()
90    }
91}
92
93impl<T> std::ops::IndexMut<usize> for OptionalVec<T> {
94    fn index_mut(&mut self, idx: usize) -> &mut Self::Output {
95        self.values[idx].as_mut().unwrap()
96    }
97}
snarkvm_r1cs/optional_vec.rs

snarkvm_r1cs/
optional_vec.rs
