Crate intspan

IntSpan handles of sets containing integer spans.

SYNOPSIS

use intspan::IntSpan;

let mut set = IntSpan::new();
for i in vec![1, 2, 3, 5, 7, 9] {
    set.add_n(i);
}
set.add_pair(100, 10000);
set.remove_n(1000);

let expected = "1-3,5,7,9,100-999,1001-10000";

let set = IntSpan::from("1-3,5,7,9,100-999,1001-10000");

DESCRIPTION

IntSpan represents sets of integers as a number of inclusive ranges, for example 1-10,19-23,45-48. Because many of its operations involve linear searches of the list of ranges its overall performance tends to be proportional to the number of distinct ranges. This is fine for small sets but suffers compared to other possible set representations (bit vectors, hash keys) when the number of ranges grows large.

This module also represents sets as ranges of values but stores those ranges in order and uses a binary search for many internal operations so that overall performance tends towards O log N where N is the number of ranges.

The internal representation used by this module is extremely simple: a set is represented as a list of integers. Integers in even numbered positions (0, 2, 4 etc) represent the start of a run of numbers while those in odd numbered positions represent the ends of runs. As an example the set (1, 3-7, 9, 11, 12) would be represented internally as (1, 2, 3, 8, 11, 13).

Sets may be infinite - assuming you're prepared to accept that infinity is actually no more than a fairly large integer. Specifically the constants neg_inf and pos_inf are defined to be (-2^31+1) and (2^31-2) respectively. To create an infinite set invert an empty one:

let mut set = IntSpan::new();
set.invert();

Sets need only be bounded in one direction - for example this is the set of all positive integers (assuming you accept the slightly feeble definition of infinity we're using):

let mut set = IntSpan::new();
set.add_pair(1, set.get_pos_inf());

This Rust crate is ported from the Java class jintspan and the Perl module AlignDB::IntSpan, which contains many codes from Set::IntSpan, Set::IntSpan::Fast and Set::IntSpan::Island.

Structs

IntSpan