atcoder/lib/math/
integer.rs

1//! 整数値の min/max と、組み込み整数型向けの小さな拡張を提供します。
2
3use std::ops::{Div, Rem};
4
5/// `lhs` と `rhs` のうち小さい方を返します。
6///
7/// 同じ値の場合は `lhs` を返します。比較可能な任意の型で使えます。
8pub fn min<T: Ord>(lhs: T, rhs: T) -> T {
9    if lhs <= rhs {
10        lhs
11    } else {
12        rhs
13    }
14}
15
16/// `lhs` と `rhs` のうち大きい方を返します。
17///
18/// 同じ値の場合は `lhs` を返します。比較可能な任意の型で使えます。
19pub fn max<T: Ord>(lhs: T, rhs: T) -> T {
20    if lhs >= rhs {
21        lhs
22    } else {
23        rhs
24    }
25}
26
27/// スライス内の最小値と最大値への参照を `(最小, 最大)` の順で返します。
28///
29/// 空スライスには `None`、要素がある場合は `Some((最小要素, 最大要素))` を返します。
30/// 同値の要素が複数ある場合、どの同値要素への参照が選ばれるかは保証しません。
31/// 要素数を `n` とすると比較回数は最大 `3 * floor(n / 2)` 回で、計算量は `O(n)` です。
32pub fn minmax<T: Ord>(values: &[T]) -> Option<(&T, &T)> {
33    if values.is_empty() {
34        return None;
35    }
36
37    let (mut minimum, mut maximum, mut index) = if values.len() % 2 == 1 {
38        (&values[0], &values[0], 1)
39    } else if values[0] <= values[1] {
40        (&values[0], &values[1], 2)
41    } else {
42        (&values[1], &values[0], 2)
43    };
44
45    while index < values.len() {
46        let first = &values[index];
47        let second = &values[index + 1];
48        let (smaller, larger) = if first <= second {
49            (first, second)
50        } else {
51            (second, first)
52        };
53
54        if smaller < minimum {
55            minimum = smaller;
56        }
57        if larger > maximum {
58            maximum = larger;
59        }
60        index += 2;
61    }
62
63    Some((minimum, maximum))
64}
65
66/// 組み込み整数型に便利な整数演算を追加する拡張トレイトです。
67///
68/// すべての符号付き・符号なし組み込み整数型に実装されています。
69/// `div_rem` は通常の整数除算に従い、除数 `0` や符号付き最小値を `-1` で割る場合は
70/// panic します。`chmin` と `chmax` は値を条件付きで更新し、その成否を `bool` で返します。
71///
72/// # Examples
73///
74/// ```
75/// use atcoder::math::integer::IntegerExt;
76///
77/// let mut value = 10_usize;
78/// assert!(value.chmin(7));
79/// assert!(!value.chmin(9));
80/// assert_eq!(value, 7);
81///
82/// assert_eq!(10_usize.div_rem(3), (3, 1));
83/// ```
84pub trait IntegerExt: Sized + Copy + Ord {
85    /// 商と余りを `(self / rhs, self % rhs)` の順に返します。
86    ///
87    /// 符号付き整数の商は `0` 方向へ切り捨て、余りは `self` と同じ符号になります。
88    /// 除数 `rhs` が `0` の場合など、通常の除算が panic する入力ではこのメソッドも panic します。
89    fn div_rem(self, rhs: Self) -> (Self, Self)
90    where
91        Self: Div<Output = Self> + Rem<Output = Self>,
92    {
93        (self / rhs, self % rhs)
94    }
95
96    /// `rhs` が `self` より小さい場合に `self` を `rhs` で置き換えます。
97    ///
98    /// 値を置き換えた場合は `true`、そのままの場合は `false` を返します。
99    fn chmin(&mut self, rhs: Self) -> bool {
100        if rhs < *self {
101            *self = rhs;
102            true
103        } else {
104            false
105        }
106    }
107
108    /// `rhs` が `self` より大きい場合に `self` を `rhs` で置き換えます。
109    ///
110    /// 値を置き換えた場合は `true`、そのままの場合は `false` を返します。
111    fn chmax(&mut self, rhs: Self) -> bool {
112        if rhs > *self {
113            *self = rhs;
114            true
115        } else {
116            false
117        }
118    }
119}
120
121macro_rules! impl_integer_ext {
122    ($($integer:ty),* $(,)?) => {
123        $(impl IntegerExt for $integer {})*
124    };
125}
126
127impl_integer_ext!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize,);
128
129#[cfg(test)]
130mod tests {
131    use super::{max, min, minmax, IntegerExt};
132
133    #[test]
134    fn returns_minimum_and_maximum_of_two_values() {
135        assert_eq!(min(3, 7), 3);
136        assert_eq!(max(3, 7), 7);
137    }
138
139    #[test]
140    fn returns_minimum_and_maximum_of_slice() {
141        assert_eq!(minmax::<i32>(&[]), None);
142        assert_eq!(minmax(&[5]), Some((&5, &5)));
143        assert_eq!(minmax(&[3, 8, 1, 6, 4]), Some((&1, &8)));
144        assert_eq!(minmax(&[3, 8, 1, 6]), Some((&1, &8)));
145    }
146
147    #[test]
148    fn calculates_quotient_and_remainder() {
149        assert_eq!(10_usize.div_rem(3), (3, 1));
150        assert_eq!((-10_i32).div_rem(3), (-3, -1));
151    }
152
153    #[test]
154    fn updates_minimum_and_maximum() {
155        let mut value = 10_i32;
156
157        assert!(value.chmin(7));
158        assert_eq!(value, 7);
159        assert!(!value.chmin(9));
160        assert_eq!(value, 7);
161
162        assert!(value.chmax(12));
163        assert_eq!(value, 12);
164        assert!(!value.chmax(8));
165        assert_eq!(value, 12);
166    }
167}
atcoder/lib/math/integer.rs

atcoder/lib/math/
integer.rs
