#Quine-McCluskey.md

Quine-McCluskey example in C++

A straightforward attempt to implement Quine-McCluskey algorithm in C++. This repo is not meant to be a useful piece of software on its own, but serve as an example and demo for my course's students.

.gitignore

.idea/
build*/

CMakeLists.txt

cmake_minimum_required(VERSION 3.1)
project(quine)

add_executable(quine
    Term.hh
    Quine.hh
    main.cpp)

set_target_properties(quine PROPERTIES
    CXX_STANDARD_REQUIRED TRUE
    CXX_STANDARD          14)

main.cpp

#include <algorithm>
#include <iostream>
#include "Term.hh"
#include "Quine.hh"

int main() {
    std::vector<Term> majorantTerms = {"011", "101", "110", "111"};
    auto simplified = getImplicants(majorantTerms);
    for (auto const& term: simplified)
        std::cout << term.to_string() << std::endl;
}

Quine.hh

#pragma once
#include <vector>
#include <boost/optional.hpp>
#include "Term.hh"

std::vector<Term> getImplicants(std::vector<Term> const& minterms) {

    using MintermBasket = std::vector<std::pair<Term, bool>>;

    MintermBasket basket, nextBasket;
    for (auto const& term: minterms)
        basket.push_back(std::make_pair(term, true));

    std::vector<Term> implicants;
    while (true) {
        nextBasket.clear();
        for (auto iter1 = basket.begin(); iter1 < basket.end(); ++iter1)
        for (auto iter2 = basket.begin(); iter2 < basket.end(); ++iter2) {
            if (iter1 > iter2)
                continue;

            auto const& minterm1  = iter1->first;
            auto const& minterm2  = iter2->first;
            bool& uncombinedFlag1 = iter1->second;
            bool& uncombinedFlag2 = iter2->second;

            const auto combinedMinterm = Term::combine(minterm1, minterm2);
            if (combinedMinterm) {
                nextBasket.push_back(std::make_pair(combinedMinterm.get(), true));
                uncombinedFlag1 = false;
                uncombinedFlag2 = false;
            }
        }

        for (auto const& pair: basket) {
            if (pair.second)
                implicants.push_back(pair.first);
        }

        if (nextBasket.empty())
            break;

        std::swap(basket, nextBasket);
    }

    return implicants;
}

std::vector<Term> expandMaxterms(std::vector<Term> const& maxterms) {
    if (maxterms.empty())
        return std::vector<Term>();

    std::vector<Term> result, nextResult;
    result.push_back(Term());

    for (auto const& currMaxterm: maxterms) {
        nextResult.clear();
        for (size_t i=0; i<currMaxterm.size(); ++i) {
            if (currMaxterm[i] == '*')
                continue;

            for (auto const& minterm: result) {
                auto oldTrite = minterm[i];
                auto newTrite = currMaxterm[i];

                if (newTrite == Term::negate(oldTrite))
                    continue;

                Term newMinterm = minterm;
                newMinterm.set(i, newTrite);
                nextResult.push_back(newMinterm);
            }
        }

        std::swap(result, nextResult);
    }

    return result;
}

std::vector<Term> selectImplicants(
        std::vector<Term> const& minterms,
        std::vector<Term> const& implicants) {

    std::vector<Term> coverageMaxterms;
    for (auto const& minterm: minterms) {
        Term coverageMaxterm;
        size_t i = 0;
        for (auto const& implicant: implicants) {
            if (minterm.contains(implicant))
                coverageMaxterm.set(i, '1');
            ++i;
        }
        coverageMaxterms.push_back(coverageMaxterm);
    }

    std::vector<Term> coverageMinterms = expandMaxterms(coverageMaxterms);

    auto bestMintermIter = std::min_element(
            coverageMinterms.begin(),
            coverageMinterms.end(),
            [](Term a, Term b){ return a.pmaskCount() < b.pmaskCount(); });

    if (bestMintermIter == coverageMinterms.end())
        return std::vector<Term>();

    std::vector<Term> result;
    for (size_t i=0; i<bestMintermIter->size(); ++i) {
        if (bestMintermIter->at(i) == '1')
            result.push_back(implicants[i]);
    }

    return result;
}

Term.hh

#pragma once
#include <cstring>
#include <limits>
#include <boost/optional.hpp>
#include <boost/dynamic_bitset.hpp>

class Term {
public:

    Term() {
        resize(0);
    }

    explicit Term(size_t size) {
        resize(size);
    }

    Term(char const* str) {
        assign(str);
    }

    char operator[](size_t idx) const {
        if (idx >= size() || !pmask(idx))
            return '*';

        return dmask(idx) ? '1' : '0';
    }

    char at(size_t idx) const {
        return (*this)[idx];
    }

    void resize(size_t size) {
        mDirectionMask.resize(size);
        mPresenceMask.resize(size);
        updateCounts();
    }

    void assign(size_t size, char val) {
        mPresenceMask.set(size, val == '1' || val == '0');
        mDirectionMask.set(size, val == '1');
        updateCounts();
    }

    template <typename BitsetType>
    void assign(BitsetType const& dmask, BitsetType const& pmask) {
        mPresenceMask  = pmask;
        mDirectionMask = dmask;

        // Make sure masks are in sync: (a) have the same size,
        // and (b) value '*' is represented by zero in dmask.
        mDirectionMask.resize(mPresenceMask.size());
        mDirectionMask &= mPresenceMask;
        updateCounts();
    }

    void assign(char const* str) {
        size_t len = std::strlen(str);

        mDirectionMask.resize(len);
        mPresenceMask.resize(len);
        for (size_t i = 0; str[i] != '\0'; ++i)
            setWithoutUpdate(i, str[i]);

        updateCounts();
    }

    void assign(std::string const& str) {
        assign(str.c_str());
    }

    void set(size_t idx, char val) {
        if (idx >= size()) {
            if (val == '*')
                return;

            mDirectionMask.resize(idx+1);
            mPresenceMask.resize(idx+1);
        }

        setWithoutUpdate(idx, val);
        updateCounts();
    }

    auto const& dmask() const { return mDirectionMask; }
    auto const& pmask() const { return mPresenceMask; }
    char dmask(size_t idx) const { return mDirectionMask[idx]; }
    char pmask(size_t idx) const { return mPresenceMask[idx]; }
    size_t dmaskCount() const { return mDirectionMaskCount; }
    size_t pmaskCount() const { return mPresenceMaskCount; }
    size_t size() const { return mPresenceMask.size(); }

    std::string to_string() const {
        std::string result(size(), '?');
        for (size_t i=0; i < size(); ++i)
            result[i] = (*this)[i];

        return result;
    }

    bool contains(Term const& other) const {
        if (size() == other.size()) {
            return other.pmask().is_subset_of(this->pmask())
                   && (this->dmask() & other.pmask()) == other.dmask();
        }

        // If the terms have different sizes, we cannot blindly use operator&
        // from the Boost bitset, because it will trigger an assertion. To avoid
        // that we should expand bitsets to the maximum set before checking.
        // TODO: Minimize copying.
        boost::dynamic_bitset<> dmask1 = this->dmask();
        boost::dynamic_bitset<> pmask1 = this->pmask();
        boost::dynamic_bitset<> dmask2 = other.dmask();
        boost::dynamic_bitset<> pmask2 = other.pmask();

        size_t newSize = std::max(size(), other.size());
        dmask1.resize(newSize);
        dmask2.resize(newSize);
        pmask1.resize(newSize);
        pmask2.resize(newSize);

        return pmask2.is_subset_of(pmask1) && (dmask1 & pmask2) == dmask2;
    }

    bool operator < (Term const& other) const {
        // Since boost::dynamic_bitset cannot compare sets of they're of
        // different sizes, we cannot implement here the most natural type
        // of term comparison. Instead, we're implementing the most efficient
        // type of comparison given the above mentioned restriction.
        // TODO: Implement true lexicographic term comparision.
        if (size() < other.size())
            return true;
        if (size() > other.size())
            return false;

        return pmask() < other.pmask()
            || dmask() < other.dmask();
    }

private:
    boost::dynamic_bitset<> mDirectionMask;
    boost::dynamic_bitset<> mPresenceMask;
    size_t    mDirectionMaskCount;
    size_t    mPresenceMaskCount;

    void setWithoutUpdate(size_t idx, char val) {
        mPresenceMask[idx]  = (val == '1' || val == '0');
        mDirectionMask[idx] = (val == '1');
    }

    void updateCounts() {
        mPresenceMaskCount  = mPresenceMask.count();
        mDirectionMaskCount = mDirectionMask.count();
    }

public:

    static char negate(char trite) {
        switch (trite) {
            case '0': return '1';
            case '1': return '0';
            default:  return '*';
        }
    }

    static boost::optional<Term> combine(Term const& a, Term const& b) {
        if (a.pmask() != b.pmask())
            return {};

        auto diff  = a.dmask() ^ b.dmask();
        if (diff.count() != 1)
            return {};

        diff.flip();

        auto pmask = a.pmask();
        pmask &= diff;

        Term result(pmask.size());
        result.assign(a.dmask() & pmask, pmask);
        return result;
    }
};