#range #smallvec #sorting #let #v

range-set

Smallvec-backed containers of sorted integer ranges

8 releases

0.0.10 Jul 16, 2023
0.0.9 Apr 16, 2022
0.0.8 Oct 8, 2021
0.0.7 Jun 25, 2021
0.0.4 Apr 30, 2018

#143 in Rust patterns

Download history 475/week @ 2023-08-12 793/week @ 2023-08-19 817/week @ 2023-08-26 814/week @ 2023-09-02 944/week @ 2023-09-09 993/week @ 2023-09-16 967/week @ 2023-09-23 872/week @ 2023-09-30 1060/week @ 2023-10-07 871/week @ 2023-10-14 940/week @ 2023-10-21 1276/week @ 2023-10-28 1330/week @ 2023-11-04 1453/week @ 2023-11-11 1179/week @ 2023-11-18 1111/week @ 2023-11-25

5,168 downloads per month
Used in 4 crates (2 directly)

Apache-2.0

55KB
903 lines

range-set

Store collections of PrimInt values as inclusive ranges using generic SmallVec-backed storage.

Documentation

A generic smallvec::Array parameter allows choosing how many ranges will fit on the stack before spilling over onto the heap:

let mut s = RangeSet::<[RangeInclusive <u32>; 1]>::from (0..=2);
println!("s: {:?}", s);
assert!(!s.spilled());

assert!(s.insert_range (8..=10).is_none());
println!("s: {:?}", s);
assert!(s.spilled());
let v : Vec <u32> = s.iter().collect();
assert_eq!(v, vec![0,1,2,8,9,10]);

assert_eq!(s.insert_range (3..=12), Some (RangeSet::from (8..=10)));
println!("s: {:?}", s);
assert!(!s.spilled());
let v : Vec <u32> = s.iter().collect();
assert_eq!(v, vec![0,1,2,3,4,5,6,7,8,9,10,11,12]);

This is most useful with large blocks of not-quite contiguous data that should be traversed in-order.

Usage

  use range_set::RangeSet;
  use std::ops::RangeInclusive;
  let mut s = RangeSet::<[RangeInclusive <u32>; 2]>::from_ranges (vec![
    1..=100,
    500..=1000
  ].into()).unwrap();
  s.insert (200);
  s.insert (400..=499);
  assert_eq!(s, RangeSet::from_ranges (vec![
    1..=100,
    200..=200,
    400..=1000
  ].into()).unwrap());

See ./examples/example.rs and documentation for more examples.

On-stack sizes

The top-level report_sizes function will report byte sizes for various combinations of integer types and array sizes. A program calling this function can be found in ./examples/example.rs. Example output:

RangeSet report sizes...
  size of RangeSet <[RangeInclusive <u8>; 1]>: 32
  size of RangeSet <[RangeInclusive <u16>; 1]>: 32
  size of RangeSet <[RangeInclusive <u32>; 1]>: 32
  size of RangeSet <[RangeInclusive <u64>; 1]>: 32
  size of RangeSet <[RangeInclusive <usize>; 1]>: 32
  size of RangeSet <[RangeInclusive <u8>; 2]>: 32
  size of RangeSet <[RangeInclusive <u16>; 2]>: 32
  size of RangeSet <[RangeInclusive <u32>; 2]>: 32
  size of RangeSet <[RangeInclusive <u64>; 2]>: 48
  size of RangeSet <[RangeInclusive <usize>; 2]>: 48
  size of RangeSet <[RangeInclusive <u8>; 4]>: 32
  size of RangeSet <[RangeInclusive <u16>; 4]>: 32
  size of RangeSet <[RangeInclusive <u32>; 4]>: 48
  size of RangeSet <[RangeInclusive <u64>; 4]>: 80
  size of RangeSet <[RangeInclusive <usize>; 4]>: 80
  size of RangeSet <[RangeInclusive <u8>; 8]>: 32
  size of RangeSet <[RangeInclusive <u16>; 8]>: 48
  size of RangeSet <[RangeInclusive <u32>; 8]>: 80
  size of RangeSet <[RangeInclusive <u64>; 8]>: 144
  size of RangeSet <[RangeInclusive <usize>; 8]>: 144
  size of RangeSet <[RangeInclusive <u8>; 16]>: 48
  size of RangeSet <[RangeInclusive <u16>; 16]>: 80
  size of RangeSet <[RangeInclusive <u32>; 16]>: 144
  size of RangeSet <[RangeInclusive <u64>; 16]>: 272
  size of RangeSet <[RangeInclusive <usize>; 16]>: 272
...RangeSet report sizes

Storing u8 (byte) ranges is not a good idea since the minimum size (to store a single range on the stack) is 32 bytes which is enough to store the full range of 256 values as individual bits (32 * 8 = 256).

Operations

Since the ranges are stored in sorted order, binary search is used when inserting and removing values.

Dependencies

~145–395KB