Algorithm-CP-IZ
view release on metacpan or search on metacpan
lib/Algorithm/CP/IZ.pm view on Meta::CPAN
package Algorithm::CP::IZ;
use 5.010000; # need Newx in XS
use strict;
use warnings;
use Carp;
use Scalar::Util qw(weaken blessed looks_like_number);
require Exporter;
use AutoLoader;
use Algorithm::CP::IZ::Int;
use Algorithm::CP::IZ::RefVarArray;
use Algorithm::CP::IZ::RefIntArray;
use Algorithm::CP::IZ::ParamValidator qw(validate);
use Algorithm::CP::IZ::ValueSelector;
use Algorithm::CP::IZ::CriteriaValueSelector;
use Algorithm::CP::IZ::NoGoodSet;
use Algorithm::CP::IZ::SearchNotify;
our @ISA = qw(Exporter);
# Items to export into callers namespace by default. Note: do not export
# names by default without a very good reason. Use EXPORT_OK instead.
# Do not simply export all your public functions/methods/constants.
# This allows declaration use Algorithm::CP::IZ ':all';
# If you do not need this, moving things directly into @EXPORT or @EXPORT_OK
# will save memory.
our %EXPORT_TAGS = ( 'value_selector' => [ qw(
CS_VALUE_SELECTOR_MIN_TO_MAX
CS_VALUE_SELECTOR_MAX_TO_MIN
CS_VALUE_SELECTOR_LOWER_AND_UPPER
CS_VALUE_SELECTOR_UPPER_AND_LOWER
CS_VALUE_SELECTOR_MEDIAN_AND_REST
CS_VALUE_SELECTION_EQ
CS_VALUE_SELECTION_NEQ
CS_VALUE_SELECTION_LE
CS_VALUE_SELECTION_LT
CS_VALUE_SELECTION_GE
CS_VALUE_SELECTION_GT
) ]);
our @EXPORT_OK = ( @{ $EXPORT_TAGS{'value_selector'} } );
our $VERSION = '0.07';
sub AUTOLOAD {
# This AUTOLOAD is used to 'autoload' constants from the constant()
# XS function.
my $constname;
our $AUTOLOAD;
($constname = $AUTOLOAD) =~ s/.*:://;
croak "&Algorithm::CP::IZ::constant not defined" if $constname eq 'constant';
my ($error, $val) = constant($constname);
if ($error) { croak $error; }
{
no strict 'refs';
# Fixed between 5.005_53 and 5.005_61
#XXX if ($] >= 5.00561) {
#XXX *$AUTOLOAD = sub () { $val };
#XXX }
#XXX else {
*$AUTOLOAD = sub { $val };
#XXX }
}
goto &$AUTOLOAD;
}
require XSLoader;
XSLoader::load('Algorithm::CP::IZ', $VERSION);
# Preloaded methods go here.
# Autoload methods go after =cut, and are processed by the autosplit program.
my $Instances = 0;
sub _report_error {
my $msg = shift;
croak __PACKAGE__ . ": ". $msg;
}
sub new {
my $class = shift;
if ($Instances > 0) {
_report_error("another instance is working.");
}
Algorithm::CP::IZ::cs_init();
$Instances++;
bless {
_vars => [],
_cxt0 => [],
_cxt => [],
_const_vars => {},
_backtracks => {},
_ref_int_arrays => {},
_ref_var_arrays => {},
}, $class;
}
lib/Algorithm/CP/IZ.pm view on Meta::CPAN
&& scalar @$vs == scalar @$var_array);
for my $obj (@$vs) {
return unless (blessed($obj)
&& $obj->isa("Algorithm::CP::IZ::ValueSelector"));
}
1;
}], "search: ValueSelectos must be a arrayref of Algorithm::CP::IZ::ValueSelector instance for each variables");
},
MaxFailFunc => sub {
my $x = shift;
validate([$x], ["C"], "search: MaxFailFunc must be a coderef");
},
NoGoodSet => sub {
my $x = shift;
validate([$x], [
sub {
my $ngs = shift;
return blessed($ngs) && $ngs->isa("Algorithm::CP::IZ::NoGoodSet");
}], "search: NoGoodSet must be a instance of Algorithm::CP::IZ::NoGoodSet");
},
Notify => sub {
my $x = shift;
validate([$x], [
sub {
my $notify = shift;
return 1 if (ref $notify eq 'HASH');
return 1 if (blessed($notify));
return 0;
}], "search: Notify must be an hashref or object");
},
);
my @keys = sort keys %$params;
for my $k (@keys) {
if (exists $checker{$k}) {
my $func = $checker{$k};
&$func($params->{$k});
}
else {
_report_error("search: Unknown Key $k in params");
}
}
return 1;
}
sub search {
my $self = shift;
my $var_array = shift;
my $params = shift;
validate([$var_array, $params], ["vA0", sub {_validate_search_params($var_array, @_)}],
"Usage: search([variables], {key=>value,...}");
my $array = [map { $$_ } @$var_array];
my $max_fail = -1;
my $find_free_var_id = 0;
my $find_free_var_func = sub { die "search: Internal error"; };
my $criteria_func;
my $value_selectors;
my $max_fail_func;
my $ngs;
my $notify;
if ($params->{FindFreeVar}) {
my $ffv = $params->{FindFreeVar};
if (ref $ffv) {
$find_free_var_id = -1;
$find_free_var_func = sub {
return &$ffv($var_array);
};
}
else {
$find_free_var_id = int($ffv);
}
}
if ($params->{Criteria}) {
$criteria_func = $params->{Criteria};
}
if ($params->{MaxFail}) {
$max_fail = int($params->{MaxFail});
}
if ($params->{ValueSelectors}) {
$value_selectors = $params->{ValueSelectors};
}
if ($params->{MaxFailFunc}) {
$max_fail_func = $params->{MaxFailFunc};
}
if ($params->{NoGoodSet}) {
$ngs = $params->{NoGoodSet};
}
if ($params->{Notify}) {
$notify = $params->{Notify};
unless (ref $notify eq 'Algorithm::CP::IZ::SearchNotify') {
$notify = Algorithm::CP::IZ::SearchNotify->new($notify);
}
$notify->set_var_array($var_array);
}
my $is_search35 = $value_selectors || $max_fail_func || $ngs || $notify;
if ($is_search35) {
unless ($value_selectors) {
if ($criteria_func) {
$Algorithm::CP::IZ::CriteriaValueSelector::CriteriaFunction = $criteria_func;
$value_selectors = [
map {
$self->create_value_selector_simple("Algorithm::CP::IZ::CriteriaValueSelector")
} (0..scalar(@$var_array)-1)];
}
else {
$value_selectors = [
map {
$self->get_value_selector(&CS_VALUE_SELECTOR_MIN_TO_MAX)
} (0..scalar(@$var_array)-1)];
}
}
my $i = 0;
for my $v (@$array) {
my $vs = $value_selectors->[$i];
$vs->prepare($i);
$i++;
}
if ($max_fail_func) {
return Algorithm::CP::IZ::cs_searchValueSelectorRestartNG(
$array,
$value_selectors,
$find_free_var_id,
$find_free_var_func,
$max_fail_func,
$max_fail,
defined($ngs) ? $ngs->{_ngs} : 0,
defined($notify) ? $notify->{_ptr} : 0);
}
else {
return Algorithm::CP::IZ::cs_searchValueSelectorFail(
$array,
$value_selectors,
$find_free_var_id,
$find_free_var_func,
$max_fail,
defined($notify) ? $notify->{_ptr} : 0);
}
}
else {
if ($criteria_func) {
return Algorithm::CP::IZ::cs_searchCriteria($array,
$find_free_var_id,
$find_free_var_func,
$criteria_func,
$max_fail);
}
else {
return Algorithm::CP::IZ::cs_search($array,
$find_free_var_id,
$find_free_var_func,
$max_fail);
}
}
if ($criteria_func) {
return Algorithm::CP::IZ::cs_searchCriteria($array,
$find_free_var_id,
$find_free_var_func,
$criteria_func,
$max_fail);
}
else {
return Algorithm::CP::IZ::cs_search($array,
$find_free_var_id,
$find_free_var_func,
$max_fail);
}
}
sub _validate_find_all_params {
my $params = shift;
return 1 unless (defined($params));
return 0 unless (ref $params eq 'HASH');
my %checker = (
FindFreeVar => sub {
my $x = shift;
if (ref $x) {
validate([$x], ["C"], "find_all: FindFreeVar must be a number or coderef");
}
else {
validate([$x], ["I"], "search: FindFreeVar must be a number or coderef");
}
},
);
my @keys = sort keys %$params;
for my $k (@keys) {
if (exists $checker{$k}) {
my $func = $checker{$k};
&$func($params->{$k});
lib/Algorithm/CP/IZ.pm view on Meta::CPAN
my $r = $self->{_ref_var_arrays}->{$key};
return $r if ($r);
my $parray = Algorithm::CP::IZ::RefVarArray->new($var_array);
$self->{_ref_var_arrays}->{$key} = $parray;
return $parray;
}
sub _create_registered_int_array {
my $self = shift;
my $int_array = shift;;
my $key = join(",", map { sprintf("%x", $_) } @$int_array);
my $r = $self->{_ref_int_arrays}->{$key};
return $r if ($r);
my $parray = Algorithm::CP::IZ::RefIntArray->new($int_array);
$self->{_ref_int_arrays}->{$key} = $parray;
return $parray;
}
sub _const_var {
my $self = shift;
my $val = shift;
my $hash = $self->{_const_vars};
return $hash->{$val} if (exists($hash->{$val}));
my $v = $self->create_int($val, $val);
$hash->{$val} = $v;
return $v;
}
sub _safe_var {
my ($vc) = @_;
confess "undef cannot be used as variable" unless (defined($vc));
return $vc if (ref $vc);
return _const_var($vc);
}
sub get_version {
my $self = shift;
my ($err, $major) = constant('IZ_VERSION_MAJOR');
if (defined($major)) {
return sprintf("%d.%d.%d",
$major,
$self->IZ_VERSION_MINOR,
$self->IZ_VERSION_PATCH);
}
# not supported
return;
}
sub get_value_selector {
my $self = shift;
my $id = shift;
return Algorithm::CP::IZ::ValueSelector::IZ->new($self, $id);
}
sub create_value_selector_simple {
my $self = shift;
my $id = shift;
return Algorithm::CP::IZ::ValueSelector::Simple->new($self, $id);
}
sub create_no_good_set {
my $self = shift;
my ($var_array, $prefilter, $max_no_good, $ext) = @_;
$max_no_good ||= 0;
validate([$var_array, $prefilter, $max_no_good], ["vA0", "C0", "I"],
"Usage: create_no_good_set([variables], prefilter, max_no_good, ext)");
my $ngsObj = Algorithm::CP::IZ::NoGoodSet->new($var_array, $prefilter, $ext);
my $ptr = Algorithm::CP::IZ::cs_createNoGoodSet($ngsObj->_parray->ptr,
scalar(@$var_array),
($prefilter ? 1 : 0),
$max_no_good,
$ngsObj);
$ngsObj->_init($ptr);
return $ngsObj;
}
sub create_search_notify {
my $iz = shift;
my $obj = shift;
return Algorithm::CP::IZ::SearchNotify->new($obj);
}
#####################################################
# Demon
#####################################################
sub event_all_known {
my $self = shift;
my ($var_array, $handler, $ext) = @_;
validate([$var_array, $handler], ["vA0", "C"],
"Usage: event_all_known([variables], code_ref, ext)");
my $parray = $self->_create_registered_var_array($var_array);
my $h = sub {
return &$handler($var_array, $ext) ? 1 : 0;
};
$self->_push_object($h);
return Algorithm::CP::IZ::cs_eventAllKnown($$parray, scalar(@$var_array), $h);
}
sub event_known {
my $self = shift;
my ($var_array, $handler, $ext) = @_;
validate([$var_array, $handler], ["vA0", "C"],
"Usage: event_known([variables], code_ref, ext)");
my $parray = $self->_create_registered_var_array($var_array);
lib/Algorithm/CP/IZ.pm view on Meta::CPAN
=head2 SIMPLE CASE
In most simple case, this library will be used like following steps:
# initialize
use Algorithm::CP::IZ;
my $iz = Algorithm::CP::IZ->new();
# construct variables
my $v1 = $iz->create_int(1, 9);
my $v2 = $iz->create_int(1, 9);
# add constraints ("v1 + v2 = 12" in this case)
$iz->Add($v1, $v2)->Eq(12);
# search solution
my $rc = $iz->search([$v1, $v2]);
# you may get "v1 = 3, v2 = 9"
print "v1 = $v1, v2 = $v2\n";
=head1 CONSTRUCTOR
=over 2
=item new
Initialize iZ-C library (cs_init is called).
For limitation of iZ-C, living instance of Algorithm::CP::IZ must be
only one per process.
=back
=head1 METHODS
=over 2
=item create_int(INT)
Create an instance of Algorithm::CP::IZ::Int. Its domain contains INT.
=item create_int(VALUES [, NAME])
Create an instance of Algorithm::CP::IZ::Int. Its domain contains values
specified by VALUES(arrayref).
=item create_int(MIN, MAX, [, NAME])
Create an instance of Algorithm::CP::IZ::Int. Its domain is {MIN..MAX}.
=item search(VARIABLES [, PARAMS])
Try to instantiate all VARIABLES(arrayref).
PARAMS will be hashref containning following keys.
=over 2
=item FindFreeVar
FindFreeVar specifies variable selection strategy.
Choose constants from Algorithm::CP::IZ::FindFreeVar or specify your own
function as coderef here.
Most simple function will be following. (select from first)
sub simple_find_free_var{
my $array = shift; # VARIABLES is in parameter
my $n = scalar @$array;
for my $i (0..$n-1) {
return $i if ($array->[$i]->is_free);
}
return -1; # no free variable
};
=item Criteria
Criteria specifies value selection strategy.
Specify your own function as coderef here.
sub sample_criteria {
# position in VARIABLES, and candidate value
my ($index, $val) = @_;
# first value used in search is
# minimum value returned by criteria.
return $val;
};
(If ValueSelector is specified, this parameter is ignored.)
=item MaxFail
Upper limit of fail count while searching solutions.
=item ValueSelectors
Arrayref of Algorithm::CP::IZ::ValueSelector instances created via
get_value_selector or create_value_selector_simple method.
(If ValueSelector is specified, this parameter is ignored.)
=item MaxFailFunc
CodeRef of subroutine which returns maxfail for restart.
=item NoGoodSet
A Algorithm::CP::IZ::NoGoodSet instance which collects NoGoods.
=item Notify
Specify a notify object receives following notification by search function.
search_start
search_end
before_value_selection
after_value_selection
enter
leave
found
if OBJECT is a object, method having notification name will be called.
if OBJECT is a hashref, notification name must be a key of hash and
value must be a coderef.
=back
Returns 1 (success) or 0 (fail).
=item find_all(VARIABLES, CALLBACK [, PARAMS])
Find all solutions. CALLBACK(coderef) is called for each solution.
(First parameter of CALLBACK is VARIABLE)
# this callback collects all solutions in @r
my @r;
sub callback {
my $var_array = shift;
push(@r, [map { $_->value } @$var_array]);
};
PARAMS will be hashref containning following keys.
=over 2
=item FindFreeVar
Same as search method.
=back
Returns 1 (success) or 0 (fail).
=item get_nb_fails
Returns fail count while searching solution.
=item get_nb_choice_points
Returns choice count while searching solution.
=item save_context
Save current status of variables and constraints.
my $v1 = $iz->create_int(1, 9);
$iz->save_context; # current status is saved.
$v1->Le(5); # $v1 is {1..5}
$iz->restore_context; # $v1 is restored to {1..9}
Returns integer which will be used for restore_context_until.
=item restore_context
Restore status of variables and constraints to last point which
'save_context' is called.
lib/Algorithm/CP/IZ.pm view on Meta::CPAN
sub callback {
# minimum value of $var is changed from $old_min.
# $var is same as $variables[$index].
# $variables and $extra are same as parameter.
my ($var, $index, $old_min, $variables, $extra) = @_;
# return 1(success) or 0(fail)
return 1;
}
EXTRA is a just a data passed to callbeck as parameter (it can be anything).
=item event_new_max(VARIABLES, CALLBACK, EXTRA)
Set a callback function which will be called when upper bound of any variable
in VARIABLES is changed.
VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.
CALLBACK is a coderef and takes parameters and must return like:
sub callback {
# maximum value of $var is changed from $old_max.
# $var is same as $variables[$index].
# $variables and $extra are same as parameter.
my ($var, $index, $old_max, $variables, $extra) = @_;
# return 1(success) or 0(fail)
return 1;
}
EXTRA is a just a data passed to callbeck as parameter (it can be anything).
=item event_neq(VARIABLES, CALLBACK, EXTRA)
Set a callback function which will be called when value of any variable is
removed in VARIABLES is changed.
VARIABLES is an arrayref contains instances Algorithm::CP::IZ::Int.
CALLBACK is a coderef and takes parameters and must return like:
sub callback {
# $val is removed from $var.
# $var is same as $variables[$index].
# $variables and $extra are same as parameter.
my ($var, $index, $val, $variables, $extra) = @_;
# return 1(success) or 0(fail)
return 1;
}
EXTRA is a just a data passed to callbeck as parameter (it can be anything).
=item get_version
Returns version string like "3.5.0".
undef will be returned if getVersion() is not supported in iZ-C (old version).
=item get_value_selector(ID)
Get built-in value selector (instance of Algorithm::CP::IZ::ValueSelector) specifed by ID.
ID must be selected from following constants defined in package Algorithm::CP::IZ.
=over
=item CS_VALUE_SELECTOR_MIN_TO_MAX
=item CS_VALUE_SELECTOR_MAX_TO_MIN
=item CS_VALUE_SELECTOR_LOWER_AND_UPPER
=item CS_VALUE_SELECTOR_UPPER_AND_LOWER
=item CS_VALUE_SELECTOR_MEDIAN_AND_REST
=back
(These values are exported by Algorithm::CP::IZ and can be imported using tag 'value_selector')
Returned object will be used as a parameter ValueSelectors when calling "search" method.
use Algorithm::CP::IZ qw(:value_selector);
my $vs = $iz->get_value_selector(CS_VALUE_SELECTOR_MIN_TO_MAX);
my $v1 = $iz->create_int(1, 9);
my $v2 = $iz->create_int(1, 9);
$iz->Add($v1, $v2)->Eq(12);
my $rc = $iz->search([$v1, $v2], {
ValueSelectors => [ $vs, $vs ],
});
=item create_value_selector_simple(CLASS_NAME)
Create user defined value-seelctor defined by class named CLASS_NAME.
This class must have constructor named "new" and method namaed "next".
use Algorithm::CP::IZ qw(:value_selector);
package VSSample1;
sub new {
my $class = shift;
my ($v, $index) = @_;
my $self = {
_pos => 0,
};
bless $self, $class;
}
sub next {
my $self = shift;
my ($v, $index) = @_;
my $pos = $self->{_pos};
my $domain = $v->domain;
# return empty after enumerate all values
return if ($pos >= @$domain);
my @ret = (CS_VALUE_SELECTION_EQ, $domain->[$pos]);
$self->{_pos} = ++$pos;
# return pair of (CS_VALUE_SELECTION_*, value)
return @ret;
}
my $v1 = $iz->create_int(1, 9);
my $v2 = $iz->create_int(1, 9);
$iz->Add($v1, $v2)->Eq(12);
my $vs = $iz->create_value_selector_simple("VSSample1");
my $rc = $iz->search([$v1, $v2], {
ValueSelectors => [ $vs, $vs ],
});
=item create_no_good_set(VARIABLES, PRE_FILTER, MAX_NO_GOOD, EXT)
Create an instance of Algorithm::CP::IZ::NoGoodSet. Returned object will be used as a
parameter NoGoodSet when calling "search" method.
=back
=head1 METHODS (Constraints)
=over 2
=item Add(VAR1, VAR2 [, VAR3....])
Create an instance of Algorithm::CP::IZ::Int constrainted to be:
Created_instance = VAR1 + VAR2 + ....
=item Mul(VAR1, VAR2 [, VAR3....])
Create an instance of Algorithm::CP::IZ::Int constrainted to be:
Created_instance = VAR1 * VAR2 * ....
=item Sub(VAR1, VAR2)
Create an instance of Algorithm::CP::IZ::Int constrainted to be:
Created_instance = VAR1 - VAR2
=item Div(VAR1, VAR2)
Create an instance of Algorithm::CP::IZ::Int constrainted to be:
Created_instance = VAR1 / VAR2
=item ScalProd(VARIABLES, COEFFICIENTS)
Create an instance of Algorithm::CP::IZ::Int constrainted to be:
Created_instance = COEFFICIENTS[0]*VARIABLES[0] + COEFFICIENTS[1]*VARIABLES[1] + ...
VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int,
and COEFFICIENTS is an arreyref contains integer values.
=item AllNeq(VARIABLES)
Constraint all variables in VARIABLES to be different each other.
VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.
Returns 1 (success) or 0 (fail).
=item Sigma(VARIABLES)
Create an Algorithm::CP::IZ::Int instance constrainted to be:
( run in 0.856 second using v1.01-cache-2.11-cpan-63c85eba8c4 )