=pod

=encoding UTF-8

=head1 NAME

Range::Merge - Merges ranges of data including subset/superset ranges

=head1 VERSION

version 2.191190

=head1 SYNOPSIS

  use Range::Merge qw(merge);
  my $output = merge($inrange);

=head1 DESCRIPTION

Many problems require merging of ranges.  For instance, one can parse
a BGP route table where there are a combinatrion of routes and produce
ranges that reduce the table size.  For instance, an ISP might announce
both 192.0.2.0/28 and 192.0.2.16/28 - these could be consolidated as
192.0.2.0/27 (assuming that other constraints, such as having identical
data, are met).

IP addresses are one example of this type of data - many variations
exist.  Because IP addresses can be represented as integers, it is possible
to write a generic range merging alogirthm that operates on integers.

=head1 FUNCTIONS

=head2 merge($ranges)

This is the soul of the C<Range::Merge> module - it merges an array
reference of ranges (passed in as the sole argument).  The output is
an array reference of the merged ranges.

=head2 merge_discrete($values)

This functionality is similar to the C<merge> function, except it simply
takes an array reference of individual, discrete, value.

The output is in standard range form.

=head2 merge_ipv4($cidr)

This is functionally similar to the C<merge> function, except for the
type of input it takes. The C<$cidr> parameter must consist of an
array reference of array references.  Each of the child array references
reference of ranges (passed in as the sole argument).  The output is
an array reference of the merged ranges.

The output is then turned back into CIDRs.

=head1 RANGE DATA DEFINITION

Range data is defined as two integers, a start and an end, along with
optional data elements.  This is represented as an array reference of
array references.  Note that the "most specific" elements are used for
the desired values for a piont on a range.  For instance, this is range
data:

  [ [0,12,'foo'], [4,8,'bar'] ]

In this case, the desired output of "merged" data would be:

  [ [0,3,'foo'], [4,8,'bar'], [9,12,'foo'] ]

This example is invalid range data:

  [ [0,12,'foo'], [8,14,'bar'] ]

The above data is invalid because of an ambiguity - Does C<12>
have the value of C<'foo'> or the value of C<'bar'>?  Thus, an exception
will be thrown.

Note that multiple data elements or no data elements can be present,
so long as the start and end integers exist for each range value.  Thus,
this is valid:

  [ [0,12], [4,8] ]

This, too is valid:

  [ [0,12,'foo','baz'], [4,8,'bar','baz'] ]

In this case, we would expect the merged output to look like:

  [ [0,3,'foo','baz'], [4,8,'bar','baz'], [9,12,'foo','baz'] ]

There is a specialized version which is simply a list of numbers, such as:

  [ 0, 1, 3, 5, 6 ]

This woud return the output:

  [ [0, 1], [3, 3], [5, 6] ]

Yet another form is used by the C<merge_discrete()> function.  There is also
a variation on this where, instead of a start and end integer, there is an IP
address (IPv4 only at this point).  For example:

  [ [ '0.0.0.0/4' ], [ '128.0.0.0/1' ] ]

This form is used by the C<merge_ipv4()> function.

=head1 AUTHOR

Joelle Maslak <jmaslak@antelope.net>

=head1 COPYRIGHT AND LICENSE

This software is copyright (c) 2016-2019 by Joelle Maslak.

This is free software; you can redistribute it and/or modify it under
the same terms as the Perl 5 programming language system itself.

=cut