File Coverage

blib/lib/Math/Polynomial/ModInt/Order.pm

Criterion	Covered	Total	%
statement	80	80	100.0
branch	20	20	100.0
condition	29	29	100.0
subroutine	16	16	100.0
pod	7	7	100.0
total	152	152	100.0

package Math::Polynomial::ModInt::Order;

use strict;
use warnings;

BEGIN {
    require Exporter;
    our @ISA = qw(Exporter);
    our @EXPORT_OK = qw($BY_INDEX $SPARSE $CONWAY);
    our %EXPORT_TAGS = ( all => \@EXPORT_OK );
    our $VERSION = '0.002';
}

sub cmp { $_[0]->(@_[1, 2])      }
sub eq  { $_[0]->(@_[1, 2]) == 0 }
sub ne  { $_[0]->(@_[1, 2]) != 0 }
sub lt  { $_[0]->(@_[1, 2]) <  0 }
sub le  { $_[0]->(@_[1, 2]) <= 0 }
sub gt  { $_[0]->(@_[1, 2]) >  0 }
sub ge  { $_[0]->(@_[1, 2]) >= 0 }

package Math::Polynomial::ModInt::Order::ByIndex;

our @ISA = (Math::Polynomial::ModInt::Order::);
$Math::Polynomial::ModInt::Order::BY_INDEX = bless \&_compare;

sub _compare ($$) {
    my ($a, $b) = @_;
    my $n = $a->degree;
    my $result =
        $a->modulus <=> $b->modulus ||
        $n          <=> $b->degree;
    while (!$result && $n >= 0) {
        $result = $a->coeff($n)->residue <=> $b->coeff($n)->residue;
        --$n;
    }
    return $result;
}

sub next_poly {
    my ($class, $poly) = @_;
    my @coeff  = $poly->coeff;
    my $one    = $poly->coeff_one;
    my $i = 0;
    {
        if ($i < @coeff) {
            $coeff[$i++] += $one or redo;
        }
        else {
            $coeff[$i] = $one;
        }
    }
    return $poly->new(@coeff);
}

package Math::Polynomial::ModInt::Order::Sparse;

our @ISA = (Math::Polynomial::ModInt::Order::);
$Math::Polynomial::ModInt::Order::SPARSE = bless \&_compare;

sub _compare ($$) {
    my ($a, $b) = @_;
    my $n = $a->proper_degree || 0;
    my $result =
        $a->modulus            <=> $b->modulus            ||
        $a->degree             <=> $b->degree             ||
        $a->coeff($n)->residue <=> $b->coeff($n)->residue ||
        $a->number_of_terms    <=> $b->number_of_terms;
    while (!$result && --$n >= 0) {
        $result = $a->coeff($n)->residue <=> $b->coeff($n)->residue;
    }
    return $result;
}

sub next_poly {
    my ($class, $poly) = @_;
    my @coeff  = $poly->coefficients;
    my $zero   = $poly->coeff_zero;
    my $one    = $poly->coeff_one;
    my $i = 0;
    my $j = 0;
    while ($i < $#coeff && $zero == $coeff[$i]) {
        ++$i;
    }
    while ($i < $#coeff && $zero == ($coeff[$i] += $one)) {
        ++$j;
        ++$i;
    }
    if ($i == $#coeff) {
        if ($j < $i) {
            ++$j;
        }
        else {
            $j = 0;
            if ($zero == ($coeff[$i] += $one)) {
                $coeff[++$i] = $one;
            }
        }
    }
    elsif ($j && $one == $coeff[$i]) {
        --$j;
    }
    while ($j > 0) {
        $coeff[--$j] = $one;
    }
    return $poly->new(@coeff);
}

package Math::Polynomial::ModInt::Order::Conway;

our @ISA = (Math::Polynomial::ModInt::Order::);
$Math::Polynomial::ModInt::Order::CONWAY = bless \&_compare;

sub _compare ($$) {
    my ($a, $b) = @_;
    my $n = $a->degree;
    my $inv = 0;
    my $result =
        $a->modulus <=> $b->modulus ||
        $n          <=> $b->degree;
    while (!$result && $n >= 0) {
        $result =
            $inv?
                (-$a->coeff($n))->residue <=> (-$b->coeff($n))->residue:
                ( $a->coeff($n))->residue <=> ( $b->coeff($n))->residue;
        --$n;
        $inv ^= 1;
    }
    return $result;
}

sub next_poly {
    my ($class, $poly) = @_;
    my @coeff  = $poly->coeff;
    my $one    = $poly->coeff_one;
    my $delta  = 1 & @coeff? $one: -$one;
    my $i = 0;
    {
        if ($i < @coeff) {
            $coeff[$i++] += $delta or $delta = -$delta, redo;
        }
        else {
            $coeff[$i] = $one;
        }
    }
    return $poly->new(@coeff);
}

1;

__END__