Hello community,
here is the log from the commit of package perl-Set-IntSpan
checked in at Fri Jan 18 00:19:51 CET 2008.
--------
--- perl-Set-IntSpan/perl-Set-IntSpan.changes 2007-08-03 22:55:37.000000000 +0200
+++ /mounts/work_src_done/STABLE/perl-Set-IntSpan/perl-Set-IntSpan.changes 2008-01-17 13:40:35.000000000 +0100
@@ -1,0 +2,8 @@
+Thu Jan 17 13:50:04 CET 2008 - pgajdos@suse.cz
+
+- updated to 1.13:
+ * recoded member(), insert(), and remove() to use a binary search
+ * added support for spans in constructors
+
+
+-------------------------------------------------------------------
Old:
----
Set-IntSpan-1.11.tar.bz2
New:
----
Set-IntSpan-1.13.tar.bz2
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Other differences:
------------------
++++++ perl-Set-IntSpan.spec ++++++
--- /var/tmp/diff_new_pack.y17623/_old 2008-01-18 00:12:37.000000000 +0100
+++ /var/tmp/diff_new_pack.y17623/_new 2008-01-18 00:12:37.000000000 +0100
@@ -1,7 +1,7 @@
#
-# spec file for package perl-Set-IntSpan (Version 1.11)
+# spec file for package perl-Set-IntSpan (Version 1.13)
#
-# Copyright (c) 2007 SUSE LINUX Products GmbH, Nuernberg, Germany.
+# Copyright (c) 2008 SUSE LINUX Products GmbH, Nuernberg, Germany.
# This file and all modifications and additions to the pristine
# package are under the same license as the package itself.
#
@@ -11,12 +11,12 @@
# norootforbuild
Name: perl-Set-IntSpan
-Version: 1.11
+Version: 1.13
Release: 1
Summary: Perl module for managing sets of integers
Group: Development/Libraries/Perl
-License: Artistic License, GPL v2 or later
-URL: http://search.cpan.org/dist/Set-IntSpan/
+License: Artistic License; GPL v2 or later
+Url: http://search.cpan.org/dist/Set-IntSpan/
Source0: Set-IntSpan-%{version}.tar.bz2
Requires: perl >= %{perl_version}
BuildRequires: perl >= 5.6
@@ -60,19 +60,23 @@
%{_var}/adm/perl-modules/perl-Set-IntSpan
%changelog
-* Fri Jul 27 2007 - pgajdos@suse.cz
+* Thu Jan 17 2008 pgajdos@suse.cz
+- updated to 1.13:
+ * recoded member(), insert(), and remove() to use a binary search
+ * added support for spans in constructors
+* Fri Jul 27 2007 pgajdos@suse.cz
- package moved from OBS, version 1.11
-* Thu Jun 21 2007 - sierkb@gmx.de
+* Thu Jun 21 2007 sierkb@gmx.de
- Update to version 1.11
- Optimize packlist handling
-* Mon Nov 13 2006 - sierkb@gmx.de
+* Mon Nov 13 2006 sierkb@gmx.de
- Rebuild for openSUSE
- Spec file cleanup: removed # neededforbuild
-* Thu Jun 22 2006 - sierkb@gmx.de
+* Thu Jun 22 2006 sierkb@gmx.de
- Update to version 1.09
-* Thu Jun 15 2006 - sierkb@gmx.de
+* Thu Jun 15 2006 sierkb@gmx.de
- Rebuild for SUSE Linux 10.1
-* Tue Nov 15 2005 - sierkb@gmx.de
+* Tue Nov 15 2005 sierkb@gmx.de
- Rebuild for SUSE Linux 10.0 OSS
-* Fri Jun 10 2005 - sierkb@gmx.de
+* Fri Jun 10 2005 sierkb@gmx.de
- Initial build for SuSE Linux
++++++ Set-IntSpan-1.11.tar.bz2 -> Set-IntSpan-1.13.tar.bz2 ++++++
diff -urN --exclude=CVS --exclude=.cvsignore --exclude=.svn --exclude=.svnignore old/Set-IntSpan-1.11/Changes new/Set-IntSpan-1.13/Changes
--- old/Set-IntSpan-1.11/Changes 2007-03-17 22:05:43.000000000 +0100
+++ new/Set-IntSpan-1.13/Changes 2007-10-27 10:05:33.000000000 +0200
@@ -1,5 +1,11 @@
jRevision history for Perl extension Set::IntSpan
+1.13 2007 Oct 27
+ - recoded member(), insert(), and remove() to use a binary search
+
+1.12 2007 Sep 08
+ - added support for spans in constructors
+
1.11 2007 Mar 17
- added mutating set operations
- added operator overloads
@@ -14,7 +20,7 @@
1.09 2005 Dec 13
- added indexing methods
- - 'die' instead of 'craok' on fatal errors
+ - 'die' instead of 'croak' on fatal errors
1.08 2004 May 07
- added the spans method
diff -urN --exclude=CVS --exclude=.cvsignore --exclude=.svn --exclude=.svnignore old/Set-IntSpan-1.11/IntSpan.pm new/Set-IntSpan-1.13/IntSpan.pm
--- old/Set-IntSpan-1.11/IntSpan.pm 2007-03-17 18:49:20.000000000 +0100
+++ new/Set-IntSpan-1.13/IntSpan.pm 2007-10-28 02:58:50.000000000 +0200
@@ -6,7 +6,7 @@
use base qw(Exporter);
use Carp;
-our $VERSION = '1.11';
+our $VERSION = '1.13';
our @EXPORT_OK = qw(grep_set map_set grep_spans map_spans);
use overload
@@ -160,25 +160,103 @@
{
my($set, $array) = @_;
+ my @spans = map { ref $_ ? [ @$_ ] : [ $_, $_ ] } @$array;
+
+ $set->_insert_spans(\@spans)
+}
+
+
+sub bySpan
+{
+ my($al, $au) = @$a;
+ my($bl, $bu) = @$b;
+
+ if (defined $al && defined $bl) { return $al <=> $bl; }
+ elsif (defined $al ) { return 1; }
+ elsif ( defined $bl) { return -1; }
+ elsif (defined $au ) { return -1; }
+ elsif ( defined $bu) { return 1; }
+ else { return 0; }
+}
+
+sub _insert_spans
+{
+ my($set, $spans) = @_;
+
+ my @edges;
$set->{negInf} = 0;
$set->{posInf} = 0;
+ $set->{edges } = \@edges;
- my @edges;
- for my $element (sort { $a <=> $b } @$array)
+ my @spans = sort bySpan @$spans;
+
+ if (@spans and not defined $spans[0][0])
+ {
+ $set->{negInf} = 1;
+ my $span = shift @spans;
+
+ if (not defined $span->[1])
+ {
+ $set->{posInf} = 1;
+ return $set;
+ }
+
+ push @edges, $span->[1];
+
+ while (@spans and not defined $spans[0][0])
+ {
+ my $span = shift @spans;
+ $edges[0] = $span->[1] if $edges[0] < $span->[1];
+ }
+ }
+
+ for (@spans) { $_->[0]--; }
+
+ if (@spans and not @edges)
+ {
+ my $span = shift @spans;
+
+ if (defined $span->[1])
+ {
+ push @edges, @$span;
+ }
+ else
+ {
+ push @edges, $span->[0];
+ $set->{posInf} = 1;
+ return $set;
+ }
+ }
+
+ while (@spans and defined $spans[0][1])
+ {
+ my $span = shift @spans;
+ if ($edges[-1] < $span->[0])
+ {
+ push @edges, @$span;
+ }
+ else
+ {
+ $edges[-1] = $span->[1] if $edges[-1] < $span->[1];
+ }
+ }
+
+ if (@spans)
{
- next if @edges and $edges[-1] == $element; # skip duplicates
+ $set->{posInf} = 1;
+ my $span = shift @spans;
- if (@edges and $edges[-1] == $element-1)
+ if ($edges[-1] < $span->[0])
{
- $edges[-1] = $element;
+ push @edges, $span->[0];
}
else
{
- push @edges, $element-1, $element;
+ pop @edges;
}
}
- $set->{edges} = \@edges
+ return $set
}
@@ -763,54 +841,29 @@
{
my($set, $n) = @_;
- my $inSet = $set->{negInf};
- my $edge = $set->{edges};
-
- for (my $i=0; $i<@$edge; $i++)
- {
- if ($inSet)
- {
- return 1 if $n <= $$edge[$i];
- $inSet = 0;
- }
- else
- {
- return 0 if $n <= $$edge[$i];
- $inSet = 1;
- }
- }
+ my $i = _bsearch($set->{edges}, $n);
- $inSet
+ $set->{negInf} xor $i & 1
}
+use constant INSERT => 0;
+use constant REMOVE => 1;
+
+sub insert { _indel(@_, INSERT); }
+sub remove { _indel(@_, REMOVE); }
-sub insert
+sub _indel # INsertion/DELetion
{
- my($set, $n) = @_;
+ my($set, $n, $indel) = @_;
defined $n or return;
- my $inSet = $set->{negInf};
my $edge = $set->{edges};
+ my $i = _bsearch($edge, $n);
- my $i;
- for ($i=0; $i<@$edge; $i++)
- {
- if ($inSet)
- {
- $n <= $edge->[$i] and return;
- $inSet = 0;
- }
- else
- {
- $n <= $edge->[$i] and last;
- $inSet = 1;
- }
- }
-
- $inSet and return;
+ return if $set->{negInf} xor $i & 1 xor $indel;
- my $lGap = $i==0 || $n-1 - $edge->[$i-1];
- my $rGap = $i==@$edge || $edge->[$i] - $n;
+ my $lGap = $i==0 || $edge->[$i-1] < $n-1;
+ my $rGap = $i==@$edge || $n < $edge->[$i];
if ( $lGap and $rGap) { splice @$edge, $i, 0, $n-1, $n }
elsif (not $lGap and $rGap) { $edge->[$i-1]++ }
@@ -818,34 +871,35 @@
else { splice @$edge, $i-1, 2 }
}
-
-sub remove
+# Returns the index of the first edge that satisifies target <= edge.
+# Returns $#$edges+1 if target > the last edge.
+# Returns 0 if edges is empty.
+sub _bsearch
{
- my($set, $n) = @_;
- defined $n or return;
+ my($edges, $target) = @_;
- my $inSet = $set->{negInf};
- my $edge = $set->{edges};
+ @$edges or return 0;
+
+ my $lower = 0;
+ my $upper = $#$edges;
- my $i;
- for ($i=0; $i<@$edge; $i++)
+ while ($lower+1 < $upper)
{
- if ($inSet)
+ my $mid = int(($lower + $upper) / 2);
+
+ if ($target <= $edges->[$mid])
{
- last if $n <= $$edge[$i];
- $inSet = 0;
+ $upper = $mid;
}
else
{
- return if $n <= $$edge[$i];
- $inSet = 1;
+ $lower = $mid+1;
}
}
- return unless $inSet;
-
- splice @{$set->{edges}}, $i, 0, $n-1, $n;
- $set->_cleanup;
+ $target <= $edges->[$lower] and return $lower;
+ $target <= $edges->[$upper] and return $upper;
+ $upper + 1
}
@@ -1099,25 +1153,12 @@
$sub_set
}
-sub bySpan
-{
- my($al, $au) = @$a;
- my($bl, $bu) = @$b;
-
- if (defined $al && defined $bl) { return $al <=> $bl; }
- elsif (defined $al ) { return 1; }
- elsif ( defined $bl) { return -1; }
- elsif (defined $au ) { return -1; }
- elsif ( defined $bu) { return 1; }
- else { return 0; }
-}
-
sub map_spans(&$)
{
my($block, $set) = @_;
my @edges = @{$set->{edges}};
- my @spans = ();
+ my @spans;
if ($set->{negInf} and $set->{posInf})
{
@@ -1145,78 +1186,7 @@
push @spans, &$block();
}
- @spans = sort bySpan @spans;
- @edges = ();
- my $map_set = $set->new;
- $map_set->{edges} = \@edges;
-
- if (@spans and not defined $spans[0][0])
- {
- $map_set->{negInf} = 1;
- my $span = shift @spans;
-
- if (not defined $span->[1])
- {
- $map_set->{posInf} = 1;
- return $map_set;
- }
-
- push @edges, $span->[1];
-
- while (@spans and not defined $spans[0][0])
- {
- my $span = shift @spans;
- $edges[0] = $span->[1] if $edges[0] < $span->[1];
- }
- }
-
- for (@spans) { $_->[0]--; }
-
- if (@spans and not @edges)
- {
- my $span = shift @spans;
-
- if (defined $span->[1])
- {
- push @edges, @$span;
- }
- else
- {
- push @edges, $span->[0];
- $map_set->{posInf} = 1;
- return $map_set;
- }
- }
-
- while (@spans and defined $spans[0][1])
- {
- my $span = shift @spans;
- if ($edges[-1] < $span->[0])
- {
- push @edges, @$span;
- }
- else
- {
- $edges[-1] = $span->[1] if $edges[-1] < $span->[1];
- }
- }
-
- if (@spans)
- {
- $map_set->{posInf} = 1;
- my $span = shift @spans;
-
- if ($edges[-1] < $span->[0])
- {
- push @edges, $span->[0];
- }
- else
- {
- pop @edges;
- }
- }
-
- $map_set
+ $set->new->_insert_spans(\@spans)
}
@@ -1708,17 +1678,42 @@
alt.foo: 1-21,28,31
alt.bar: 1-14192,14194,14196-14221
+A run of consecutive integers is sometimes called a I<span>.
+
Sets are stored internally in a run-length coded form.
This provides for both compact storage and efficient computation.
In particular,
set operations can be performed directly on the encoded representation.
CSet::IntSpan is designed to manage finite sets.
-However, it can also represent some simple infinite sets, such as {x | x>n}.
+However, it can also represent some simple infinite sets, such as { x | x>n }.
This allows operations involving complements to be carried out consistently,
without having to worry about the actual value of INT_MAX on your machine.
+=head1 SPANS
+
+A I<span> is a run of consecutive integers.
+A span may be represented by an array reference,
+in any of 5 forms:
+
+=head2 Finite forms
+
+ Span Set
+ [ $n, $n ] { n }
+ [ $a, $b ] { x | a<=x && x<=b}
+
+=head2 Infinite forms
+
+ Span Set
+ [ undef, $b ] { x | x<=b }
+ [ $a , undef ] { x | x>=a }
+ [ undef, undef ] The set of all integers
+
+
+Some methods operate directly on spans.
+
+
=head1 SET SPECIFICATIONS
Many of the methods take a I<set specification>.
@@ -1737,16 +1732,11 @@
removes all elements from $set.
+
=head2 Object reference
If an object reference is given, it is taken to be a CSet::IntSpan object.
-=head2 Array reference
-
-If an array reference is given,
-then the elements of the array are taken to be the elements of the set.
-The array may contain duplicate elements.
-The elements of the array may be in any order.
=head2 Run list
@@ -1757,7 +1747,7 @@
Each run specifies a set of consecutive integers.
The set is the union of all the runs.
-Runs may be written in any of several forms.
+Runs may be written in any of 5 forms.
=head2 Finite forms
@@ -1769,7 +1759,7 @@
=item a-b
-{x | a<=x && x<=b}
+{ x | a<=x && x<=b }
=back
@@ -1779,11 +1769,11 @@
=item (-n
-{x | x<=n}
+{ x | x<=n }
=item n-)
-{x | x>=n}
+{ x | x>=n }
=item (-)
@@ -1807,37 +1797,48 @@
=head2 Examples
-=over 15
-
-=item S< >-
-
-{ }
+ Run list Set
+ "-" { }
+ "1" { 1 }
+ "1-2" { 1, 2 }
+ "-5--1" { -5, -4, -3, -2, -1 }
+ "(-)" the integers
+ "(--1" the negative integers
+ "1-3, 4, 18-21" { 1, 2, 3, 4, 18, 19, 20, 21 }
-=item S< >1
-{ 1 }
+=head2 Array reference
-=item S< >1-2
+If an array reference is given,
+then the elements of the array specify the elements of the set.
+The array may contain
-{ 1, 2 }
+=over 4
-=item S< >-5--1
+=item *
-{ -5, -4, -3, -2, -1 }
+integers
-=item S< >(-)
+=item *
-the integers
+L
%d\n",
+ printf "#%-12s %-12s %d -> %d\n",
"member", $run_list, $int, $result;
my $expected = $Member->[$s][$i];
$result ? $expected : ! $expected or Not; OK;
@@ -90,11 +90,9 @@
$set->$method($int);
my $result = run_list $set;
- printf "#%-12s %-12s %d -> %s\n",
+ printf "#%-12s %-12s %d -> %s\n",
$method, $run_list, $int, $result;
$result eq $expected->[$s][$i] or Not; OK;
}
}
}
-
-
diff -urN --exclude=CVS --exclude=.cvsignore --exclude=.svn --exclude=.svnignore old/Set-IntSpan-1.11/t/overload.t new/Set-IntSpan-1.13/t/overload.t
--- old/Set-IntSpan-1.11/t/overload.t 2007-03-17 18:42:55.000000000 +0100
+++ new/Set-IntSpan-1.13/t/overload.t 2007-10-27 10:09:12.000000000 +0200
@@ -1,7 +1,7 @@
# -*- perl -*-
use strict;
-use Set::IntSpan 1.11;
+use Set::IntSpan 1.13;
my $N = 1;
sub Not { print "not " }
diff -urN --exclude=CVS --exclude=.cvsignore --exclude=.svn --exclude=.svnignore old/Set-IntSpan-1.11/t/real_set.t new/Set-IntSpan-1.13/t/real_set.t
--- old/Set-IntSpan-1.11/t/real_set.t 2007-02-19 01:25:56.000000000 +0100
+++ new/Set-IntSpan-1.13/t/real_set.t 2007-10-27 10:09:17.000000000 +0200
@@ -1,7 +1,7 @@
# -*- perl -*-
use strict;
-use Set::IntSpan 1.07;
+use Set::IntSpan 1.13;
my $N = 1;
sub Not { print "not " }
diff -urN --exclude=CVS --exclude=.cvsignore --exclude=.svn --exclude=.svnignore old/Set-IntSpan-1.11/t/relation.t new/Set-IntSpan-1.13/t/relation.t
--- old/Set-IntSpan-1.11/t/relation.t 2007-02-19 01:25:56.000000000 +0100
+++ new/Set-IntSpan-1.13/t/relation.t 2007-10-27 10:09:22.000000000 +0200
@@ -1,7 +1,7 @@
# -*- perl -*-
use strict;
-use Set::IntSpan 1.07;
+use Set::IntSpan 1.13;
my $N = 1;
sub Not { print "not " }
diff -urN --exclude=CVS --exclude=.cvsignore --exclude=.svn --exclude=.svnignore old/Set-IntSpan-1.11/t/set_spec.t new/Set-IntSpan-1.13/t/set_spec.t
--- old/Set-IntSpan-1.11/t/set_spec.t 2007-02-19 01:25:56.000000000 +0100
+++ new/Set-IntSpan-1.13/t/set_spec.t 2007-10-27 10:09:30.000000000 +0200
@@ -1,7 +1,7 @@
-# -*- perl -*-
-
+# -*- perl -*-
+
use strict;
-use Set::IntSpan 1.07;
+use Set::IntSpan 1.13;
my $N = 1;
sub Not { print "not " }
diff -urN --exclude=CVS --exclude=.cvsignore --exclude=.svn --exclude=.svnignore old/Set-IntSpan-1.11/t/spans.t new/Set-IntSpan-1.13/t/spans.t
--- old/Set-IntSpan-1.11/t/spans.t 2007-03-04 15:57:57.000000000 +0100
+++ new/Set-IntSpan-1.13/t/spans.t 2007-10-27 10:09:35.000000000 +0200
@@ -1,7 +1,7 @@
# -*- perl -*-
use strict;
-use Set::IntSpan 1.10 qw(grep_spans map_spans);
+use Set::IntSpan 1.13 qw(grep_spans map_spans);
my $N = 1;
sub Not { print "not " }
diff -urN --exclude=CVS --exclude=.cvsignore --exclude=.svn --exclude=.svnignore old/Set-IntSpan-1.11/t/subclass.t new/Set-IntSpan-1.13/t/subclass.t
--- old/Set-IntSpan-1.11/t/subclass.t 2007-02-19 01:25:56.000000000 +0100
+++ new/Set-IntSpan-1.13/t/subclass.t 2007-10-27 10:09:40.000000000 +0200
@@ -1,7 +1,7 @@
# -*- perl -*-
use strict;
-use Set::IntSpan 1.07;
+use Set::IntSpan 1.13;
@Foo::Bar::ISA = qw(Set::IntSpan);
diff -urN --exclude=CVS --exclude=.cvsignore --exclude=.svn --exclude=.svnignore old/Set-IntSpan-1.11/t/unary.t new/Set-IntSpan-1.13/t/unary.t
--- old/Set-IntSpan-1.11/t/unary.t 2007-03-17 04:01:51.000000000 +0100
+++ new/Set-IntSpan-1.13/t/unary.t 2007-10-27 10:09:45.000000000 +0200
@@ -1,7 +1,7 @@
# -*- perl -*-
use strict;
-use Set::IntSpan 1.11;
+use Set::IntSpan 1.13;
my $N = 1;
sub Not { print "not " }
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Remember to have fun...
---------------------------------------------------------------------
To unsubscribe, e-mail: opensuse-commit+unsubscribe@opensuse.org
For additional commands, e-mail: opensuse-commit+help@opensuse.org
participants (1)