multiversx_sc/types/static_buffer/
sparse_array.rs

1use alloc::format;
2
3use crate::{
4    abi::{TypeAbi, TypeAbiFrom, TypeDescriptionContainer, TypeName},
5    api::{ErrorApi, ErrorApiImpl},
6    codec::{self, arrayvec::ArrayVec, NestedDecode, NestedEncode, TopDecode, TopEncode},
7};
8use core::marker::PhantomData;
9
10const EMPTY_ENTRY: usize = 0;
11static INVALID_INDEX_ERR_MSG: &[u8] = b"Index out of bounds";
12
13/// A special type of array that initially holds the values from 0 to N
14/// If array[i] == i, then the default value (0) is stored instead
15#[derive(Clone)]
16pub struct SparseArray<E, const CAPACITY: usize>
17where
18    E: ErrorApi,
19{
20    array: [usize; CAPACITY],
21    len: usize,
22    _phantom: PhantomData<E>,
23}
24
25impl<E, const CAPACITY: usize> SparseArray<E, CAPACITY>
26where
27    E: ErrorApi,
28{
29    /// initializes a sparse array that holds the values from range [0, len)
30    pub fn new(len: usize) -> Self {
31        if len > CAPACITY {
32            E::error_api_impl().signal_error(b"Length exceeds capacity");
33        }
34
35        SparseArray {
36            array: [0usize; CAPACITY],
37            len,
38            _phantom: PhantomData,
39        }
40    }
41
42    #[inline]
43    pub fn len(&self) -> usize {
44        self.len
45    }
46
47    #[inline]
48    pub fn is_empty(&self) -> bool {
49        self.len == 0
50    }
51
52    /// Returns the underlying array as a slice, without converting 0-values to their actual value
53    #[inline]
54    pub fn as_raw_slice(&self) -> &[usize] {
55        &self.array[..self.len]
56    }
57
58    /// Gets the value at the given `index`.
59    /// If the value is 0, then `index` is returned.
60    pub fn get(&self, index: usize) -> usize {
61        self.require_valid_index(index);
62        self.get_item_unchecked(index)
63    }
64
65    /// Sets the value at the given `index`.
66    /// If the `index` and `value` are equal, then `0` is stored.
67    pub fn set(&mut self, index: usize, value: usize) {
68        self.require_valid_index(index);
69        self.set_item_unchecked(index, value);
70    }
71
72    /// Removes the value at the given index.
73    /// The value at `index` is set to the last item in the array
74    /// and length is decremented
75    pub fn swap_remove(&mut self, index: usize) -> usize {
76        self.require_valid_index(index);
77
78        let last_item_index = self.len - 1;
79        let last_item = self.get_item_unchecked(last_item_index);
80
81        let current_item = if index != last_item_index {
82            let item_at_index = self.get_item_unchecked(index);
83            self.set_item_unchecked(index, last_item);
84
85            item_at_index
86        } else {
87            last_item
88        };
89
90        self.set_item_unchecked(last_item_index, EMPTY_ENTRY);
91        self.len -= 1;
92
93        current_item
94    }
95
96    fn get_item_unchecked(&self, index: usize) -> usize {
97        let value = self.array[index];
98        if value == EMPTY_ENTRY {
99            index
100        } else {
101            value
102        }
103    }
104
105    fn set_item_unchecked(&mut self, index: usize, value: usize) {
106        if index == value {
107            self.array[index] = EMPTY_ENTRY;
108        } else {
109            self.array[index] = value;
110        }
111    }
112
113    fn require_valid_index(&self, index: usize) {
114        if index >= self.len {
115            E::error_api_impl().signal_error(INVALID_INDEX_ERR_MSG);
116        }
117    }
118
119    pub fn iter(&self) -> SparseArrayIterator<'_, E, CAPACITY> {
120        SparseArrayIterator::new(self)
121    }
122}
123
124impl<'a, E, const CAPACITY: usize> IntoIterator for &'a SparseArray<E, CAPACITY>
125where
126    E: ErrorApi,
127{
128    type Item = usize;
129
130    type IntoIter = SparseArrayIterator<'a, E, CAPACITY>;
131
132    fn into_iter(self) -> Self::IntoIter {
133        self.iter()
134    }
135}
136
137pub struct SparseArrayIterator<'a, E, const CAPACITY: usize>
138where
139    E: ErrorApi,
140{
141    array_ref: &'a SparseArray<E, CAPACITY>,
142    current_index: usize,
143    last_index: usize,
144}
145
146impl<'a, E, const CAPACITY: usize> SparseArrayIterator<'a, E, CAPACITY>
147where
148    E: ErrorApi,
149{
150    pub fn new(array: &'a SparseArray<E, CAPACITY>) -> Self {
151        Self {
152            array_ref: array,
153            current_index: 0,
154            last_index: array.len - 1,
155        }
156    }
157}
158
159impl<E, const CAPACITY: usize> Iterator for SparseArrayIterator<'_, E, CAPACITY>
160where
161    E: ErrorApi,
162{
163    type Item = usize;
164
165    fn next(&mut self) -> Option<Self::Item> {
166        let next_index = self.current_index;
167        if next_index > self.last_index {
168            return None;
169        }
170
171        self.current_index += 1;
172
173        Some(self.array_ref.get(next_index))
174    }
175
176    fn size_hint(&self) -> (usize, Option<usize>) {
177        let remaining = self.last_index - self.current_index + 1;
178        (remaining, Some(remaining))
179    }
180}
181
182impl<E, const CAPACITY: usize> ExactSizeIterator for SparseArrayIterator<'_, E, CAPACITY> where
183    E: ErrorApi
184{
185}
186
187impl<E, const CAPACITY: usize> DoubleEndedIterator for SparseArrayIterator<'_, E, CAPACITY>
188where
189    E: ErrorApi,
190{
191    fn next_back(&mut self) -> Option<Self::Item> {
192        let next_index = self.last_index;
193        if next_index < self.current_index {
194            return None;
195        }
196
197        self.last_index -= 1;
198
199        Some(self.array_ref.get(next_index))
200    }
201}
202
203impl<E, const CAPACITY: usize> Clone for SparseArrayIterator<'_, E, CAPACITY>
204where
205    E: ErrorApi,
206{
207    fn clone(&self) -> Self {
208        Self {
209            array_ref: self.array_ref,
210            current_index: self.current_index,
211            last_index: self.last_index,
212        }
213    }
214}
215
216impl<E, const CAPACITY: usize> TopEncode for SparseArray<E, CAPACITY>
217where
218    E: ErrorApi,
219{
220    fn top_encode_or_handle_err<O, H>(&self, output: O, h: H) -> Result<(), H::HandledErr>
221    where
222        O: codec::TopEncodeOutput,
223        H: codec::EncodeErrorHandler,
224    {
225        let mut nested_buffer = output.start_nested_encode();
226        for item in self.iter() {
227            item.dep_encode_or_handle_err(&mut nested_buffer, h)?;
228        }
229        output.finalize_nested_encode(nested_buffer);
230
231        Ok(())
232    }
233}
234
235impl<E, const CAPACITY: usize> NestedEncode for SparseArray<E, CAPACITY>
236where
237    E: ErrorApi,
238{
239    fn dep_encode_or_handle_err<O, H>(&self, dest: &mut O, h: H) -> Result<(), H::HandledErr>
240    where
241        O: codec::NestedEncodeOutput,
242        H: codec::EncodeErrorHandler,
243    {
244        self.len.dep_encode_or_handle_err(dest, h)?;
245        for item in self.iter() {
246            item.dep_encode_or_handle_err(dest, h)?;
247        }
248
249        Ok(())
250    }
251}
252
253impl<E, const CAPACITY: usize> TopDecode for SparseArray<E, CAPACITY>
254where
255    E: ErrorApi,
256{
257    fn top_decode_or_handle_err<I, H>(input: I, h: H) -> Result<Self, H::HandledErr>
258    where
259        I: codec::TopDecodeInput,
260        H: codec::DecodeErrorHandler,
261    {
262        match ArrayVec::<usize, CAPACITY>::top_decode(input) {
263            Ok(array_vec) => {
264                let len = array_vec.len();
265                let mut array = [0usize; CAPACITY];
266                let array_slice = &mut array[..len];
267                array_slice.copy_from_slice(array_vec.as_slice());
268
269                Ok(Self {
270                    array,
271                    len: array_vec.len(),
272                    _phantom: PhantomData,
273                })
274            }
275            Err(e) => Err(h.handle_error(e)),
276        }
277    }
278}
279
280impl<E, const CAPACITY: usize> NestedDecode for SparseArray<E, CAPACITY>
281where
282    E: ErrorApi,
283{
284    fn dep_decode_or_handle_err<I, H>(input: &mut I, h: H) -> Result<Self, H::HandledErr>
285    where
286        I: codec::NestedDecodeInput,
287        H: codec::DecodeErrorHandler,
288    {
289        match ArrayVec::<usize, CAPACITY>::dep_decode(input) {
290            Ok(array_vec) => {
291                let len = array_vec.len();
292                let mut array = [0usize; CAPACITY];
293                let array_slice = &mut array[..len];
294                array_slice.copy_from_slice(array_vec.as_slice());
295
296                Ok(Self {
297                    array,
298                    len: array_vec.len(),
299                    _phantom: PhantomData,
300                })
301            }
302            Err(e) => Err(h.handle_error(e)),
303        }
304    }
305}
306
307impl<E, const CAPACITY: usize> TypeAbiFrom<Self> for SparseArray<E, CAPACITY> where E: ErrorApi {}
308impl<E, const CAPACITY: usize> TypeAbiFrom<&Self> for SparseArray<E, CAPACITY> where E: ErrorApi {}
309
310impl<E, const CAPACITY: usize> TypeAbi for SparseArray<E, CAPACITY>
311where
312    E: ErrorApi,
313{
314    type Unmanaged = Self;
315
316    /// It is semantically equivalent to any list of `usize`.
317    fn type_name() -> TypeName {
318        <&[usize] as TypeAbi>::type_name()
319    }
320
321    fn type_name_rust() -> TypeName {
322        format!("SparseArray<$API, {CAPACITY}usize>")
323    }
324
325    fn provide_type_descriptions<TDC: TypeDescriptionContainer>(accumulator: &mut TDC) {
326        usize::provide_type_descriptions(accumulator);
327    }
328}
multiversx_sc/types/static_buffer/sparse_array.rs

multiversx_sc/types/static_buffer/
sparse_array.rs
