tycho_types/dict/
typed.rs

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

tycho_types/dict/
typed.rs
