Set::IntSpan::Fast 1.15

Set::IntSpan::Fast is a Perl module for fast handling of sets containing integer spans.

SYNOPSIS

use Set::IntSpan::Fast;

my $set = Set::IntSpan::Fast->new();
$set->add(1, 3, 5, 7, 9);
$set->add_range(100, 1_000_000);
print $set->as_string(), "n"; # prints 1,3,5,7,9,100-1000000

The Set::IntSpan module 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 Set::IntSpan::Fast::NEGATIVE_INFINITY and Set::IntSpan::Fast::POSITIVE_INFINITY are defined to be -(2^31-1) and (2^31-2) respectively. To create an infinite set invert an empty one:

my $inf = Set::IntSpan::Fast->new()->complement();

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):

my $pos_int = Set::IntSpan::Fast->new();
$pos_int->add_range(1, $pos_int->POSITIVE_INFINITY);

Product's homepage

Requirements:

· Perl