devela 0.27.0

A development layer of coherence.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

// devela::data::layout::sort::impls_alloc
//
//! Implements sorting algorithms for exclusive generic arrays `[T: Ord; N]`.
//

use crate::{BTreeMap, Sort, Vec};

impl<T: Ord> Sort<&mut [T]> {
    /// Sorts a slice using counting sort, and returns the ordered frequencies.
    ///
    /// Counting sort is particularly efficient when the range of input values is
    /// small compared to the number of elements to be sorted.
    ///
    /// # Examples
    /// ```
    /// # use devela::Sort;
    /// let mut data = [4, 64, 4, 2, 4, 8, 8, 4, 8, 4, 2, 8, 64, 4, 8, 4, 2];
    /// let freq = Sort(&mut data[..]).counting();
    /// assert_eq![data, [2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 64, 64]];
    /// assert_eq![freq, [3, 7, 5, 2]];
    /// ```
    pub fn counting(self) -> Vec<usize>
    where
        T: Clone,
    {
        let mut counts = BTreeMap::new();
        // Calculate the frequencies and save them
        for item in self.0.iter() {
            let count = counts.entry(item.clone()).or_insert(0);
            *count += 1;
        }
        let freq: Vec<usize> = counts.values().copied().collect();
        // Reconstruct the sorted slice
        let mut i = 0;
        for (item, &count) in counts.iter() {
            for _ in 0..count {
                self.0[i] = item.clone();
                i += 1;
            }
        }
        freq
    }

    /// Sorts a `slice` using merge sort.
    ///
    /// It allocates one vector for the entire sort operation.
    ///
    /// # Examples
    /// ```
    /// # use devela::Sort;
    /// let mut arr = [4, 7, -5, 1, -13, 0];
    /// Sort(&mut arr[..]).merge();
    /// assert_eq![arr, [-13, -5, 0, 1, 4, 7]];
    /// ```
    pub fn merge(self)
    where
        T: Copy,
    {
        let len = self.0.len();
        let mut buffer = Vec::with_capacity(len);
        buffer.resize(len, self.0[0]);
        helper::sort_merge_internal(self.0, &mut buffer);
    }
}

// private helper fns
mod helper {
    use crate::is;

    pub(super) fn sort_merge_internal<T: Ord + Copy>(slice: &mut [T], buffer: &mut [T]) {
        let len = slice.len();
        is![len <= 1, return];
        let mid = len / 2;
        sort_merge_internal(&mut slice[..mid], buffer);
        sort_merge_internal(&mut slice[mid..], buffer);
        sort_merge_merge(&slice[..mid], &slice[mid..], &mut buffer[..len]);
        slice.copy_from_slice(&buffer[..len]);
    }
    pub(super) fn sort_merge_merge<T: Ord + Copy>(left: &[T], right: &[T], slice: &mut [T]) {
        let (mut i, mut j, mut k) = (0, 0, 0);
        while i < left.len() && j < right.len() {
            is![
                left[i] < right[j],
                {
                    slice[k] = left[i];
                    i += 1;
                },
                {
                    slice[k] = right[j];
                    j += 1;
                }
            ];
            k += 1;
        }
        is![i < left.len(), slice[k..].copy_from_slice(&left[i..])];
        is![j < right.len(), slice[k..].copy_from_slice(&right[j..])];
    }
}