rstared

rstared::RTreed is a simple Rust decorator that adds a passively listening R-tree, rstar::RTree, to the following collections:

HashMap, gated by the std feature (enabled by default);
HashSet, gated by the std feature (enabled by default);
BTreeMap, not feature-gated;
BTreeSet, not feature-gated;
stable_vec::StableVec, gated by the stable-vec feature (example usage: examples/stable_vec.rs);
thunderdome::Arena, gated by the thunderdome feature (example usage: examples/thunderdome.rs).

This library is no_std-compatible and has no mandatory third-party dependencies except for alloc.

Usage

Basic usage

Add rstared as a dependency to your Cargo.toml together with the features that gate the collections you are going to use. For example, to use rstared with stable_vec::StableVec and thunderdome::Arena, write

[dependencies]
rstared = { version = "0.3", features = ["stable-vec", "thunderdome"] }

Following is a basic usage example taken from examples/basic_usage.rs:

use std::collections::HashMap;

use rstar::{AABB, primitives::Rectangle};
use rstared::{Insert, RTreed, Remove};

fn main() {
    // A hashmap of 2D rectangles will be the underlying collection.
    let rect_hashmap: HashMap<i32, Rectangle<(i32, i32)>> = HashMap::new();

    // Wrap `RTreed` around the hashmap.
    let mut rtreed =
        RTreed::<i32, Rectangle<(i32, i32)>, HashMap<i32, Rectangle<(i32, i32)>>>::new(
            rect_hashmap,
        );

    // Insert two rectangles, recording them in the R-tree.
    rtreed.insert(1, Rectangle::from_corners((0, 0), (1, 1)));
    rtreed.insert(2, Rectangle::from_corners((1, 1), (2, 2)));

    // Locate the two rectangles in the R-tree.
    assert_eq!(
        rtreed
            .rtree()
            .locate_in_envelope(&AABB::from_corners((0, 0), (2, 2)))
            .count(),
        2
    );

    // Now remove one of the rectangles, recording this in the R-tree.
    rtreed.remove(&1);

    // Make the same query to the R-tree as before.
    // Only one rectangle is now present.
    assert_eq!(
        rtreed
            .rtree()
            .locate_in_envelope(&AABB::from_corners((0, 0), (2, 2)))
            .count(),
        1
    );
}

Usage on maps with pushing

Some data structures with map semantics also provide a special type of insertion where a value is inserted without specifying a key, which the structure instead automatically generates and returns by itself. This operation is called pushing.

If a supported type has a push interface, you can use it through RTreed by calling .push(), like this:

rtreed.push('A');

StableVec and thunderdome::Arena are instances of supported pushable maps.

Contributing

We welcome issues and pull requests from anyone both to our canonical repository on Codeberg and to our GitHub mirror.

Licence

undoredo is dual-licensed as under either of