Revision history for Algorithm-QuineMcCluskey
1.01
2019-12-03
- Debug changes only, does not affect the operation of the
non-debug code:
Smart comments had some obsolete variables that are now
changed. The chart() function, used by Smart comments, made
use of firstidx(), which was provided by a module that is no
longer included. Changed the code in chart() to use the any()
function from List::Util instead.
- Minor correction to README.md.
1.00
2019-02-10
- Moved the formatting functions to_boolean() and
to_boolean_term() over to Logic::Minimizer. Tie::Cycle is no
longer used, and gets removed from the build requirement in
Build.PL.
- README is now README.md.
- With Logic::Minimizer finally released yesterday, it's time to
send this off to CPAN.
2018-10-06
- Removed the terms parameter from find_essentials(),
covered_least(), and row_dominance(), which we already
had in other structures. This shortened the loops and reduced
the number of loop structures needed. Another speed-up.
2018-09-29
- Replace columns(), a function that rotated the primes
hash using grep and any(), with new function transpose(),
which does the same thing using hash keys, and which NYTProf
says is faster.
2018-08-30
- Examining remels() more closely, it became obvious that
it was using maskedmatch() as an block argument to indexes()
for every single term against every single element three
loops deep. Since maskedmatch() has a set-up cost, this
seems wasteful. Created a new function maskedmatchindexes(),
which sets up the masks before going through the list once.
- Which means we no longer are using the indexes() function
from List::MoreUtils, which is now removed.
2018-08-29
- We now use Logic::Minimizer as a base class.
- Consequently, removed attributes and methods that are
now in Logic::Minimizer, and are provided automatically.
- Use L::M's catch_errors() for attribute validation.
- Update Build.PL with Logic::Minimizer requirement.
- And updated the version number everywhere.
0.19
2019-07-31
- There was more processing than needed in least_covered() to do
what was basically a find-the-minimum loop, plus it was
throwing away information that had to be re-created by the
next line of code.
Consolidated all of that, resulting in fewer hash-of-array
manipulations, and changed the return value from the single
term to the term plus its covers.
This won't result in a significant speed increase, as most
terms are already eliminated by the time we reach this code,
but it does simplify it and make it more readable.
- A side-effect of the above is that countels() is no longer
needed, and was removed.
- Also, while I was doing A-B comparisons, the new version of the
function was named covered_least(), and it stayed that way.
- Streamlined remels() some more, and changed it from a function
that got called multiple times for each item in a list, to a
function that is called once with a list.
- Moved the next-level-implicant check of version 0.18 outward
two loops (some duplicates still popped up as two different
terms could bit flip to the same implicant). Moved the push
operation of those implicants outward too, using the keys
of the hash used in checking for them.
- Created width=>6 tests in new files 28-solve.t and 29-solve.t.
0.18
2018-07-10
- Check for existence of next-level implicant before pushing it
on the list. Which means the next loop runs shorter, saving time.
- Since we only consider Hamming distances of 1 when comparing
covers, it doesn't make sense to have a separate Hamming
distance function to find the sole difference position. Merged
the code of hdist() and diffpos() into new function hammingd1pos(),
which lets us skip the list-checking functions. Since this function
is embedded four loops deep, this also saves time.
- Function remels() was checking item by item even in cases where
the list items to remove were the entire list. Streamlined that.
- The Hamming distance change above meant pairwise() isn't needed
now, which was the cause of the version requirement change of
List::MoreUtils. Put the older version number back in the
requirement.
0.17
2018-06-21
- Require latest version (0.428) of List::MoreUtils, as there seems
to be a crash-worthy side-effect happening with its earlier version
and Perl 5.26, as reported by Slaven Rezic.
- Upped the version req's of Tie::Cycle, namespace::autoclean, and
Module::Build while I was at it.
0.16
2017-02-27
- The test in 24-solve.t, "A problem with sixteen possible covers",
had typos in four of its covers, all involving the term that
should have been BC'D' (the D variable was missing its complement
symbol).
0.15
2017-01-31
- Stupidly didn't upgrade the version number in QuineMcCluskey.pm.
- Fix tests in 24-solve.t and 27-solve.t that had a typo in their
solution sets.
0.14
2017-01-19
- Had set the weed-out-expensive-solutions cost at the start of
the loop at 2**width, wrongly thinking that that would be the
maximum cost. Found a couple cases where that's not true,
making solve() return them as "()". Put those cases in a new
test file 27-solve.t.
- Changed the weeding-out code to use an actual cost from the
covers array for the starting value.
0.13
2017-01-5
- The special cases where all entries are covered (i.e., all 1s or
all 0s in the truth table) causes a cover of all dc characters,
which returns "()" for solve(). That's a little unhelpful, so
check for that and return either a "(1)" or "(0)".
0.12
2016-10-8
- In BUILD, limit 'vars' to the number of variables actually needed.
- With that change, remove array slice of 'vars' in other parts of
the code.
- Add an 'order_by' attribute (undocumented for now) for use in
to_boolean().
- Removed an unnecessary loop in to_boolean().
- Corrected the sorting in the get_covers() example.
- Update comments and Smart Comments.
0.11
2016-8-25
- Add method all_solutions(). Update the POD concerning using
get_covers() to refer to all_solutions().
0.10
2016-7-20
- Check to see if the terms (minterms, maxterms, or
dont-cares) are larger than 'width' in bit size.
It's possible I made that mistake myself recently.
- And although it's not an error, run the terms through
sort and uniq before converting to bitstrings. It
makes visual inspection of the debug output easier.
0.09
2016-6-27
- Found a case where don't-care terms with no covers
were nonetheless included with the prime implicants.
Fixed by changing a map{}-everything-will-work into
a loop with an if statement to check for that.
- New test file 25-solve.t (Rock Paper Scissors) that
covers the above problem.
- Streamlined the bit term functions, and added some
more 'smart' comments to show the bit terms.
- Added a release_status key to the Build.PL hash.
0.08
2016-4-21
- Changed a "sum map" to a "scalar grep" in countels(),
and inlined the diffposes() code in hdist() and diffpos().
This let us eliminate the last cases of calling sum().
- These changes, along with using the any() function from
List::MoreUtils instead of List::Util, mean that we don't
need to load List::Util anymore.
- Edited Build.PL add 'provides' and 'add-to-cleanup' keys;
bumped the min version requirement of List::MoreUtils to 0.401;
Removed List::Util and bumped the dist version.
- Module now at version 0.08.
0.07
2015-8-14
- List::MoreUtils wasn't in the list of required modules
in Build.PL. Added it.
- The description of get_covers() in the documentation
wasn't enough. Extended the example.
- Bump the version to 0.07.
0.06
2015-8-1
- The changes of 2015-5-30 mean that the check for an empty
array in row_dominance() isn't needed anymore.
- Use a simple join() in uniqel() instead of Data::Dumper.
- Remove Data::Dumper from 'requires' key in Build.PL.
- Bumped Version everywhere to 0.06; up to CPAN.
0.05
2015-7-29
- Documented methods get_primes(), get_essentials(), and
get_covers().
- Changed attribute essentials from HashRef to ArrayRef.
It makes get_essentials() a bit more useful.
- Renamed tableform() function to chart().
- Updated README to current status of the API.
- Version 0.05 now, and up to CPAN.
0.04
2015-6-13
- The build-and-break-a-columnstring mechanism for making
complements and duals of the object was clear but involved
using extra memory, potentially a lot. Removed that and
use the get_complement() function of List::Compare::Functional
instead.
- I hadn't listed namespace::autoclean in the dependency list
in Build.PL, and I am hearing about it from the testers.
- Similarly, some testers have a List::Utils module that's older
than October 2013, when any() was introduced. Specified version
1.35 in Build.PL to be safe.
- Bump everthing's version up to 0.04. Up to CPAN.
0.03
2015-6-12
- The minimum perl required was 5.10.1, but the module
was using the /r modifier on the tr// operator, which
doesn't appear until 5.14. Oops. Changed the string
assignment order in dual() and complement().
- Version goes to 0.03, and up to CPAN.
0.02
2015-6-11
- Realized that the maskmatcher regex could be changed to
not require the don't-care character, which means it doesn't
need to be in the parameter list of maskmatcher(),
purge_elements(), or remels().
- Renamed maskmatcher() maskedmatch(), because the grammar
was bugging me.
- With that, Version 0.02 is ready for CPAN.
2015-6-3
- Util.pm now has an %EXPORT_TAGS.
- Change the covers attribute to contain all of the minimal
covers, not just the one that happens to be in the zeroth
position in the covers array.
- Change solve() to return a scalar.
- With solve() now returning a scalar, change tests to look
for an answer in a set of possible answers (some terms sets
can be covered by more than one equation.)
2015-5-30
- Make remels() remove the hash key if the array ref is empty.
- Change columns() to not auto-create empty keys.
2015-4-18
- Made the primes attribute "lazy", so that one can look
up prime implicants without going through the solving
process.
2015-4-15
- Replace row_dom() and col_dom() with row_dominance()
in Util.pm. When they were changed to returning keys
instead of deleting from the hash immediately, they
became essentially the same function, just called
with different parameters.
2015-3-27
- Changed row_dom() and col_dom() to return the rows/cols
to remove, instead of removing them inside.
- Changed row_dom() and col_dom() from methods to functions,
and moved the code to Util.pm
2015-3-6
- Method find_essentials() is essentially a single-term search
through the hash of arrays. Changed it from a method to a
function and moved it to Util.pm.
- Found an error in remels(), which was only removing one
matched array element instead of all matched elements.
2015-1-26
- Changed argument list to purge_essentials(). Had been
taking an esssentials hash, but since it was only using the
keys of the hash, we only need to pass those.
- In purge_essentials() change the order of deletion. The
primes hash "rows" (hash entries) are removed first,
*before* going through the hash to look for the "column"
in the array ref. Shortens the search for the "column".
- The argument list change lets me use purge_essentials()
later in recurse_solve(), replacing a remels()/delete
pair of lines.
- Renamed purge_essentials() to purge_elements(), since
the above change means we're not just purging essentials
now.
2015-1-18
- Removed sortterms attribute -- always sort.
- Simplified covers loop (helped by removing sortterms).
- Moved a constant calculation of the %reduced hash out
a loop.
2015-1-16
- New function tableformat() (current name, at least) to show
primes hash in the table form used in textbook Quine-McCluskey
descriptions. Should help users understand what's going on,
and help in debugging too.
- New module to contain tableforms() (and future functions),
named it Algorithm::QuineMcCluskey::Format.
- Do-while using is_LequivalentR() was supposed to be comparing
hash keys, but a 'keys' had been left off on one side.
Fixing that saves at least one loop.
- Avoid calling recurse_solve() if the reduced primes hash is
empty.
2015-1-6
- Added new object-creating methods dual() and complement().
- Added tests for the new methods.
2015-1-1
- No default parameters for find_essentials(). The primes
hash must be passed in, while the binary-formatted terms
are collectd from the object.
- Found spots in QM.pm and Util.pm where a "sum map {}"
construct can be replaced with "any {}", which has the
advantage of early break out of the loop on a match.
2014-12-3
- The weight count in find_primes() and the cost count in
recursive_solve() were using sum of a map block using
split. A match in list context is much simpler, changed
them to that (and put the function for it in Util.pm).
2014-11-27
- Add \Q and \E around don't-care character in maskmatcher()
substitution code in case someone chose a substitution
metacharacter as their don't-care character.
2014-11-26
- Was looping around remel() for each arrayref in the hash.
Now just pass the hash in directly (this necessitated
changing one of the outer loops in purge_essentials,
and remel() becomes remels()).
2014-11-13
- The test with don't-care terms randomly fails two thirds
of the time. Separate it into its own file, and add
debugging statements.
2014-11-4
- Extended the object test to consider minterms, maxterms,
and columnstrings methods of creation.
- deAlias considered finished and merged into the master
branch.
2014-10-31
- Added columnstring attribute, and wrote bitstring code
for setting and getting it.
- Changed minterms, maxterms, and dontcares back to
'rw', allowing the columnstring attribute to set them.
2014-10-28
- Changed to_boolean() to take an argument list instead of
automatically using the covers attribute internally. This
will allow the user (or the test files) to check terms before
or during minimization.
- Separated out the var-by-var code from to_boolean(). Now it
calls a new method to_boolean_term() for each individual term
in the covers (or other) list, for easier output manipulation.
2014-09-28
- The 'covers' attribute gets changed from ArrayRef[Int] to
ArrayRef[Str].
2014-09-21
- Added namespace::autoclean as recommended in the Moose Best
Practices manual.
- Changed the all the "terms" attributes to 'ro'.
2014-09-19
- For internal clarity, renamed allterms() to all_bit_terms(),
and minmax_terms() to minmax_bit_terms().
- Methods maskmatch() and maskmatches() now combined into a single
method (one called the other, but there was no reason for the
separate internal function, and it saved re-creating
utility variables over and over).
- Check if there's an overlap between the don't-care list and
the min or max term list, and call it an error if there is.
- Attributes actually check their type now (thanks Moose) so
the qw operators around the term lists are now removed in
the documentation and in the test files.
2014-08-20
- No more default arguments (in the form of $self->get_primes())
for row_dom(), col_dom(), and purge_essentials()). Always
pass in the argument -- it's less confusing that way.
- Trim Util.pm of tobits() -- it's embedded in BUILD now.
2014-08-19
- More work in find_primes(). An array slice in a hash isn't
working as originally coded (I seem to recall the rules
changing some time ago). Changed it to two statements for
now.
2014-07-07
- After looking over the labeling in the run.t file, added
a new attribute, "title". We can now say what the A::QMcC
object actually represents.
- Broke up run.t into separate test files. The original
file was compact and in theory easy to add to, but I was
having trouble figuring out what was causing my Moose
errors. Plus, there were too many eval calls in the code.
- The original code changed the minterms, maxterms, and
dontcares attributes from the passed-in list of decimal
into bitstrings, and saved them back in the attributes.
We can't do that now, because Moose has set those fields
typed as 'ArrarRef[Int]'.
So, set up three new fields that represent the three fields
in their bitstring form: min_bits, max_bits, and dc_bits.
2014-04-30
- Moosified ("has" declarations) the attributes.
- Achieved a compile-error-free version using Moose instead
of Alias. Now to make it runtime-error-free.
- As part of the compilation process, moved from a Makefile.PL
base (which was creating errors of its own) to Build.PL,
which Just Works.
- Turned attributes boolean, imp, and bits into a local
variables as they were only used in single functions.
- Defined and made use of predicate functions for attributes
minterms, maxterms, and dontcares. Simplifies some sanity
checks.
- Added methods allterms() and minmax_terms() to simplify
coding.
- List::MoreUtils isn't actually being used in A::QMcC (it is
used in A::QMcC::Util though).
0.01 2006-06-24T21:32-0500
First version, released on an unsuspecting world. Supports
single-output problems only.