Rust RangeBoundsの紹介

# TLDR
関数などの引数に range を受け取って普通にイテレーションするとき(簡単のため `u64` を使っています)
```rust
use std::ops::RangeBounds;
use std::iter::IntoIterator;
pub fn sum_n<R: RangeBounds<u64> + IntoIterator<Item=u64>>(range: R) -> u64 {
    let mut result = 0;
    for r in range {
        result += r
    }
    return result
}
```

普通にイテレーションするわけではなく、 `start` と `end` の値がほしいとき
```rust
use std::ops::{Bound, RangeBounds};
pub fn sum_1<R: RangeBounds<u64>>(range: R) -> u64 {
    let start = match range.start_bound() {
        Bound::Unbounded => 0,
        Bound::Excluded(&s) => s + 1,
        Bound::Included(&s) => s,
    };
    let end = match range.end_bound() {
        Bound::Unbounded => panic!("end_bound should be decided"),
        Bound::Excluded(&t) => t - 1,
        Bound::Included(&t) => t,
    };
    assert!(start <= end);
    (start + end) * (end - start + 1) / 2
}
```

※ スライスの範囲を指定するように使うときは、`end_bound` は `Included` のほうで `+1` することが多いと思います。(そういうときは最大のサイズ `max_len` がどこかに存在すると思います)
```rust
    let end = match range.end_bound() {
        Bound::Unbounded => max_len,
        Bound::Excluded(&t) => t.min(max_len),
        Bound::Included(&t) => (t + 1).min(max_len),
    };
```

# Range 構造体
`Range` 構造体は、for 文などでよく使っている `0..10` のようなものです。
主には、 `std::ops::Range` です。

https://doc.rust-lang.org/std/ops/struct.Range.html
```rust
    let mut result = 0;
    for i in 0..10 {
        result += i
    }
    assert_eq!(result, 45)
```


実は、 `Range` の他にも `RangeFrom` や `RangeToInclusive` などいろいろあります 。

https://doc.rust-lang.org/std/ops/index.html#structs

`start..end` や `start..` や `..=end` などはそれぞれ違う構造体で表現されているんですね。

## RangeBounds トレイト
`Range` 構造体の他にも `RangeFrom` 構造体や `RangeToInclusive` 構造体などがありました。しかし、これらは全て範囲を表すオブジェクトなので、共通するインターフェースが用意されていると嬉しいですよね。それが `RangeBounds` トレイトです。

https://doc.rust-lang.org/std/ops/trait.RangeBounds.html

`Range` 構造体や `RangeFrom` 構造体、 `RangeToInclusive` 構造体などにはこの `RangeBounds` トレイトが実装されています。

## 総和を計算する
`RangeBounds` トレイトの使用例として、受け取った範囲の和を返す関数を作成してみます。
```rust
use std::iter::IntoIterator;
use std::ops::RangeBounds;
pub fn sum_n<R: RangeBounds<u64> + IntoIterator<Item = u64>>(range: R) -> u64 {
    let mut result = 0;
    for r in range {
        result += r
    }
    result
}
```
foldなど使えばfor文を使わずに書けますが、ここではfor文を使って書いておきます。
参考:

https://qiita.com/hystcs/items/f7f40026bb34421a1271

この `sum_n` 関数は、次のように使うことができます。
```rust
fn main() {
    assert_eq!(sum_n(1..10), 45);
    assert_eq!(sum_n(1..=10), 55);
}
```

しかし、この関数にはいくつか問題があります。`..end` のように書いたときの `RangeTo` などの構造体は、`RangeBounds` は実装しているものの、`Iterator` は実装していません。当然と言えば当然ですが、始点の情報がないのでイテレーションすることができません。次のように書くとコンパイルエラーとなってしまいます。
```rust
fn main() {
    assert_eq!(sum_n(..10), 45);
}
```
```
error[E0277]: `RangeTo<u64>` is not an iterator
 --> src/main1.rs:2:22
  |
2 |     assert_eq!(sum_n(..10), 45);
  |                ----- ^^^^ if you meant to iterate until a value, add a starting value
  |                |
  |                required by a bound introduced by this call
  |
  = help: the trait `Iterator` is not implemented for `RangeTo<u64>`
  = note: `..end` is a `RangeTo`, which cannot be iterated on; you might have meant to have a bounded `Range`: `0..end`
  = note: required because of the requirements on the impl of `IntoIterator` for `RangeTo<u64>`
```

また、単純に前から順に足していっているので、最初の値 `start` と最後の値 `end` が離れていると、当然処理に時間がかかってしまいます。さらには、`end` を指定しない、`start..` のように書いたときの `RangeFrom` 構造体を渡してしまうと、この関数は、リリースビルドでは、無限ループに陥ってしまいます(デバッグビルドでは加算のオーバーフローでプログラムが終了します)。


イテレーションするだけなら `RangeBounds` は用いる必要がないですが、引数が `Range` (など)であってほしい、ということを型のレベルで表現することができるので、望まない入力をコンパイルエラーにできることはうれしいですね。

## 総和を効率化する
さて、先ほどの `sum_n` 関数では、最初の値 $s$ と最後の値 $t$ が大きく離れていると、計算に時間がかかってしまいました。幸いなことに、皆さんご存じの通り、 $s$ から $t$ までの和を計算する公式があります。
$$
\sum_{i=s}^{t} i = \frac{(s + t)(t - s + 1)}{2}
$$
先ほどの方法では時間計算量は $O(t-s)$ ですが、この方法であれば $O(1)$ です。どれだけ離れた $s$ と $t$ を持ってきても計算時間は(理論上)変わらないのでうれしいです。
これはRustのプログラムでは、次の`sum_1` 関数のように書けます。
```rust
use std::ops::{Bound, RangeBounds};
pub fn sum_1<R: RangeBounds<u64>>(range: R) -> u64 {
    let start = match range.start_bound() {
        Bound::Unbounded => 0,
        Bound::Excluded(&s) => s + 1,
        Bound::Included(&s) => s,
    };
    let end = match range.end_bound() {
        Bound::Unbounded => panic!("end_bound should be decided"),
        Bound::Excluded(&t) => t - 1,
        Bound::Included(&t) => t,
    };
    assert!(start <= end);
    (start + end) * (end - start + 1) / 2
}
```

なんか長いですね、そのあたりについては[最後](#なんか長いがなぜか)に少し詳細を書きたいと思います。やっていることは単純で、`RangeBound` トレイトによって提供される `start_bound` メソッドと `end_bound` メソッドで最初と最後の値を持ってきているだけです。ただし、`..end` の場合と `..=end` の場合で、`end` の値は 1 多かったり少なかったりします。それを表すのが `Bound::Excluded` や `Bound::Included` ですね。 `Bound::Unbounded` は単純に値が指定されていないことを表します。 `start` についても `Excluded` が用意されていますが、普通に使っている限りは `start` が `Excluded` になることは無いと思います(標準では用意されていないので)。

この `sum_1` 関数は、次のように使うことができます。
```rust
fn main() {
    assert_eq!(sum_1(1..10), 45);
    assert_eq!(sum_1(1..=10), 55);
    assert_eq!(sum_1(..10), 45);
    // println!("{}", sum_1(1..)); // panic!
}
```
最後にコメントアウトしている行は、range の最後を指定していないため、`panic!` するように `sum_1` 関数で記述されています。ここで適当な上限の値を好きに書いておけば、`panic!` を避けることもできます。range の最後を指定しないとき、初めの `sum_n` 関数では無限ループに陥ってしまっていましたが、この方法を使えば無限ループは避けることができます。

## スライスの範囲を指定する場合
さて、ここまでは単純に range の和を扱ってきましたが、range はスライスの範囲を指定する用途で使用されることも多いと思います。
```rust
fn main() {
    let v = vec![1, 2, 3, 4];
    println!("{:?}", &v[1..3]) // [2, 3]
}
```
このようなものを表現したいときは、先ほどの `sum_1` 関数とは、`end_bound` の1足したり引いたりが少し変わってくると思います。

```rust
use std::ops::{Bound, RangeBounds};
pub fn range_decide<R: RangeBounds<usize>>(range: R, len: usize) -> (usize, usize) {
    let start = match range.start_bound() {
        Bound::Unbounded => 0,
        Bound::Excluded(&s) => s + 1,
        Bound::Included(&s) => s,
    };
    let end = match range.end_bound() {
        Bound::Unbounded => len,
        Bound::Excluded(&t) => t.min(len),
        Bound::Included(&t) => (t + 1).min(len),
    };
    assert!(start <= end);
    (start, end)
}
```
```rust
fn main() {
    let max_len = 100;
    assert_eq!(range_decide(5..10, max_len), (5, 10));
    assert_eq!(range_decide(5..=10, max_len), (5, 11));
    assert_eq!(range_decide(0.., max_len), (0, 100));
    assert_eq!(range_decide(..10, max_len), (0, 10));
    assert_eq!(range_decide(..=10, max_len), (0, 11));
    assert_eq!(range_decide(.., max_len), (0, 100));
    assert_eq!(range_decide(5..5, max_len), (5, 5));
}
```
半開区間で表したいときはこちらの方がいいですね。


# なんか長いがなぜか
スライスの範囲を指定するときと同じ様子で `end_bound` に1を足す `std::slice::range` メソッドが、標準で用意されています(2022/07/17 現在 nightly-only ですが…)。

https://doc.rust-lang.org/std/slice/fn.range.html

この関数は、第一引数に任意の `RangeBounds<usize>` を指定し、第二引数には `RangeTo` のオブジェクト(`..end` のような形のもの)を指定します。`usize` 限定ではありますが、使用例としては次のようになります。
```rust
#![feature(slice_range)]
fn main() {
    let max_len = 100;
    let range = std::slice::range(..10, ..max_len);
    assert_eq!((range.start, range.end), (0, 10));
}
```

このあたりについては GitHub のこのあたりの issue でやり取りされているようです。

https://github.com/rust-lang/rust/issues/76393

# まとめ
range 系の構造体を一括で扱うことができるトレイト `RangeBounds` を紹介しました。

https://doc.rust-lang.org/std/ops/trait.RangeBounds.html

このトレイトを用いることで、関数の引数などで、範囲を指定することができます。
単純にイテレーションしたい場合には別途 `IntoIter` なども求めることになりますが、`RangeBounds` を用いることで、range であることを指定できるのはうれしいですね。