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

zarts/
lib.rs
