compression/
bucket_sort.rs

1//! rust-compression
2//!
3//! # Licensing
4//! This Source Code is subject to the terms of the Mozilla Public License
5//! version 2.0 (the "License"). You can obtain a copy of the License at
6//! <http://mozilla.org/MPL/2.0/>.
7#![cfg(any(feature = "bzip2", feature = "deflate", feature = "lzhuf"))]
8
9use crate::core::ops::{Add, Sub};
10use crate::core::usize;
11#[cfg(not(feature = "std"))]
12#[allow(unused_imports)]
13use alloc::vec;
14#[cfg(not(feature = "std"))]
15use alloc::vec::Vec;
16use num_traits::{cast, Bounded, NumCast};
17
18pub(crate) trait BucketSort {
19    type Item;
20    fn bucket_sort_by_key<
21        K: Clone + Add + Sub<Output = K> + NumCast,
22        F: Fn(&Self::Item) -> K,
23    >(
24        &self,
25        key_selector: F,
26        min: K,
27        max: K,
28    ) -> Vec<Self::Item>;
29
30    fn bucket_sort_all_by_key<K, F>(&self, key_selector: F) -> Vec<Self::Item>
31    where
32        K: Bounded + Clone + Add + Sub<Output = K> + NumCast,
33        F: Fn(&Self::Item) -> K,
34    {
35        self.bucket_sort_by_key(
36            key_selector,
37            Bounded::min_value(),
38            Bounded::max_value(),
39        )
40    }
41}
42
43impl<T: Clone> BucketSort for [T] {
44    type Item = T;
45    fn bucket_sort_by_key<
46        K: Clone + Add + Sub<Output = K> + NumCast,
47        F: Fn(&T) -> K,
48    >(
49        &self,
50        key_selector: F,
51        min: K,
52        max: K,
53    ) -> Vec<T> {
54        let mut ret = self.to_vec();
55        let mut bucket =
56            vec![0; cast::<K, usize>(max - min.clone()).unwrap() + 2];
57
58        for i in 0..self.len() {
59            bucket[cast::<_, usize>(key_selector(&self[i]) - min.clone())
60                .unwrap()
61                + 1] += 1;
62        }
63        for i in 2..bucket.len() {
64            bucket[i] += bucket[i - 1];
65        }
66        for i in self {
67            let val = i.clone();
68            let idx =
69                cast::<_, usize>(key_selector(&val) - min.clone()).unwrap();
70            ret[bucket[idx]] = val;
71            bucket[idx] += 1;
72        }
73        ret
74    }
75}
compression/bucket_sort.rs

compression/
bucket_sort.rs
