[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Automake::Conditional::invert
From: |
Alexandre Duret-Lutz |
Subject: |
Automake::Conditional::invert |
Date: |
Tue, 19 Nov 2002 22:13:47 +0100 |
User-agent: |
Gnus/5.090008 (Oort Gnus v0.08) Emacs/20.7 (i386-debian-linux-gnu) |
>>> "Raja" == Raja R Harinath <address@hidden> writes:
[...]
Raja> If you really want to worry about scalability, A::CS::invert would be
Raja> better written as a product-of-sums to sum-of-products converter,
Raja> rather than explicitly enumerating every truth-value candidate.
[...]
Here is my proposal. make check is running.
2002-11-19 Alexandre Duret-Lutz <address@hidden>
* lib/Automake/ConditionalSet.pm (conds): Use value() to simplify.
(invert): Rewrite as a product-of-sums to sum-of-products converter.
Suggested by Raja R Harinath.
* lib/Automake/tests/ConditionalSet.pl (test_invert): Update.
* automake.in (condition_negate): Move ...
* lib/Automake/Conditional.pm (negate_condition): ... here.
Index: automake.in
===================================================================
RCS file: /cvs/automake/automake/automake.in,v
retrieving revision 1.1389
diff -u -r1.1389 automake.in
--- automake.in 19 Nov 2002 20:02:38 -0000 1.1389
+++ automake.in 19 Nov 2002 21:09:02 -0000
@@ -5925,21 +5925,6 @@
################################################################
-# $NEGATION
-# condition_negate ($COND)
-# ------------------------
-sub condition_negate ($)
-{
- my ($cond) = @_;
-
- $cond =~ s/TRUE$/TRUEO/;
- $cond =~ s/FALSE$/TRUE/;
- $cond =~ s/TRUEO$/FALSE/;
-
- return $cond;
-}
-
-
## ------------------------------ ##
## Handling the condition stack. ##
## ------------------------------ ##
@@ -5957,7 +5942,7 @@
$cond = "${cond}_TRUE"
unless $cond =~ /^TRUE|FALSE$/;
- $cond = condition_negate ($cond)
+ $cond = Automake::Conditional::condition_negate ($cond)
if $negate;
push (@cond_stack, $cond);
@@ -5979,14 +5964,15 @@
return;
}
- $cond_stack[$#cond_stack] = condition_negate ($cond_stack[$#cond_stack]);
+ $cond_stack[$#cond_stack] =
+ Automake::Conditional::condition_negate ($cond_stack[$#cond_stack]);
# If $COND is given, check against it.
if (defined $cond)
{
$cond = "${cond}_TRUE"
unless $cond =~ /^TRUE|FALSE$/;
- $cond = condition_negate ($cond)
+ $cond = Automake::Conditional::condition_negate ($cond)
if $negate;
err ($where, "else reminder ($negate$cond) incompatible with "
@@ -6018,7 +6004,7 @@
{
$cond = "${cond}_TRUE"
unless $cond =~ /^TRUE|FALSE$/;
- $cond = condition_negate ($cond)
+ $cond = Automake::Conditional::condition_negate ($cond)
if $negate;
err ($where, "endif reminder ($negate$cond) incompatible with "
Index: lib/Automake/Conditional.pm
===================================================================
RCS file: /cvs/automake/automake/lib/Automake/Conditional.pm,v
retrieving revision 1.4
diff -u -r1.4 Conditional.pm
--- lib/Automake/Conditional.pm 14 Nov 2002 16:12:00 -0000 1.4
+++ lib/Automake/Conditional.pm 19 Nov 2002 21:09:03 -0000
@@ -443,6 +443,23 @@
return @ret;
}
+=item C<condition_negate ($condstr)>
+
+Negate a condition string.
+
+=cut
+
+sub condition_negate ($)
+{
+ my ($cond) = @_;
+
+ $cond =~ s/TRUE$/TRUEO/;
+ $cond =~ s/FALSE$/TRUE/;
+ $cond =~ s/TRUEO$/FALSE/;
+
+ return $cond;
+}
+
=head1 SEE ALSO
L<Automake::ConditionalSet>.
Index: lib/Automake/ConditionalSet.pm
===================================================================
RCS file: /cvs/automake/automake/lib/Automake/ConditionalSet.pm,v
retrieving revision 1.5
diff -u -r1.5 ConditionalSet.pm
--- lib/Automake/ConditionalSet.pm 19 Nov 2002 20:02:39 -0000 1.5
+++ lib/Automake/ConditionalSet.pm 19 Nov 2002 21:09:06 -0000
@@ -153,7 +153,7 @@
{
my ($self) = @_;
return @{$self->{'conds'}} if exists $self->{'conds'};
- my @conds = map { $self->{'hash'}{$_} } (keys %{$self->{'hash'}});
+ my @conds = values %{$self->{'hash'}};
@conds = sort { $a->string cmp $b->string } @conds;
$self->{'conds'} = address@hidden;
return @conds;
@@ -332,15 +332,37 @@
return $self->{'invert'} if defined $self->{'invert'};
- # Generate permutations for all subconditions.
- my @perm = $self->permutations->conds;
+ # The invert of an empty ConditionalSet is TRUE.
+ my %res = (&TRUE => TRUE);
- # Now remove all conditions which imply one of the input conditions.
- my @conds = $self->conds;
- my @notconds =
- grep { ! $_->implies_any (@conds) } $self->permutations->conds;
- my $res = new Automake::ConditionalSet @notconds;
+ # !((a.b)+(c.d)+(e.f))
+ # = (!a+!b).(!c+!d).(!e+!f)
+ # We develop this into a sum of product iteratively, starting from TRUE:
+ # 1) TRUE
+ # 2) TRUE.!a + TRUE.!b
+ # 3) TRUE.!a.!c + TRUE.!b.!c + TRUE.!a.!d + TRUE.!b.!d
+ # 4) TRUE.!a.!c.!e + TRUE.!b.!c.!e + TRUE.!a.!d.!e + TRUE.!b.!d.!e
+ # + TRUE.!a.!c.!f + TRUE.!b.!c.!f + TRUE.!a.!d.!f + TRUE.!b.!d.!f
+ #
+ # We store each product (i.e., each Conditional) in a Hash, so
+ # that duplicates get removed automatically.
+ foreach my $set ($self->conds)
+ {
+ my @old = values %res;
+ %res = ();
+ for my $cond ($set->conds)
+ {
+ my $negstr = Automake::Conditional::condition_negate $cond;
+ my $neg = new Automake::Conditional $negstr;
+ foreach my $r (@old)
+ {
+ my $m = $r->merge ($neg);
+ $res{$m} = $m;
+ }
+ }
+ }
+ my $res = new Automake::ConditionalSet values %res;
# Cache result.
$self->{'invert'} = $res;
# It's tempting to also set $res->{'invert'} to $self, but that
Index: lib/Automake/tests/ConditionalSet.pl
===================================================================
RCS file: /cvs/automake/automake/lib/Automake/tests/ConditionalSet.pl,v
retrieving revision 1.2
diff -u -r1.2 ConditionalSet.pl
--- lib/Automake/tests/ConditionalSet.pl 19 Nov 2002 20:02:39 -0000
1.2
+++ lib/Automake/tests/ConditionalSet.pl 19 Nov 2002 21:09:08 -0000
@@ -109,11 +109,10 @@
[[["COND1_TRUE", "COND2_TRUE"],
["COND3_FALSE", "COND2_TRUE"]],
- [["COND1_FALSE","COND2_FALSE","COND3_FALSE"],
- ["COND1_TRUE", "COND2_FALSE","COND3_FALSE"],
- ["COND1_FALSE","COND2_FALSE","COND3_TRUE"],
- ["COND1_TRUE", "COND2_FALSE","COND3_TRUE"],
- ["COND1_FALSE","COND2_TRUE", "COND3_TRUE"]]],
+ [["COND2_FALSE"],
+ ["COND2_FALSE", "COND3_TRUE"],
+ ["COND1_FALSE", "COND2_FALSE"],
+ ["COND1_FALSE", "COND3_TRUE"]]],
[[["COND1_TRUE", "COND2_TRUE"],
["TRUE"]],
@@ -121,9 +120,8 @@
[[["COND1_TRUE", "COND2_TRUE"],
["FALSE"]],
- [["COND1_FALSE", "COND2_TRUE"],
- ["COND1_FALSE", "COND2_FALSE"],
- ["COND1_TRUE", "COND2_FALSE"]]],
+ [["COND1_FALSE"],
+ ["COND2_FALSE"]]],
[[["COND1_TRUE"],
["COND2_FALSE"]],
@@ -137,7 +135,8 @@
my $inv = $set->invert;
if ($inv != $res)
{
- print " (I) " . $inv->string . ' != ' . $res->string . "\n";
+ print " (I) " . $set->string . "\n\t"
+ . $inv->string . ' != ' . $res->string . "\n";
return 1;
}
}
--
Alexandre Duret-Lutz
- Automake::Conditional::simplify (Quine-McCluskey), Alexandre Duret-Lutz, 2002/11/16
- Re: Automake::Conditional::simplify (Quine-McCluskey), Raja R Harinath, 2002/11/16
- Automake::Conditional::invert,
Alexandre Duret-Lutz <=
- Re: Automake::Conditional::invert, Raja R Harinath, 2002/11/19
- Re: Automake::Conditional::invert, Alexandre Duret-Lutz, 2002/11/20
- Re: Automake::Conditional::invert, Raja R Harinath, 2002/11/20
- Re: Automake::Conditional::invert, Alexandre Duret-Lutz, 2002/11/20
- Re: Automake::Conditional::invert, Raja R Harinath, 2002/11/20
- FYI: make_conditional_string, Alexandre Duret-Lutz, 2002/11/21
FYI: simplify variable_not_always_defined_in_cond, Alexandre Duret-Lutz, 2002/11/20