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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

use std::{
    fmt::{self, Debug},
    ops::Index,
};

/// 座標圧縮です。
///
/// # Examples
///
/// ```
/// use zarts::SortedSeq;
/// let values = vec![2, -1, -1, 5, -1, 2, -3];
/// // -3, -1, 2, 5
/// let seq = SortedSeq::new(values);
/// assert_eq!(seq.ord(&-3), 0);
/// assert_eq!(seq.ord(&-1), 1);
/// assert_eq!(seq.ord(&2), 2);
/// assert_eq!(seq.ord(&5), 3);
///
/// assert_eq!(seq.at(0), &(-3));
/// assert_eq!(seq.at(1), &(-1));
/// assert_eq!(seq.at(2), &2);
/// assert_eq!(seq.at(3), &5);
/// ```
///
/// # Panics
///
/// 構築時に与えられなかったキーを引くとパニックです。
///
/// ```should_panic
/// use zarts::SortedSeq;
/// let primes = vec![2, 3, 5, 7, 11];
/// let seq = SortedSeq::new(primes);
/// seq.ord(&4);
/// ```
///
/// index が集合のサイズ以上だとパニックです。
///
/// ```should_panic
/// use zarts::SortedSeq;
/// let values = vec![1, 1, 2, 2, 3, 4, 9, 9];
/// let seq = SortedSeq::new(values);
/// seq.at(5);
/// ```
///
pub struct SortedSeq<T>(Vec<T>);

impl<T> FromIterator<T> for SortedSeq<T>
where
    T: Ord,
{
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        Self::new(iter)
    }
}

impl<T> SortedSeq<T>
where
    T: Ord,
{
    pub fn new(values: impl IntoIterator<Item = T>) -> Self {
        let mut values = values.into_iter().collect::<Vec<_>>();
        values.sort_unstable();
        values.dedup();
        Self(values)
    }

    /// 集合内で小さいほうから何番目か (0-indexed) を返します
    pub fn ord(&self, value: &T) -> usize {
        self.0
            .binary_search(value)
            .unwrap_or_else(|_| panic!("not found"))
    }

    /// index 番目の値を返します
    pub fn at(&self, index: usize) -> &T {
        &self[index]
    }

    /// 集合のサイズを返します
    pub fn size(&self) -> usize {
        self.0.len()
    }
}

impl<T> Index<usize> for SortedSeq<T> {
    type Output = T;

    fn index(&self, index: usize) -> &Self::Output {
        &self.0[index]
    }
}

impl<T> Debug for SortedSeq<T>
where
    T: Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{:?}", self.0)
    }
}

#[cfg(test)]
mod tests {
    use crate::SortedSeq;

    #[test]
    fn ord_test() {
        let seq = SortedSeq::new(vec![4, 4, 2, 5, 2, 9]);
        // 2, 4, 5, 9
        assert_eq!(seq.ord(&2), 0);
        assert_eq!(seq.ord(&4), 1);
        assert_eq!(seq.ord(&5), 2);
        assert_eq!(seq.ord(&9), 3);
    }

    #[test]
    fn index_test() {
        let seq = SortedSeq::new([4, 4, 2, 5, 2, 9]);
        // 2, 4, 5, 9
        assert_eq!(seq.at(0), &2);
        assert_eq!(seq.at(1), &4);
        assert_eq!(seq.at(2), &5);
        assert_eq!(seq.at(3), &9);
    }

    #[test]
    #[should_panic]
    fn not_found_test() {
        let seq: SortedSeq<i32> = SortedSeq::new(vec![4, 4, 2, 5, 2, 9]);
        seq.ord(&6);
    }
}