blazinterner/
mapping.rs

1use super::{Arena, ArenaSlice, ArenaStr, Index, Interned, InternedSlice, InternedStr};
2#[cfg(feature = "retain")]
3use crate::DefaultBuildHasher;
4use alloc::boxed::Box;
5use alloc::vec;
6use alloc::vec::Vec;
7#[cfg(feature = "retain")]
8use bit_set::BitSet;
9use core::borrow::Borrow;
10use core::cmp::Ordering;
11use core::hash::{BuildHasher, Hash};
12#[cfg(feature = "retain")]
13use core::marker::PhantomData;
14use either::Either;
15
16impl<T: ?Sized, Storage, H, I> Arena<T, Storage, H, I>
17where
18    T: Ord,
19    Storage: Borrow<T>,
20    I: Index,
21{
22    /// Returns a sorted mapping of the items in this arena.
23    pub fn sort(&self) -> Mapping<I> {
24        let mut mapping: Vec<I> = (0..self.len()).map(I::from_usize).collect();
25        mapping.sort_by_cached_key(|i| self.lookup_ref(Interned::new(*i)));
26        let reverse = ReverseMapping::new(mapping.into_boxed_slice());
27        let forward = reverse.reverse();
28        Mapping { forward, reverse }
29    }
30}
31
32impl<T: ?Sized, Storage, H, I> Arena<T, Storage, H, I>
33where
34    I: Index,
35{
36    /// Returns the identity mapping of the items in this arena.
37    ///
38    /// This can be useful to rehash the arena.
39    pub fn identity(&self) -> Mapping<I> {
40        Mapping::identity(I::from_usize(self.len()))
41    }
42
43    /// Returns a mapping to build an arena containing only the items of this
44    /// arena that satisfy the given predicate.
45    pub fn retain(&self, filter: impl Fn(Interned<T, Storage, H, I>) -> bool) -> Mapping<I> {
46        Mapping::retain(self.len(), |i| filter(Interned::new(i)))
47    }
48
49    /// Returns a mapping to build an arena containing only the given items.
50    ///
51    /// See also [`retain_builder()`](Self::retain_builder) if you need a more
52    /// flexible way of adding items to retain.
53    #[cfg(feature = "retain")]
54    pub fn retain_values(
55        &self,
56        values: impl Iterator<Item = Interned<T, Storage, H, I>>,
57    ) -> Mapping<I> {
58        let mut builder = self.retain_builder();
59        for v in values {
60            builder.insert(v);
61        }
62        builder.build()
63    }
64
65    /// Returns a builder allowing to select items to retain, and create an
66    /// arena containing only these.
67    #[cfg(feature = "retain")]
68    pub fn retain_builder(&self) -> RetainBuilder<T, Storage, H, I> {
69        let len = self.len();
70        RetainBuilder {
71            len,
72            retained: BitSet::with_capacity(len),
73            _phantom: PhantomData,
74        }
75    }
76}
77
78impl<T: ?Sized, Storage, H, I> Arena<T, Storage, H, I>
79where
80    T: Eq + Hash,
81    Storage: Borrow<T> + Clone,
82    I: Index,
83{
84    /// Returns a re-ordered version of this arena based on the given mapping.
85    ///
86    /// See also [`map_rehash()`](Self::map_rehash) to use a different hash
87    /// function in the resulting arena.
88    pub fn map(&self, mapping: &ReverseMapping<I>) -> Self
89    where
90        H: Default + BuildHasher,
91    {
92        self.map_rehash(mapping)
93    }
94
95    /// Returns a re-ordered version of this arena based on the given mapping.
96    ///
97    /// See also [`map()`](Self::map) if the resulting arena uses the same hash
98    /// function.
99    pub fn map_rehash<HH>(&self, mapping: &ReverseMapping<I>) -> Arena<T, Storage, HH, I>
100    where
101        HH: Default + BuildHasher,
102    {
103        let mut arena = Arena::with_capacity(mapping.len());
104        for i in mapping.iter() {
105            arena.push(self.lookup(Interned::new(i)));
106        }
107        arena
108    }
109
110    /// Returns a re-ordered version of this arena based on the given mapping,
111    /// where each item is additionally transformed according to the given
112    /// function `f`.
113    ///
114    /// The transformation function should be injective, i.e. different inputs
115    /// should map to different outputs. Otherwise a value may appear twice in
116    /// the resulting arena.
117    ///
118    /// See also [`map2_rehash()`](Self::map2_rehash) to use a different hash
119    /// function in the resulting arena.
120    pub fn map2(&self, mapping: &ReverseMapping<I>, f: impl Fn(&T) -> Storage) -> Self
121    where
122        H: Default + BuildHasher,
123    {
124        self.map2_rehash(mapping, f)
125    }
126
127    /// Returns a re-ordered version of this arena based on the given mapping,
128    /// where each item is additionally transformed according to the given
129    /// function `f`.
130    ///
131    /// The transformation function should be injective, i.e. different inputs
132    /// should map to different outputs. Otherwise a value may appear twice in
133    /// the resulting arena.
134    ///
135    /// See also [`map2()`](Self::map2) if the resulting arena uses the same
136    /// hash function.
137    pub fn map2_rehash<HH>(
138        &self,
139        mapping: &ReverseMapping<I>,
140        f: impl Fn(&T) -> Storage,
141    ) -> Arena<T, Storage, HH, I>
142    where
143        HH: Default + BuildHasher,
144    {
145        let mut arena = Arena::with_capacity(mapping.len());
146        for i in mapping.iter() {
147            arena.push(f(self.lookup_ref(Interned::new(i))));
148        }
149        arena
150    }
151}
152
153/// A builder to select items to retain in an [`Arena`].
154///
155/// This struct is created by the [`retain_builder()`](Arena::retain_builder)
156/// method on [`Arena`].
157#[cfg(feature = "retain")]
158pub struct RetainBuilder<T: ?Sized, Storage = T, H = DefaultBuildHasher, I = u32> {
159    len: usize,
160    retained: BitSet,
161    _phantom: PhantomData<Interned<T, Storage, H, I>>,
162}
163
164#[cfg(feature = "retain")]
165impl<T: ?Sized, Storage, H, I> RetainBuilder<T, Storage, H, I>
166where
167    I: Index,
168{
169    /// Marks the given item as retained.
170    ///
171    /// Returns [`true`] if the item is newly inserted and [`false`] if it was
172    /// already inserted before.
173    pub fn insert(&mut self, value: Interned<T, Storage, H, I>) -> bool {
174        self.retained.insert(value.id_().to_usize())
175    }
176
177    /// Returns a mapping to build an [`Arena`] containing only the items that
178    /// have been retained via [`insert()`](Self::insert).
179    pub fn build(self) -> Mapping<I> {
180        Mapping::retain(self.len, |i: I| self.retained.contains(i.to_usize()))
181    }
182}
183
184impl<T, H, I> ArenaSlice<T, H, I>
185where
186    T: Ord,
187    I: Index,
188{
189    /// Returns a sorted mapping of the items in this arena.
190    pub fn sort(&self) -> Mapping<I> {
191        let mut mapping: Vec<I> = (0..self.slices()).map(I::from_usize).collect();
192        mapping.sort_by_cached_key(|i| CustomSliceOrd(self.lookup(InternedSlice::new(*i))));
193        let reverse = ReverseMapping::new(mapping.into_boxed_slice());
194        let forward = reverse.reverse();
195        Mapping { forward, reverse }
196    }
197}
198
199impl<T, H, I> ArenaSlice<T, H, I>
200where
201    I: Index,
202{
203    /// Returns a mapping to build an arena containing only the items of this
204    /// arena that satisfy the given predicate.
205    pub fn retain(&self, filter: impl Fn(InternedSlice<T, H, I>) -> bool) -> Mapping<I> {
206        Mapping::retain(self.slices(), |i| filter(InternedSlice::new(i)))
207    }
208
209    /// Returns a mapping to build an arena containing only the given items.
210    ///
211    /// See also [`retain_builder()`](Self::retain_builder) if you need a more
212    /// flexible way of adding items to retain.
213    #[cfg(feature = "retain")]
214    pub fn retain_values(
215        &self,
216        values: impl Iterator<Item = InternedSlice<T, H, I>>,
217    ) -> Mapping<I> {
218        let mut builder = self.retain_builder();
219        for v in values {
220            builder.insert(v);
221        }
222        builder.build()
223    }
224
225    /// Returns a builder allowing to select items to retain, and create an
226    /// arena containing only these.
227    #[cfg(feature = "retain")]
228    pub fn retain_builder(&self) -> RetainSliceBuilder<T, H, I> {
229        let len = self.slices();
230        RetainSliceBuilder {
231            len,
232            retained: BitSet::with_capacity(len),
233            _phantom: PhantomData,
234        }
235    }
236}
237
238impl<T, H, I> ArenaSlice<T, H, I>
239where
240    T: Default + Clone + Eq + Hash,
241    I: Index,
242{
243    /// Returns a re-ordered version of this arena based on the given mapping.
244    ///
245    /// See also [`map_rehash()`](Self::map_rehash) to use a different hash
246    /// function in the resulting arena.
247    pub fn map(&self, mapping: &ReverseMapping<I>) -> Self
248    where
249        H: Default + BuildHasher,
250    {
251        self.map_rehash(mapping)
252    }
253
254    /// Returns a re-ordered version of this arena based on the given mapping.
255    ///
256    /// See also [`map()`](Self::map) if the resulting arena uses the same hash
257    /// function.
258    pub fn map_rehash<HH>(&self, mapping: &ReverseMapping<I>) -> ArenaSlice<T, HH, I>
259    where
260        HH: Default + BuildHasher,
261    {
262        let mut arena = ArenaSlice::with_capacity(mapping.len(), self.items());
263        for i in mapping.iter() {
264            arena.push(self.lookup(InternedSlice::new(i)));
265        }
266        arena
267    }
268}
269
270impl<T, H, I> ArenaSlice<T, H, I>
271where
272    T: Default + Eq + Hash,
273    I: Index,
274{
275    /// Returns a re-ordered version of this arena based on the given mapping,
276    /// where each slice element is additionally transformed according to
277    /// the given function `f`.
278    ///
279    /// The transformation function should be injective, i.e. different inputs
280    /// should map to different outputs. Otherwise a value may appear twice in
281    /// the resulting arena.
282    ///
283    /// See also [`map2_rehash()`](Self::map2_rehash) to use a different hash
284    /// function in the resulting arena.
285    pub fn map2(&self, mapping: &ReverseMapping<I>, f: impl Fn(&T) -> T) -> Self
286    where
287        H: Default + BuildHasher,
288    {
289        self.map2_rehash(mapping, f)
290    }
291
292    /// Returns a re-ordered version of this arena based on the given mapping,
293    /// where each slice element is additionally transformed according to
294    /// the given function `f`.
295    ///
296    /// The transformation function should be injective, i.e. different inputs
297    /// should map to different outputs. Otherwise a value may appear twice in
298    /// the resulting arena.
299    ///
300    /// See also [`map2()`](Self::map2) if the resulting arena uses the same
301    /// hash function.
302    pub fn map2_rehash<HH>(
303        &self,
304        mapping: &ReverseMapping<I>,
305        f: impl Fn(&T) -> T,
306    ) -> ArenaSlice<T, HH, I>
307    where
308        HH: Default + BuildHasher,
309    {
310        let mut arena = ArenaSlice::with_capacity(mapping.len(), self.items());
311        for i in mapping.iter() {
312            let slice = self.lookup(InternedSlice::new(i));
313            let iter = slice.iter().map(&f);
314            // SAFETY: The iterator length is trusted, as it's a simple mapping
315            // on a slice iterator.
316            unsafe { arena.push_iter_mut_(iter) };
317        }
318        arena
319    }
320}
321
322/// A builder to select items to retain in an [`ArenaSlice`].
323///
324/// This struct is created by the
325/// [`retain_builder()`](ArenaSlice::retain_builder) method on [`ArenaSlice`].
326#[cfg(feature = "retain")]
327pub struct RetainSliceBuilder<T, H = DefaultBuildHasher, I = u32> {
328    len: usize,
329    retained: BitSet,
330    _phantom: PhantomData<InternedSlice<T, H, I>>,
331}
332
333#[cfg(feature = "retain")]
334impl<T, H, I> RetainSliceBuilder<T, H, I>
335where
336    I: Index,
337{
338    /// Marks the given item as retained.
339    ///
340    /// Returns [`true`] if the item is newly inserted and [`false`] if it was
341    /// already inserted before.
342    pub fn insert(&mut self, value: InternedSlice<T, H, I>) -> bool {
343        self.retained.insert(value.id_().to_usize())
344    }
345
346    /// Returns a mapping to build an [`ArenaSlice`] containing only the items
347    /// that have been retained via [`insert()`](Self::insert).
348    pub fn build(self) -> Mapping<I> {
349        Mapping::retain(self.len, |i: I| self.retained.contains(i.to_usize()))
350    }
351}
352
353#[derive(PartialEq, Eq)]
354struct CustomSliceOrd<'a, T>(&'a [T]);
355
356impl<T: Ord> PartialOrd for CustomSliceOrd<'_, T> {
357    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
358        Some(self.cmp(other))
359    }
360}
361
362impl<T: Ord> Ord for CustomSliceOrd<'_, T> {
363    fn cmp(&self, other: &Self) -> Ordering {
364        self.0
365            .len()
366            .cmp(&other.0.len())
367            .then_with(|| self.0.cmp(other.0))
368    }
369}
370
371impl<H, I> ArenaStr<H, I>
372where
373    I: Index,
374{
375    /// Returns a sorted mapping of the items in this arena.
376    pub fn sort(&self) -> Mapping<I> {
377        let mut mapping: Vec<I> = (0..self.strings()).map(I::from_usize).collect();
378        mapping.sort_by_cached_key(|i| CustomStrOrd(self.lookup(InternedStr::new(*i))));
379        let reverse = ReverseMapping::new(mapping.into_boxed_slice());
380        let forward = reverse.reverse();
381        Mapping { forward, reverse }
382    }
383
384    /// Returns a mapping to build an arena containing only the items of this
385    /// arena that satisfy the given predicate.
386    pub fn retain(&self, filter: impl Fn(InternedStr<H, I>) -> bool) -> Mapping<I> {
387        Mapping::retain(self.strings(), |i| filter(InternedStr::new(i)))
388    }
389
390    /// Returns a mapping to build an arena containing only the given items.
391    ///
392    /// See also [`retain_builder()`](Self::retain_builder) if you need a more
393    /// flexible way of adding items to retain.
394    #[cfg(feature = "retain")]
395    pub fn retain_values(&self, values: impl Iterator<Item = InternedStr<H, I>>) -> Mapping<I> {
396        let mut builder = self.retain_builder();
397        for v in values {
398            builder.insert(v);
399        }
400        builder.build()
401    }
402
403    /// Returns a builder allowing to select items to retain, and create an
404    /// arena containing only these.
405    #[cfg(feature = "retain")]
406    pub fn retain_builder(&self) -> RetainStrBuilder<H, I> {
407        let len = self.strings();
408        RetainStrBuilder {
409            len,
410            retained: BitSet::with_capacity(len),
411            _phantom: PhantomData,
412        }
413    }
414}
415
416impl<H, I> ArenaStr<H, I>
417where
418    I: Index,
419{
420    /// Returns a re-ordered version of this arena based on the given mapping.
421    ///
422    /// See also [`map_rehash()`](Self::map_rehash) to use a different hash
423    /// function in the resulting arena.
424    pub fn map(&self, mapping: &ReverseMapping<I>) -> Self
425    where
426        H: Default + BuildHasher,
427    {
428        self.map_rehash(mapping)
429    }
430
431    /// Returns a re-ordered version of this arena based on the given mapping.
432    ///
433    /// See also [`map()`](Self::map) if the resulting arena uses the same hash
434    /// function.
435    pub fn map_rehash<HH>(&self, mapping: &ReverseMapping<I>) -> ArenaStr<HH, I>
436    where
437        HH: Default + BuildHasher,
438    {
439        let mut arena = ArenaStr::with_capacity(mapping.len(), self.bytes());
440        for i in mapping.iter() {
441            arena.push(self.lookup(InternedStr::new(i)));
442        }
443        arena
444    }
445}
446
447/// A builder to select items to retain in an [`ArenaStr`].
448///
449/// This struct is created by the [`retain_builder()`](ArenaStr::retain_builder)
450/// method on [`ArenaStr`].
451#[cfg(feature = "retain")]
452pub struct RetainStrBuilder<H = DefaultBuildHasher, I = u32> {
453    len: usize,
454    retained: BitSet,
455    _phantom: PhantomData<InternedStr<H, I>>,
456}
457
458#[cfg(feature = "retain")]
459impl<H, I> RetainStrBuilder<H, I>
460where
461    I: Index,
462{
463    /// Marks the given item as retained.
464    ///
465    /// Returns [`true`] if the item is newly inserted and [`false`] if it was
466    /// already inserted before.
467    pub fn insert(&mut self, value: InternedStr<H, I>) -> bool {
468        self.retained.insert(value.id_().to_usize())
469    }
470
471    /// Returns a mapping to build an [`ArenaStr`] containing only the items
472    /// that have been retained via [`insert()`](Self::insert).
473    pub fn build(self) -> Mapping<I> {
474        Mapping::retain(self.len, |i: I| self.retained.contains(i.to_usize()))
475    }
476}
477
478#[derive(PartialEq, Eq)]
479struct CustomStrOrd<'a>(&'a str);
480
481impl PartialOrd for CustomStrOrd<'_> {
482    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
483        Some(self.cmp(other))
484    }
485}
486
487impl Ord for CustomStrOrd<'_> {
488    fn cmp(&self, other: &Self) -> Ordering {
489        self.0
490            .len()
491            .cmp(&other.0.len())
492            .then_with(|| self.0.cmp(other.0))
493    }
494}
495
496/// A mapping to re-order items in an [`Arena`], [`ArenaSlice`] or [`ArenaStr`].
497pub struct Mapping<I = u32> {
498    /// Forward mapping, to map interned handles.
499    pub forward: ForwardMapping<I>,
500    /// Reverse mapping, to re-order the arena.
501    pub reverse: ReverseMapping<I>,
502}
503
504impl<I: Index> Mapping<I> {
505    /// Creates a new identity mapping with the given number of items.
506    pub fn identity(count: I) -> Self {
507        Self {
508            forward: ForwardMapping::identity(count),
509            reverse: ReverseMapping::identity(count),
510        }
511    }
512
513    /// Checks wether this mapping is the identity.
514    pub fn is_identity(&self) -> bool {
515        self.forward.is_identity()
516    }
517
518    /// Maps the given interned handle to a handle for the re-ordered arena.
519    ///
520    /// See also [`map_rehash()`](Self::map_rehash) if the resulting arena uses
521    /// a different hash function.
522    pub fn map<T: ?Sized, Storage, H>(
523        &self,
524        index: Interned<T, Storage, H, I>,
525    ) -> Interned<T, Storage, H, I> {
526        self.forward.map(index)
527    }
528
529    /// Maps the given interned handle to a handle for the re-ordered arena.
530    ///
531    /// See also [`map_slice_rehash()`](Self::map_slice_rehash) if the resulting
532    /// arena uses a different hash function.
533    pub fn map_slice<T, H>(&self, index: InternedSlice<T, H, I>) -> InternedSlice<T, H, I> {
534        self.forward.map_slice(index)
535    }
536
537    /// Maps the given interned handle to a handle for the re-ordered arena.
538    ///
539    /// See also [`map_str_rehash()`](Self::map_str_rehash) if the resulting
540    /// arena uses a different hash function.
541    pub fn map_str<H>(&self, index: InternedStr<H, I>) -> InternedStr<H, I> {
542        self.forward.map_str(index)
543    }
544
545    /// Maps the given interned handle to a handle for the re-ordered arena.
546    ///
547    /// See also [`map()`](Self::map) if the resulting arena uses the same hash
548    /// function.
549    pub fn map_rehash<T: ?Sized, Storage, H, HH>(
550        &self,
551        index: Interned<T, Storage, H, I>,
552    ) -> Interned<T, Storage, HH, I> {
553        self.forward.map_rehash(index)
554    }
555
556    /// Maps the given interned handle to a handle for the re-ordered arena.
557    ///
558    /// See also [`map_slice()`](Self::map_slice) if the resulting arena uses
559    /// the same hash function.
560    pub fn map_slice_rehash<T, H, HH>(
561        &self,
562        index: InternedSlice<T, H, I>,
563    ) -> InternedSlice<T, HH, I> {
564        self.forward.map_slice_rehash(index)
565    }
566
567    /// Maps the given interned handle to a handle for the re-ordered arena.
568    ///
569    /// See also [`map_str()`](Self::map_str) if the resulting arena uses the
570    /// same hash function.
571    pub fn map_str_rehash<H, HH>(&self, index: InternedStr<H, I>) -> InternedStr<HH, I> {
572        self.forward.map_str_rehash(index)
573    }
574
575    fn retain(len: usize, filter: impl Fn(I) -> bool) -> Self {
576        let mut reverse = Vec::new();
577        let mut forward = Vec::with_capacity(len);
578        let mut next = I::ZERO;
579        let mut is_identity = true;
580
581        for i in (0..len).map(I::from_usize) {
582            if filter(i) {
583                reverse.push(i);
584                forward.push(next);
585                next.incr();
586            } else {
587                forward.push(I::MAX);
588                is_identity = false;
589            }
590        }
591
592        let reverse = ReverseMapping::new(reverse.into_boxed_slice());
593        let forward = if is_identity {
594            MappingImpl::Identity(I::from_usize(len))
595        } else {
596            MappingImpl::Map(forward.into_boxed_slice())
597        };
598        Self {
599            forward: ForwardMapping(forward),
600            reverse,
601        }
602    }
603}
604
605/// A mapping to re-order items in an [`Arena`], [`ArenaSlice`] or [`ArenaStr`].
606#[cfg_attr(test, derive(PartialEq, Eq, Debug))]
607pub struct ReverseMapping<I = u32>(MappingImpl<I>);
608
609impl<I: Index> ReverseMapping<I> {
610    /// Creates a new identity mapping with the given number of items.
611    fn identity(count: I) -> Self {
612        Self(MappingImpl::Identity(count))
613    }
614
615    fn new(map: Box<[I]>) -> Self {
616        Self(MappingImpl::new(map))
617    }
618
619    /// Returns the number of mapped items.
620    fn len(&self) -> usize {
621        self.0.len().to_usize()
622    }
623
624    fn reverse(&self) -> ForwardMapping<I> {
625        ForwardMapping(self.0.reverse())
626    }
627
628    /// Returns the mapped indices in order.
629    pub fn iter(&self) -> impl ExactSizeIterator<Item = I> {
630        self.0.iter()
631    }
632}
633
634/// A mapping to re-order items in an [`Arena`], [`ArenaSlice`] or [`ArenaStr`].
635#[cfg_attr(test, derive(Clone, PartialEq, Eq, Debug))]
636pub struct ForwardMapping<I = u32>(MappingImpl<I>);
637
638impl<I: Index> ForwardMapping<I> {
639    /// Creates a new identity mapping with the given number of items.
640    pub fn identity(count: I) -> Self {
641        Self(MappingImpl::Identity(count))
642    }
643
644    /// Checks wether this mapping is the identity.
645    pub fn is_identity(&self) -> bool {
646        self.0.is_identity()
647    }
648
649    /// Maps the given interned handle to a handle for the re-ordered arena.
650    ///
651    /// See also [`map_rehash()`](Self::map_rehash) if the resulting arena uses
652    /// a different hash function.
653    pub fn map<T: ?Sized, Storage, H>(
654        &self,
655        index: Interned<T, Storage, H, I>,
656    ) -> Interned<T, Storage, H, I> {
657        self.map_rehash(index)
658    }
659
660    /// Maps the given interned handle to a handle for the re-ordered arena.
661    ///
662    /// See also [`map_slice_rehash()`](Self::map_slice_rehash) if the resulting
663    /// arena uses a different hash function.
664    pub fn map_slice<T, H>(&self, index: InternedSlice<T, H, I>) -> InternedSlice<T, H, I> {
665        self.map_slice_rehash(index)
666    }
667
668    /// Maps the given interned handle to a handle for the re-ordered arena.
669    ///
670    /// See also [`map_str_rehash()`](Self::map_str_rehash) if the resulting
671    /// arena uses a different hash function.
672    pub fn map_str<H>(&self, index: InternedStr<H, I>) -> InternedStr<H, I> {
673        self.map_str_rehash(index)
674    }
675
676    /// Maps the given interned handle to a handle for the re-ordered arena.
677    ///
678    /// See also [`map()`](Self::map) if the resulting arena uses the same hash
679    /// function.
680    pub fn map_rehash<T: ?Sized, Storage, H, HH>(
681        &self,
682        index: Interned<T, Storage, H, I>,
683    ) -> Interned<T, Storage, HH, I> {
684        Interned::new(self.0.at(index.id_()))
685    }
686
687    /// Maps the given interned handle to a handle for the re-ordered arena.
688    ///
689    /// See also [`map_slice()`](Self::map_slice) if the resulting arena uses
690    /// the same hash function.
691    pub fn map_slice_rehash<T, H, HH>(
692        &self,
693        index: InternedSlice<T, H, I>,
694    ) -> InternedSlice<T, HH, I> {
695        InternedSlice::new(self.0.at(index.id_()))
696    }
697
698    /// Maps the given interned handle to a handle for the re-ordered arena.
699    ///
700    /// See also [`map_str()`](Self::map_str) if the resulting arena uses the
701    /// same hash function.
702    pub fn map_str_rehash<H, HH>(&self, index: InternedStr<H, I>) -> InternedStr<HH, I> {
703        InternedStr::new(self.0.at(index.id_()))
704    }
705
706    /// Returned a composition of this mapping followed by the other mapping.
707    ///
708    /// The composition is such that for any interned handle `index`,
709    /// `map1.compose(map2).map(index)` is equal to `map2.map(map1.map(index))`.
710    pub fn compose(self, other: Self) -> Self {
711        Self(self.0.compose(other.0))
712    }
713
714    /// Returns the number of items that are remapped by this mapping.
715    #[cfg(feature = "debug")]
716    pub fn count_remapped(&self) -> usize {
717        self.0.count_remapped()
718    }
719}
720
721#[cfg_attr(test, derive(Clone, PartialEq, Eq, Debug))]
722enum MappingImpl<I> {
723    Identity(I),
724    Map(Box<[I]>),
725}
726
727impl<I: Index> MappingImpl<I> {
728    fn new(map: Box<[I]>) -> Self {
729        // Check if the map is the identity.
730        if map.iter().enumerate().all(|(i, j)| i == j.to_usize()) {
731            MappingImpl::Identity(I::from_usize(map.len()))
732        } else {
733            MappingImpl::Map(map)
734        }
735    }
736
737    /// Checks wether this mapping is the identity.
738    fn is_identity(&self) -> bool {
739        match self {
740            Self::Identity(_) => true,
741            Self::Map(_) => false,
742        }
743    }
744
745    fn len(&self) -> I {
746        match self {
747            Self::Identity(len) => *len,
748            Self::Map(map) => I::from_usize(map.len()),
749        }
750    }
751
752    fn at(&self, index: I) -> I {
753        match self {
754            MappingImpl::Identity(_) => index,
755            MappingImpl::Map(map) => map[index.to_usize()],
756        }
757    }
758
759    fn compose(self, other: MappingImpl<I>) -> Self {
760        let len = self.len();
761        assert_eq!(len, other.len());
762        match (self, other) {
763            (MappingImpl::Identity(len), MappingImpl::Identity(_)) => MappingImpl::Identity(len),
764            (MappingImpl::Map(map), MappingImpl::Identity(_))
765            | (MappingImpl::Identity(_), MappingImpl::Map(map)) => MappingImpl::Map(map),
766            (MappingImpl::Map(left), MappingImpl::Map(right)) => {
767                let map = left.iter().map(|i| right[i.to_usize()]).collect();
768                Self::new(map)
769            }
770        }
771    }
772
773    fn reverse(&self) -> MappingImpl<I> {
774        match self {
775            MappingImpl::Identity(len) => MappingImpl::Identity(*len),
776            MappingImpl::Map(map) => {
777                let mut reverse = vec![I::ZERO; map.len()];
778                for i in 0..map.len() {
779                    reverse[map[i].to_usize()] = I::from_usize(i);
780                }
781                MappingImpl::Map(reverse.into_boxed_slice())
782            }
783        }
784    }
785
786    fn iter(&self) -> impl ExactSizeIterator<Item = I> {
787        match self {
788            Self::Identity(len) => Either::Left((0..len.to_usize()).map(I::from_usize)),
789            Self::Map(map) => Either::Right(map.iter().copied()),
790        }
791    }
792
793    /// Returns the number of items that are remapped by this mapping.
794    #[cfg(feature = "debug")]
795    fn count_remapped(&self) -> usize {
796        match self {
797            Self::Identity(_) => 0,
798            Self::Map(map) => map
799                .iter()
800                .enumerate()
801                .filter(|&(i, j)| i != j.to_usize())
802                .count(),
803        }
804    }
805}
806
807#[cfg(test)]
808mod test {
809    use super::*;
810    use crate::DefaultBuildHasher;
811
812    type InternedU32 = Interned<u32, u32, DefaultBuildHasher, u32>;
813
814    #[test]
815    fn arena_str_sort() {
816        let mut arena: ArenaStr = ArenaStr::default();
817        arena.push("bbbb");
818        arena.push("dd");
819        arena.push("e");
820        arena.push("aaaaa");
821        arena.push("ccc");
822
823        let mapping = arena.sort();
824        assert!(!mapping.is_identity());
825        assert_eq!(
826            mapping.reverse,
827            ReverseMapping(MappingImpl::Map(
828                [2, 1, 4, 0, 3].into_iter().map(Index::from_usize).collect()
829            ))
830        );
831        assert_eq!(
832            mapping.forward,
833            ForwardMapping(MappingImpl::Map(
834                [3, 1, 0, 4, 2].into_iter().map(Index::from_usize).collect()
835            ))
836        );
837    }
838
839    #[test]
840    fn arena_str_sort_identity() {
841        let mut arena: ArenaStr = ArenaStr::default();
842        arena.push("e");
843        arena.push("dd");
844        arena.push("ccc");
845        arena.push("bbbb");
846        arena.push("aaaaa");
847
848        let mapping = arena.sort();
849        assert!(mapping.is_identity());
850        assert_eq!(
851            mapping.reverse,
852            ReverseMapping(MappingImpl::Identity(Index::from_usize(5)))
853        );
854        assert_eq!(
855            mapping.forward,
856            ForwardMapping(MappingImpl::Identity(Index::from_usize(5)))
857        );
858    }
859
860    #[test]
861    fn arena_str_sort_map() {
862        let mut arena: ArenaStr = ArenaStr::default();
863        arena.push("bbbb");
864        arena.push("dd");
865        arena.push("e");
866        arena.push("aaaaa");
867        arena.push("ccc");
868
869        let mapping = arena.sort();
870        let sorted: ArenaStr = arena.map(&mapping.reverse);
871
872        let mut expected = ArenaStr::default();
873        expected.push("e");
874        expected.push("dd");
875        expected.push("ccc");
876        expected.push("bbbb");
877        expected.push("aaaaa");
878
879        assert_eq!(sorted, expected);
880    }
881
882    #[test]
883    fn arena_str_retain_identity() {
884        let mut arena: ArenaStr = ArenaStr::default();
885        arena.push("e");
886        arena.push("dd");
887        arena.push("ccc");
888        arena.push("bbbb");
889        arena.push("aaaaa");
890
891        let mapping = arena.retain(|i| arena.lookup(i).len() <= 3);
892        assert!(!mapping.is_identity());
893        assert_eq!(
894            mapping.reverse,
895            ReverseMapping(MappingImpl::Identity(Index::from_usize(3)))
896        );
897        assert_eq!(
898            mapping.forward,
899            ForwardMapping(MappingImpl::Map(Box::new([
900                Index::from_usize(0),
901                Index::from_usize(1),
902                Index::from_usize(2),
903                Index::MAX,
904                Index::MAX
905            ])))
906        );
907    }
908
909    #[test]
910    fn arena_str_retain() {
911        let mut arena: ArenaStr = ArenaStr::default();
912        let _ = arena.intern_mut("bbbb");
913        let d = arena.intern_mut("dd");
914        let e = arena.intern_mut("e");
915        let _ = arena.intern_mut("aaaaa");
916        let c = arena.intern_mut("ccc");
917
918        let mapping = arena.retain(|i| arena.lookup(i).len() <= 3);
919        let filtered: ArenaStr = arena.map(&mapping.reverse);
920
921        let mut expected = ArenaStr::default();
922        expected.push("dd");
923        expected.push("e");
924        expected.push("ccc");
925
926        assert_eq!(filtered, expected);
927
928        let cc = mapping.forward.map_str(c);
929        let dd = mapping.forward.map_str(d);
930        let ee = mapping.forward.map_str(e);
931        assert_eq!(filtered.lookup(cc), "ccc");
932        assert_eq!(filtered.lookup(dd), "dd");
933        assert_eq!(filtered.lookup(ee), "e");
934    }
935
936    #[cfg(feature = "retain")]
937    #[test]
938    fn arena_str_retain_values() {
939        let mut arena: ArenaStr = ArenaStr::default();
940        let _ = arena.intern_mut("bbbb");
941        let d = arena.intern_mut("dd");
942        let e = arena.intern_mut("e");
943        let _ = arena.intern_mut("aaaaa");
944        let c = arena.intern_mut("ccc");
945
946        let mapping = arena.retain_values([d, e, c].into_iter());
947        let filtered: ArenaStr = arena.map(&mapping.reverse);
948
949        let mut expected = ArenaStr::default();
950        expected.push("dd");
951        expected.push("e");
952        expected.push("ccc");
953
954        assert_eq!(filtered, expected);
955
956        let cc = mapping.forward.map_str(c);
957        let dd = mapping.forward.map_str(d);
958        let ee = mapping.forward.map_str(e);
959        assert_eq!(filtered.lookup(cc), "ccc");
960        assert_eq!(filtered.lookup(dd), "dd");
961        assert_eq!(filtered.lookup(ee), "e");
962    }
963
964    #[cfg(feature = "retain")]
965    #[test]
966    fn arena_str_retain_builder() {
967        let mut arena: ArenaStr = ArenaStr::default();
968        let _ = arena.intern_mut("bbbb");
969        let d = arena.intern_mut("dd");
970        let e = arena.intern_mut("e");
971        let _ = arena.intern_mut("aaaaa");
972        let c = arena.intern_mut("ccc");
973
974        let mut builder = arena.retain_builder();
975        assert!(builder.insert(d));
976        assert!(builder.insert(e));
977        assert!(builder.insert(c));
978        assert!(!builder.insert(e));
979        let mapping = builder.build();
980        let filtered: ArenaStr = arena.map(&mapping.reverse);
981
982        let mut expected = ArenaStr::default();
983        expected.push("dd");
984        expected.push("e");
985        expected.push("ccc");
986
987        assert_eq!(filtered, expected);
988
989        let cc = mapping.forward.map_str(c);
990        let dd = mapping.forward.map_str(d);
991        let ee = mapping.forward.map_str(e);
992        assert_eq!(filtered.lookup(cc), "ccc");
993        assert_eq!(filtered.lookup(dd), "dd");
994        assert_eq!(filtered.lookup(ee), "e");
995    }
996
997    #[test]
998    fn reverse_mapping_iter() {
999        let mapping = ReverseMapping(MappingImpl::<u32>::new(Box::new([2, 1, 4, 0, 3])));
1000        assert_eq!(mapping.iter().collect::<Vec<_>>(), vec![2, 1, 4, 0, 3]);
1001    }
1002
1003    #[test]
1004    fn reverse_mapping_reverse() {
1005        let mapping = ReverseMapping(MappingImpl::<u32>::new(Box::new([2, 1, 4, 0, 3])));
1006        assert_eq!(
1007            mapping.reverse(),
1008            ForwardMapping(MappingImpl::Map(Box::new([3, 1, 0, 4, 2])))
1009        );
1010
1011        let mapping = ReverseMapping(MappingImpl::<u32>::new(Box::new([0, 1, 2, 3, 4])));
1012        assert_eq!(mapping.reverse(), ForwardMapping(MappingImpl::Identity(5)));
1013    }
1014
1015    #[test]
1016    fn forward_mapping_map() {
1017        let mapping = ForwardMapping(MappingImpl::<u32>::Map(Box::new([3, 1, 0, 4, 2])));
1018        assert_eq!(mapping.map(InternedU32::new(0)), InternedU32::new(3));
1019        assert_eq!(mapping.map(InternedU32::new(1)), InternedU32::new(1));
1020        assert_eq!(mapping.map(InternedU32::new(2)), InternedU32::new(0));
1021        assert_eq!(mapping.map(InternedU32::new(3)), InternedU32::new(4));
1022        assert_eq!(mapping.map(InternedU32::new(4)), InternedU32::new(2));
1023
1024        let mapping = ForwardMapping(MappingImpl::Identity(5));
1025        assert_eq!(mapping.map(InternedU32::new(0)), InternedU32::new(0));
1026        assert_eq!(mapping.map(InternedU32::new(1)), InternedU32::new(1));
1027        assert_eq!(mapping.map(InternedU32::new(2)), InternedU32::new(2));
1028        assert_eq!(mapping.map(InternedU32::new(3)), InternedU32::new(3));
1029        assert_eq!(mapping.map(InternedU32::new(4)), InternedU32::new(4));
1030    }
1031
1032    #[test]
1033    fn forward_mapping_compose() {
1034        let mapping1 = ForwardMapping(MappingImpl::<u32>::Map(Box::new([3, 1, 0, 4, 2])));
1035        let mapping2 = ForwardMapping(MappingImpl::<u32>::Map(Box::new([4, 0, 2, 3, 1])));
1036        let composed = mapping1.clone().compose(mapping2.clone());
1037        assert_eq!(
1038            composed,
1039            ForwardMapping(MappingImpl::Map(Box::new([3, 0, 4, 1, 2])))
1040        );
1041
1042        for i in 0..5 {
1043            let index = InternedU32::new(i);
1044            assert_eq!(composed.map(index), mapping2.map(mapping1.map(index)));
1045        }
1046    }
1047
1048    #[cfg(feature = "debug")]
1049    #[test]
1050    fn forward_mapping_count_remapped() {
1051        let mapping = ForwardMapping(MappingImpl::<u32>::Map(Box::new([3, 1, 0, 4, 2])));
1052        assert_eq!(mapping.count_remapped(), 4);
1053    }
1054}
blazinterner/mapping.rs

blazinterner/
mapping.rs
