zarts/
lib.rs

1use std::{
2    fmt::{self, Debug},
3    ops::Index,
4};
5
6/// 座標圧縮です。
7///
8/// # Examples
9///
10/// ```
11/// use zarts::SortedSeq;
12/// let values = vec![2, -1, -1, 5, -1, 2, -3];
13/// // -3, -1, 2, 5
14/// let seq = SortedSeq::new(values);
15/// assert_eq!(seq.ord(&-3), 0);
16/// assert_eq!(seq.ord(&-1), 1);
17/// assert_eq!(seq.ord(&2), 2);
18/// assert_eq!(seq.ord(&5), 3);
19///
20/// assert_eq!(seq.at(0), &(-3));
21/// assert_eq!(seq.at(1), &(-1));
22/// assert_eq!(seq.at(2), &2);
23/// assert_eq!(seq.at(3), &5);
24/// ```
25///
26/// # Panics
27///
28/// 構築時に与えられなかったキーを引くとパニックです。
29///
30/// ```should_panic
31/// use zarts::SortedSeq;
32/// let primes = vec![2, 3, 5, 7, 11];
33/// let seq = SortedSeq::new(primes);
34/// seq.ord(&4);
35/// ```
36///
37/// index が集合のサイズ以上だとパニックです。
38///
39/// ```should_panic
40/// use zarts::SortedSeq;
41/// let values = vec![1, 1, 2, 2, 3, 4, 9, 9];
42/// let seq = SortedSeq::new(values);
43/// seq.at(5);
44/// ```
45///
46pub struct SortedSeq<T>(Vec<T>);
47
48impl<T> SortedSeq<T>
49where
50    T: Ord,
51{
52    pub fn new(mut values: Vec<T>) -> Self {
53        values.sort_unstable();
54        values.dedup();
55        Self(values)
56    }
57
58    /// 集合内で小さいほうから何番目か (0-indexed) を返します
59    pub fn ord(&self, value: &T) -> usize {
60        self.0
61            .binary_search(value)
62            .unwrap_or_else(|_| panic!("not found"))
63    }
64
65    /// index 番目の値を返します
66    pub fn at(&self, index: usize) -> &T {
67        &self[index]
68    }
69
70    /// 集合のサイズを返します
71    pub fn len(&self) -> usize {
72        self.0.len()
73    }
74
75    pub fn is_empty(&self) -> bool {
76        self.0.is_empty()
77    }
78}
79
80impl<T> FromIterator<T> for SortedSeq<T>
81where
82    T: Ord,
83{
84    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
85        Self::new(iter.into_iter().collect())
86    }
87}
88
89impl<T> Index<usize> for SortedSeq<T> {
90    type Output = T;
91
92    fn index(&self, index: usize) -> &Self::Output {
93        &self.0[index]
94    }
95}
96
97impl<T> Debug for SortedSeq<T>
98where
99    T: Debug,
100{
101    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
102        write!(f, "{:?}", self.0)
103    }
104}
105
106#[cfg(test)]
107mod tests {
108    use crate::SortedSeq;
109
110    #[test]
111    fn ord_test() {
112        let seq = SortedSeq::new(vec![4, 4, 2, 5, 2, 9]);
113        // 2, 4, 5, 9
114        assert_eq!(seq.ord(&2), 0);
115        assert_eq!(seq.ord(&4), 1);
116        assert_eq!(seq.ord(&5), 2);
117        assert_eq!(seq.ord(&9), 3);
118    }
119
120    #[test]
121    fn index_test() {
122        let seq = SortedSeq::new(vec![4, 4, 2, 5, 2, 9]);
123        // 2, 4, 5, 9
124        assert_eq!(seq.at(0), &2);
125        assert_eq!(seq.at(1), &4);
126        assert_eq!(seq.at(2), &5);
127        assert_eq!(seq.at(3), &9);
128    }
129
130    #[test]
131    #[should_panic]
132    fn not_found_test() {
133        let seq: SortedSeq<i32> = SortedSeq::new(vec![4, 4, 2, 5, 2, 9]);
134        seq.ord(&6);
135    }
136}
zarts/lib.rs

zarts/
lib.rs
