Get a subslice centered around a value: `slice::window`

libs
1

I needed a sub-slice around an index: the center, with a given size. While there is a sliding window (iterator) for slices there is no way to get a window around a value.

I wonder if others see value in adding something like this to the slice API. Its not trivial to write yourself as there are some tricky edge cases. I'm not sure if this should live in the std however.

Possible API:
pub fn window(&self, center: usize, window: usize) -> &[T];
Examples:
let slice = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

let (center, window_size) = (0, 4);
assert_eq(slice.window(center, window_size),  &[0, 1, 2, 3]);

let (center, window_size) = (5, 4);
assert_eq(slice.window(center, window_size),  &[4, 5, 6, 7]);

let (center, window_size) = (10, 4);
assert_eq(slice.window(center, window_size),  &[7, 8, 9, 10]);
Unresolved questions:
  • What should be the name of the method?
  • When the window size is even, should there be more elements in front or behind the center? In the examples above I chose more elements after.
  • How should the window act around the edges of the slice? Should it:
    • keep the window size the same but move the center (like in the example above)
    • return a smaller slice.
  • What should happen if the slice is smaller then the window?
Main question now:
  • Should this live in the stdlib? And if not is there a crate it should live in instead?
2

It's pretty easy to resolve these by taking a radius rather than a width.

Where radius is the distance from center to either end. center can be any index within the slice, and if center < radius or center + 1 + radius > len, you just cut off the range at either end of the slice.

Implementation would look something like this:

pub fn window_around(&self, center: usize, radius: usize) -> &Self {
    assert!(center < self.len());

    let start = center.saturating_sub(radius);
    let end = center
        .saturating_add(1)
        .saturating_add(radius)
        .min(self.len());

    &self[start..end]
}
1 Like
3

Note that this can be written fairly succinctly as

slice[(center-len/2)..][..len]

(this makes the left side longer in case of even len)

or

slice[(center-radius)..][..(radius*2+1)]

(here radius excludes the center, ie. a window with radius 2 has diameter 5.)

These panic if the window exceeds the slice bounds (though the treatment overflow is not entirely rigorous). Different handling would require a bit more code, so it's not entirely straightforward. And admittedly it's easy to make off-by-one errors writing the code by hand.

4

To match this exact behavior in the edge cases (edit: well… except it doesn’t quite work for window == 0), you could thus use something like

        &self[center
            .saturating_sub((window - 1) / 2)
            .min(self.len() - window)..][..window]

Rust Playground

Edit: And to have the balancing for even cases the other way, it’d be

        &self[center
            .saturating_sub(window / 2)
            .min(self.len() - window)..][..window]

Rust Playground

and would not fail for window == 0 either. I think I might prefer this approach, as indices often indicate positions between elements, and with that interpretation, it’d be the center of the window again…

slice  [ a , b , c , d , e , f , g ]
       ^   ^   ^   ^   ^   ^   ^   ^
       |   |   |   |   |   |   |   |
index  0   1   2   3   4   5   6   7

window around index 3, size 4:
==============================

window     [ b , c , d , e ]
       ^   ^   ^   ^   ^   ^   ^   ^
       |   |   |   |   |   |   |   |
index  0   1   2   3   4   5   6   7
5

Thanks for all those suggestions! For completion I'll add what I arrived at, it is a lot more bulky though:

fn center_window<T>(slice: &[T], center: usize, window: usize) -> &[T] {
    let space_before = center;
    let space_ahead = slice.len() - center - 1;

    let n_before;
    let n_after;

    let half_window = window.div_ceil(2);
    if center < slice.len() / 2 {
        // bigger chance that there is space ahead of the center then before
        n_before = usize::min(space_before, half_window - 1);
        n_after = usize::min(space_ahead, window - n_before - 1);
    } else {
        n_after = usize::min(space_ahead, half_window - 1);
        n_before = usize::min(space_before, window - n_after - 1);
    }

    &slice[center - n_before..=center + n_after]
}

To get back to the big question: does it make sense to have this in the std?

And if so what should the behaviour be?

  • a radius around the center (thanks pitaj!)
  • a fixed size window that moves the center when it gets close to the edge
  • both?

The fixed size window API could return an array. We could call it array_window, then the radius based approach might be called centered_window.

Normally I would think of use-cases and see if they justify adding the method however I am at a loss here. I only have my own use case: getting the n-most similar items out of an already sorted list.

6

I suppose could could think of phrasing this in terms of that iterator, though.

For example, .array_windows::<N>().nth(center - N/2), though that does have different edge cases from some of the other things brought up here.

I do wonder if there are just too many choices for this to be a good fit for std, though. Like I could easily imagine someone wanting a smaller window if the "center" is the first or last item, for example. It might be that you just writing a function that meets your specific requirements is the best option, rather than having it in core.

Are there any smaller pieces that could help you? For example, would it be helpful to have RangeInclusive::from_center_and_radius(c, r) that gives (c-r)..=(c+r)? I'm not really convinced that's overall worth it either, since I don't want to have to make checked and saturating and such versions of it, but maybe someone can come up with something smart.

7

Good point, there might be something else that could make dealing with the edge cases easier. Expanding Range is interesting.

Best I could think of is a family of functions like:

RangeInclusive::radius_around(self, center, radius)
// use it with a slice `data`:
let window = (0..data.len()).radius_around(c, r);
let window = &data[window];

It would take care of the edge cases. Will need some bounds, probably std::ops::Add and std::ops::Sub.

Its still the question whether this is worth it. I am leaning towards no now. Something like this would fit well into a numerics/slices crate like pythons numpy or a slice version of itertools. It seems better to wait for something like that to emerge then add this to the std.

8

Perhaps ndarray - Rust ? It having something for getting a neighbourhood of an element seems highly reasonable.

1 Like
9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.