sfcpl 0.1.1

private library for atcoder
Documentation 
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
134
135
136
137
138

//! Varified

use cargo_snippet::snippet;
use std::ops::{Add, Div};

/// # Usage
///
/// `T`は基本的にusizeが入る想定
///
/// `pred`について`l`側が`true`、
/// `r`側が`false`を返すような単調性を持っているとき、
///
/// `pred`を満たす`T`の中で最も大きいものを求める。
///
/// 最初に`l`と`r`について`pred`がそれぞれ`true`、`false`を返すかどうかを調べるので、
/// 範囲は閉空間で指定して良い。
///
/// 返り値`res`は必ず、
///
/// Some(inner) (l <= inner <= r) | None
///
/// になる
///
/// ```rust
/// use sfcpl::binary_search::binary_search;
///
/// let v = vec![1, 3, 3, 3, 4, 6, 7, 7, 8, 10];
/// assert_eq!(3, binary_search(|i| v[i] < 4, 0, v.len() - 1).unwrap());
/// assert_eq!(9, binary_search(|i| v[i] <= 10, 0, v.len() - 1).unwrap());
/// ```
#[snippet("binary_search")]
pub fn binary_search<T, F>(pred: F, l: T, r: T) -> Option<T>
where
    T: Add<Output = T> + Div<Output = T> + PartialEq + Copy + From<u8>,
    F: Fn(T) -> bool,
{
    if !pred(l) {
        return None;
    }
    if pred(r) {
        return Some(r);
    }

    let mut l = l;
    let mut r = r;
    let two = T::from(2);

    loop {
        let m = (l + r) / two;
        if l == m {
            break Some(l);
        }

        if pred(m) {
            l = m;
        } else {
            r = m;
        }
    }
}

#[test]
fn binary_search_test() {
    let v = vec![1, 3, 3, 3, 4, 6, 7, 7, 8, 10];

    assert_eq!(3, binary_search(|i| v[i] < 4, 0, v.len() - 1).unwrap());
    assert_eq!(9, binary_search(|i| v[i] <= 10, 0, v.len() - 1).unwrap());
}

/// `v`以上の要素が最初に現れるindex
///
/// ```rust
/// use sfcpl::binary_search::lower_bound;
///
/// let v: &[i32] = &[1, 3, 3, 4, 5];
/// assert_eq!(lower_bound(v, &0), 0);
/// assert_eq!(lower_bound(v, &1), 0);
/// assert_eq!(lower_bound(v, &2), 1);
/// assert_eq!(lower_bound(v, &3), 1);
/// assert_eq!(lower_bound(v, &4), 3);
/// assert_eq!(lower_bound(v, &5), 4);
/// assert_eq!(lower_bound(v, &999), 5);
/// ```
#[snippet("binary_search")]
pub fn lower_bound<T: PartialOrd>(v: &[T], val: &T) -> usize {
    let t = binary_search(|x| v[x] < *val, 0, v.len() - 1);
    match t {
        Some(e) => e + 1,
        None => 0,
    }
}

#[test]
fn lower_bound_test() {
    let v: &[i32] = &[1, 3, 3, 4, 5];
    assert_eq!(lower_bound(v, &0), 0);
    assert_eq!(lower_bound(v, &1), 0);
    assert_eq!(lower_bound(v, &2), 1);
    assert_eq!(lower_bound(v, &3), 1);
    assert_eq!(lower_bound(v, &4), 3);
    assert_eq!(lower_bound(v, &5), 4);
    assert_eq!(lower_bound(v, &999), 5);
}

/// `v`より大きい要素が最初に現れるindex
///
/// ```rust
/// use sfcpl::binary_search::upper_bound;
///
/// let v: &[i32] = &[1, 3, 3, 4, 5];
/// assert_eq!(upper_bound(v, &0), 0);
/// assert_eq!(upper_bound(v, &1), 1);
/// assert_eq!(upper_bound(v, &2), 1);
/// assert_eq!(upper_bound(v, &3), 3);
/// assert_eq!(upper_bound(v, &4), 4);
/// assert_eq!(upper_bound(v, &5), 5);
/// assert_eq!(upper_bound(v, &999), 5);
/// ```
#[snippet("binary_search")]
pub fn upper_bound<T: PartialOrd>(v: &[T], val: &T) -> usize {
    let t = binary_search(|x| v[x] <= *val, 0, v.len() - 1);
    match t {
        Some(e) => e + 1,
        None => 0,
    }
}

#[test]
fn upper_bound_test() {
    let v: &[i32] = &[1, 3, 3, 4, 5];
    assert_eq!(upper_bound(v, &0), 0);
    assert_eq!(upper_bound(v, &1), 1);
    assert_eq!(upper_bound(v, &2), 1);
    assert_eq!(upper_bound(v, &3), 3);
    assert_eq!(upper_bound(v, &4), 4);
    assert_eq!(upper_bound(v, &5), 5);
    assert_eq!(upper_bound(v, &999), 5);
}