Найти большие и нижние ключи в BTreeSet в одном поиске - PullRequest
Новая
       16

Найти большие и нижние ключи в BTreeSet в одном поиске

0 голосов
/ 15 мая 2018

Я бы хотел найти в Rust BTreeSet ключи, которые строго ниже и больше указанного ключа.

Например, если задано значение { "1", "3" }, а ключ поиска - "2", тогда ответ должен быть ("1", "3"). В тех случаях, когда более низкое или большее значение не существует, None должно быть возвращено.

Я могу добиться нужного результата, дважды вызвав метод range() для BTreeSet.

Есть ли способ сделать это с помощью одного поиска, как в C ++? std::set в C ++ имеет двунаправленный итератор: 

// $CXX -std=c++17 less-than.c++ -o less-than && ./less-than

#include <cassert>
#include <optional>
#include <set>
#include <string>
#include <iostream>

using std::optional;
using std::pair;
using std::set;
using std::string;

pair<optional<string>, optional<string>> bounding_box(
    const set<string>& space,
    const string& point)
{
    if (space.empty()) { return {}; }

    optional<string> gt_bound;
    optional<string> lt_bound;

    const auto ge_bound_it = space.lower_bound(point);

    if (ge_bound_it != space.end()) {
        if (*ge_bound_it == point) {
            // lower_bound returned an equal point, use the next one
            // if it exists
            const auto gt_bound_it = std::next(ge_bound_it, 1);

            if (gt_bound_it != space.end()) {
                gt_bound = *gt_bound_it;
            }
        } else {
            gt_bound = *ge_bound_it;
        }

    }

    if (ge_bound_it != space.begin()) {
        lt_bound = *std::next(ge_bound_it, -1);
    }

    return {lt_bound, gt_bound};
}

int main() {
    {
        const auto box = bounding_box({"1", "3"}, "2");
        assert(box.first);
        assert(*box.first == "1");

        assert(box.second);
        assert(*box.second == "3");
    }

    {
        const auto box = bounding_box({"1", "3"}, "4");
        assert(box.first);
        assert(*box.first == "3");

        assert(!box.second);
    }

    {
        const auto box = bounding_box({"1", "3"}, "0");
        assert(!box.first);

        assert(box.second);
        assert(*box.second == "1");
    }

    {
        const auto box = bounding_box({"3", "3"}, "3");
        assert(!box.first);
        assert(!box.second);
    }

    {
        const auto box = bounding_box({"3", "4"}, "3");
        assert(!box.first);
        assert(box.second);
        assert(*box.second == "4");
    }

    {
        const auto box = bounding_box({}, "3");
        assert(!box.first);
        assert(!box.second);
    }
}

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *ной метод search.

Ответы [ 2 ]

0 голосов
/ 15 мая 2018

В Rust нет API курсора, как сказано в ответе Шепмастера. Иногда вы можете смоделировать это, когда ваш итератор реализует DoubleEndedIterator с next() и next_back().

Однако, если я хорошо понимаю, что вы пытаетесь сделать, вам не нужны эти вещи, потому что набор заказан. Вы можете написать свой код, пройдя каждую пару и остановиться, когда второй элемент больше вашей «точки»: 

use std::collections::BTreeSet;

fn find_bounds<'a>(set: &'a BTreeSet<&str>, point: &str) -> (Option<&'a str>, Option<&'a str>) {
    let mut it = set.iter();
    let mut lower = match it.next() {
        None => return (None, None),
        Some(s) if *s > point => return (None, Some(s)),
        Some(s) => s,
    };

    while let Some(upper) = it.next() {
        if *upper > point {
            return (Some(lower), Some(*upper));
        }
        lower = upper;
    }
    (Some(lower), None)
}

#[test]
fn tests() {
    let mut s = BTreeSet::new();

    s.insert("a");
    s.insert("c");
    s.insert("t");
    s.insert("g");

    assert_eq!(find_bounds(&s, "f"), (Some("c"), Some("g")));
    assert_eq!(find_bounds(&s, "z"), (Some("t"), None));
    assert_eq!(find_bounds(&s, " "), (None, Some("a")));
}

Код не очень хорошо написан, но работает.

0 голосов
/ 15 мая 2018

Нет, нет способа сделать это за один поиск; вам нужно позвонить range дважды .

Были дискуссии об улучшении BTreeMap / BTreeSet, чтобы иметь "курсорный" API. Недавно был открыт запрос на получение, чтобы сделать это , но он был закрыт, так как считалось, что необходимо больше обсуждать, как должен выглядеть и работать такой API.

Возможно, вы будете тем, кто возглавит дискуссию о таком API?

Смотри также:

...