"capacity overflow" on remove when RTreeParams::MIN_SIZE = 1

[laundmo]

It appears that removing a object when the MIN_SIZE = 1 causes capacity overflow panic.

Could anyone elaobrate why? mabye this behaviour should be documented?

The code below reproduces the issue for me, on version 0.9.3

use rstar::{RStarInsertionStrategy, RTree, RTreeParams};

pub struct WierdParams;

impl RTreeParams for WierdParams {
    const MIN_SIZE: usize = 1;
    const MAX_SIZE: usize = 4;
    const REINSERTION_COUNT: usize = 1;
    type DefaultInsertionStrategy = RStarInsertionStrategy;
}

fn main() {
    let mut items: Vec<[f32; 2]> = Vec::new();
    for i in 0..2 {
        items.push([i as f32, i as f32]);
    }
    let mut tree: RTree<_, WierdParams> = RTree::bulk_load_with_params(items);
    println!("{:?}", tree.remove(&[1.0, 1.0]).is_some());
}

[urschrei]

It seems like this issue is purely related to MIN_SIZE being set to 1, as that value will trigger the panic irrespective of any other RTreeParams values, but I haven't yet figured out why.

[urschrei]

From https://github.com/georust/rstar/blob/master/rstar/src/algorithm/removal.rs#L61

If MIN_SIZE is set to 1, you end up with:

1. a call to log(1), which is 0
2. .ceil(), which is inf
3. as usize which is 18446744073709551615 (2^64 -1), causing a capacity overflow because it's bigger than 2^63 - 1 (the maximum isize value on a 64-bit platform)

So the fix could be as simple as an assert in verify_parameters

assert!(
    P::MIN_SIZE >= 2,
    "MIN_SIZE of {:?} is too small. Must be at least 2",
    P::MIN_SIZE
);

Is there any reason one would want MIN_SIZE to be 1? We'd need a slightly different way to handle that value if so.

[urschrei]

The fix now checks for 1 and sets max capacity to 1 if so and has a separate assert to ensure MIN_SIZE > 0

[laundmo]

Is there any reason one would want MIN_SIZE to be 1? We'd need a slightly different way to handle that value if so.

i was purely going by what the docs claim would get best insertion performance when i ran into this - small minsize and big maxsize. i don't quite understand exactly what these values do.