中点分割器

概述

这是一个灵活的无状态中点分割方法实现。

通过让用户控制输入和输出类型来实现灵活性。也就是说，这个实现不仅限于数值类型。此外，实现是无状态的。在 Bisector 结构体上实现的 bisect 方法不保留最后一步的内部可变状态。这使用户可以选择重新执行一个步骤，或者按照用户希望的方式真正执行任何步骤（尽管增量步骤仍然最为合理 😅）。

内部可变状态的缺乏还允许实现接受共享引用（&self），而不是独占引用（&mut self），这在处理许多所有权情况时很方便，这也是这个 crate 的原始原因。

安装

Cargo

1. 在 crates.io 上的最新发布版本 (推荐)

将 bisector crate 添加到 Cargo 清单文件（Cargo.toml）中的依赖列表

[dependencies]
bisector = "*" # replace `*` with latest version

2. GitHub 上的最新开发版本

将 bisector crate 添加到 Cargo 清单文件（Cargo.toml）中的依赖列表

[dependencies]
bisector = { git = "https://github.com/foresterre/bisector.git" }

MSRV

使用 cargo-msrv 确定了最小支持的 Rust 版本，并在 CI 运行期间进行了验证。下表列出了当前和历史上 bisector 的 MSRV。

示例

示例 1

fn main() {
    let values = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    let bisector = Bisector::new(&values);

    let start_from = Indices::from_bisector(&bisector);

    // In this example, we'll manually step through the bisection (i.e. without a loop).

    // (1) We use the default starting indices (i.e. left = 0, right = |values| - 1 = 9);
    let step: Step<u32, u32> = bisector.bisect(|&value| ConvergeTo::Left(value), start_from);

    // We converge to the left, so our view of values will be halved to the left half.
    assert_eq!(step.indices, Indices::new(0, 4));
    assert_eq!(step.result.unwrap().try_into_left().unwrap(), 5);

    // (2) Now we use the next indices produced by step, to progress our bisection: step.indices
    //      Because we zig-zag, we'll now converge to the right
    let step: Step<u32, u32> = bisector.bisect(|&value| ConvergeTo::Right(value), step.indices);

    // We converge to the right, so our view of values will be halved to the right half of our previous
    // view.
    assert_eq!(step.indices, Indices::new(3, 4));
    assert_eq!(step.result.unwrap().try_into_right().unwrap(), 3);

    // (3) Step further: zig-zag left
    let final_step: Step<u32, u32> =
        bisector.bisect(|&value| ConvergeTo::Left(value), step.indices);

    assert_eq!(final_step.indices, Indices::new(3, 3));
    assert_eq!(final_step.result.unwrap().try_into_left().unwrap(), 4);

    // (4a) Step a one more time to check we are at the end: left
    let step: Step<u32, u32> =
        bisector.bisect(|&value| ConvergeTo::Left(value), final_step.indices);

    assert_eq!(step.indices, Indices::new(3, 3));
    assert!(step.result.is_none());

    // (4b) Step a one more time to check we are at the end: right
    let step: Step<u32, u32> =
        bisector.bisect(|&value| ConvergeTo::Right(value), final_step.indices);

    assert_eq!(step.indices, Indices::new(3, 3));
    assert!(step.result.is_none());
}

示例 2

// NB: output held by ConvergeTo does *not* need to be of the same type as
// the value. In this example, it just happens to be the case.
fn f(value: u32) -> ConvergeTo<u32, u32> {
    if value >= 5 && value <= 6 {
        ConvergeTo::Right(value)
    } else {
        ConvergeTo::Left(value)
    }
}

fn main() {
    let values = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

    let bisector = Bisector::new(&values);
    let mut elements_seen = vec![];
    let mut value = None;

    let mut i = Indices::from_bisector(&bisector);
    while let Step {
        indices,
        result: Some(t),
    } = bisector.bisect(|&v| f(v), i)
    {
        i = indices;

        let val = match t {
            ConvergeTo::Left(l) => l,
            ConvergeTo::Right(r) => r,
        };

        elements_seen.push(val);
        value = Some(val);
    }

    println!("{:?}", elements_seen);
    println!("Final converged to '{}'", value.unwrap());
}

示例：在 cargo msrv 中的 bisect

可以在 cargo msrv 中找到一个更复杂的 示例。

注意：链接的修订版本是在添加 Bisector::try_bisect 方法之前实现的。为了覆盖收敛函数中的可能错误情况，您可能希望使用 Bisector::try_bisect 而不是 Bisector::bisect。

许可证

根据您选择以下任何一个许可证：

• Apache License, Version 2.0, (LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

自由选择。

贡献

除非您明确声明，否则根据 Apache-2.0 许可证定义的，您有意提交以包含在作品中的任何贡献，应按照上述方式双许可，不附加任何额外条款或条件。