cw_storage_plus/
deque.rs

1use std::{any::type_name, convert::TryInto, marker::PhantomData};
2
3use cosmwasm_std::{
4    from_json, storage_keys::namespace_with_key, to_json_vec, StdError, StdResult, Storage,
5};
6use serde::{de::DeserializeOwned, Serialize};
7
8use crate::namespace::Namespace;
9
10// metadata keys need to have different length than the position type (4 bytes) to prevent collisions
11const TAIL_KEY: &[u8] = b"t";
12const HEAD_KEY: &[u8] = b"h";
13
14/// A deque stores multiple items at the given key. It provides efficient FIFO and LIFO access,
15/// as well as direct index access.
16///
17/// It has a maximum capacity of `u32::MAX - 1`. Make sure to never exceed that number when using this type.
18/// If you do, the methods won't work as intended anymore.
19pub struct Deque<T> {
20    // prefix of the deque items
21    namespace: Namespace,
22    // see https://doc.rust-lang.org/std/marker/struct.PhantomData.html#unused-type-parameters for why this is needed
23    item_type: PhantomData<T>,
24}
25
26impl<T> Deque<T> {
27    /// Creates a new [`Deque`] with the given storage key. This is a constant function only suitable
28    /// when you have a prefix in the form of a static string slice.
29    pub const fn new(prefix: &'static str) -> Self {
30        Self {
31            namespace: Namespace::from_static_str(prefix),
32            item_type: PhantomData,
33        }
34    }
35
36    /// Creates a new [`Deque`] with the given storage key. Use this if you might need to handle
37    /// a dynamic string. Otherwise, you should probably prefer [`Deque::new`].
38    pub fn new_dyn(prefix: impl Into<Namespace>) -> Self {
39        Self {
40            namespace: prefix.into(),
41            item_type: PhantomData,
42        }
43    }
44}
45
46impl<T: Serialize + DeserializeOwned> Deque<T> {
47    /// Adds the given value to the end of the deque
48    pub fn push_back(&self, storage: &mut dyn Storage, value: &T) -> StdResult<()> {
49        // save value
50        let pos = self.tail(storage)?;
51        self.set_unchecked(storage, pos, value)?;
52        // update tail
53        self.set_tail(storage, pos.wrapping_add(1));
54
55        Ok(())
56    }
57
58    /// Adds the given value to the front of the deque
59    pub fn push_front(&self, storage: &mut dyn Storage, value: &T) -> StdResult<()> {
60        // need to subtract first, because head potentially points to existing element
61        let pos = self.head(storage)?.wrapping_sub(1);
62        self.set_unchecked(storage, pos, value)?;
63        // update head
64        self.set_head(storage, pos);
65
66        Ok(())
67    }
68
69    /// Removes the last element of the deque and returns it
70    pub fn pop_back(&self, storage: &mut dyn Storage) -> StdResult<Option<T>> {
71        // get position
72        let pos = self.tail(storage)?.wrapping_sub(1);
73        let value = self.get_unchecked(storage, pos)?;
74        if value.is_some() {
75            self.remove_unchecked(storage, pos);
76            // only update tail if a value was popped
77            self.set_tail(storage, pos);
78        }
79        Ok(value)
80    }
81
82    /// Removes the first element of the deque and returns it
83    pub fn pop_front(&self, storage: &mut dyn Storage) -> StdResult<Option<T>> {
84        // get position
85        let pos = self.head(storage)?;
86        let value = self.get_unchecked(storage, pos)?;
87        if value.is_some() {
88            self.remove_unchecked(storage, pos);
89            // only update head if a value was popped
90            self.set_head(storage, pos.wrapping_add(1));
91        }
92        Ok(value)
93    }
94
95    /// Returns the first element of the deque without removing it
96    pub fn front(&self, storage: &dyn Storage) -> StdResult<Option<T>> {
97        let pos = self.head(storage)?;
98        self.get_unchecked(storage, pos)
99    }
100
101    /// Returns the last element of the deque without removing it
102    pub fn back(&self, storage: &dyn Storage) -> StdResult<Option<T>> {
103        let pos = self.tail(storage)?.wrapping_sub(1);
104        self.get_unchecked(storage, pos)
105    }
106
107    /// Gets the length of the deque.
108    #[allow(clippy::len_without_is_empty)]
109    pub fn len(&self, storage: &dyn Storage) -> StdResult<u32> {
110        Ok(calc_len(self.head(storage)?, self.tail(storage)?))
111    }
112
113    /// Returns `true` if the deque contains no elements.
114    pub fn is_empty(&self, storage: &dyn Storage) -> StdResult<bool> {
115        Ok(self.len(storage)? == 0)
116    }
117
118    /// Gets the head position from storage.
119    ///
120    /// Unless the deque is empty, this points to the first element.
121    #[inline]
122    fn head(&self, storage: &dyn Storage) -> StdResult<u32> {
123        self.read_meta_key(storage, HEAD_KEY)
124    }
125
126    /// Gets the tail position from storage.
127    ///
128    /// This points to the first empty position after the last element.
129    #[inline]
130    fn tail(&self, storage: &dyn Storage) -> StdResult<u32> {
131        self.read_meta_key(storage, TAIL_KEY)
132    }
133
134    #[inline]
135    fn set_head(&self, storage: &mut dyn Storage, value: u32) {
136        self.set_meta_key(storage, HEAD_KEY, value);
137    }
138
139    #[inline]
140    fn set_tail(&self, storage: &mut dyn Storage, value: u32) {
141        self.set_meta_key(storage, TAIL_KEY, value);
142    }
143
144    /// Helper method for `tail` and `head` methods to handle reading the value from storage
145    fn read_meta_key(&self, storage: &dyn Storage, key: &[u8]) -> StdResult<u32> {
146        let full_key = namespace_with_key(&[self.namespace.as_slice()], key);
147        storage
148            .get(&full_key)
149            .map(|vec| {
150                Ok(u32::from_be_bytes(vec.as_slice().try_into().map_err(
151                    |e| StdError::msg(format!("parse error u32: {e}")),
152                )?))
153            })
154            .unwrap_or(Ok(0))
155    }
156
157    /// Helper method for `set_tail` and `set_head` methods to write to storage
158    #[inline]
159    fn set_meta_key(&self, storage: &mut dyn Storage, key: &[u8], value: u32) {
160        let full_key = namespace_with_key(&[self.namespace.as_slice()], key);
161        storage.set(&full_key, &value.to_be_bytes());
162    }
163
164    /// Returns the value at the given position in the queue or `None` if the index is out of bounds
165    pub fn get(&self, storage: &dyn Storage, pos: u32) -> StdResult<Option<T>> {
166        let head = self.head(storage)?;
167        let tail = self.tail(storage)?;
168
169        if pos >= calc_len(head, tail) {
170            // out of bounds
171            return Ok(None);
172        }
173
174        let pos = head.wrapping_add(pos);
175        self.get_unchecked(storage, pos)
176            .and_then(|v| v.ok_or_else(|| StdError::msg(format!("deque position {pos} not found"))))
177            .map(Some)
178    }
179
180    /// Sets the value at the given position in the queue. Returns [`StdError::NotFound`] if index is out of bounds
181    pub fn set(&self, storage: &mut dyn Storage, pos: u32, value: &T) -> StdResult<()> {
182        let head = self.head(storage)?;
183        let tail = self.tail(storage)?;
184
185        if pos >= calc_len(head, tail) {
186            // out of bounds
187            return Err(StdError::msg(format!("deque position {pos} not found")));
188        }
189
190        self.set_unchecked(storage, pos, value)
191    }
192
193    /// Tries to get the value at the given position
194    /// Used internally
195    fn get_unchecked(&self, storage: &dyn Storage, pos: u32) -> StdResult<Option<T>> {
196        let prefixed_key = namespace_with_key(&[self.namespace.as_slice()], &pos.to_be_bytes());
197        let value = storage.get(&prefixed_key);
198        value.map(|v| from_json(v)).transpose()
199    }
200
201    /// Removes the value at the given position
202    /// Used internally
203    fn remove_unchecked(&self, storage: &mut dyn Storage, pos: u32) {
204        let prefixed_key = namespace_with_key(&[self.namespace.as_slice()], &pos.to_be_bytes());
205        storage.remove(&prefixed_key);
206    }
207
208    /// Tries to set the value at the given position
209    /// Used internally when pushing
210    fn set_unchecked(&self, storage: &mut dyn Storage, pos: u32, value: &T) -> StdResult<()> {
211        let prefixed_key = namespace_with_key(&[self.namespace.as_slice()], &pos.to_be_bytes());
212        storage.set(&prefixed_key, &to_json_vec(value)?);
213
214        Ok(())
215    }
216}
217
218// used internally to avoid additional storage loads
219#[inline]
220fn calc_len(head: u32, tail: u32) -> u32 {
221    tail.wrapping_sub(head)
222}
223
224impl<T: Serialize + DeserializeOwned> Deque<T> {
225    pub fn iter<'a>(&'a self, storage: &'a dyn Storage) -> StdResult<DequeIter<'a, T>> {
226        Ok(DequeIter {
227            deque: self,
228            storage,
229            start: self.head(storage)?,
230            end: self.tail(storage)?,
231        })
232    }
233}
234
235pub struct DequeIter<'a, T>
236where
237    T: Serialize + DeserializeOwned,
238{
239    deque: &'a Deque<T>,
240    storage: &'a dyn Storage,
241    start: u32,
242    end: u32,
243}
244
245impl<T> Iterator for DequeIter<'_, T>
246where
247    T: Serialize + DeserializeOwned,
248{
249    type Item = StdResult<T>;
250
251    fn next(&mut self) -> Option<Self::Item> {
252        if self.start == self.end {
253            return None;
254        }
255
256        let item = self
257            .deque
258            .get_unchecked(self.storage, self.start)
259            .and_then(|item| item.ok_or_else(|| StdError::msg(type_name::<T>())));
260        self.start = self.start.wrapping_add(1);
261
262        Some(item)
263    }
264
265    fn size_hint(&self) -> (usize, Option<usize>) {
266        let len = calc_len(self.start, self.end) as usize;
267        (len, Some(len))
268    }
269
270    // The default implementation calls `next` repeatedly, which is very costly in our case.
271    // It is used when skipping over items, so this allows cheap skipping.
272    //
273    // Once `advance_by` is stabilized, we can implement that instead (`nth` calls it internally).
274    fn nth(&mut self, n: usize) -> Option<Self::Item> {
275        // make sure that we don't skip past the end
276        if calc_len(self.start, self.end) < n as u32 {
277            // mark as empty
278            self.start = self.end;
279        } else {
280            self.start = self.start.wrapping_add(n as u32);
281        }
282        self.next()
283    }
284}
285
286impl<T> DoubleEndedIterator for DequeIter<'_, T>
287where
288    T: Serialize + DeserializeOwned,
289{
290    fn next_back(&mut self) -> Option<Self::Item> {
291        if self.start == self.end {
292            return None;
293        }
294
295        let item = self
296            .deque
297            .get_unchecked(self.storage, self.end.wrapping_sub(1)) // end points to position after last element
298            .and_then(|item| item.ok_or_else(|| StdError::msg(type_name::<T>())));
299        self.end = self.end.wrapping_sub(1);
300
301        Some(item)
302    }
303
304    // see [`DequeIter::nth`]
305    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
306        // make sure that we don't skip past the start
307        if calc_len(self.start, self.end) < n as u32 {
308            // mark as empty
309            self.end = self.start;
310        } else {
311            self.end = self.end.wrapping_sub(n as u32);
312        }
313        self.next_back()
314    }
315}
316#[cfg(test)]
317mod tests {
318    use crate::deque::Deque;
319
320    use cosmwasm_std::testing::MockStorage;
321    use cosmwasm_std::StdResult;
322    use serde::{Deserialize, Serialize};
323
324    #[test]
325    fn owned_key() {
326        let mut store = MockStorage::new();
327
328        for i in 1..4 {
329            let key = format!("key{i}");
330            let item = Deque::new_dyn(key);
331            for i in 0..i {
332                item.push_back(&mut store, &i).unwrap();
333            }
334        }
335
336        assert_eq!(
337            Deque::<u32>::new("key1")
338                .iter(&store)
339                .unwrap()
340                .collect::<Result<Vec<_>, _>>()
341                .unwrap(),
342            vec![0]
343        );
344        assert_eq!(
345            Deque::<u32>::new("key2")
346                .iter(&store)
347                .unwrap()
348                .collect::<Result<Vec<_>, _>>()
349                .unwrap(),
350            vec![0, 1]
351        );
352        assert_eq!(
353            Deque::<u32>::new("key3")
354                .iter(&store)
355                .unwrap()
356                .collect::<Result<Vec<_>, _>>()
357                .unwrap(),
358            vec![0, 1, 2]
359        );
360    }
361
362    #[test]
363    fn push_and_pop() {
364        const PEOPLE: Deque<String> = Deque::new("people");
365        let mut store = MockStorage::new();
366
367        // push some entries
368        PEOPLE.push_back(&mut store, &"jack".to_owned()).unwrap();
369        PEOPLE.push_back(&mut store, &"john".to_owned()).unwrap();
370        PEOPLE.push_back(&mut store, &"joanne".to_owned()).unwrap();
371
372        // pop them, should be in correct order
373        assert_eq!("jack", PEOPLE.pop_front(&mut store).unwrap().unwrap());
374        assert_eq!("john", PEOPLE.pop_front(&mut store).unwrap().unwrap());
375
376        // push again in-between
377        PEOPLE.push_back(&mut store, &"jason".to_owned()).unwrap();
378
379        // pop last person from first batch
380        assert_eq!("joanne", PEOPLE.pop_front(&mut store).unwrap().unwrap());
381
382        // pop the entry pushed in-between
383        assert_eq!("jason", PEOPLE.pop_front(&mut store).unwrap().unwrap());
384
385        // nothing after that
386        assert_eq!(None, PEOPLE.pop_front(&mut store).unwrap());
387
388        // now push to the front
389        PEOPLE.push_front(&mut store, &"pascal".to_owned()).unwrap();
390        PEOPLE.push_front(&mut store, &"peter".to_owned()).unwrap();
391        PEOPLE.push_front(&mut store, &"paul".to_owned()).unwrap();
392
393        assert_eq!("pascal", PEOPLE.pop_back(&mut store).unwrap().unwrap());
394        assert_eq!("paul", PEOPLE.pop_front(&mut store).unwrap().unwrap());
395        assert_eq!("peter", PEOPLE.pop_back(&mut store).unwrap().unwrap());
396    }
397
398    #[test]
399    fn length() {
400        let deque: Deque<u32> = Deque::new("test");
401        let mut store = MockStorage::new();
402
403        assert_eq!(deque.len(&store).unwrap(), 0);
404        assert!(deque.is_empty(&store).unwrap());
405
406        // push some entries
407        deque.push_front(&mut store, &1234).unwrap();
408        deque.push_back(&mut store, &2345).unwrap();
409        deque.push_front(&mut store, &3456).unwrap();
410        deque.push_back(&mut store, &4567).unwrap();
411        assert_eq!(deque.len(&store).unwrap(), 4);
412        assert!(!deque.is_empty(&store).unwrap());
413
414        // pop some
415        deque.pop_front(&mut store).unwrap();
416        deque.pop_back(&mut store).unwrap();
417        deque.pop_front(&mut store).unwrap();
418        assert_eq!(deque.len(&store).unwrap(), 1);
419        assert!(!deque.is_empty(&store).unwrap());
420
421        // pop the last one
422        deque.pop_front(&mut store).unwrap();
423        assert_eq!(deque.len(&store).unwrap(), 0);
424        assert!(deque.is_empty(&store).unwrap());
425
426        // should stay 0 after that
427        assert_eq!(deque.pop_back(&mut store).unwrap(), None);
428        assert_eq!(
429            deque.len(&store).unwrap(),
430            0,
431            "popping from empty deque should keep length 0"
432        );
433        assert!(deque.is_empty(&store).unwrap());
434    }
435
436    #[test]
437    fn iterator() {
438        let deque: Deque<u32> = Deque::new("test");
439        let mut store = MockStorage::new();
440
441        // push some items
442        deque.push_back(&mut store, &1).unwrap();
443        deque.push_back(&mut store, &2).unwrap();
444        deque.push_back(&mut store, &3).unwrap();
445        deque.push_back(&mut store, &4).unwrap();
446
447        let items: StdResult<Vec<_>> = deque.iter(&store).unwrap().collect();
448        assert_eq!(items.unwrap(), [1, 2, 3, 4]);
449
450        // nth should work correctly
451        let mut iter = deque.iter(&store).unwrap();
452        assert!(iter.nth(6).is_none());
453        assert_eq!(iter.start, iter.end, "iter should detect skipping too far");
454        assert!(iter.next().is_none());
455
456        let mut iter = deque.iter(&store).unwrap();
457        assert_eq!(iter.nth(1).unwrap().unwrap(), 2);
458        assert_eq!(iter.next().unwrap().unwrap(), 3);
459    }
460
461    #[test]
462    fn reverse_iterator() {
463        let deque: Deque<u32> = Deque::new("test");
464        let mut store = MockStorage::new();
465
466        // push some items
467        deque.push_back(&mut store, &1).unwrap();
468        deque.push_back(&mut store, &2).unwrap();
469        deque.push_back(&mut store, &3).unwrap();
470        deque.push_back(&mut store, &4).unwrap();
471
472        let items: StdResult<Vec<_>> = deque.iter(&store).unwrap().rev().collect();
473        assert_eq!(items.unwrap(), [4, 3, 2, 1]);
474
475        // nth should work correctly
476        let mut iter = deque.iter(&store).unwrap();
477        assert!(iter.nth_back(6).is_none());
478        assert_eq!(iter.start, iter.end, "iter should detect skipping too far");
479        assert!(iter.next_back().is_none());
480
481        let mut iter = deque.iter(&store).unwrap().rev();
482        assert_eq!(iter.nth(1).unwrap().unwrap(), 3);
483        assert_eq!(iter.next().unwrap().unwrap(), 2);
484
485        // mixed
486        let mut iter = deque.iter(&store).unwrap();
487        assert_eq!(iter.next().unwrap().unwrap(), 1);
488        assert_eq!(iter.next_back().unwrap().unwrap(), 4);
489        assert_eq!(iter.next_back().unwrap().unwrap(), 3);
490        assert_eq!(iter.next().unwrap().unwrap(), 2);
491        assert!(iter.next().is_none());
492        assert!(iter.next_back().is_none());
493    }
494
495    #[test]
496    fn wrapping() {
497        let deque: Deque<u32> = Deque::new("test");
498        let mut store = MockStorage::new();
499
500        // simulate deque that was pushed and popped `u32::MAX` times
501        deque.set_head(&mut store, u32::MAX);
502        deque.set_tail(&mut store, u32::MAX);
503
504        // should be empty
505        assert_eq!(deque.pop_front(&mut store).unwrap(), None);
506        assert_eq!(deque.len(&store).unwrap(), 0);
507
508        // pushing should still work
509        deque.push_back(&mut store, &1).unwrap();
510        assert_eq!(
511            deque.len(&store).unwrap(),
512            1,
513            "length should calculate correctly, even when wrapping"
514        );
515        assert_eq!(
516            deque.pop_front(&mut store).unwrap(),
517            Some(1),
518            "popping should work, even when wrapping"
519        );
520    }
521
522    #[test]
523    fn wrapping_iterator() {
524        let deque: Deque<u32> = Deque::new("test");
525        let mut store = MockStorage::new();
526
527        deque.set_head(&mut store, u32::MAX);
528        deque.set_tail(&mut store, u32::MAX);
529
530        deque.push_back(&mut store, &1).unwrap();
531        deque.push_back(&mut store, &2).unwrap();
532        deque.push_back(&mut store, &3).unwrap();
533        deque.push_back(&mut store, &4).unwrap();
534        deque.push_back(&mut store, &5).unwrap();
535
536        let mut iter = deque.iter(&store).unwrap();
537        assert_eq!(iter.next().unwrap().unwrap(), 1);
538        assert_eq!(iter.next().unwrap().unwrap(), 2);
539        assert_eq!(iter.next_back().unwrap().unwrap(), 5);
540        assert_eq!(iter.nth(1).unwrap().unwrap(), 4);
541        assert!(iter.nth(1).is_none());
542        assert_eq!(iter.start, iter.end);
543    }
544
545    #[test]
546    fn front_back() {
547        let deque: Deque<u64> = Deque::new("test");
548        let mut store = MockStorage::new();
549
550        assert_eq!(deque.back(&store).unwrap(), None);
551        deque.push_back(&mut store, &1).unwrap();
552        assert_eq!(deque.back(&store).unwrap(), Some(1));
553        assert_eq!(deque.front(&store).unwrap(), Some(1));
554        deque.push_back(&mut store, &2).unwrap();
555        assert_eq!(deque.back(&store).unwrap(), Some(2));
556        assert_eq!(deque.front(&store).unwrap(), Some(1));
557        deque.push_front(&mut store, &3).unwrap();
558        assert_eq!(deque.back(&store).unwrap(), Some(2));
559        assert_eq!(deque.front(&store).unwrap(), Some(3));
560    }
561
562    #[derive(Serialize, Deserialize, PartialEq, Debug, Clone)]
563    struct Data {
564        pub name: String,
565        pub age: i32,
566    }
567
568    const DATA: Deque<Data> = Deque::new("data");
569
570    #[test]
571    fn readme_works() -> StdResult<()> {
572        let mut store = MockStorage::new();
573
574        // read methods return a wrapped Option<T>, so None if the deque is empty
575        let empty = DATA.front(&store)?;
576        assert_eq!(None, empty);
577
578        // some example entries
579        let p1 = Data {
580            name: "admin".to_string(),
581            age: 1234,
582        };
583        let p2 = Data {
584            name: "user".to_string(),
585            age: 123,
586        };
587
588        // use it like a queue by pushing and popping at opposite ends
589        DATA.push_back(&mut store, &p1)?;
590        DATA.push_back(&mut store, &p2)?;
591
592        let admin = DATA.pop_front(&mut store)?;
593        assert_eq!(admin.as_ref(), Some(&p1));
594        let user = DATA.pop_front(&mut store)?;
595        assert_eq!(user.as_ref(), Some(&p2));
596
597        // or push and pop at the same end to use it as a stack
598        DATA.push_back(&mut store, &p1)?;
599        DATA.push_back(&mut store, &p2)?;
600
601        let user = DATA.pop_back(&mut store)?;
602        assert_eq!(user.as_ref(), Some(&p2));
603        let admin = DATA.pop_back(&mut store)?;
604        assert_eq!(admin.as_ref(), Some(&p1));
605
606        // you can also iterate over it
607        DATA.push_front(&mut store, &p1)?;
608        DATA.push_front(&mut store, &p2)?;
609
610        let all: StdResult<Vec<_>> = DATA.iter(&store)?.collect();
611        assert_eq!(all?, [p2.clone(), p1.clone()]);
612
613        // or access an index directly
614        assert_eq!(DATA.get(&store, 0)?, Some(p2));
615        assert_eq!(DATA.get(&store, 1)?, Some(p1));
616        assert_eq!(DATA.get(&store, 3)?, None);
617
618        Ok(())
619    }
620
621    #[test]
622    fn iterator_errors_when_item_missing() {
623        let mut store = MockStorage::new();
624
625        let deque = Deque::new("error_test");
626
627        deque.push_back(&mut store, &1u32).unwrap();
628        // manually remove it
629        deque.remove_unchecked(&mut store, 0);
630
631        let mut iter = deque.iter(&store).unwrap();
632
633        assert_eq!(
634            "kind: Other, error: u32",
635            iter.next().unwrap().unwrap_err().to_string(),
636            "iterator should error when item is missing"
637        );
638
639        let mut iter = deque.iter(&store).unwrap().rev();
640
641        assert_eq!(
642            "kind: Other, error: u32",
643            iter.next().unwrap().unwrap_err().to_string(),
644            "reverse iterator should error when item is missing"
645        );
646    }
647
648    #[test]
649    fn get() {
650        let mut store = MockStorage::new();
651
652        let deque = Deque::new("test");
653
654        deque.push_back(&mut store, &1u32).unwrap();
655        deque.push_back(&mut store, &2).unwrap();
656
657        assert_eq!(deque.get(&store, 0).unwrap(), Some(1));
658        assert_eq!(deque.get(&store, 1).unwrap(), Some(2));
659        assert_eq!(
660            deque.get(&store, 2).unwrap(),
661            None,
662            "out of bounds access should return None"
663        );
664
665        // manually remove storage item
666        deque.remove_unchecked(&mut store, 1);
667
668        assert_eq!(
669            "kind: Other, error: deque position 1 not found",
670            deque.get(&store, 1).unwrap_err().to_string(),
671            "missing deque item should error"
672        );
673
674        // start fresh
675        let deque = Deque::new("test2");
676
677        deque.push_back(&mut store, &0u32).unwrap();
678        deque.push_back(&mut store, &1).unwrap();
679        // push to front to move the head index
680        deque.push_front(&mut store, &u32::MAX).unwrap();
681        deque.push_front(&mut store, &(u32::MAX - 1)).unwrap();
682
683        assert_eq!(deque.get(&store, 0).unwrap().unwrap(), u32::MAX - 1);
684        assert_eq!(deque.get(&store, 1).unwrap().unwrap(), u32::MAX);
685        assert_eq!(deque.get(&store, 2).unwrap().unwrap(), 0);
686        assert_eq!(deque.get(&store, 3).unwrap().unwrap(), 1);
687        assert_eq!(
688            deque.get(&store, 5).unwrap(),
689            None,
690            "out of bounds access should return None"
691        );
692    }
693
694    #[test]
695    fn set() {
696        let mut store = MockStorage::new();
697        let deque = Deque::new("test");
698
699        deque.push_back(&mut store, &1u32).unwrap();
700        deque.push_back(&mut store, &2).unwrap();
701
702        deque.set(&mut store, 1, &3).unwrap();
703
704        assert_eq!(deque.get(&store, 1).unwrap(), Some(3));
705        assert_eq!(deque.back(&store).unwrap(), Some(3));
706        assert_eq!(
707            deque.get(&store, 2).unwrap(),
708            None,
709            "out of bounds access should return None"
710        );
711
712        assert_eq!(
713            "kind: Other, error: deque position 2 not found",
714            deque.set(&mut store, 2, &3).unwrap_err().to_string(),
715            "setting value at an out of bounds index should error"
716        );
717
718        assert_eq!(deque.pop_back(&mut store).unwrap(), Some(3));
719
720        assert_eq!(
721            "kind: Other, error: deque position 1 not found",
722            deque.set(&mut store, 1, &3).unwrap_err().to_string(),
723            "setting value at an out of bounds index should error"
724        );
725    }
726}
cw_storage_plus/deque.rs

cw_storage_plus/
deque.rs
