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> FromIterator<T> for SortedSeq<T>
49where
50    T: Ord,
51{
52    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
53        Self::new(iter)
54    }
55}
56
57impl<T> SortedSeq<T>
58where
59    T: Ord,
60{
61    pub fn new(values: impl IntoIterator<Item = T>) -> Self {
62        let mut values = values.into_iter().collect::<Vec<_>>();
63        values.sort_unstable();
64        values.dedup();
65        Self(values)
66    }
67
68    /// 集合内で小さいほうから何番目か (0-indexed) を返します
69    pub fn ord(&self, value: &T) -> usize {
70        self.0
71            .binary_search(value)
72            .unwrap_or_else(|_| panic!("not found"))
73    }
74
75    /// index 番目の値を返します
76    pub fn at(&self, index: usize) -> &T {
77        &self[index]
78    }
79
80    /// 集合のサイズを返します
81    pub fn size(&self) -> usize {
82        self.0.len()
83    }
84}
85
86impl<T> Index<usize> for SortedSeq<T> {
87    type Output = T;
88
89    fn index(&self, index: usize) -> &Self::Output {
90        &self.0[index]
91    }
92}
93
94impl<T> Debug for SortedSeq<T>
95where
96    T: Debug,
97{
98    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
99        write!(f, "{:?}", self.0)
100    }
101}
102
103#[cfg(test)]
104mod tests {
105    use crate::SortedSeq;
106
107    #[test]
108    fn ord_test() {
109        let seq = SortedSeq::new(vec![4, 4, 2, 5, 2, 9]);
110        // 2, 4, 5, 9
111        assert_eq!(seq.ord(&2), 0);
112        assert_eq!(seq.ord(&4), 1);
113        assert_eq!(seq.ord(&5), 2);
114        assert_eq!(seq.ord(&9), 3);
115    }
116
117    #[test]
118    fn index_test() {
119        let seq = SortedSeq::new([4, 4, 2, 5, 2, 9]);
120        // 2, 4, 5, 9
121        assert_eq!(seq.at(0), &2);
122        assert_eq!(seq.at(1), &4);
123        assert_eq!(seq.at(2), &5);
124        assert_eq!(seq.at(3), &9);
125    }
126
127    #[test]
128    #[should_panic]
129    fn not_found_test() {
130        let seq: SortedSeq<i32> = SortedSeq::new(vec![4, 4, 2, 5, 2, 9]);
131        seq.ord(&6);
132    }
133}
zarts/lib.rs

zarts/
lib.rs
