1use std::collections::BTreeMap;
2
3pub fn btree_sort<T: Ord>(vec: Vec<T>) -> BTreeMap<T, usize> {
4 vec.into_iter().fold(BTreeMap::new(), |mut acc, e| {
5 let b = acc.entry(e).or_insert(0);
6 *b += 1;
7 acc
8 })
9}
10
11pub trait BTreeSort<T: Ord> {
12 fn uniques(self) -> Vec<T>;
13 fn sorted(self) -> Vec<T>;
14 fn reverse_uniques(self) -> Vec<T>;
15 fn reverse_sort(self) -> Vec<T>;
16}
17
18impl<T: Ord + Clone> BTreeSort<T> for BTreeMap<T, usize> {
19 fn uniques(self) -> Vec<T> {
20 self.into_iter().map(|(k, _)| k).collect::<Vec<T>>()
21 }
22
23 fn reverse_uniques(self) -> Vec<T> {
24 let mut ord = self.into_iter().map(|(k, _)| k).collect::<Vec<T>>();
25 ord.reverse();
26 ord
27 }
28
29 fn sorted(self) -> Vec<T> {
30 self.into_iter()
31 .map(|(k, v)| vec![k; v])
32 .flatten()
33 .collect::<Vec<T>>()
34 }
35
36 fn reverse_sort(self) -> Vec<T> {
37 let mut ord = self
38 .into_iter()
39 .map(|(k, v)| vec![k; v])
40 .flatten()
41 .collect::<Vec<T>>();
42 ord.reverse();
43 ord
44 }
45}
46
47impl<T: Ord + Clone> BTreeSort<T> for Vec<T> {
48 fn uniques(self) -> Vec<T> {
49 btree_sort(self).into_iter().map(|(k, _)| k).collect::<Vec<T>>()
50 }
51
52 fn reverse_uniques(self) -> Vec<T> {
53 let mut ord = btree_sort(self).into_iter().map(|(k, _)| k).collect::<Vec<T>>();
54 ord.reverse();
55 ord
56 }
57
58 fn sorted(self) -> Vec<T> {
59 btree_sort(self).into_iter()
60 .map(|(k, v)| vec![k; v])
61 .flatten()
62 .collect::<Vec<T>>()
63 }
64
65 fn reverse_sort(self) -> Vec<T> {
66 let mut ord = btree_sort(self)
67 .into_iter()
68 .map(|(k, v)| vec![k; v])
69 .flatten()
70 .collect::<Vec<T>>();
71 ord.reverse();
72 ord
73 }
74}
75
76#[cfg(test)]
77mod test {
78 use super::*;
79
80 #[test]
81 fn integers() {
82 let vec = vec![7, 3, 4, 5, 6, 8, 3, 2, -4, 5, 7, 8, 0, 9];
83 let sort = btree_sort(vec);
84
85 assert_eq!(sort.clone().uniques(), vec![-4, 0, 2, 3, 4, 5, 6, 7, 8, 9]);
86 assert_eq!(
87 sort.sorted(),
88 vec![-4, 0, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9]
89 );
90 }
91
92 #[test]
93 fn usize() {
94 let vec: Vec<usize> = vec![7, 3, 4, 5, 6, 8, 3, 2, 5, 7, 8, 0, 9];
95 let sort = btree_sort(vec);
96
97 assert_eq!(sort.clone().uniques(), vec![0, 2, 3, 4, 5, 6, 7, 8, 9]);
98 assert_eq!(
99 sort.clone().sorted(),
100 vec![0, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9]
101 );
102 assert_eq!(sort.reverse_uniques(), vec![9, 8, 7, 6, 5, 4, 3, 2, 0]);
103 }
104
105 #[test]
106 fn chars() {
107 let vec = vec!['h', 'g', 'p', 'a', 'c', 'g'];
108 let sort = btree_sort(vec);
109
110 assert_eq!(sort.clone().uniques(), vec!['a', 'c', 'g', 'h', 'p']);
111 assert_eq!(sort.clone().sorted(), vec!['a', 'c', 'g', 'g', 'h', 'p']);
112 assert_eq!(sort.reverse_sort(), vec!['p', 'h', 'g', 'g', 'c', 'a']);
113 }
114
115 #[test]
116 fn string() {
117 let vec = vec!["ha", "he", "ga", "12", "pow", "he", "543", "as", "cd", "ga"];
118 let sort = btree_sort(vec);
119
120 assert_eq!(
121 sort.clone().uniques(),
122 vec!["12", "543", "as", "cd", "ga", "ha", "he", "pow"]
123 );
124 assert_eq!(
125 sort.sorted(),
126 vec!["12", "543", "as", "cd", "ga", "ga", "ha", "he", "he", "pow"]
127 );
128 }
129
130 #[test]
131 fn vec_usize() {
132 let vec: Vec<usize> = vec![7, 3, 4, 5, 6, 8, 3, 2, 5, 7, 8, 0, 9];
133
134 assert_eq!(vec.clone().uniques(), vec![0, 2, 3, 4, 5, 6, 7, 8, 9]);
135 assert_eq!(
136 vec.clone().sorted(),
137 vec![0, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9]
138 );
139 assert_eq!(vec.reverse_uniques(), vec![9, 8, 7, 6, 5, 4, 3, 2, 0]);
140 }
141}