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

tycho_types/dict/
typed.rs
