everscale_types/dict/
typed.rs

1use std::borrow::Borrow;
2use std::collections::BTreeMap;
3use std::marker::PhantomData;
4
5use crate::cell::*;
6use crate::dict::dict_remove_owned;
7use crate::error::Error;
8use crate::util::*;
9
10use super::{
11    build_dict_from_sorted_iter, dict_find_bound, dict_find_owned, dict_get, dict_get_owned,
12    dict_insert, dict_load_from_root, dict_split_by_prefix, DictBound, DictKey, SetMode,
13};
14use super::{dict_remove_bound_owned, raw::*};
15
16/// Typed dictionary with fixed length keys.
17#[repr(transparent)]
18pub struct Dict<K, V> {
19    pub(crate) root: Option<Cell>,
20    _key: PhantomData<K>,
21    _value: PhantomData<V>,
22}
23
24impl<K, V> ExactSize for Dict<K, V> {
25    #[inline]
26    fn exact_size(&self) -> Size {
27        Size {
28            bits: 1,
29            refs: self.root.is_some() as u8,
30        }
31    }
32}
33
34impl<'a, K, V> Load<'a> for Dict<K, V> {
35    #[inline]
36    fn load_from(slice: &mut CellSlice<'a>) -> Result<Self, Error> {
37        Ok(Self {
38            root: ok!(<_>::load_from(slice)),
39            _key: PhantomData,
40            _value: PhantomData,
41        })
42    }
43}
44
45impl<K, V> Store for Dict<K, V> {
46    #[inline]
47    fn store_into(
48        &self,
49        builder: &mut CellBuilder,
50        context: &mut dyn CellContext,
51    ) -> Result<(), Error> {
52        self.root.store_into(builder, context)
53    }
54}
55
56impl<K, V> Default for Dict<K, V> {
57    #[inline]
58    fn default() -> Self {
59        Self::new()
60    }
61}
62
63impl<K, V> Clone for Dict<K, V> {
64    fn clone(&self) -> Self {
65        Self {
66            root: self.root.clone(),
67            _key: PhantomData,
68            _value: PhantomData,
69        }
70    }
71}
72
73impl<K, V> Eq for Dict<K, V> {}
74
75impl<K, V> PartialEq for Dict<K, V> {
76    fn eq(&self, other: &Self) -> bool {
77        match (&self.root, &other.root) {
78            (Some(this), Some(other)) => this.eq(other),
79            (None, None) => true,
80            _ => false,
81        }
82    }
83}
84
85impl<K, V> From<Option<Cell>> for Dict<K, V> {
86    #[inline]
87    fn from(dict: Option<Cell>) -> Self {
88        Self::from_raw(dict)
89    }
90}
91
92impl<K, V> std::fmt::Debug for Dict<K, V> {
93    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
94        debug_struct_field1_finish(f, "Dict", "root", &self.root)
95    }
96}
97
98impl<K, V> Dict<K, V> {
99    /// Creates an empty dictionary
100    pub const fn new() -> Self {
101        Self {
102            root: None,
103            _key: PhantomData,
104            _value: PhantomData,
105        }
106    }
107
108    /// Creates a dictionary from a raw cell.
109    pub const fn from_raw(dict: Option<Cell>) -> Self {
110        Self {
111            root: dict,
112            _key: PhantomData,
113            _value: PhantomData,
114        }
115    }
116
117    /// Returns `true` if the dictionary contains no elements.
118    pub const fn is_empty(&self) -> bool {
119        self.root.is_none()
120    }
121
122    /// Returns the underlying root cell of the dictionary.
123    #[inline]
124    pub const fn root(&self) -> &Option<Cell> {
125        &self.root
126    }
127
128    /// Returns the underlying root cell of the dictionary.
129    #[inline]
130    pub fn into_root(self) -> Option<Cell> {
131        self.root
132    }
133
134    /// Converts into a dictionary with an equivalent value type.
135    #[inline]
136    pub fn cast_into<Q, T>(self) -> Dict<Q, T>
137    where
138        Q: EquivalentRepr<K>,
139        T: EquivalentRepr<V>,
140    {
141        Dict {
142            root: self.root,
143            _key: PhantomData,
144            _value: PhantomData,
145        }
146    }
147
148    /// Casts itself into a lazy loaded for an equivalent type.
149    pub fn cast_ref<Q, T>(&self) -> &Dict<Q, T>
150    where
151        Q: EquivalentRepr<K>,
152        T: EquivalentRepr<V>,
153    {
154        // SAFETY: Dict is #[repr(transparent)]
155        unsafe { &*(self as *const Self as *const Dict<Q, T>) }
156    }
157}
158
159impl<K: DictKey, V> Dict<K, V> {
160    /// Loads a non-empty dictionary from a root cell.
161    #[inline]
162    pub fn load_from_root_ext(
163        slice: &mut CellSlice<'_>,
164        context: &mut dyn CellContext,
165    ) -> Result<Self, Error> {
166        match dict_load_from_root(slice, K::BITS, context) {
167            Ok(root) => Ok(Self {
168                root: Some(root),
169                _key: PhantomData,
170                _value: PhantomData,
171            }),
172            Err(e) => Err(e),
173        }
174    }
175}
176
177impl<K, V> Dict<K, V>
178where
179    K: Store + DictKey,
180{
181    /// Returns `true` if the dictionary contains a value for the specified key.
182    #[inline]
183    pub fn contains_key<Q>(&self, key: Q) -> Result<bool, Error>
184    where
185        Q: Borrow<K>,
186    {
187        fn contains_key_impl<K>(root: &Option<Cell>, key: &K) -> Result<bool, Error>
188        where
189            K: Store + DictKey,
190        {
191            let mut builder = CellBuilder::new();
192            ok!(key.store_into(&mut builder, &mut Cell::empty_context()));
193            Ok(ok!(dict_get(
194                root.as_ref(),
195                K::BITS,
196                builder.as_data_slice(),
197                &mut Cell::empty_context()
198            ))
199            .is_some())
200        }
201        contains_key_impl(&self.root, key.borrow())
202    }
203}
204
205impl<K, V> Dict<K, V>
206where
207    K: Store + DictKey,
208{
209    /// Returns the value corresponding to the key.
210    #[inline]
211    pub fn get<'a: 'b, 'b, Q>(&'a self, key: Q) -> Result<Option<V>, Error>
212    where
213        Q: Borrow<K> + 'b,
214        V: Load<'a>,
215    {
216        pub fn get_impl<'a: 'b, 'b, K, V>(
217            root: &'a Option<Cell>,
218            key: &'b K,
219        ) -> Result<Option<V>, Error>
220        where
221            K: Store + DictKey,
222            V: Load<'a>,
223        {
224            let Some(mut value) = ({
225                let mut builder = CellBuilder::new();
226                ok!(key.store_into(&mut builder, &mut Cell::empty_context()));
227                ok!(dict_get(
228                    root.as_ref(),
229                    K::BITS,
230                    builder.as_data_slice(),
231                    &mut Cell::empty_context()
232                ))
233            }) else {
234                return Ok(None);
235            };
236
237            match V::load_from(&mut value) {
238                Ok(value) => Ok(Some(value)),
239                Err(e) => Err(e),
240            }
241        }
242
243        get_impl(&self.root, key.borrow())
244    }
245
246    /// Returns the raw value corresponding to the key.
247    #[inline]
248    pub fn get_raw<'a: 'b, 'b, Q>(&'a self, key: Q) -> Result<Option<CellSlice<'a>>, Error>
249    where
250        Q: Borrow<K> + 'b,
251    {
252        pub fn get_raw_impl<'a: 'b, 'b, K>(
253            root: &'a Option<Cell>,
254            key: &'b K,
255        ) -> Result<Option<CellSlice<'a>>, Error>
256        where
257            K: Store + DictKey,
258        {
259            let mut builder = CellBuilder::new();
260            ok!(key.store_into(&mut builder, &mut Cell::empty_context()));
261            dict_get(
262                root.as_ref(),
263                K::BITS,
264                builder.as_data_slice(),
265                &mut Cell::empty_context(),
266            )
267        }
268
269        get_raw_impl(&self.root, key.borrow())
270    }
271
272    /// Returns cell slice parts of the value corresponding to the key.
273    ///
274    /// NOTE: Uses the default cell context.
275    #[inline]
276    pub fn get_raw_owned<Q>(&self, key: Q) -> Result<Option<CellSliceParts>, Error>
277    where
278        Q: Borrow<K>,
279    {
280        pub fn get_raw_impl<K>(
281            root: &Option<Cell>,
282            key: &K,
283        ) -> Result<Option<CellSliceParts>, Error>
284        where
285            K: Store + DictKey,
286        {
287            let mut builder = CellBuilder::new();
288            ok!(key.store_into(&mut builder, &mut Cell::empty_context()));
289            dict_get_owned(
290                root.as_ref(),
291                K::BITS,
292                builder.as_data_slice(),
293                &mut Cell::empty_context(),
294            )
295        }
296
297        get_raw_impl(&self.root, key.borrow())
298    }
299
300    /// Removes the value associated with key in dictionary.
301    /// Returns an optional removed value.
302    ///
303    /// The dict is rebuilt using an empty cell context.
304    pub fn remove<Q>(&mut self, key: Q) -> Result<Option<V>, Error>
305    where
306        Q: Borrow<K>,
307        for<'a> V: Load<'a> + 'static,
308    {
309        match ok!(self.remove_raw_ext(key, &mut Cell::empty_context())) {
310            Some((cell, range)) => {
311                let mut slice = ok!(range.apply(&cell));
312                Ok(Some(ok!(V::load_from(&mut slice))))
313            }
314            None => Ok(None),
315        }
316    }
317
318    /// Removes the value associated with key in dictionary.
319    /// Returns an optional removed value as cell slice parts.
320    ///
321    /// The dict is rebuilt using an empty cell context.
322    pub fn remove_raw<Q>(&mut self, key: Q) -> Result<Option<CellSliceParts>, Error>
323    where
324        Q: Borrow<K>,
325    {
326        self.remove_raw_ext(key, &mut Cell::empty_context())
327    }
328
329    /// Removes the lowest key from the dict.
330    /// Returns an optional removed key and value as cell slice parts.
331    ///
332    /// Use [`remove_bound_ext`] if you need to use a custom cell context.
333    ///
334    /// [`remove_bound_ext`]: RawDict::remove_bound_ext
335    pub fn remove_min_raw(&mut self, signed: bool) -> Result<Option<(K, CellSliceParts)>, Error> {
336        self.remove_bound_raw_ext(DictBound::Min, signed, &mut Cell::empty_context())
337    }
338
339    /// Removes the largest key from the dict.
340    /// Returns an optional removed key and value as cell slice parts.
341    ///
342    /// Use [`remove_bound_ext`] if you need to use a custom cell context.
343    ///
344    /// [`remove_bound_ext`]: RawDict::remove_bound_ext
345    pub fn remove_max_raw(&mut self, signed: bool) -> Result<Option<(K, CellSliceParts)>, Error> {
346        self.remove_bound_raw_ext(DictBound::Max, signed, &mut Cell::empty_context())
347    }
348
349    /// Removes the specified dict bound.
350    /// Returns an optional removed key and value as cell slice parts.
351    ///
352    /// Use [`remove_bound_ext`] if you need to use a custom cell context.
353    ///
354    /// [`remove_bound_ext`]: RawDict::remove_bound_ext
355    pub fn remove_bound_raw(
356        &mut self,
357        bound: DictBound,
358        signed: bool,
359    ) -> Result<Option<(K, CellSliceParts)>, Error> {
360        self.remove_bound_raw_ext(bound, signed, &mut Cell::empty_context())
361    }
362
363    /// Split dictionary into 2 dictionaries by the first key bit.
364    pub fn split(&self) -> Result<(Self, Self), Error> {
365        self.split_by_prefix_ext(&Default::default(), &mut Cell::empty_context())
366    }
367
368    /// Split dictionary into 2 dictionaries by the first key bit.
369    pub fn split_ext(&self, context: &mut dyn CellContext) -> Result<(Self, Self), Error> {
370        self.split_by_prefix_ext(&Default::default(), context)
371    }
372
373    /// Split dictionary into 2 dictionaries at the prefix.
374    pub fn split_by_prefix(&self, key_prefix: &CellSlice<'_>) -> Result<(Self, Self), Error> {
375        self.split_by_prefix_ext(key_prefix, &mut Cell::empty_context())
376    }
377
378    /// Split dictionary into 2 dictionaries at the prefix.
379    pub fn split_by_prefix_ext(
380        &self,
381        key_prefix: &CellSlice<'_>,
382        context: &mut dyn CellContext,
383    ) -> Result<(Self, Self), Error> {
384        let (left, right) = ok!(dict_split_by_prefix(
385            self.root.as_ref(),
386            K::BITS,
387            key_prefix,
388            context
389        ));
390        Ok((Self::from_raw(left), Self::from_raw(right)))
391    }
392}
393
394impl<K, V> Dict<K, V>
395where
396    K: Store + DictKey,
397    V: Store,
398{
399    /// Builds a dictionary from a sorted collection.
400    pub fn try_from_btree<Q, T>(sorted: &BTreeMap<Q, T>) -> Result<Self, Error>
401    where
402        Q: Borrow<K>,
403        T: Borrow<V>,
404        K: Ord,
405    {
406        let root = ok!(build_dict_from_sorted_iter(
407            sorted.iter().map(|(k, v)| (k.borrow(), v.borrow())),
408            K::BITS,
409            &mut Cell::empty_context()
410        ));
411        Ok(Self {
412            root,
413            _key: PhantomData,
414            _value: PhantomData,
415        })
416    }
417
418    /// Builds a dictionary from a sorted slice.
419    pub fn try_from_sorted_slice<Q, T>(sorted: &[(Q, T)]) -> Result<Self, Error>
420    where
421        Q: Borrow<K>,
422        T: Borrow<V>,
423        K: Ord,
424    {
425        let root = ok!(build_dict_from_sorted_iter(
426            sorted.iter().map(|(k, v)| (k.borrow(), v.borrow())),
427            K::BITS,
428            &mut Cell::empty_context()
429        ));
430        Ok(Self {
431            root,
432            _key: PhantomData,
433            _value: PhantomData,
434        })
435    }
436
437    /// Sets the value associated with the key in the dictionary.
438    ///
439    /// Use [`set_ext`] if you need to use a custom cell context.
440    ///
441    /// [`set_ext`]: Dict::set_ext
442    pub fn set<Q, T>(&mut self, key: Q, value: T) -> Result<bool, Error>
443    where
444        Q: Borrow<K>,
445        T: Borrow<V>,
446    {
447        self.set_ext(key, value, &mut Cell::empty_context())
448    }
449
450    /// Sets the value associated with the key in the dictionary
451    /// only if the key was already present in it.
452    ///
453    /// Use [`replace_ext`] if you need to use a custom cell context.
454    ///
455    /// [`replace_ext`]: Dict::replace_ext
456    pub fn replace<Q, T>(&mut self, key: Q, value: T) -> Result<bool, Error>
457    where
458        Q: Borrow<K>,
459        T: Borrow<V>,
460    {
461        self.replace_ext(key, value, &mut Cell::empty_context())
462    }
463
464    /// Sets the value associated with key in dictionary,
465    /// but only if it is not already present.
466    ///
467    /// Use [`add_ext`] if you need to use a custom cell context.
468    ///
469    /// [`add_ext`]: Dict::add_ext
470    pub fn add<Q, T>(&mut self, key: Q, value: T) -> Result<bool, Error>
471    where
472        Q: Borrow<K>,
473        T: Borrow<V>,
474    {
475        self.add_ext(key, value, &mut Cell::empty_context())
476    }
477}
478
479impl<K, V> Dict<K, V>
480where
481    K: Store + DictKey,
482{
483    /// Gets an iterator over the entries of the dictionary, sorted by key.
484    /// The iterator element type is `Result<(K, V)>`.
485    ///
486    /// If the dictionary is invalid, finishes after the first invalid element,
487    /// returning an error.
488    ///
489    /// # Performance
490    ///
491    /// In the current implementation, iterating over dictionary builds a key
492    /// for each element. Use [`values`] or [`raw_values`] if you don't need keys from an iterator.
493    ///
494    /// [`values`]: Dict::values
495    /// [`raw_values`]: Dict::raw_values
496    pub fn iter<'a>(&'a self) -> Iter<'a, K, V>
497    where
498        V: Load<'a>,
499    {
500        Iter::new(&self.root)
501    }
502
503    /// Gets an iterator over the entries of two dictionaries, sorted by key.
504    /// The iterator element type is `Result<(K, Option<V>, Option<V>)>`.
505    ///
506    /// If the dictionary is invalid, finishes after the first invalid element,
507    /// returning an error.
508    ///
509    /// # Performance
510    ///
511    /// In the current implementation, iterating over dictionary builds a key
512    /// for each element.
513    pub fn iter_union<'a>(&'a self, other: &'a Self) -> UnionIter<'a, K, V>
514    where
515        V: Load<'a>,
516    {
517        UnionIter::new(&self.root, &other.root)
518    }
519
520    /// Gets an iterator over the keys of the dictionary, in sorted order.
521    /// The iterator element type is `Result<K>`.
522    ///
523    /// If the dictionary is invalid, finishes after the first invalid element,
524    /// returning an error.
525    ///
526    /// # Performance
527    ///
528    /// In the current implementation, iterating over dictionary builds a key
529    /// for each element. Use [`values`] if you don't need keys from an iterator.
530    ///
531    /// [`values`]: Dict::values
532    pub fn keys(&'_ self) -> Keys<'_, K> {
533        Keys::new(&self.root)
534    }
535
536    /// Computes the minimal key in dictionary that is lexicographically greater than `key`,
537    /// and returns it along with associated value as cell slice parts.
538    #[inline]
539    pub fn get_next<Q>(&self, key: Q, signed: bool) -> Result<Option<(K, V)>, Error>
540    where
541        Q: Borrow<K>,
542        for<'a> V: Load<'a>,
543    {
544        self.find_ext(key, DictBound::Max, false, signed)
545    }
546
547    /// Computes the maximal key in dictionary that is lexicographically smaller than `key`,
548    /// and returns it along with associated value as cell slice parts.
549    #[inline]
550    pub fn get_prev<Q>(&self, key: Q, signed: bool) -> Result<Option<(K, V)>, Error>
551    where
552        Q: Borrow<K>,
553        for<'a> V: Load<'a>,
554    {
555        self.find_ext(key, DictBound::Min, false, signed)
556    }
557
558    /// Computes the minimal key in dictionary that is lexicographically greater than `key`,
559    /// and returns it along with associated value as cell slice parts.
560    #[inline]
561    pub fn get_or_next<Q>(&self, key: Q, signed: bool) -> Result<Option<(K, V)>, Error>
562    where
563        Q: Borrow<K>,
564        for<'a> V: Load<'a>,
565    {
566        self.find_ext(key, DictBound::Max, true, signed)
567    }
568
569    /// Computes the maximal key in dictionary that is lexicographically smaller than `key`,
570    /// and returns it along with associated value as cell slice parts.
571    #[inline]
572    pub fn get_or_prev<Q>(&self, key: Q, signed: bool) -> Result<Option<(K, V)>, Error>
573    where
574        Q: Borrow<K>,
575        for<'a> V: Load<'a>,
576    {
577        self.find_ext(key, DictBound::Min, true, signed)
578    }
579
580    #[inline]
581    fn find_ext<Q>(
582        &self,
583        key: Q,
584        towards: DictBound,
585        inclusive: bool,
586        signed: bool,
587    ) -> Result<Option<(K, V)>, Error>
588    where
589        Q: Borrow<K>,
590        for<'a> V: Load<'a>,
591    {
592        fn find_impl<K, V>(
593            root: &Option<Cell>,
594            key: &K,
595            towards: DictBound,
596            inclusive: bool,
597            signed: bool,
598        ) -> Result<Option<(K, V)>, Error>
599        where
600            K: DictKey + Store,
601            for<'a> V: Load<'a>,
602        {
603            let context = &mut Cell::empty_context();
604            let Some((key, (cell, range))) = ({
605                let mut builder = CellBuilder::new();
606                ok!(key.store_into(&mut builder, context));
607                // TODO: add `dict_find` with non-owned return type
608                ok!(dict_find_owned(
609                    root.as_ref(),
610                    K::BITS,
611                    builder.as_data_slice(),
612                    towards,
613                    inclusive,
614                    signed,
615                    context,
616                ))
617            }) else {
618                return Ok(None);
619            };
620            let value = &mut ok!(range.apply(&cell));
621
622            match K::from_raw_data(key.raw_data()) {
623                Some(key) => Ok(Some((key, ok!(V::load_from(value))))),
624                None => Err(Error::CellUnderflow),
625            }
626        }
627
628        find_impl(&self.root, key.borrow(), towards, inclusive, signed)
629    }
630}
631
632impl<K, V> Dict<K, V>
633where
634    K: DictKey,
635{
636    /// Gets an iterator over the values of the dictionary, in order by key.
637    /// The iterator element type is `Result<V>`.
638    ///
639    /// If the dictionary is invalid, finishes after the first invalid element,
640    /// returning an error.
641    pub fn values<'a>(&'a self) -> Values<'a, V>
642    where
643        V: Load<'a>,
644    {
645        Values::new(&self.root, K::BITS)
646    }
647
648    /// Returns the lowest key and a value corresponding to the key.
649    pub fn get_min<'a>(&'a self, signed: bool) -> Result<Option<(K, V)>, Error>
650    where
651        V: Load<'a>,
652    {
653        Ok(match ok!(self.get_bound_raw(DictBound::Min, signed)) {
654            Some((key, ref mut value)) => Some((key, ok!(V::load_from(value)))),
655            None => None,
656        })
657    }
658
659    /// Returns the lowest key and a value corresponding to the key.
660    pub fn get_max<'a>(&'a self, signed: bool) -> Result<Option<(K, V)>, Error>
661    where
662        V: Load<'a>,
663    {
664        Ok(match ok!(self.get_bound_raw(DictBound::Max, signed)) {
665            Some((key, ref mut value)) => Some((key, ok!(V::load_from(value)))),
666            None => None,
667        })
668    }
669
670    /// Finds the specified dict bound and returns a key and a raw value corresponding to the key.
671    pub fn get_bound_raw(
672        &self,
673        bound: DictBound,
674        signed: bool,
675    ) -> Result<Option<(K, CellSlice<'_>)>, Error> {
676        let Some((key, value)) = ok!(dict_find_bound(
677            self.root.as_ref(),
678            K::BITS,
679            bound,
680            signed,
681            &mut Cell::empty_context()
682        )) else {
683            return Ok(None);
684        };
685        match K::from_raw_data(key.raw_data()) {
686            Some(key) => Ok(Some((key, value))),
687            None => Err(Error::CellUnderflow),
688        }
689    }
690
691    /// Removes the specified dict bound.
692    /// Returns an optional removed key and value as cell slice parts.
693    ///
694    /// Key and dict are serialized using the provided cell context.
695    pub fn remove_bound_raw_ext(
696        &mut self,
697        bound: DictBound,
698        signed: bool,
699        context: &mut dyn CellContext,
700    ) -> Result<Option<(K, CellSliceParts)>, Error> {
701        let removed = ok!(dict_remove_bound_owned(
702            &mut self.root,
703            K::BITS,
704            bound,
705            signed,
706            context
707        ));
708        Ok(match removed {
709            Some((key, value)) => match K::from_raw_data(key.raw_data()) {
710                Some(key) => Some((key, value)),
711                None => return Err(Error::CellUnderflow),
712            },
713            None => None,
714        })
715    }
716}
717
718impl<K, V> Dict<K, V>
719where
720    K: Store + DictKey,
721{
722    /// Removes the value associated with key in dictionary.
723    /// Returns an optional removed value as cell slice parts.
724    ///
725    /// Dict is rebuild using the provided cell context.
726    #[inline]
727    pub fn remove_raw_ext<Q>(
728        &mut self,
729        key: Q,
730        context: &mut dyn CellContext,
731    ) -> Result<Option<CellSliceParts>, Error>
732    where
733        Q: Borrow<K>,
734    {
735        fn remove_raw_ext_impl<K>(
736            root: &mut Option<Cell>,
737            key: &K,
738            context: &mut dyn CellContext,
739        ) -> Result<Option<CellSliceParts>, Error>
740        where
741            K: Store + DictKey,
742        {
743            let mut builder = CellBuilder::new();
744            ok!(key.store_into(&mut builder, &mut Cell::empty_context()));
745            dict_remove_owned(root, &mut builder.as_data_slice(), K::BITS, false, context)
746        }
747
748        remove_raw_ext_impl(&mut self.root, key.borrow(), context)
749    }
750
751    /// Gets an iterator over the raw entries of the dictionary, sorted by key.
752    /// The iterator element type is `Result<(CellBuilder, CellSlice)>`.
753    ///
754    /// If the dictionary is invalid, finishes after the first invalid element,
755    /// returning an error.
756    ///
757    /// # Performance
758    ///
759    /// In the current implementation, iterating over dictionary builds a key
760    /// for each element. Use [`values`] or [`raw_values`] if you don't need keys from an iterator.
761    ///
762    /// [`values`]: Dict::values
763    /// [`raw_values`]: Dict::raw_values
764    pub fn raw_iter(&'_ self) -> RawIter<'_> {
765        RawIter::new(&self.root, K::BITS)
766    }
767
768    /// Gets an iterator over the raw entries of two dictionaries, sorted by key.
769    /// The iterator element type is `Result<(CellBuilder, Option<CellSlice>, Option<CellSlice>)>`.
770    ///
771    /// If the dictionary is invalid, finishes after the first invalid element,
772    /// returning an error.
773    ///
774    /// # Performance
775    ///
776    /// In the current implementation, iterating over dictionary builds a key
777    /// for each element.
778    pub fn raw_iter_union<'a>(&'a self, other: &'a Self) -> UnionRawIter<'a> {
779        UnionRawIter::new(&self.root, &other.root, K::BITS)
780    }
781
782    /// Gets an iterator over the raw keys of the dictionary, in sorted order.
783    /// The iterator element type is `Result<CellBuilder>`.
784    ///
785    /// If the dictionary is invalid, finishes after the first invalid element,
786    /// returning an error.
787    ///
788    /// # Performance
789    ///
790    /// In the current implementation, iterating over dictionary builds a key
791    /// for each element. Use [`values`] or [`raw_values`] if you don't need keys from an iterator.
792    ///
793    /// [`values`]: Dict::values
794    /// [`raw_values`]: Dict::raw_values
795    pub fn raw_keys(&'_ self) -> RawKeys<'_> {
796        RawKeys::new(&self.root, K::BITS)
797    }
798}
799
800impl<K, V> Dict<K, V>
801where
802    K: DictKey,
803{
804    /// Gets an iterator over the raw values of the dictionary, in order by key.
805    /// The iterator element type is `Result<CellSlice>`.
806    ///
807    /// If the dictionary is invalid, finishes after the first invalid element,
808    /// returning an error.
809    pub fn raw_values(&'_ self) -> RawValues<'_> {
810        RawValues::new(&self.root, K::BITS)
811    }
812}
813
814impl<K, V> Dict<K, V>
815where
816    K: Store + DictKey,
817    V: Store,
818{
819    /// Sets the value associated with the key in the dictionary.
820    pub fn set_ext<Q, T>(
821        &mut self,
822        key: Q,
823        value: T,
824        context: &mut dyn CellContext,
825    ) -> Result<bool, Error>
826    where
827        Q: Borrow<K>,
828        T: Borrow<V>,
829    {
830        self.insert_impl(key.borrow(), value.borrow(), SetMode::Set, context)
831    }
832
833    /// Sets the value associated with the key in the dictionary
834    /// only if the key was already present in it.
835    pub fn replace_ext<Q, T>(
836        &mut self,
837        key: Q,
838        value: T,
839        context: &mut dyn CellContext,
840    ) -> Result<bool, Error>
841    where
842        Q: Borrow<K>,
843        T: Borrow<V>,
844    {
845        self.insert_impl(key.borrow(), value.borrow(), SetMode::Replace, context)
846    }
847
848    /// Sets the value associated with key in dictionary,
849    /// but only if it is not already present.
850    pub fn add_ext<Q, T>(
851        &mut self,
852        key: Q,
853        value: T,
854        context: &mut dyn CellContext,
855    ) -> Result<bool, Error>
856    where
857        Q: Borrow<K>,
858        T: Borrow<V>,
859    {
860        self.insert_impl(key.borrow(), value.borrow(), SetMode::Add, context)
861    }
862
863    fn insert_impl(
864        &mut self,
865        key: &K,
866        value: &V,
867        mode: SetMode,
868        context: &mut dyn CellContext,
869    ) -> Result<bool, Error>
870    where
871        K: Store + DictKey,
872        V: Store,
873    {
874        let mut key_builder = CellBuilder::new();
875        ok!(key.store_into(&mut key_builder, &mut Cell::empty_context()));
876        dict_insert(
877            &mut self.root,
878            &mut key_builder.as_data_slice(),
879            K::BITS,
880            value,
881            mode,
882            context,
883        )
884    }
885}
886
887#[cfg(feature = "serde")]
888impl<K, V> serde::Serialize for Dict<K, V>
889where
890    K: serde::Serialize + Store + DictKey,
891    for<'a> V: serde::Serialize + Load<'a>,
892{
893    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
894    where
895        S: serde::Serializer,
896    {
897        use serde::ser::{Error, SerializeMap};
898
899        if serializer.is_human_readable() {
900            let mut ser = serializer.serialize_map(None)?;
901            for ref entry in self.iter() {
902                let (key, value) = match entry {
903                    Ok(entry) => entry,
904                    Err(e) => return Err(Error::custom(e)),
905                };
906                ok!(ser.serialize_entry(key, value));
907            }
908            ser.end()
909        } else {
910            crate::boc::BocRepr::serialize(self, serializer)
911        }
912    }
913}
914
915#[cfg(feature = "serde")]
916impl<'de, K, V> serde::Deserialize<'de> for Dict<K, V>
917where
918    K: serde::Deserialize<'de> + std::hash::Hash + Eq + Store + DictKey,
919    V: serde::Deserialize<'de> + Store,
920{
921    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
922    where
923        D: serde::Deserializer<'de>,
924    {
925        if deserializer.is_human_readable() {
926            let map = ok!(ahash::HashMap::<K, V>::deserialize(deserializer));
927
928            // TODO: Build from sorted collection
929            let cx = &mut Cell::empty_context();
930            let mut dict = Dict::new();
931            for (key, value) in map {
932                if let Err(e) = dict.set_ext(key, value, cx) {
933                    return Err(serde::de::Error::custom(e));
934                }
935            }
936            Ok(dict)
937        } else {
938            crate::boc::BocRepr::deserialize(deserializer)
939        }
940    }
941}
942
943/// An iterator over the entries of a [`Dict`].
944///
945/// This struct is created by the [`iter`] method on [`Dict`]. See its documentation for more.
946///
947/// [`iter`]: Dict::iter
948pub struct Iter<'a, K, V> {
949    inner: RawIter<'a>,
950    _key: PhantomData<K>,
951    _value: PhantomData<V>,
952}
953
954impl<K, V> Clone for Iter<'_, K, V> {
955    fn clone(&self) -> Self {
956        Self {
957            inner: self.inner.clone(),
958            _key: PhantomData,
959            _value: PhantomData,
960        }
961    }
962}
963
964impl<'a, K, V> Iter<'a, K, V>
965where
966    K: DictKey,
967{
968    /// Creates an iterator over the entries of a dictionary.
969    pub fn new(root: &'a Option<Cell>) -> Self {
970        Self {
971            inner: RawIter::new(root, K::BITS),
972            _key: PhantomData,
973            _value: PhantomData,
974        }
975    }
976
977    /// Changes the direction of the iterator to descending.
978    #[inline]
979    pub fn reversed(mut self) -> Self {
980        self.inner = self.inner.reversed();
981        self
982    }
983
984    /// Changes the behavior of the iterator to reverse the high bit.
985    #[inline]
986    pub fn signed(mut self) -> Self {
987        self.inner = self.inner.signed();
988        self
989    }
990}
991
992impl<'a, K, V> Iterator for Iter<'a, K, V>
993where
994    K: DictKey,
995    V: Load<'a>,
996{
997    type Item = Result<(K, V), Error>;
998
999    fn next(&mut self) -> Option<Self::Item> {
1000        Some(match self.inner.next()? {
1001            Ok((key, mut value)) => {
1002                let err = if let Some(key) = K::from_raw_data(key.raw_data()) {
1003                    match V::load_from(&mut value) {
1004                        Ok(value) => return Some(Ok((key, value))),
1005                        Err(e) => e,
1006                    }
1007                } else {
1008                    Error::CellUnderflow
1009                };
1010                Err(self.inner.finish(err))
1011            }
1012            Err(e) => Err(e),
1013        })
1014    }
1015}
1016
1017/// An iterator over the entries across two [`Dict`].
1018///
1019/// This struct is created by the [`iter_union`] method on [`Dict`].
1020///
1021/// [`iter_union`]: Dict::iter_union
1022pub struct UnionIter<'a, K, V> {
1023    inner: UnionRawIter<'a>,
1024    _key: PhantomData<K>,
1025    _value: PhantomData<V>,
1026}
1027
1028impl<'a, K, V> UnionIter<'a, K, V>
1029where
1030    K: DictKey,
1031{
1032    /// Creates an iterator over the entries of a dictionary.
1033    pub fn new(left_root: &'a Option<Cell>, right_root: &'a Option<Cell>) -> Self {
1034        Self {
1035            inner: UnionRawIter::new(left_root, right_root, K::BITS),
1036            _key: PhantomData,
1037            _value: PhantomData,
1038        }
1039    }
1040
1041    /// Changes the direction of the iterator to descending.
1042    #[inline]
1043    pub fn reversed(mut self) -> Self {
1044        self.inner = self.inner.reversed();
1045        self
1046    }
1047
1048    /// Changes the behavior of the iterator to reverse the high bit.
1049    #[inline]
1050    pub fn signed(mut self) -> Self {
1051        self.inner = self.inner.signed();
1052        self
1053    }
1054}
1055
1056impl<'a, K, V> Iterator for UnionIter<'a, K, V>
1057where
1058    K: DictKey,
1059    V: Load<'a>,
1060{
1061    type Item = Result<(K, Option<V>, Option<V>), Error>;
1062
1063    fn next(&mut self) -> Option<Self::Item> {
1064        fn load_opt_value<'a, V: Load<'a>>(
1065            value: &mut Option<CellSlice<'a>>,
1066        ) -> Result<Option<V>, Error> {
1067            match value {
1068                Some(mut value) => match V::load_from(&mut value) {
1069                    Ok(value) => Ok(Some(value)),
1070                    Err(e) => Err(e),
1071                },
1072                None => Ok(None),
1073            }
1074        }
1075
1076        Some(match self.inner.next()? {
1077            Ok((key, mut left_value, mut right_value)) => {
1078                let err = if let Some(key) = K::from_raw_data(key.raw_data()) {
1079                    match (
1080                        load_opt_value(&mut left_value),
1081                        load_opt_value(&mut right_value),
1082                    ) {
1083                        (Ok(left), Ok(right)) => return Some(Ok((key, left, right))),
1084                        (Err(e), _) => e,
1085                        (_, Err(e)) => e,
1086                    }
1087                } else {
1088                    Error::CellUnderflow
1089                };
1090                Err(self.inner.finish(err))
1091            }
1092            Err(e) => Err(e),
1093        })
1094    }
1095}
1096
1097/// An iterator over the keys of a [`Dict`].
1098///
1099/// This struct is created by the [`keys`] method on [`Dict`]. See its
1100/// documentation for more.
1101///
1102/// [`keys`]: Dict::keys
1103pub struct Keys<'a, K> {
1104    inner: RawIter<'a>,
1105    _key: PhantomData<K>,
1106}
1107
1108impl<'a, K> Clone for Keys<'a, K> {
1109    fn clone(&self) -> Self {
1110        Self {
1111            inner: self.inner.clone(),
1112            _key: PhantomData,
1113        }
1114    }
1115}
1116
1117impl<'a, K> Keys<'a, K>
1118where
1119    K: DictKey,
1120{
1121    /// Creates an iterator over the keys of a dictionary.
1122    pub fn new(root: &'a Option<Cell>) -> Self {
1123        Self {
1124            inner: RawIter::new(root, K::BITS),
1125            _key: PhantomData,
1126        }
1127    }
1128
1129    /// Changes the direction of the iterator to descending.
1130    #[inline]
1131    pub fn reversed(mut self) -> Self {
1132        self.inner = self.inner.reversed();
1133        self
1134    }
1135
1136    /// Changes the behavior of the iterator to reverse the high bit.
1137    #[inline]
1138    pub fn signed(mut self) -> Self {
1139        self.inner = self.inner.signed();
1140        self
1141    }
1142}
1143
1144impl<'a, K> Iterator for Keys<'a, K>
1145where
1146    K: DictKey,
1147{
1148    type Item = Result<K, Error>;
1149
1150    fn next(&mut self) -> Option<Self::Item> {
1151        Some(match self.inner.next()? {
1152            Ok((key, _)) => match K::from_raw_data(key.raw_data()) {
1153                Some(key) => Ok(key),
1154                None => Err(self.inner.finish(Error::CellUnderflow)),
1155            },
1156            Err(e) => Err(e),
1157        })
1158    }
1159}
1160
1161/// An iterator over the values of a [`Dict`].
1162///
1163/// This struct is created by the [`values`] method on [`Dict`]. See its documentation for more.
1164///
1165/// [`values`]: Dict::values
1166pub struct Values<'a, V> {
1167    inner: RawValues<'a>,
1168    _value: PhantomData<V>,
1169}
1170
1171impl<V> Clone for Values<'_, V> {
1172    fn clone(&self) -> Self {
1173        Self {
1174            inner: self.inner.clone(),
1175            _value: PhantomData,
1176        }
1177    }
1178}
1179
1180impl<'a, V> Values<'a, V> {
1181    /// Creates an iterator over the values of a dictionary.
1182    pub fn new(root: &'a Option<Cell>, bit_len: u16) -> Self {
1183        Self {
1184            inner: RawValues::new(root, bit_len),
1185            _value: PhantomData,
1186        }
1187    }
1188
1189    /// Changes the direction of the iterator to descending.
1190    #[inline]
1191    pub fn reversed(mut self) -> Self {
1192        self.inner = self.inner.reversed();
1193        self
1194    }
1195
1196    /// Changes the behavior of the iterator to reverse the high bit.
1197    #[inline]
1198    pub fn signed(mut self) -> Self {
1199        self.inner = self.inner.signed();
1200        self
1201    }
1202}
1203
1204impl<'a, V> Iterator for Values<'a, V>
1205where
1206    V: Load<'a>,
1207{
1208    type Item = Result<V, Error>;
1209
1210    fn next(&mut self) -> Option<Self::Item> {
1211        match self.inner.next()? {
1212            Ok(mut value) => match V::load_from(&mut value) {
1213                Ok(value) => Some(Ok(value)),
1214                Err(e) => Some(Err(self.inner.finish(e))),
1215            },
1216            Err(e) => Some(Err(e)),
1217        }
1218    }
1219}
1220
1221#[cfg(test)]
1222mod tests {
1223    use anyhow::Context;
1224
1225    use super::*;
1226    use crate::prelude::*;
1227
1228    #[test]
1229    fn dict_set() {
1230        let mut dict = Dict::<u32, u16>::new();
1231        assert!(dict.set(123, 0xffff).unwrap());
1232        assert_eq!(dict.get(123).unwrap(), Some(0xffff));
1233
1234        assert!(dict.set(123, 0xcafe).unwrap());
1235        assert_eq!(dict.get(123).unwrap(), Some(0xcafe));
1236    }
1237
1238    #[test]
1239    #[cfg_attr(miri, ignore)] // takes too long to execute on miri
1240    fn dict_set_complex() {
1241        let mut dict = Dict::<u32, bool>::new();
1242        for i in 0..520 {
1243            assert!(dict.set(i, true).unwrap());
1244        }
1245    }
1246
1247    #[test]
1248    fn dict_bounds() {
1249        let mut dict = Dict::<i32, bool>::new();
1250        for i in -10..=10 {
1251            assert!(dict.set(i, i < 0).unwrap());
1252        }
1253
1254        assert_eq!(dict.get_min(false).unwrap(), Some((0, false)));
1255        assert_eq!(dict.get_max(false).unwrap(), Some((-1, true)));
1256
1257        assert_eq!(dict.get_min(true).unwrap(), Some((-10, true)));
1258        assert_eq!(dict.get_max(true).unwrap(), Some((10, false)));
1259
1260        let mut dict = Dict::<u32, u8>::new();
1261        for i in 1..=3 {
1262            dict.set(i, 0xff).unwrap();
1263        }
1264        assert_eq!(dict.get_min(false).unwrap(), Some((1, 0xff)));
1265        assert_eq!(dict.get_max(false).unwrap(), Some((3, 0xff)));
1266    }
1267
1268    #[test]
1269    fn dict_remove_bounds() {
1270        let mut dict = Dict::<i32, bool>::new();
1271        for i in -10..=10 {
1272            dict.set(i, i < 0).unwrap();
1273        }
1274
1275        let parse_removed = |(i, (cell, range)): (i32, CellSliceParts)| {
1276            let mut value = range.apply(&cell)?;
1277            let value = bool::load_from(&mut value)?;
1278            Ok::<_, Error>((i, value))
1279        };
1280
1281        // Min, unsigned
1282        {
1283            let mut dict = dict.clone();
1284            for i in 0..=10 {
1285                let removed = dict.remove_min_raw(false).unwrap().unwrap();
1286                assert_eq!(parse_removed(removed).unwrap(), (i, false));
1287            }
1288            for i in -10..=-1 {
1289                let removed = dict.remove_min_raw(false).unwrap().unwrap();
1290                assert_eq!(parse_removed(removed).unwrap(), (i, true));
1291            }
1292            assert!(dict.is_empty());
1293        }
1294
1295        // Min, signed
1296        {
1297            let mut dict = dict.clone();
1298            for i in -10..=10 {
1299                let removed = dict.remove_min_raw(true).unwrap().unwrap();
1300                assert_eq!(parse_removed(removed).unwrap(), (i, i < 0));
1301            }
1302            assert!(dict.is_empty());
1303        }
1304
1305        // Max, unsigned
1306        {
1307            let mut dict = dict.clone();
1308            for i in (-10..=-1).rev() {
1309                let removed = dict.remove_max_raw(false).unwrap().unwrap();
1310                assert_eq!(parse_removed(removed).unwrap(), (i, true));
1311            }
1312            for i in (0..=10).rev() {
1313                let removed = dict.remove_max_raw(false).unwrap().unwrap();
1314                assert_eq!(parse_removed(removed).unwrap(), (i, false));
1315            }
1316            assert!(dict.is_empty());
1317        }
1318
1319        // Max, signed
1320        {
1321            let mut dict = dict.clone();
1322            for i in (-10..=10).rev() {
1323                let removed = dict.remove_max_raw(true).unwrap().unwrap();
1324                assert_eq!(parse_removed(removed).unwrap(), (i, i < 0));
1325            }
1326            assert!(dict.is_empty());
1327        }
1328    }
1329
1330    #[test]
1331    fn dict_replace() {
1332        let mut dict = Dict::<u32, bool>::new();
1333        assert!(!dict.replace(123, false).unwrap());
1334        assert!(!dict.contains_key(123).unwrap());
1335
1336        assert!(dict.set(123, false).unwrap());
1337        assert_eq!(dict.get(123).unwrap(), Some(false));
1338        assert!(dict.replace(123, true).unwrap());
1339        assert_eq!(dict.get(123).unwrap(), Some(true));
1340    }
1341
1342    #[test]
1343    fn dict_add() {
1344        let mut dict = Dict::<u32, bool>::new();
1345
1346        assert!(dict.add(123, false).unwrap());
1347        assert_eq!(dict.get(123).unwrap(), Some(false));
1348
1349        assert!(!dict.add(123, true).unwrap());
1350        assert_eq!(dict.get(123).unwrap(), Some(false));
1351    }
1352
1353    #[test]
1354    fn dict_remove() {
1355        let mut dict = Dict::<u32, u32>::new();
1356
1357        for i in 0..10 {
1358            assert!(dict.set(i, i).unwrap());
1359        }
1360
1361        let mut check_remove = |n: u32, expected: Option<u32>| -> anyhow::Result<()> {
1362            let removed = dict.remove(n).context("Failed to remove")?;
1363            anyhow::ensure!(removed == expected);
1364            Ok(())
1365        };
1366
1367        check_remove(0, Some(0)).unwrap();
1368
1369        check_remove(4, Some(4)).unwrap();
1370
1371        check_remove(9, Some(9)).unwrap();
1372        check_remove(9, None).unwrap();
1373
1374        check_remove(5, Some(5)).unwrap();
1375        check_remove(5, None).unwrap();
1376
1377        check_remove(100, None).unwrap();
1378
1379        check_remove(1, Some(1)).unwrap();
1380        check_remove(2, Some(2)).unwrap();
1381        check_remove(3, Some(3)).unwrap();
1382        check_remove(6, Some(6)).unwrap();
1383        check_remove(7, Some(7)).unwrap();
1384        check_remove(8, Some(8)).unwrap();
1385
1386        assert!(dict.is_empty());
1387    }
1388
1389    #[test]
1390    fn dict_iter() {
1391        let boc = Boc::decode_base64("te6ccgEBFAEAeAABAcABAgPOQAUCAgHUBAMACQAAAI3gAAkAAACjoAIBIA0GAgEgCgcCASAJCAAJAAAAciAACQAAAIfgAgEgDAsACQAAAFZgAAkAAABsIAIBIBEOAgEgEA8ACQAAADqgAAkAAABQYAIBIBMSAAkAAAAe4AAJAAAAv2A=").unwrap();
1392        let dict = boc.parse::<Dict<u32, u32>>().unwrap();
1393
1394        let size = dict.values().count();
1395        assert_eq!(size, 10);
1396
1397        for (i, entry) in dict.iter().enumerate() {
1398            let (key, _) = entry.unwrap();
1399            assert_eq!(key, i as u32);
1400        }
1401
1402        let signed_range = -10..10;
1403
1404        let mut dict = Dict::<i32, i32>::new();
1405        for i in signed_range.clone() {
1406            assert!(dict.set(i, i).unwrap());
1407        }
1408
1409        let mut signed_range_iter = signed_range.clone();
1410        for (entry, i) in dict.iter().signed().zip(&mut signed_range_iter) {
1411            let (key, value) = entry.unwrap();
1412            assert_eq!(key, i);
1413            assert_eq!(value, i);
1414        }
1415        assert_eq!(signed_range_iter.next(), None);
1416
1417        let mut signed_range_iter = signed_range.rev();
1418        for (entry, i) in dict.iter().reversed().signed().zip(&mut signed_range_iter) {
1419            let (key, value) = entry.unwrap();
1420            assert_eq!(key, i);
1421            assert_eq!(value, i);
1422        }
1423        assert_eq!(signed_range_iter.next(), None);
1424    }
1425
1426    #[test]
1427    fn dict_next_prev_unsigned() {
1428        let mut dict = Dict::<u32, u32>::new();
1429
1430        for i in 0..=10 {
1431            dict.set(i, i).unwrap();
1432        }
1433
1434        for i in 20..=30 {
1435            dict.set(i, i).unwrap();
1436        }
1437
1438        println!("{}", BocRepr::encode_base64(&dict).unwrap());
1439
1440        assert_eq!(dict.get_prev(0, false).unwrap(), None);
1441        assert_eq!(dict.get_or_prev(0, false).unwrap(), Some((0, 0)));
1442
1443        assert_eq!(dict.get_next(30, false).unwrap(), None);
1444        assert_eq!(dict.get_or_next(30, false).unwrap(), Some((30, 30)));
1445
1446        assert_eq!(dict.get_prev(15, false).unwrap(), Some((10, 10)));
1447        assert_eq!(dict.get_or_prev(15, false).unwrap(), Some((10, 10)));
1448
1449        assert_eq!(dict.get_next(15, false).unwrap(), Some((20, 20)));
1450        assert_eq!(dict.get_or_next(15, false).unwrap(), Some((20, 20)));
1451
1452        assert_eq!(dict.get_next(19, false).unwrap(), Some((20, 20)));
1453        assert_eq!(dict.get_or_next(19, false).unwrap(), Some((20, 20)));
1454
1455        assert_eq!(dict.get_prev(20, false).unwrap(), Some((10, 10)));
1456        assert_eq!(dict.get_or_prev(20, false).unwrap(), Some((20, 20)));
1457
1458        assert_eq!(dict.get_next(100, false).unwrap(), None);
1459        assert_eq!(dict.get_or_next(100, false).unwrap(), None);
1460
1461        assert_eq!(dict.get_prev(100, false).unwrap(), Some((30, 30)));
1462        assert_eq!(dict.get_or_prev(100, false).unwrap(), Some((30, 30)));
1463    }
1464
1465    #[test]
1466    fn dict_next_prev_signed() {
1467        let mut dict = Dict::<i32, i32>::new();
1468
1469        for i in -20..=-10 {
1470            dict.set(i, i).unwrap();
1471        }
1472
1473        assert_eq!(dict.get_prev(-20, true).unwrap(), None);
1474        assert_eq!(dict.get_or_prev(-20, true).unwrap(), Some((-20, -20)));
1475
1476        assert_eq!(dict.get_next(-10, true).unwrap(), None);
1477        assert_eq!(dict.get_or_next(-10, true).unwrap(), Some((-10, -10)));
1478
1479        for i in 10..=20 {
1480            dict.set(i, i).unwrap();
1481        }
1482
1483        println!("{}", BocRepr::encode_base64(&dict).unwrap());
1484
1485        assert_eq!(dict.get_next(-100, true).unwrap(), Some((-20, -20)));
1486        assert_eq!(dict.get_or_next(-100, true).unwrap(), Some((-20, -20)));
1487
1488        assert_eq!(dict.get_prev(-100, true).unwrap(), None);
1489        assert_eq!(dict.get_or_prev(-100, true).unwrap(), None);
1490
1491        assert_eq!(dict.get_prev(-20, true).unwrap(), None);
1492        assert_eq!(dict.get_or_prev(-20, true).unwrap(), Some((-20, -20)));
1493
1494        assert_eq!(dict.get_next(20, true).unwrap(), None);
1495        assert_eq!(dict.get_or_next(20, true).unwrap(), Some((20, 20)));
1496
1497        assert_eq!(dict.get_prev(-10, true).unwrap(), Some((-11, -11)));
1498        assert_eq!(dict.get_or_prev(-10, true).unwrap(), Some((-10, -10)));
1499
1500        assert_eq!(dict.get_next(-10, true).unwrap(), Some((10, 10)));
1501        assert_eq!(dict.get_or_next(-10, true).unwrap(), Some((-10, -10)));
1502
1503        assert_eq!(dict.get_prev(-9, true).unwrap(), Some((-10, -10)));
1504        assert_eq!(dict.get_or_prev(-9, true).unwrap(), Some((-10, -10)));
1505
1506        assert_eq!(dict.get_prev(0, true).unwrap(), Some((-10, -10)));
1507        assert_eq!(dict.get_or_prev(0, true).unwrap(), Some((-10, -10)));
1508
1509        assert_eq!(dict.get_next(0, true).unwrap(), Some((10, 10)));
1510        assert_eq!(dict.get_or_next(0, true).unwrap(), Some((10, 10)));
1511
1512        assert_eq!(dict.get_prev(10, true).unwrap(), Some((-10, -10)));
1513        assert_eq!(dict.get_or_prev(10, true).unwrap(), Some((10, 10)));
1514
1515        assert_eq!(dict.get_next(100, true).unwrap(), None);
1516        assert_eq!(dict.get_or_next(100, true).unwrap(), None);
1517
1518        assert_eq!(dict.get_prev(100, true).unwrap(), Some((20, 20)));
1519        assert_eq!(dict.get_or_prev(100, true).unwrap(), Some((20, 20)));
1520
1521        // All negative
1522        let mut dict = Dict::<i32, i32>::new();
1523        for i in -10..=-5 {
1524            dict.set(i, i).unwrap();
1525        }
1526
1527        assert_eq!(dict.get_prev(-20, true).unwrap(), None);
1528        assert_eq!(dict.get_or_prev(-20, true).unwrap(), None);
1529        assert_eq!(dict.get_prev(-10, true).unwrap(), None);
1530        assert_eq!(dict.get_or_prev(-10, true).unwrap(), Some((-10, -10)));
1531
1532        assert_eq!(dict.get_next(-20, true).unwrap(), Some((-10, -10)));
1533        assert_eq!(dict.get_or_next(-20, true).unwrap(), Some((-10, -10)));
1534        assert_eq!(dict.get_next(-10, true).unwrap(), Some((-9, -9)));
1535        assert_eq!(dict.get_or_next(-10, true).unwrap(), Some((-10, -10)));
1536
1537        assert_eq!(dict.get_prev(-7, true).unwrap(), Some((-8, -8)));
1538        assert_eq!(dict.get_or_prev(-7, true).unwrap(), Some((-7, -7)));
1539        assert_eq!(dict.get_next(-7, true).unwrap(), Some((-6, -6)));
1540        assert_eq!(dict.get_or_next(-7, true).unwrap(), Some((-7, -7)));
1541
1542        assert_eq!(dict.get_prev(-5, true).unwrap(), Some((-6, -6)));
1543        assert_eq!(dict.get_or_prev(-5, true).unwrap(), Some((-5, -5)));
1544        assert_eq!(dict.get_prev(-4, true).unwrap(), Some((-5, -5)));
1545        assert_eq!(dict.get_or_prev(-4, true).unwrap(), Some((-5, -5)));
1546
1547        assert_eq!(dict.get_next(-5, true).unwrap(), None);
1548        assert_eq!(dict.get_or_next(-5, true).unwrap(), Some((-5, -5)));
1549        assert_eq!(dict.get_next(-4, true).unwrap(), None);
1550        assert_eq!(dict.get_or_next(-4, true).unwrap(), None);
1551
1552        assert_eq!(dict.get_next(0, true).unwrap(), None);
1553        assert_eq!(dict.get_or_next(0, true).unwrap(), None);
1554        assert_eq!(dict.get_next(1, true).unwrap(), None);
1555        assert_eq!(dict.get_or_next(1, true).unwrap(), None);
1556
1557        // All positive
1558        let mut dict = Dict::<i32, i32>::new();
1559        for i in 5..=10 {
1560            dict.set(i, i).unwrap();
1561        }
1562
1563        assert_eq!(dict.get_prev(-1, true).unwrap(), None);
1564        assert_eq!(dict.get_or_prev(-1, true).unwrap(), None);
1565        assert_eq!(dict.get_prev(0, true).unwrap(), None);
1566        assert_eq!(dict.get_or_prev(0, true).unwrap(), None);
1567
1568        assert_eq!(dict.get_next(4, true).unwrap(), Some((5, 5)));
1569        assert_eq!(dict.get_or_next(4, true).unwrap(), Some((5, 5)));
1570        assert_eq!(dict.get_next(5, true).unwrap(), Some((6, 6)));
1571        assert_eq!(dict.get_or_next(5, true).unwrap(), Some((5, 5)));
1572
1573        assert_eq!(dict.get_prev(7, true).unwrap(), Some((6, 6)));
1574        assert_eq!(dict.get_or_prev(7, true).unwrap(), Some((7, 7)));
1575        assert_eq!(dict.get_next(7, true).unwrap(), Some((8, 8)));
1576        assert_eq!(dict.get_or_next(7, true).unwrap(), Some((7, 7)));
1577
1578        assert_eq!(dict.get_prev(10, true).unwrap(), Some((9, 9)));
1579        assert_eq!(dict.get_or_prev(10, true).unwrap(), Some((10, 10)));
1580        assert_eq!(dict.get_prev(11, true).unwrap(), Some((10, 10)));
1581        assert_eq!(dict.get_or_prev(11, true).unwrap(), Some((10, 10)));
1582
1583        assert_eq!(dict.get_next(10, true).unwrap(), None);
1584        assert_eq!(dict.get_or_next(10, true).unwrap(), Some((10, 10)));
1585        assert_eq!(dict.get_next(11, true).unwrap(), None);
1586        assert_eq!(dict.get_or_next(11, true).unwrap(), None);
1587
1588        assert_eq!(dict.get_prev(20, true).unwrap(), Some((10, 10)));
1589        assert_eq!(dict.get_or_prev(20, true).unwrap(), Some((10, 10)));
1590        assert_eq!(dict.get_next(20, true).unwrap(), None);
1591        assert_eq!(dict.get_or_next(20, true).unwrap(), None);
1592
1593        // Single positive on edge
1594        let mut dict = Dict::<i32, i32>::new();
1595        dict.set(0, 0).unwrap();
1596
1597        assert_eq!(dict.get_prev(0, true).unwrap(), None);
1598        assert_eq!(dict.get_or_prev(0, true).unwrap(), Some((0, 0)));
1599        assert_eq!(dict.get_next(-1, true).unwrap(), Some((0, 0)));
1600        assert_eq!(dict.get_or_next(-1, true).unwrap(), Some((0, 0)));
1601
1602        // Single negative on edge
1603        let mut dict = Dict::<i32, i32>::new();
1604        dict.set(-1, -1).unwrap();
1605
1606        assert_eq!(dict.get_prev(0, true).unwrap(), Some((-1, -1)));
1607        assert_eq!(dict.get_or_prev(0, true).unwrap(), Some((-1, -1)));
1608        assert_eq!(dict.get_next(-1, true).unwrap(), None);
1609        assert_eq!(dict.get_or_next(-1, true).unwrap(), Some((-1, -1)));
1610    }
1611
1612    #[test]
1613    fn dict_same_after_remove() -> anyhow::Result<()> {
1614        let mut dict = Dict::<i32, i32>::new();
1615        dict.set(-1, 1)?;
1616        dict.set(-2, 2)?;
1617
1618        let removed = dict.remove(-2).unwrap();
1619        assert_eq!(removed, Some(2));
1620
1621        let mut dict2 = Dict::<i32, i32>::new();
1622        dict2.set(-1, 1)?;
1623
1624        assert_eq!(dict, dict2);
1625        Ok(())
1626    }
1627
1628    #[test]
1629    fn get_signed_next() {
1630        let cell = Boc::decode_base64("te6ccgEBCwEAaAACAskDAQIBIAQCAgHOCAgCASAEBAIBIAUFAgEgBgYCASAHBwIBIAgIAgEgCQkBAwDgCgBoQgBAJTazb04k/ooV5DE4d+ixdwixajACdzkuZVb6ymgnqyHc1lAAAAAAAAAAAAAAAAAAAA==").unwrap();
1631        let dict = Dict::<i16, Cell>::from_raw(Some(cell));
1632
1633        for item in dict.iter() {
1634            let (key, cell) = item.unwrap();
1635            println!("{key}, {}", cell.display_root());
1636        }
1637
1638        let res = dict.get_next(-1, true).unwrap();
1639        println!("{res:?}");
1640    }
1641
1642    #[test]
1643    #[cfg_attr(miri, ignore)]
1644    fn big_dict() {
1645        use rand::{Rng, SeedableRng};
1646
1647        let mut rng = rand_xorshift::XorShiftRng::from_seed([0u8; 16]);
1648
1649        let values = (0..100000)
1650            .map(|_| (rng.gen::<u32>(), rng.gen::<u64>()))
1651            .collect::<Vec<_>>();
1652
1653        // Wrap builder into a new function for the flamegraph
1654        #[inline(never)]
1655        fn test_big_dict(values: &[(u32, u64)]) -> Dict<u32, u64> {
1656            let mut result = Dict::<u32, u64>::new();
1657            for (key, value) in values {
1658                result.set(key, value).unwrap();
1659            }
1660            result
1661        }
1662
1663        test_big_dict(&values);
1664    }
1665
1666    #[test]
1667    fn dict_iter_union() -> anyhow::Result<()> {
1668        let mut left = Dict::<i32, i32>::new();
1669        let mut right = Dict::<i32, i32>::new();
1670
1671        // Fill
1672        for i in -4i32..4 {
1673            left.set(i, i)?;
1674        }
1675        for i in -2i32..6 {
1676            right.set(i, i + 100)?;
1677        }
1678
1679        fn compare_iter_values(
1680            iter: UnionIter<'_, i32, i32>,
1681            values: &[(i32, Option<i32>, Option<i32>)],
1682        ) {
1683            let mut values = values.iter();
1684
1685            for entry in iter {
1686                let (key, left_value, right_value) = entry.unwrap();
1687                assert_eq!(values.next(), Some(&(key, left_value, right_value)));
1688            }
1689            assert_eq!(values.next(), None);
1690        }
1691
1692        // Unsigned
1693        compare_iter_values(
1694            left.iter_union(&right),
1695            &[
1696                (0, Some(0), Some(100)),
1697                (1, Some(1), Some(101)),
1698                (2, Some(2), Some(102)),
1699                (3, Some(3), Some(103)),
1700                (4, None, Some(104)),
1701                (5, None, Some(105)),
1702                (-4, Some(-4), None),
1703                (-3, Some(-3), None),
1704                (-2, Some(-2), Some(98)),
1705                (-1, Some(-1), Some(99)),
1706            ],
1707        );
1708
1709        // Unsigned reversed
1710        compare_iter_values(
1711            left.iter_union(&right).reversed(),
1712            &[
1713                (-1, Some(-1), Some(99)),
1714                (-2, Some(-2), Some(98)),
1715                (-3, Some(-3), None),
1716                (-4, Some(-4), None),
1717                (5, None, Some(105)),
1718                (4, None, Some(104)),
1719                (3, Some(3), Some(103)),
1720                (2, Some(2), Some(102)),
1721                (1, Some(1), Some(101)),
1722                (0, Some(0), Some(100)),
1723            ],
1724        );
1725
1726        // Signed
1727        compare_iter_values(
1728            left.iter_union(&right).signed(),
1729            &[
1730                (-4, Some(-4), None),
1731                (-3, Some(-3), None),
1732                (-2, Some(-2), Some(98)),
1733                (-1, Some(-1), Some(99)),
1734                (0, Some(0), Some(100)),
1735                (1, Some(1), Some(101)),
1736                (2, Some(2), Some(102)),
1737                (3, Some(3), Some(103)),
1738                (4, None, Some(104)),
1739                (5, None, Some(105)),
1740            ],
1741        );
1742
1743        // Signed reversed
1744        compare_iter_values(
1745            left.iter_union(&right).signed().reversed(),
1746            &[
1747                (5, None, Some(105)),
1748                (4, None, Some(104)),
1749                (3, Some(3), Some(103)),
1750                (2, Some(2), Some(102)),
1751                (1, Some(1), Some(101)),
1752                (0, Some(0), Some(100)),
1753                (-1, Some(-1), Some(99)),
1754                (-2, Some(-2), Some(98)),
1755                (-3, Some(-3), None),
1756                (-4, Some(-4), None),
1757            ],
1758        );
1759
1760        Ok(())
1761    }
1762}
everscale_types/dict/typed.rs

everscale_types/dict/
typed.rs
