rusty_perm/
from_sorting.rs

1use crate::common::*;
2
3use algorithm::*;
4
5/// An operator that builds a permutation type by sorting slice-like types.
6pub trait PermFromSorting<S, T>
7where
8    S: AsRef<[T]>,
9    Self: Sized,
10{
11    type Output;
12
13    /// Builds a permutation by sorting a slice-like type.
14    fn from_sort(vec: S) -> Self::Output
15    where
16        T: Ord;
17
18    /// Builds a permutation by sorting a slice-like type with a comparing function.
19    fn from_sort_by<F>(vec: S, compare: F) -> Self::Output
20    where
21        F: FnMut(&T, &T) -> Ordering;
22
23    /// Builds a permutation by sorting a slice-like type with a key function.
24    fn from_sort_by_key<B, F>(vec: S, f: F) -> Self::Output
25    where
26        B: Ord,
27        F: FnMut(&T) -> B;
28
29    /// Builds a permutation by sorting a slice-like type with a key function. The key is not re-computed twice.
30    fn from_sort_by_cached_key<B, F>(vec: S, f: F) -> Self::Output
31    where
32        B: Ord,
33        F: FnMut(&T) -> B;
34}
35
36mod without_std {
37    use super::*;
38    use crate::perm_type::PermS;
39
40    impl<T, const SIZE: usize> PermFromSorting<[T; SIZE], T> for PermS<SIZE> {
41        type Output = Self;
42
43        fn from_sort(vec: [T; SIZE]) -> Self::Output
44        where
45            T: Ord,
46        {
47            Self::from_sort(&vec)
48        }
49
50        fn from_sort_by<F>(vec: [T; SIZE], compare: F) -> Self::Output
51        where
52            F: FnMut(&T, &T) -> Ordering,
53        {
54            Self::from_sort_by(&vec, compare)
55        }
56
57        fn from_sort_by_key<B, F>(vec: [T; SIZE], f: F) -> Self::Output
58        where
59            B: Ord,
60            F: FnMut(&T) -> B,
61        {
62            Self::from_sort_by_key(&vec, f)
63        }
64
65        fn from_sort_by_cached_key<B, F>(vec: [T; SIZE], f: F) -> Self::Output
66        where
67            B: Ord,
68            F: FnMut(&T) -> B,
69        {
70            Self::from_sort_by_cached_key(&vec, f)
71        }
72    }
73
74    impl<T, const SIZE: usize> PermFromSorting<&[T; SIZE], T> for PermS<SIZE> {
75        type Output = Self;
76
77        fn from_sort(vec: &[T; SIZE]) -> Self::Output
78        where
79            T: Ord,
80        {
81            let mut perm = Self::identity();
82            sort(&mut perm.indices, vec);
83            perm
84        }
85
86        fn from_sort_by<F>(vec: &[T; SIZE], compare: F) -> Self::Output
87        where
88            F: FnMut(&T, &T) -> Ordering,
89        {
90            let mut perm = Self::identity();
91            sort_by(&mut perm.indices, vec, compare);
92            perm
93        }
94
95        fn from_sort_by_key<B, F>(vec: &[T; SIZE], f: F) -> Self::Output
96        where
97            B: Ord,
98            F: FnMut(&T) -> B,
99        {
100            let mut perm = Self::identity();
101            sort_by_key(&mut perm.indices, vec, f);
102            perm
103        }
104
105        fn from_sort_by_cached_key<B, F>(vec: &[T; SIZE], f: F) -> Self::Output
106        where
107            B: Ord,
108            F: FnMut(&T) -> B,
109        {
110            let mut perm = Self::identity();
111            sort_by_cached_key(&mut perm.indices, vec, f);
112            perm
113        }
114    }
115
116    impl<T, const SIZE: usize> PermFromSorting<&[T], T> for PermS<SIZE> {
117        type Output = Option<Self>;
118
119        fn from_sort(vec: &[T]) -> Self::Output
120        where
121            T: Ord,
122        {
123            if vec.len() != SIZE {
124                return None;
125            }
126            let mut perm = Self::identity();
127            sort(&mut perm.indices, vec);
128            Some(perm)
129        }
130
131        fn from_sort_by<F>(vec: &[T], compare: F) -> Self::Output
132        where
133            F: FnMut(&T, &T) -> Ordering,
134        {
135            if vec.len() != SIZE {
136                return None;
137            }
138            let mut perm = Self::identity();
139            sort_by(&mut perm.indices, vec, compare);
140            Some(perm)
141        }
142
143        fn from_sort_by_key<B, F>(vec: &[T], f: F) -> Self::Output
144        where
145            B: Ord,
146            F: FnMut(&T) -> B,
147        {
148            if vec.len() != SIZE {
149                return None;
150            }
151            let mut perm = Self::identity();
152            sort_by_key(&mut perm.indices, vec, f);
153            Some(perm)
154        }
155
156        fn from_sort_by_cached_key<B, F>(vec: &[T], f: F) -> Self::Output
157        where
158            B: Ord,
159            F: FnMut(&T) -> B,
160        {
161            if vec.len() != SIZE {
162                return None;
163            }
164            let mut perm = Self::identity();
165            sort_by_cached_key(&mut perm.indices, vec, f);
166            Some(perm)
167        }
168    }
169
170    #[cfg(test)]
171    mod tests {
172        use super::*;
173        use crate::perm_trait::Permutation;
174        use rand::prelude::*;
175
176        #[test]
177        fn static_perm_from_array() {
178            const SIZE: usize = 1024;
179            let mut rng = rand::thread_rng();
180
181            for _ in 0..100 {
182                let array = {
183                    let mut array = [0isize; SIZE];
184                    rng.fill(&mut array);
185                    array
186                };
187
188                {
189                    let sorted = {
190                        let mut array = array.clone();
191                        array.sort();
192                        array
193                    };
194
195                    let perm = PermS::from_sort(&array);
196                    perm.indices().iter().enumerate().for_each(|(dst, &src)| {
197                        assert_eq!(sorted[dst], array[src]);
198                    });
199                }
200
201                {
202                    let sorted = {
203                        let mut array = array.clone();
204                        array.sort_by(|lhs, rhs| lhs.cmp(rhs));
205                        array
206                    };
207
208                    let perm = PermS::from_sort_by(&array, |lhs, rhs| lhs.cmp(rhs));
209                    perm.indices().iter().enumerate().for_each(|(dst, &src)| {
210                        assert_eq!(sorted[dst], array[src]);
211                    });
212                }
213
214                {
215                    let sorted = {
216                        let mut array = array.clone();
217                        array.sort_by_key(|value| -value);
218                        array
219                    };
220
221                    let perm = PermS::from_sort_by_key(&array, |value| -value);
222                    perm.indices().iter().enumerate().for_each(|(dst, &src)| {
223                        assert_eq!(sorted[dst], array[src]);
224                    });
225                }
226
227                {
228                    let sorted = {
229                        let mut array = array.clone();
230                        array.sort_by_cached_key(|value| -value);
231                        array
232                    };
233
234                    let perm = PermS::from_sort_by_cached_key(&array, |value| -value);
235                    perm.indices().iter().enumerate().for_each(|(dst, &src)| {
236                        assert_eq!(sorted[dst], array[src]);
237                    });
238                }
239            }
240        }
241    }
242}
243
244#[cfg(feature = "std")]
245mod with_std {
246    use super::*;
247    use crate::perm_type::{PermD, PermS};
248
249    impl<T, const SIZE: usize> PermFromSorting<[T; SIZE], T> for PermD {
250        type Output = Self;
251
252        fn from_sort(vec: [T; SIZE]) -> Self::Output
253        where
254            T: Ord,
255        {
256            Self::from_sort(vec.as_ref())
257        }
258
259        fn from_sort_by<F>(vec: [T; SIZE], compare: F) -> Self::Output
260        where
261            F: FnMut(&T, &T) -> Ordering,
262        {
263            Self::from_sort_by(vec.as_ref(), compare)
264        }
265
266        fn from_sort_by_key<B, F>(vec: [T; SIZE], f: F) -> Self::Output
267        where
268            B: Ord,
269            F: FnMut(&T) -> B,
270        {
271            Self::from_sort_by_key(vec.as_ref(), f)
272        }
273
274        fn from_sort_by_cached_key<B, F>(vec: [T; SIZE], f: F) -> Self::Output
275        where
276            B: Ord,
277            F: FnMut(&T) -> B,
278        {
279            Self::from_sort_by_cached_key(vec.as_ref(), f)
280        }
281    }
282
283    impl<T, const SIZE: usize> PermFromSorting<&[T; SIZE], T> for PermD {
284        type Output = Self;
285
286        fn from_sort(vec: &[T; SIZE]) -> Self::Output
287        where
288            T: Ord,
289        {
290            Self::from_sort(vec.as_ref())
291        }
292
293        fn from_sort_by<F>(vec: &[T; SIZE], compare: F) -> Self::Output
294        where
295            F: FnMut(&T, &T) -> Ordering,
296        {
297            Self::from_sort_by(vec.as_ref(), compare)
298        }
299
300        fn from_sort_by_key<B, F>(vec: &[T; SIZE], f: F) -> Self::Output
301        where
302            B: Ord,
303            F: FnMut(&T) -> B,
304        {
305            Self::from_sort_by_key(vec.as_ref(), f)
306        }
307
308        fn from_sort_by_cached_key<B, F>(vec: &[T; SIZE], f: F) -> Self::Output
309        where
310            B: Ord,
311            F: FnMut(&T) -> B,
312        {
313            Self::from_sort_by_cached_key(vec.as_ref(), f)
314        }
315    }
316
317    impl<T> PermFromSorting<&[T], T> for PermD {
318        type Output = Self;
319
320        fn from_sort(vec: &[T]) -> Self::Output
321        where
322            T: Ord,
323        {
324            let mut perm = Self::identity(vec.len());
325            sort(&mut perm.indices, vec);
326            perm
327        }
328
329        fn from_sort_by<F>(vec: &[T], compare: F) -> Self::Output
330        where
331            F: FnMut(&T, &T) -> Ordering,
332        {
333            let mut perm = Self::identity(vec.len());
334            sort_by(&mut perm.indices, vec, compare);
335            perm
336        }
337
338        fn from_sort_by_key<B, F>(vec: &[T], f: F) -> Self::Output
339        where
340            B: Ord,
341            F: FnMut(&T) -> B,
342        {
343            let mut perm = Self::identity(vec.len());
344            sort_by_key(&mut perm.indices, vec, f);
345            perm
346        }
347
348        fn from_sort_by_cached_key<B, F>(vec: &[T], f: F) -> Self::Output
349        where
350            B: Ord,
351            F: FnMut(&T) -> B,
352        {
353            let mut perm = Self::identity(vec.len());
354            sort_by_cached_key(&mut perm.indices, vec, f);
355            perm
356        }
357    }
358
359    impl<T> PermFromSorting<Vec<T>, T> for PermD {
360        type Output = Self;
361
362        fn from_sort(vec: Vec<T>) -> Self::Output
363        where
364            T: Ord,
365        {
366            Self::from_sort(vec.as_slice())
367        }
368
369        fn from_sort_by<F>(vec: Vec<T>, compare: F) -> Self::Output
370        where
371            F: FnMut(&T, &T) -> Ordering,
372        {
373            Self::from_sort_by(vec.as_slice(), compare)
374        }
375
376        fn from_sort_by_key<B, F>(vec: Vec<T>, f: F) -> Self::Output
377        where
378            B: Ord,
379            F: FnMut(&T) -> B,
380        {
381            Self::from_sort_by_key(vec.as_slice(), f)
382        }
383
384        fn from_sort_by_cached_key<B, F>(vec: Vec<T>, f: F) -> Self::Output
385        where
386            B: Ord,
387            F: FnMut(&T) -> B,
388        {
389            Self::from_sort_by_cached_key(vec.as_slice(), f)
390        }
391    }
392
393    impl<T, const SIZE: usize> PermFromSorting<Vec<T>, T> for PermS<SIZE> {
394        type Output = Option<Self>;
395
396        fn from_sort(vec: Vec<T>) -> Self::Output
397        where
398            T: Ord,
399        {
400            Self::from_sort(vec.as_slice())
401        }
402
403        fn from_sort_by<F>(vec: Vec<T>, compare: F) -> Self::Output
404        where
405            F: FnMut(&T, &T) -> Ordering,
406        {
407            Self::from_sort_by(vec.as_slice(), compare)
408        }
409
410        fn from_sort_by_key<B, F>(vec: Vec<T>, f: F) -> Self::Output
411        where
412            B: Ord,
413            F: FnMut(&T) -> B,
414        {
415            Self::from_sort_by_key(vec.as_slice(), f)
416        }
417
418        fn from_sort_by_cached_key<B, F>(vec: Vec<T>, f: F) -> Self::Output
419        where
420            B: Ord,
421            F: FnMut(&T) -> B,
422        {
423            Self::from_sort_by_cached_key(vec.as_slice(), f)
424        }
425    }
426
427    #[cfg(test)]
428    mod tests {
429        use super::*;
430        use crate::perm_trait::Permutation;
431        use rand::prelude::*;
432
433        #[test]
434        fn static_perm_from_vec() {
435            const SIZE: usize = 1024;
436            let mut rng = rand::thread_rng();
437
438            for _ in 0..100 {
439                let array = {
440                    let mut array = vec![0isize; SIZE];
441                    rng.fill(array.as_mut_slice());
442                    array
443                };
444
445                {
446                    let sorted = {
447                        let mut array = array.clone();
448                        array.sort();
449                        array
450                    };
451
452                    let perm = PermS::<SIZE>::from_sort(array.as_slice()).unwrap();
453                    perm.indices().iter().enumerate().for_each(|(dst, &src)| {
454                        assert_eq!(sorted[dst], array[src]);
455                    });
456                }
457
458                {
459                    let sorted = {
460                        let mut array = array.clone();
461                        array.sort_by(|lhs, rhs| lhs.cmp(rhs));
462                        array
463                    };
464
465                    let perm =
466                        PermS::<SIZE>::from_sort_by(array.as_slice(), |lhs, rhs| lhs.cmp(rhs))
467                            .unwrap();
468                    perm.indices().iter().enumerate().for_each(|(dst, &src)| {
469                        assert_eq!(sorted[dst], array[src]);
470                    });
471                }
472
473                {
474                    let sorted = {
475                        let mut array = array.clone();
476                        array.sort_by_key(|value| -value);
477                        array
478                    };
479
480                    let perm =
481                        PermS::<SIZE>::from_sort_by_key(array.as_slice(), |value| -value).unwrap();
482                    perm.indices().iter().enumerate().for_each(|(dst, &src)| {
483                        assert_eq!(sorted[dst], array[src]);
484                    });
485                }
486
487                {
488                    let sorted = {
489                        let mut array = array.clone();
490                        array.sort_by_cached_key(|value| -value);
491                        array
492                    };
493
494                    let perm =
495                        PermS::<SIZE>::from_sort_by_cached_key(array.as_slice(), |value| -value)
496                            .unwrap();
497                    perm.indices().iter().enumerate().for_each(|(dst, &src)| {
498                        assert_eq!(sorted[dst], array[src]);
499                    });
500                }
501            }
502        }
503
504        #[test]
505        fn dynamic_perm_from_vec() {
506            const SIZE: usize = 1024;
507            let mut rng = rand::thread_rng();
508
509            for _ in 0..100 {
510                let array = {
511                    let mut array = vec![0isize; SIZE];
512                    rng.fill(array.as_mut_slice());
513                    array
514                };
515
516                {
517                    let sorted = {
518                        let mut array = array.clone();
519                        array.sort();
520                        array
521                    };
522
523                    let perm = PermD::from_sort(array.as_slice());
524                    perm.indices().iter().enumerate().for_each(|(dst, &src)| {
525                        assert_eq!(sorted[dst], array[src]);
526                    });
527                }
528
529                {
530                    let sorted = {
531                        let mut array = array.clone();
532                        array.sort_by(|lhs, rhs| lhs.cmp(rhs));
533                        array
534                    };
535
536                    let perm = PermD::from_sort_by(array.as_slice(), |lhs, rhs| lhs.cmp(rhs));
537                    perm.indices().iter().enumerate().for_each(|(dst, &src)| {
538                        assert_eq!(sorted[dst], array[src]);
539                    });
540                }
541
542                {
543                    let sorted = {
544                        let mut array = array.clone();
545                        array.sort_by_key(|value| -value);
546                        array
547                    };
548
549                    let perm = PermD::from_sort_by_key(array.as_slice(), |value| -value);
550                    perm.indices().iter().enumerate().for_each(|(dst, &src)| {
551                        assert_eq!(sorted[dst], array[src]);
552                    });
553                }
554
555                {
556                    let sorted = {
557                        let mut array = array.clone();
558                        array.sort_by_cached_key(|value| -value);
559                        array
560                    };
561
562                    let perm = PermD::from_sort_by_cached_key(array.as_slice(), |value| -value);
563                    perm.indices().iter().enumerate().for_each(|(dst, &src)| {
564                        assert_eq!(sorted[dst], array[src]);
565                    });
566                }
567            }
568        }
569    }
570}
571
572#[cfg(not(feature = "std"))]
573mod algorithm {
574    use super::*;
575
576    pub fn sort<T>(identity: &mut [usize], vec: &[T])
577    where
578        T: Ord,
579    {
580        quicksort(identity, |&lhs, &rhs| vec[lhs].cmp(&vec[rhs]));
581    }
582
583    pub fn sort_by<T, F>(identity: &mut [usize], vec: &[T], mut compare: F)
584    where
585        F: FnMut(&T, &T) -> Ordering,
586    {
587        quicksort(identity, |&lhs, &rhs| compare(&vec[lhs], &vec[rhs]));
588    }
589
590    pub fn sort_by_key<T, B, F>(identity: &mut [usize], vec: &[T], mut f: F)
591    where
592        B: Ord,
593        F: FnMut(&T) -> B,
594    {
595        quicksort(identity, |&lhs, &rhs| f(&vec[lhs]).cmp(&f(&vec[rhs])));
596    }
597
598    pub fn sort_by_cached_key<T, B, F>(identity: &mut [usize], vec: &[T], mut f: F)
599    where
600        B: Ord,
601        F: FnMut(&T) -> B,
602    {
603        quicksort(identity, |&lhs, &rhs| f(&vec[lhs]).cmp(&f(&vec[rhs])));
604    }
605
606    fn quicksort<T, F>(slice: &mut [T], mut compare: F)
607    where
608        F: FnMut(&T, &T) -> Ordering,
609    {
610        unsafe {
611            quicksort_unsafe(slice.as_mut_ptr(), slice.len(), &mut compare);
612        }
613    }
614
615    unsafe fn quicksort_unsafe<T, F>(slice: *mut T, len: usize, compare: &mut F)
616    where
617        F: FnMut(&T, &T) -> Ordering,
618    {
619        if len <= 1 {
620            return;
621        }
622
623        let mut lid = 1;
624        let mut rid = len;
625
626        // partition
627        while lid < rid {
628            match compare(slice.add(lid).as_ref().unwrap(), slice.as_ref().unwrap()) {
629                Ordering::Less | Ordering::Equal => lid += 1,
630                Ordering::Greater => {
631                    rid -= 1;
632                    mem::swap(
633                        slice.add(lid).as_mut().unwrap(),
634                        slice.add(rid).as_mut().unwrap(),
635                    );
636                }
637            }
638        }
639
640        // move pivot
641        mem::swap(
642            slice.as_mut().unwrap(),
643            slice.add(lid - 1).as_mut().unwrap(),
644        );
645
646        quicksort_unsafe(slice, lid, compare);
647        quicksort_unsafe(slice.add(lid), len - lid, compare);
648    }
649
650    #[cfg(test)]
651    mod tests {
652        use super::*;
653        use rand::prelude::*;
654
655        #[test]
656        fn quicksort_test() {
657            let mut rng = rand::thread_rng();
658
659            {
660                let mut values = [0; 0];
661                quicksort(&mut values, |lhs, rhs| lhs.cmp(rhs));
662            }
663
664            {
665                let value: usize = rng.gen();
666                let mut values = [value];
667                quicksort(&mut values, |lhs, rhs| lhs.cmp(rhs));
668                assert!(values[0] == value);
669            }
670
671            for _ in 0..100 {
672                let first: usize = rng.gen();
673                let second: usize = rng.gen();
674                let mut values = [first, second];
675                quicksort(&mut values, |lhs, rhs| lhs.cmp(rhs));
676
677                if first < second {
678                    assert!(values == [first, second]);
679                } else {
680                    assert!(values == [second, first]);
681                }
682            }
683
684            {
685                for _ in 0..1000 {
686                    let mut values = [0usize; 1024];
687                    rng.fill(&mut values[..]);
688                    quicksort(&mut values, |lhs, rhs| lhs.cmp(rhs));
689                    let is_correct = values
690                        .iter()
691                        .scan(None, |prev, &curr| {
692                            let orig_prev = *prev;
693                            *prev = Some(curr);
694                            let correct = orig_prev.map(|prev| prev <= curr).unwrap_or(true);
695                            Some(correct)
696                        })
697                        .all(|correct| correct);
698                    assert!(is_correct);
699                }
700            }
701        }
702    }
703}
704
705#[cfg(feature = "std")]
706mod algorithm {
707    use super::*;
708
709    pub fn sort<T>(identity: &mut [usize], vec: &[T])
710    where
711        T: Ord,
712    {
713        identity.sort_by_key(|&index| &vec[index]);
714    }
715
716    pub fn sort_by<T, F>(identity: &mut [usize], vec: &[T], mut compare: F)
717    where
718        F: FnMut(&T, &T) -> Ordering,
719    {
720        identity.sort_by(|&lhs, &rhs| compare(&vec[lhs], &vec[rhs]));
721    }
722
723    pub fn sort_by_key<T, B, F>(identity: &mut [usize], vec: &[T], mut f: F)
724    where
725        B: Ord,
726        F: FnMut(&T) -> B,
727    {
728        identity.sort_by_key(|&index| f(&vec[index]));
729    }
730
731    pub fn sort_by_cached_key<T, B, F>(identity: &mut [usize], vec: &[T], mut f: F)
732    where
733        B: Ord,
734        F: FnMut(&T) -> B,
735    {
736        identity.sort_by_cached_key(|&index| f(&vec[index]));
737    }
738}
rusty_perm/from_sorting.rs

rusty_perm/
from_sorting.rs
