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

pub mod bubblesort;
pub mod insertionsort;

pub trait SortingAlgorithm: std::fmt::Debug + Default {
    fn sort_with_stats<T, S>(&self, slice: &mut [T], stats: S) -> S
    where
        T: Ord,
        S: SortingStatsTrait;

    fn sort<'s, T: Ord>(&self, slice: &'s mut [T]) -> &'s mut [T] {
        self.sort_with_stats(slice, EmptySortingStats);
        slice
    }
}

pub trait SortingStatsTrait {
    fn comparisons(&mut self, n: i64);
    fn swaps(&mut self, n: i64);

    #[inline]
    fn comparison(&mut self) {
        self.comparisons(1)
    }

    #[inline]
    fn swap(&mut self) {
        self.swaps(1)
    }
}

#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct EmptySortingStats;
impl SortingStatsTrait for EmptySortingStats {
    #[inline]
    fn comparisons(&mut self, _n: i64) {}

    #[inline]
    fn swaps(&mut self, _n: i64) {}
}

#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct SortingStats {
    comparisons: i64,
    swaps: i64,
}

impl SortingStatsTrait for SortingStats {
    #[inline]
    fn comparisons(&mut self, n: i64) {
        self.comparisons += n
    }

    #[inline]
    fn swaps(&mut self, n: i64) {
        self.swaps += n
    }
}

#[derive(Debug, Default)]
struct NoopSort;

impl SortingAlgorithm for NoopSort {
    fn sort_with_stats<T, S>(&self, _slice: &mut [T], stats: S) -> S
    where
        T: Ord,
        S: SortingStatsTrait,
    {
        stats
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn noopsort() {
        let mut v = [3, 2, 1, 7, 6];
        assert_eq!(
            NoopSort.sort_with_stats(&mut v[..], EmptySortingStats),
            EmptySortingStats
        );
        assert_eq!(v, [3, 2, 1, 7, 6]);
    }
}