9
\$\begingroup\$

I have this library/program that allows a client programmer to simulate logical circuits. Without further ado, here is my code:

AbstractCircuitComponent.hpp

#ifndef NET_CODERODDE_CIRCUITS_ABSTRACT_CIRCUIT_COMPONENT_HPP
#define NET_CODERODDE_CIRCUITS_ABSTRACT_CIRCUIT_COMPONENT_HPP

#include <string>
#include <vector>

namespace net {
namespace coderodde {
namespace circuits {

    class AbstractCircuitComponent {
        std::string m_name;

    protected:
        AbstractCircuitComponent* m_output;

    public:

        AbstractCircuitComponent(const std::string& name) :
        m_name{name},
        m_output{nullptr}
        {}

        virtual ~AbstractCircuitComponent() {}

        std::string const& getName() const { return m_name; }

        virtual bool doCycle() const = 0;

        AbstractCircuitComponent* getOutputComponent() {
            return m_output;
        }

        void setOutputComponent(AbstractCircuitComponent* output) {
            this->m_output = output;
        }

        virtual std::vector<AbstractCircuitComponent*>
            getInputComponents() const = 0;

        virtual std::vector<AbstractCircuitComponent*>
            getOutputComponents() const = 0;
    };

} // End of namespace net::coderodde::circuits.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_CIRCUITS_ABSTRACT_CIRCUIT_COMPONENT_HPP

AbstractSingleInputPinCircuitComponent.hpp

#ifndef NET_CODERODDE_CIRCUITS_ABSTRACT_SINGLE_INPUT_PIN_CIRCUIT_COMPONENT_HPP
#define NET_CODERODDE_CIRCUITS_ABSTRACT_SINGLE_INPUT_PIN_CIRCUIT_COMPONENT_HPP

#include "AbstractCircuitComponent.hpp"
#include <string>

namespace net {
namespace coderodde {
namespace circuits {

    class AbstractSingleInputPinCircuitComponent :
    public AbstractCircuitComponent {

    protected:

        AbstractCircuitComponent* m_input;

    public:

        AbstractSingleInputPinCircuitComponent(const std::string& name) :
        AbstractCircuitComponent{name},
        m_input{nullptr} {}

        AbstractCircuitComponent* getInputComponent() {
            return m_input;
        }

        void setInputComponent(AbstractCircuitComponent* input) {
            m_input = input;
        }

        std::vector<AbstractCircuitComponent*> getInputComponents() const {
            std::vector<AbstractCircuitComponent*> input_components = {
                m_input
            };

            return input_components;
        }

        std::vector<AbstractCircuitComponent*> getOutputComponents() const {
            std::vector<AbstractCircuitComponent*> output_components = {
                m_output
            };

            return output_components;
        }
    };

} // End of namespace net::coderodde::circuits.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_CIRCUITS_ABSTRACT_SINGLE_INPUT_PIN_CIRCUIT_COMPONENT_HPP

AbstractDoubleInputPinCircuitComponent.hpp

#ifndef NET_CODERODDE_CIRCUITS_ABSTRACT_DOUBLE_INPUT_PIN_CIRCUIT_COMPONENT_HPP
#define NET_CODERODDE_CIRCUITS_ABSTRACT_DOUBLE_INPUT_PIN_CIRCUIT_COMPONENT_HPP

#include "AbstractCircuitComponent.hpp"
#include <string>
#include <utility>

namespace net {
namespace coderodde {
namespace circuits {

    class AbstractDoubleInputPinCircuitComponent :
    public AbstractCircuitComponent {

    protected:
        AbstractCircuitComponent* m_input1;
        AbstractCircuitComponent* m_input2;

    public:
        AbstractDoubleInputPinCircuitComponent(const std::string& name) :
        AbstractCircuitComponent{name},
        m_input1{nullptr},
        m_input2{nullptr} {}

        AbstractCircuitComponent* getInputComponent1() { return m_input1; }
        AbstractCircuitComponent* getInputComponent2() { return m_input2; }

        void setInputComponent1(AbstractCircuitComponent* input) {
            m_input1 = input;
        }

        void setInputComponent2(AbstractCircuitComponent* input) {
            m_input2 = input;
        }

        std::vector<AbstractCircuitComponent*> getInputComponents() const {
            std::vector<AbstractCircuitComponent*> input_components = {
                m_input1, m_input2
            };

            return input_components;
        }

        std::vector<AbstractCircuitComponent*> getOutputComponents() const {
            std::vector<AbstractCircuitComponent*> output_components = {
                m_output
            };

            return output_components;
        }
    };

} // End of namespace net::coderodde::circuits.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_CIRCUITS_ABSTRACT_DOUBLE_INPUT_PIN_CIRCUIT_COMPONENT_HPP

Circuit.hpp

#ifndef NET_CODERODDE_CIRCUITS_CIRCUIT_HPP
#define NET_CODERODDE_CIRCUITS_CIRCUIT_HPP

#include "BackwardCycleException.hpp"
#include "ForwardCycleException.hpp"
#include "IncompleteCircuitException.hpp"
#include "InputPinOccupiedException.hpp"
#include "components/AbstractCircuitComponent.hpp"
#include "components/AbstractDoubleInputPinCircuitComponent.hpp"
#include "components/AbstractSingleInputPinCircuitComponent.hpp"
#include "components/support/AndGate.hpp"
#include "components/support/BranchWire.hpp"
#include "components/support/InputGate.hpp"
#include "components/support/NotGate.hpp"
#include "components/support/OrGate.hpp"
#include "components/support/OutputGate.hpp"

#include <algorithm>
#include <iterator>
#include <sstream>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

namespace net {
namespace coderodde {
namespace circuits {

    enum class Color {
        WHITE,
        GRAY,
        BLACK
    };

    class Circuit : public AbstractCircuitComponent {
    public:

        friend class TargetComponentSelector;

        Circuit(const std::string& name, size_t inputPins, size_t outputPins) :
        AbstractCircuitComponent{checkName(name)},
        m_number_of_input_pins {checkInputPinCount(inputPins)},
        m_number_of_output_pins{checkOutputPinCount(outputPins)}
        {
            for (size_t input_pin = 0;
                 input_pin < m_number_of_input_pins;
                 input_pin++) {
                std::stringstream ss;
                ss << INPUT_PIN_NAME_PREFIX << input_pin;
                std::string input_component_name;
                input_component_name = ss.str();

                InputGate* input_component =
                    new InputGate{input_component_name};

                m_component_map[input_component_name] = input_component;
                m_component_set.insert(input_component);
                m_input_gates.push_back(input_component);
            }

            for (size_t output_pin = 0;
                 output_pin < m_number_of_output_pins;
                 output_pin++) {
                std::stringstream ss;
                ss << OUTPUT_PIN_NAME_PREFIX << output_pin;
                std::string output_component_name;
                output_component_name = ss.str();

                OutputGate* output_component =
                    new OutputGate(output_component_name);

                m_component_map[output_component_name] = output_component;
                m_component_set.insert(output_component);
                m_output_gates.push_back(output_component);
            }
        }

        Circuit(Circuit& circuit, std::string const& name)
        :
        Circuit{checkName(name),
                circuit.m_number_of_input_pins,
                circuit.m_number_of_output_pins} {
            std::unordered_map<AbstractCircuitComponent*,
                               AbstractCircuitComponent*> component_map;

            for (InputGate* mapped_input_gate : m_input_gates) {
                AbstractCircuitComponent* input_gate =
                circuit.m_component_map[mapped_input_gate->getName()];

                component_map[input_gate] = mapped_input_gate;
            }

            for (OutputGate* mapped_output_gate : m_output_gates) {
                AbstractCircuitComponent* output_gate =
                circuit.m_component_map[mapped_output_gate->getName()];

                component_map[output_gate] = mapped_output_gate;
            }

            for (AbstractCircuitComponent* component :
                 circuit.m_component_set) {
                if (!isInputGate(component) && !isOutputGate(component)) {
                    component_map[component] = copyComponent(component);
                }
            }

            for (AbstractCircuitComponent* component :
                 circuit.m_component_set) {
                AbstractCircuitComponent* mapped_component =
                component_map[component];

                for (AbstractCircuitComponent* input_component :
                     component->getInputComponents()) {
                    AbstractCircuitComponent* mapped_input_component =
                    component_map[input_component];

                    connectInput(component,
                                 input_component,
                                 mapped_component,
                                 mapped_input_component);
                }

                for (AbstractCircuitComponent* output_component :
                     component->getOutputComponents()) {
                    AbstractCircuitComponent* mapped_output_component =
                    component_map[output_component];

                    connectOutput(component,
                                  mapped_component,
                                  mapped_output_component);
                }
            }
        }

        ~Circuit() {
            for (AbstractCircuitComponent* component : m_component_set) {
                if (m_circuit_set.find(component) == m_circuit_set.end()) {
                    delete component;
                }
            }
        }

        size_t size() {
            return m_component_set.size();
        }

        void addNotGate(std::string not_gate_name) {
            checkIsNotLocked();
            checkNewGateName(not_gate_name);
            NotGate* not_gate = new NotGate{not_gate_name};
            m_component_map[not_gate_name] = not_gate;
            m_component_set.insert(not_gate);
        }

        void addAndGate(std::string and_gate_name) {
            checkIsNotLocked();
            checkNewGateName(and_gate_name);
            AndGate* and_gate = new AndGate{and_gate_name};
            m_component_map[and_gate_name] = and_gate;
            m_component_set.insert(and_gate);
        }

        void addOrGate(std::string or_gate_name) {
            checkIsNotLocked();
            checkNewGateName(or_gate_name);
            OrGate* or_gate = new OrGate{or_gate_name};
            m_component_map[or_gate_name] = or_gate;
            m_component_set.insert(or_gate);
        }

        void addCircuit(Circuit& circuit) {
            checkIsNotLocked();
            checkNewGateName(circuit.getName());
            m_component_map[circuit.getName()] = &circuit;
            m_component_set.insert(&circuit);
            m_circuit_set.insert(&circuit);
        }

        size_t getNumberOfInputPins() {
            return m_number_of_input_pins;
        }

        size_t getNumberOfOutputPins() {
            return m_number_of_output_pins;
        }

        bool doCycle() const {
            for (OutputGate* output_gate : m_output_gates) {
                output_gate->doCycle();
            }

            return false;
        }

        void setInputBits(std::vector<bool>& bits) {
            unsetAllInputPins();

            for (size_t i = 0; i < bits.size(); ++i) {
                m_input_gates[i]->setBit(bits[i]);
            }
        }

        std::vector<bool> doCycle(std::vector<bool>& bits) {
            setInputBits(bits);
            return getOutputBits();
        }

        std::vector<bool> getOutputBits() {
            std::vector<bool> output_bits{};
            output_bits.resize(m_number_of_output_pins);

            for (size_t i = 0; i < m_output_gates.size(); ++i) {
                output_bits[i] = m_output_gates[i]->doCycle();
            }

            return output_bits;
        }

        std::vector<AbstractCircuitComponent*> getInputComponents() const {
            std::vector<AbstractCircuitComponent*> input_components;
            input_components.assign(m_input_gates.cbegin(),
                                    m_input_gates.cend());

            return input_components;
        }

        std::vector<AbstractCircuitComponent*> getOutputComponents() const {
            std::vector<AbstractCircuitComponent*> output_components;
            output_components.assign(m_output_gates.cbegin(),
                                     m_output_gates.cend());

            return output_components;
        }

        void connectToFirstInputPin(std::string const& source_component_name,
                                    std::string const& target_component_name) {
            AbstractCircuitComponent* source_component;
            AbstractCircuitComponent* target_component;

            source_component = getComponentByName(source_component_name);
            target_component = getComponentByName(target_component_name);

            checkIsDoubleInputGate(target_component);

            if (((AbstractDoubleInputPinCircuitComponent*) target_component)
                ->getInputComponent1() != nullptr) {
                throw InputPinOccupiedException{
                    "The first input pin of ... is occupied"
                };
            }

            if (source_component->getOutputComponent() == nullptr) {
                ((AbstractDoubleInputPinCircuitComponent*) target_component)
                ->setInputComponent1(source_component);

                source_component->setOutputComponent(target_component);
            } else if (isBranchWire(source_component->getOutputComponent())) {
                ((AbstractDoubleInputPinCircuitComponent*) target_component)
                ->setInputComponent1(source_component->getOutputComponent());

                ((BranchWire*) source_component->getOutputComponent())->
                connectTo(target_component);
            } else {
                // Replace an existing wire with BranchWire.
                BranchWire* branch_wire = new BranchWire();

                // Introduce the new BranchWire to the circuit.
                m_component_set.insert(branch_wire);

                // Load the BranchWire outputs:
                branch_wire->connectTo(
                                       source_component->getOutputComponent());

                branch_wire->connectTo(target_component);

                if (isDoubleInputPinComponent(
                                    source_component->getOutputComponent())) {
                    AbstractDoubleInputPinCircuitComponent* tmp_component =
                    (AbstractDoubleInputPinCircuitComponent*)
                    source_component->getOutputComponent();

                    if (tmp_component->getInputComponent2() ==
                        source_component) {
                        tmp_component->setInputComponent1(branch_wire);
                    } else {
                        tmp_component->setInputComponent2(branch_wire);
                    }
                } else {
                    AbstractSingleInputPinCircuitComponent* tmp_component =
                    (AbstractSingleInputPinCircuitComponent*)
                    source_component->getOutputComponent();

                    tmp_component->setInputComponent(branch_wire);
                }

                ((AbstractDoubleInputPinCircuitComponent*) target_component)
                ->setInputComponent1(branch_wire);

                source_component->setOutputComponent(branch_wire);
                branch_wire->setInputComponent(source_component);
            }
        }

        void connectToSecondInputPin(std::string const& source_component_name,
                                     std::string const& target_component_name) {
            AbstractCircuitComponent* source_component;
            AbstractCircuitComponent* target_component;

            source_component = getComponentByName(source_component_name);
            target_component = getComponentByName(target_component_name);

            checkIsDoubleInputGate(target_component);

            if (((AbstractDoubleInputPinCircuitComponent*) target_component)
                ->getInputComponent2() != nullptr) {
                throw InputPinOccupiedException{
                    "The second input pin of ... is occupied."
                };
            }

            if (source_component->getOutputComponent() == nullptr) {
                ((AbstractDoubleInputPinCircuitComponent*) target_component)
                ->setInputComponent2(source_component);

                source_component->setOutputComponent(target_component);
            } else if (isBranchWire(source_component->getOutputComponent())) {
                ((AbstractDoubleInputPinCircuitComponent*) target_component)
                ->setInputComponent2(source_component->getOutputComponent());

                ((BranchWire*) source_component->getOutputComponent())
                ->connectTo(target_component);
            } else {
                // Replace an existing wire with BranchWire.
                BranchWire* branch_wire = new BranchWire();

                // Introduce the new BranchWire to the circuit.
                m_component_set.insert(branch_wire);

                // Load the BranchWire outputs:
                branch_wire->connectTo(source_component->getOutputComponent());
                branch_wire->connectTo(target_component);

                if (isDoubleInputPinComponent(
                                    source_component->getOutputComponent())) {
                    AbstractDoubleInputPinCircuitComponent* tmp_component =
                    (AbstractDoubleInputPinCircuitComponent*)
                    source_component->getOutputComponent();

                    if (tmp_component->getInputComponent1() ==
                        source_component) {
                        tmp_component->setInputComponent1(branch_wire);
                    } else {
                        tmp_component->setInputComponent2(branch_wire);
                    }
                } else {
                    AbstractSingleInputPinCircuitComponent* tmp_component =
                    (AbstractSingleInputPinCircuitComponent*)
                    source_component->getOutputComponent();

                    tmp_component->setInputComponent(branch_wire);
                }

                ((AbstractDoubleInputPinCircuitComponent*) target_component)
                ->setInputComponent2(branch_wire);

                source_component->setOutputComponent(branch_wire);
                branch_wire->setInputComponent(source_component);
            }
        }

        void connectTo(std::string const& source_component_name,
                       std::string const& target_component_name) {
            AbstractCircuitComponent* source_component;
            AbstractCircuitComponent* target_component;

            source_component = getComponentByName(source_component_name);
            target_component = getComponentByName(target_component_name);

            checkIsSingleInputGate(target_component);

            if (((AbstractSingleInputPinCircuitComponent*) target_component)
                ->getInputComponent() != nullptr) {
                throw InputPinOccupiedException{
                    "The only input pin is occupied."
                };
            }

            if (source_component->getOutputComponent() == nullptr) {
                ((AbstractSingleInputPinCircuitComponent*) target_component)
                ->setInputComponent(source_component);

                source_component->setOutputComponent(target_component);
            } else if (
                       isBranchWire(source_component->getOutputComponent())) {
                ((AbstractSingleInputPinCircuitComponent*) target_component)
                ->setInputComponent(source_component->getOutputComponent());

                ((BranchWire*) source_component->getOutputComponent())
                ->connectTo(target_component);
            } else {
                // Replace an existing wire with BranchWire.
                BranchWire* branch_wire = new BranchWire();

                // Introduce the BranchWire to the circuit.
                m_component_set.insert(branch_wire);

                // Load the BranchWire outputs.
                branch_wire->connectTo(source_component->getOutputComponent());
                branch_wire->connectTo(target_component);

                source_component->setOutputComponent(branch_wire);
                ((AbstractSingleInputPinCircuitComponent*) target_component)
                ->setInputComponent(branch_wire);

                branch_wire->setInputComponent(source_component);
            }
        }

        void lock() {
            if (m_locked) {
                return;
            }

            m_locked = true;
            lockSubcircuits();
            checkAllPinsAreConnected();
            checkIsDagInForwardDirection();
            checkIsDagInBackwardDirection();
        }

    private:

        bool isInputGate(AbstractCircuitComponent* input_gate_candidate) {
            return dynamic_cast<InputGate*>(input_gate_candidate) != nullptr;
        }

        bool isOutputGate(AbstractCircuitComponent* output_gate_candidate) {
            return dynamic_cast<OutputGate*>(output_gate_candidate) != nullptr;
        }

        bool isAndGate(AbstractCircuitComponent* and_gate_candidiate) {
            return dynamic_cast<AndGate*>(and_gate_candidiate) != nullptr;
        }

        bool isOrGate(AbstractCircuitComponent* or_gate_candidate) {
            return dynamic_cast<OrGate*>(or_gate_candidate) != nullptr;
        }

        bool isNotGate(AbstractCircuitComponent* not_gate_candidate) {
            return dynamic_cast<NotGate*>(not_gate_candidate) != nullptr;
        }

        bool isBranchWire(AbstractCircuitComponent* branch_wire_candidate) {
            return dynamic_cast<BranchWire*>(branch_wire_candidate) != nullptr;
        }

        AbstractCircuitComponent* copyComponent(
                                                AbstractCircuitComponent* component) {
            if (isNotGate(component)) {
                return new NotGate(component->getName());
            }

            if (isAndGate(component)) {
                return new AndGate(component->getName());
            }

            if (isOrGate(component)) {
                return new OrGate(component->getName());
            }

            if (isBranchWire(component)) {
                return new BranchWire();
            }

            throw std::logic_error{"Should not get here."};
        }

        void connectInput(AbstractCircuitComponent* component,
                          AbstractCircuitComponent* input_component,
                          AbstractCircuitComponent* mapped_component,
                          AbstractCircuitComponent* mapped_input_component) {
            if (isSingleInputPinComponent(mapped_component)) {
                ((AbstractSingleInputPinCircuitComponent*) mapped_component)
                ->setInputComponent(mapped_input_component);
            } else {
                AbstractDoubleInputPinCircuitComponent* component1 =
                (AbstractDoubleInputPinCircuitComponent*) mapped_component;

                AbstractDoubleInputPinCircuitComponent* component2 =
                (AbstractDoubleInputPinCircuitComponent*) component;

                if (input_component == component2->getInputComponent1()) {
                    component1->setInputComponent1(mapped_input_component);
                } else {
                    component1->setInputComponent2(mapped_input_component);
                }
            }
        }

        void connectOutput(AbstractCircuitComponent* component,
                           AbstractCircuitComponent* mapped_component,
                           AbstractCircuitComponent* mapped_output_component) {
            if (isBranchWire(component)) {
                BranchWire* branch_wire = (BranchWire*) mapped_component;
                branch_wire->connectTo(mapped_output_component);
            } else {
                mapped_component->setOutputComponent(mapped_output_component);
            }
        }

        bool isCircuit(AbstractCircuitComponent* circuit_candidate) {
            return dynamic_cast<Circuit*>(circuit_candidate) != nullptr;
        }

        void lockSubcircuits() {
            for (AbstractCircuitComponent* component : m_component_set) {
                if (isCircuit(component)) {
                    ((Circuit*) component)->lock();
                }
            }
        }

        void checkInputGateConnected(AbstractCircuitComponent* component) {
            InputGate* gate = (InputGate*) component;

            if (gate->getOutputComponent() == nullptr) {
                throw IncompleteCircuitException{"A"};
            }
        }

        void checkOutputGateConnected(AbstractCircuitComponent* component) {
            OutputGate* gate = (OutputGate*) component;

            if (gate->getInputComponent() == nullptr) {
                throw IncompleteCircuitException{"FD"};
            }
        }

        void checkAllPinsAreConnected() {
            for (const std::pair<std::string, AbstractCircuitComponent*> p :
                 m_component_map) {
                std::string name = p.first;
                AbstractCircuitComponent* component = p.second;

                if (isInputGate(component)) {
                    checkInputGateConnected(component);
                } else if (isOutputGate(component)) {
                    checkOutputGateConnected(component);
                } else if (isSingleInputPinComponent(component)) {
                    checkSingleInputComponentConnected(
                            (AbstractSingleInputPinCircuitComponent*) component,
                            name);
                } else if (isDoubleInputPinComponent(component)) {
                    checkDoubleInputComponentConnected(
                            (AbstractDoubleInputPinCircuitComponent*) component,
                            name);
                } else {
                    throw std::logic_error{"Unknown circuit type."};
                }
            }
        }

        void checkOutputIsConnected(AbstractCircuitComponent* component,
                                    std::string const& component_name) {
            if (component->getOutputComponent() == nullptr) {
                std::stringstream ss;
                ss << "The output pin of \""
                << component_name
                << "\" is null.";

                throw IncompleteCircuitException{ss.str()};
            }
        }

        void checkSingleInputComponentConnected(
                            AbstractSingleInputPinCircuitComponent* component,
                            std::string const& component_name) {
            if (component->getInputComponent() == nullptr) {
                std::stringstream ss;
                ss << "The only input pin of \""
                   << component_name
                   << "\" is null.";

                throw IncompleteCircuitException{ss.str()};
            }

            checkOutputIsConnected(component, component_name);
        }

        void checkDoubleInputComponentConnected(
                            AbstractDoubleInputPinCircuitComponent* component,
                            std::string const& component_name) {
            if (component->getInputComponent1() == nullptr) {
                std::stringstream ss;
                ss << "The first input pin of \""
                   << component_name
                   << "\" is null.";

                throw IncompleteCircuitException{ss.str()};
            }

            if (component->getInputComponent2() == nullptr) {
                std::stringstream ss;
                ss << "The second input pin of \""
                   << component_name
                   << "\" is null.";

                throw IncompleteCircuitException{ss.str()};
            }

            checkOutputIsConnected(component, component_name);
        }

        static const size_t MINIMUM_INPUT_PINS  = 1;
        static const size_t MINIMUM_OUTPUT_PINS = 1;

        static const std::string INPUT_PIN_NAME_PREFIX;
        static const std::string OUTPUT_PIN_NAME_PREFIX;

        std::unordered_map<std::string,
                           AbstractCircuitComponent*> m_component_map;
        std::unordered_set<AbstractCircuitComponent*> m_component_set;
        std::unordered_set<AbstractCircuitComponent*> m_circuit_set;

        const size_t m_number_of_input_pins;
        const size_t m_number_of_output_pins;

        std::vector<InputGate*> m_input_gates;
        std::vector<OutputGate*> m_output_gates;

        bool m_locked{false};

        template<typename Out>
        void split(std::string const& s, char delimeter, Out result) {
            std::stringstream ss;
            ss.str(s);
            std::string item;

            while (std::getline(ss, item, delimeter)) {
                *(result++) = item;
            }
        }

        std::vector<std::string> split(std::string const& s, char delimeter) {
            std::vector<std::string> elements;
            split(s, delimeter, std::back_inserter(elements));
            return elements;
        }

        const std::string& checkName(const std::string& name) {
            if (name.empty()) {
                throw std::invalid_argument{"The circuit name is empty."};
            }

            if (name.find(INPUT_PIN_NAME_PREFIX) == 0) {
                throw std::invalid_argument{
                    "The circuit name has illegal prefix."
                };
            }

            if (name.find(OUTPUT_PIN_NAME_PREFIX) == 0) {
                throw std::invalid_argument{
                    "The circuit name has illegal prefix."
                };
            }

            return name;
        }

        size_t checkInputPinCount(size_t inputPins) {
            if (inputPins == 0) {
                throw std::invalid_argument{"Number of input pins is zero."};
            }

            return inputPins;
        }

        size_t checkOutputPinCount(size_t outputPins) {
            if (outputPins == 0) {
                throw std::invalid_argument{"Number of output pins is zero."};
            }

            return outputPins;
        }

        void checkIsNotLocked() {
            if (m_locked) {
                throw std::logic_error{"The circuit is locked."};
            }
        }

        bool hasPrefix(std::string const& str, std::string const& prefix) {
            return std::mismatch(prefix.begin(),
                                 prefix.end(),
                                 str.begin()).first == prefix.end();
        }

        const std::string checkNewGateName(const std::string& gate_name) {
            if (gate_name.empty()) {
                throw std::invalid_argument{"The name of a new gate is empty."};
            }

            if (hasPrefix(gate_name, INPUT_PIN_NAME_PREFIX) ||
                hasPrefix(gate_name, OUTPUT_PIN_NAME_PREFIX)) {
                throw std::invalid_argument{
                    "The new gate name has invalid prefix."
                };
            }

            if (m_component_map.find(gate_name) != m_component_map.cend()) {
                throw std::invalid_argument{
                    "The new gate name is already occupied."
                };
            }

            return gate_name;
        }

        void unsetAllInputPins() {
            for (InputGate* input_gate : m_input_gates) {
                input_gate->setBit(false);
            }
        }

        AbstractCircuitComponent*
        getComponentByName(std::string const& component_name) {
            AbstractCircuitComponent* component;

            std::vector<std::string> component_name_components =
            split(component_name, '.');

            if (component_name_components.size() > 1) {
                if (component_name_components.size() != 2) {
                    throw std::invalid_argument{"More than one dot operators."};
                }

                Circuit* subcircuit =
                (Circuit*) m_component_map[component_name_components[0]];

                if (subcircuit == nullptr) {
                    throw std::invalid_argument{
                        "Subcircuit is not present in this circuit."
                    };
                }

                component =
                subcircuit->m_component_map[component_name_components[1]];
            } else {
                component = m_component_map[component_name];
            }

            if (component == nullptr) {
                throw std::invalid_argument{
                    "The target component is not present in the circuit."
                };
            }

            return component;
        }

        bool isDoubleInputPinComponent(AbstractCircuitComponent* component) {
            return dynamic_cast<AbstractDoubleInputPinCircuitComponent*>
            (component) != nullptr;
        }

        bool isSingleInputPinComponent(AbstractCircuitComponent* component) {
            return dynamic_cast<AbstractSingleInputPinCircuitComponent*>
            (component) != nullptr;
        }

        void checkIsSingleInputGate(AbstractCircuitComponent* gate) {
            if (dynamic_cast<AbstractSingleInputPinCircuitComponent*>(gate)
                == nullptr) {
                throw std::logic_error{
                    "A single input pin is expected here."
                };
            }
        }

        void checkIsDoubleInputGate(AbstractCircuitComponent* gate) {
            if (dynamic_cast<AbstractDoubleInputPinCircuitComponent*>(gate)
                == nullptr) {
                throw std::logic_error{
                    "A double input pin is expected here."
                };
            }
        }

        void checkIsDagInForwardDirection() {
            std::unordered_map<AbstractCircuitComponent*, Color> colors;

            for (AbstractCircuitComponent* component : m_component_set) {
                colors[component] = Color::WHITE;
            }

            for (AbstractCircuitComponent* component : m_input_gates) {
                if (colors[component] == Color::WHITE) {
                    dfsForwardVisit(component, colors);
                }
            }
        }

        void checkIsDagInBackwardDirection() {
            std::unordered_map<AbstractCircuitComponent*, Color> colors;

            for (AbstractCircuitComponent* component : m_component_set) {
                colors[component] = Color::WHITE;
            }

            for (AbstractCircuitComponent* component : m_output_gates) {
                if (colors[component] == Color::WHITE) {
                    dfsBackwardVisit(component, colors);
                }
            }
        }

        void dfsForwardVisit(
                AbstractCircuitComponent* component,
                std::unordered_map<AbstractCircuitComponent*, Color>& colors) {
            colors[component] = Color::GRAY;

            for (AbstractCircuitComponent* child :
                 component->getOutputComponents()) {
                if (colors[child] == Color::GRAY) {
                    std::stringstream ss;
                    ss << "Found a cycle in circuit\""
                       << getName()
                       << "\" in forward direction.";

                    throw ForwardCycleException(ss.str());
                }

                if (colors[child] == Color::WHITE) {
                    dfsForwardVisit(child, colors);
                }
            }

            colors[component] = Color::BLACK;
        }

        void dfsBackwardVisit(
                AbstractCircuitComponent* component,
                std::unordered_map<AbstractCircuitComponent*, Color>& colors) {
            colors[component] = Color::GRAY;

            for (AbstractCircuitComponent* parent :
                 component->getInputComponents()) {
                if (colors[parent] == Color::GRAY) {
                    std::stringstream ss;
                    ss << "Found a cycle in circuit\""
                       << getName()
                       << "\" in backward direction.";

                    throw BackwardCycleException(ss.str());
                }

                if (colors[parent] == Color::WHITE) {
                    dfsBackwardVisit(parent, colors);
                }
            }

            colors[component] = Color::BLACK;
        }
    };

    const std::string Circuit::INPUT_PIN_NAME_PREFIX  = "inputPin";
    const std::string Circuit::OUTPUT_PIN_NAME_PREFIX = "outputPin";

} // End of namespace net::coderodde::circuits.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_CIRCUITS_CIRCUIT_HPP

AndGate.hpp

#ifndef NET_CODERODDE_CIRCUITS_AND_GATE_HPP
#define NET_CODERODDE_CIRCUITS_AND_GATE_HPP

#include "../AbstractDoubleInputPinCircuitComponent.hpp"
#include <string>
#include <utility>
#include <vector>

namespace net {
namespace coderodde {
namespace circuits {

    class AndGate : public AbstractDoubleInputPinCircuitComponent {
    public:

        AndGate(const std::string& name) :
        AbstractDoubleInputPinCircuitComponent{name} {}

        bool doCycle() const {
            return m_input1->doCycle() && m_input2->doCycle();
        }
    };

} // End of namespace net::coderodde::circuits.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_CIRCUITS_AND_GATE_HPP

NotGate.hpp

#ifndef NET_CODERODDE_CIRCUITS_NOT_GATE_HPP
#define NET_CODERODDE_CIRCUITS_NOT_GATE_HPP

#include "../AbstractCircuitComponent.hpp"
#include "../AbstractSingleInputPinCircuitComponent.hpp"
#include <string>
#include <utility>
#include <vector>

namespace net {
namespace coderodde {
namespace circuits {

    class NotGate : public AbstractSingleInputPinCircuitComponent {
    public:

        NotGate(const std::string& name) :
        AbstractSingleInputPinCircuitComponent{name} {}

        bool doCycle() const {
            return !m_input->doCycle();
        }
    };

} // End of namespace net::coderodde::circuits.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_CIRCUITS_NOT_GATE_HPP

OrGate.hpp

#ifndef NET_CODERODDE_CIRCUITS_OR_GATE_HPP
#define NET_CODERODDE_CIRCUITS_OR_GATE_HPP

#include "../AbstractDoubleInputPinCircuitComponent.hpp"
#include <string>
#include <utility>
#include <vector>

namespace net {
namespace coderodde {
namespace circuits {

    class OrGate : public AbstractDoubleInputPinCircuitComponent {
    public:

        OrGate(const std::string& name) :
        AbstractDoubleInputPinCircuitComponent{name} {}

        bool doCycle() const {
            return m_input1->doCycle() || m_input2->doCycle();
        }
    };

} // End of namespace net::coderodde::circuits.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_CIRCUITS_OR_GATE_HPP

BranchWire.hpp

#ifndef NET_CODERODDE_CIRCUITS_BRANCH_WIRE_HPP
#define NET_CODERODDE_CIRCUITS_BRANCH_WIRE_HPP

#include "../AbstractCircuitComponent.hpp"
#include "../AbstractSingleInputPinCircuitComponent.hpp"
#include <string>
#include <unordered_set>
#include <utility>

namespace net {
namespace coderodde {
namespace circuits {

    class BranchWire : public AbstractSingleInputPinCircuitComponent {
    public:

        BranchWire() : AbstractSingleInputPinCircuitComponent{"dummy_name"} {}

        bool doCycle() const {
            return m_input->doCycle();
        }

        void connectTo(AbstractCircuitComponent* component) {
            m_outputs.insert(component);
        }

        void removeFrom(AbstractCircuitComponent* component) {
            m_outputs.erase(component);
        }

        std::vector<AbstractCircuitComponent*> getOutputComponents() const {
            std::vector<AbstractCircuitComponent*> output_components;
            output_components.assign(m_outputs.cbegin(), m_outputs.cend()); 
            return output_components;
        }

    private:
        std::unordered_set<AbstractCircuitComponent*> m_outputs;
    };

} // End of namespace net::coderodde::circuits.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_CIRCUITS_BRANCH_WIRE_HPP

InputGate.hpp

#ifndef NET_CODERODDE_CIRCUITS_INPUT_GATE_HPP
#define NET_CODERODDE_CIRCUITS_INPUT_GATE_HPP

#include "../AbstractSingleInputPinCircuitComponent.hpp"
#include <string>

namespace net {
namespace coderodde {
namespace circuits {

    class InputGate : public AbstractSingleInputPinCircuitComponent {
    public:

        InputGate(const std::string& name, bool bit) :
        AbstractSingleInputPinCircuitComponent{name},
        m_bit{bit}
        {}

        InputGate(const std::string& name) : InputGate{name, DEFAULT_BIT} {}

        bool doCycle() const {
            if (m_input != nullptr) {
                return m_input->doCycle();
            }

            return m_bit;
        }

        bool getBit() const {
            return m_bit;
        }

        void setBit(bool bit) {
            m_bit = bit;
        }

        std::vector<AbstractCircuitComponent*> getInputComponents() const {
            std::vector<AbstractCircuitComponent*> input_components;

            if (m_input != nullptr) {
                input_components.push_back(m_input);
            }

            return input_components;
        }

    private:

        static const bool DEFAULT_BIT = false;
        bool m_bit;
    };

} // End of namespace net::coderodde::circuits.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_CIRCUITS_INPUT_GATE_HPP

OutputGate.hpp

#ifndef NET_CODERODDE_CIRCUITS_OUTPUT_GATE_HPP
#define NET_CODERODDE_CIRCUITS_OUTPUT_GATE_HPP

#include "../AbstractSingleInputPinCircuitComponent.hpp"
#include <string>

namespace net {
namespace coderodde {
namespace circuits {

    class OutputGate : public AbstractSingleInputPinCircuitComponent {
    public:

        OutputGate(const std::string& name) :
        AbstractSingleInputPinCircuitComponent{name} {}

        bool doCycle() const {
            return m_input->doCycle();
        }

        std::vector<AbstractCircuitComponent*> getOutputComponents() const {
            std::vector<AbstractCircuitComponent*> output_components;

            if (m_output != nullptr) {
                output_components.push_back(m_output);
            }

            return output_components;
        }
    };

} // End of namespace net::coderodde::circuits.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_CIRCUITS_OUTPUT_GATE_HPP

main.cpp

#include "assert.hpp"
#include "net/coderodde/circuits/BackwardCycleException.hpp"
#include "net/coderodde/circuits/Circuit.hpp"
#include "net/coderodde/circuits/ForwardCycleException.hpp"
#include "net/coderodde/circuits/InputPinOccupiedException.hpp"
#include <iostream>
#include <sstream>

using net::coderodde::circuits::BackwardCycleException;
using net::coderodde::circuits::Circuit;
using net::coderodde::circuits::ForwardCycleException;
using net::coderodde::circuits::InputPinOccupiedException;

std::string toBinaryString(std::vector<bool>& bits) {
    std::stringstream ss;
    std::string str;

    for (bool b : bits) {
        ss << (b ? '1' : '0');
    }

    return ss.str();
}

void demo() {
    std::cout << "xor:\n";

    //// The xor gate:
    Circuit xor1{"xor1", 2, 1};

    xor1.addAndGate("and1");
    xor1.addAndGate("and2");
    xor1.addNotGate("not1");
    xor1.addNotGate("not2");
    xor1.addOrGate("or");

    xor1.connectTo("inputPin0", "not1");
    xor1.connectToFirstInputPin("not1", "and1");
    xor1.connectToSecondInputPin("inputPin1", "and1");

    xor1.connectTo("inputPin1", "not2");
    xor1.connectToSecondInputPin("not2", "and2");
    xor1.connectToFirstInputPin("inputPin0", "and2");

    xor1.connectToFirstInputPin("and1", "or");
    xor1.connectToSecondInputPin("and2", "or");
    xor1.connectTo("or", "outputPin0");

    for (bool bit1 : { false, true }) {
        for (bool bit2 : { false, true }) {
            std::vector<bool> input = { bit1, bit2 };
            std::vector<bool> output = xor1.doCycle(input);
            std::cout << toBinaryString(input);
            std::cout << " " << output[0] << "\n";
        }
    }

    //// The 2-bit by 2-bit addition circuit:
    std::cout << "\n2-bit by 2-bit addition:\n";

    Circuit c {"additionCircuit", 4, 3};
    Circuit xor2{xor1, "xor2"};
    Circuit xor3{xor1, "xor3"};

    c.addCircuit(xor1);
    c.addCircuit(xor2);
    c.addCircuit(xor3);

    c.addAndGate("and1");
    c.addAndGate("and2");
    c.addAndGate("and3");
    c.addAndGate("and4");

    c.addOrGate("or1");
    c.addOrGate("or2");

    // Output bit 1:
    c.connectTo("inputPin0", "xor1.inputPin0");
    c.connectTo("inputPin2", "xor1.inputPin1");
    c.connectTo("xor1.outputPin0", "outputPin2");

    // Carry bit:
    c.connectToFirstInputPin("inputPin0", "and1");
    c.connectToSecondInputPin("inputPin2", "and1");

    // Output bit 2:
    c.connectTo("and1", "xor2.inputPin0");
    c.connectTo("inputPin1", "xor2.inputPin1");
    c.connectTo("inputPin3", "xor3.inputPin1");
    c.connectTo("xor2.outputPin0", "xor3.inputPin0");
    c.connectTo("xor3.outputPin0", "outputPin1");

    // Output bit3:
    c.connectToFirstInputPin("inputPin1", "and2");
    c.connectToSecondInputPin("inputPin3", "and2");
    c.connectToFirstInputPin("and1", "and3");
    c.connectToSecondInputPin("inputPin1", "and3");
    c.connectToFirstInputPin("and1", "and4");
    c.connectToSecondInputPin("inputPin3", "and4");

    c.connectToFirstInputPin("and2", "or1");
    c.connectToSecondInputPin("and3", "or1");
    c.connectToFirstInputPin("or1", "or2");
    c.connectToSecondInputPin("and4", "or2");
    c.connectTo("or2", "outputPin0");

    for (bool bit1 : { false, true }) {
        for (bool bit0 : { false, true }) {
            for (bool bit3 : { false, true }) {
                for (bool bit2 : { false, true }) {
                    std::vector<bool> inputInt1 = { bit1, bit0 };
                    std::vector<bool> inputInt2 = { bit3, bit2 };
                    std::vector<bool> input = { bit0, bit1, bit2, bit3 };
                    std::vector<bool> output = c.doCycle(input);
                    std::cout << toBinaryString(inputInt1)
                              << " + "
                              << toBinaryString(inputInt2)
                              << " = "
                              << toBinaryString(output)
                              << "\n";
                }
            }
        }
    }
}

void testFindsForwardCycle() {
    Circuit c{"c", 1, 1, };

    c.addAndGate("and");
    c.connectToFirstInputPin("inputPin0", "and");
    c.connectTo("and", "outputPin0");
    c.connectToSecondInputPin("and", "and");

    bool catched = false;

    try {
        c.lock();
    } catch (ForwardCycleException& ex) {
        catched = true;
    } catch (...) {
        catched = false;
    }

    ASSERT(catched);
}

void testFindsBackwardCycle() {
    Circuit c{"circuit", 1, 1};

    c.addOrGate("or");
    c.addAndGate("and");

    c.connectToFirstInputPin("inputPin0", "or");
    c.connectToSecondInputPin("and", "or");
    c.connectTo("or", "outputPin0");
    c.connectToFirstInputPin("and", "and");
    c.connectToSecondInputPin("and", "and");

    bool catched = false;

    try {
        c.lock();
    } catch (BackwardCycleException& ex) {
        catched = true;
    } catch (...) {
        catched = false;
    }

    ASSERT(catched);
}

void testCannotConnectToOccupiedInput() {
    Circuit c{"myCircuit", 1, 1};

    c.addNotGate("not");
    c.connectTo("inputPin0", "outputPin0");
    c.connectTo("inputPin0", "not");

    bool catched = false;

    try {
        c.connectTo("not", "outputPin0");
    } catch (InputPinOccupiedException& ex) {
        catched = true;
    } catch (...) {
        catched = false;
    }

    ASSERT(catched);
}

void test1() {
    Circuit c{"c", 4, 1};

    c.addAndGate("and1");
    c.addAndGate("and2");
    c.addOrGate("or");

    c.connectToFirstInputPin("inputPin0", "and1");
    c.connectToSecondInputPin("inputPin1", "and1");
    c.connectToFirstInputPin("inputPin2", "and2");
    c.connectToSecondInputPin("inputPin3", "and2");
    c.connectToFirstInputPin("and1", "or");
    c.connectToSecondInputPin("and2", "or");
    c.connectTo("or", "outputPin0");

    for (bool bit0 : { false, true }) {
        for (bool bit1 : { false, true }) {
            for (bool bit2 : { false, true }) {
                for (bool bit3 : { false, true }) {
                    bool expected = (bit0 && bit1) || (bit2 && bit3);
                    std::vector<bool> input = { bit0, bit1, bit2, bit3 };
                    std::vector<bool> output = c.doCycle(input);
                    ASSERT(output.size() == 1);
                    ASSERT(expected == output[0]);
                }
            }
        }
    }
}

void test2() {
    Circuit c{"c", 2, 1};

    c.addAndGate("and1");
    c.addAndGate("and2");
    c.addNotGate("not1");
    c.addNotGate("not2");
    c.addOrGate("or");

    c.connectToFirstInputPin("inputPin0", "and1");
    c.connectTo("inputPin1", "not1");
    c.connectToSecondInputPin("not1", "and1");

    c.connectTo("inputPin0", "not2");
    c.connectToFirstInputPin("not2", "and2");
    c.connectToSecondInputPin("inputPin1", "and2");

    c.connectToFirstInputPin("and1", "or");
    c.connectToSecondInputPin("and2", "or");
    c.connectTo("or", "outputPin0");

    for (bool bit0 : { false, true }) {
        for (bool bit1 : { false, true }) {
            bool expected = (bit0 && !bit1) || (!bit0 && bit1);
            std::vector<bool> input = { bit0, bit1 };
            std::vector<bool> output = c.doCycle(input);
            ASSERT(output.size() == 1);
            ASSERT(expected == output[0]);
        }
    }
}

void testSubcircuit() {
    Circuit subcircuit {"mySubcircuit", 2, 1};

    subcircuit.addAndGate("and");
    subcircuit.addNotGate("not1");
    subcircuit.addNotGate("not2");

    subcircuit.connectTo("inputPin0", "not1");
    subcircuit.connectTo("inputPin1", "not2");
    subcircuit.connectToFirstInputPin("not1", "and");
    subcircuit.connectToSecondInputPin("not2", "and");
    subcircuit.connectTo("and", "outputPin0");

    Circuit circuit {"myCircuit", 2, 1};
    circuit.addCircuit(subcircuit);
    circuit.addNotGate("not");

    circuit.connectTo("inputPin0", "mySubcircuit.inputPin0");
    circuit.connectTo("inputPin1", "mySubcircuit.inputPin1");
    circuit.connectTo("mySubcircuit.outputPin0", "not");
    circuit.connectTo("not", "outputPin0");

    for (bool bit0 : { false, true }) {
        for (bool bit1 : { false, true }) {
            std::vector<bool> input = { bit0, bit1 };
            std::vector<bool> output = circuit.doCycle(input);
            bool expected = !(!bit0 && !bit1);
            ASSERT(output.size() == 1);
            ASSERT(output[0] == expected);
        }
    }
}

void testCopyConstructor() {
    Circuit c1{"c", 2, 2};

    c1.addAndGate("and");
    c1.addOrGate("or");

    c1.connectToFirstInputPin("inputPin0", "and");
    c1.connectToSecondInputPin("inputPin1", "and");
    c1.connectToFirstInputPin("inputPin0", "or");
    c1.connectToSecondInputPin("inputPin1", "or");
    c1.connectTo("and", "outputPin0");
    c1.connectTo("or", "outputPin1");

    Circuit c2{c1, "c2"};

    for (bool bit0 : { false, true }) {
        for (bool bit1 : { false, true }) {
            std::vector<bool> input = { bit0, bit1 };
            std::vector<bool> output1 = c1.doCycle(input);
            std::vector<bool> output2 = c2.doCycle(input);
            ASSERT(output1.size() == 2);
            ASSERT(output2.size() == 2);

            for (int i = 0; i < 2; ++i) {
                ASSERT(output1[i] == output2[i]);
            }
        }
    }
}

void test() {
    testFindsForwardCycle();
    testFindsBackwardCycle();
    testCannotConnectToOccupiedInput();
    test1();
    test2();
    testSubcircuit();
    testCopyConstructor();
}

int main() {
    demo();
    test();
    REPORT
}

The entire project is here.

Critique request

Please tell me anything that comes to mind. Especially, I would like the following questions answered:

  1. Should I split classes into headers + implementation .cpp files?
  2. Valgrind says I leak memory; I don't know where to start to hunt them.
  3. I intended to provide a fluent API: instead of writing circuit.connectToFirstPinOf("and1", "or") I intended to write circuit.connect("and1").toFirstPinOf("or"). However, I ended up with a circular dependency that I could not resolve. Can anyone please address that?
\$\endgroup\$
7
  • \$\begingroup\$ @Incomputable I don't quite understand your arrangement. Consider elaborating it in an answer. \$\endgroup\$
    – coderodde
    Oct 14, 2017 at 12:33
  • \$\begingroup\$ how do you know in which sequence you need to invoke the logic of each? When I was writing up an answer I stumbled upon that problem. The only thing I have in mind is to let pins somehow reflect the owner. \$\endgroup\$ Oct 14, 2017 at 13:09
  • \$\begingroup\$ @Incomputable I don't. I trigger each OutputGate and it asks for bits from its input, which asks further on, and so on. \$\endgroup\$
    – coderodde
    Oct 14, 2017 at 14:03
  • \$\begingroup\$ A sample main that shows how you intend to use this would be most helpful. \$\endgroup\$
    – Edward
    Oct 14, 2017 at 14:52
  • \$\begingroup\$ @Edward, its on the github. \$\endgroup\$ Oct 14, 2017 at 15:41

2 Answers 2

5
\$\begingroup\$

Here are some ideas for ways to improve your code.

Consider shortening names

I'm going to take a deep breath and type the name of one of your classes:

net::coderodde::circuits::AbstractDoubleInputPinCircuitComponent

One one hand, it's a descriptive name, but on the other hand, that's a really long name. Longer names tend to be harder for humans to read and parse, so you might want to consider shortening some of these names a bit. To choose one obvious way to do so, I'd suggest dropping the net namespace.

Separate interface from implementation

It makes the code somewhat longer for a code review, but it's often very useful to separate the interface from the implementation. Put the interface into a separate .h files and the corresponding implementation into a .cpp file. It helps users (or reviewers) of the code see and understand the interface and hides implementation details.

Think of the user

The code requires the user to give every circuit a name, every component a name and every input pin and output pin a name. Further, the code will throw an exception unless very specific names are given as if an input pin name does not begin with "inputPin". This seems to me to be a very unhelpful interface. If I create, for example, an eight input OR gate, I'd rather the software simply number them for me. Also most circuit CAD programs will autonumber parts. Make the computer do the tedious work, and let the human concentrate on the creative parts.

Remove restrictions

There does not seem to me to be a good reason to have the lock() and unlock() functions. They seem only to enforce a number of restrictions which I'd also suggest should be eliminated. For instance, in real circuits, it's not uncommon for there to be no input pins (a clock circuit, for example, may have no input and a single output) or to have output pins that are simply not connected (e.g. the Q and Q# outputs of a flip-flop). Rather than enforcing such restrictions, offer them as functions so the user can decide. Additionally, as with flip-flops, it's common for real circuits to have cycles.

Use the appropriate data structure

Most real logic parts have a fixed number of pins and one can't really add new inputs or outputs on the fly. That suggests that rather than std::vector, a std::array might be a more appropriate data structure.

Avoid relative paths in #includes

Generally it's better to omit relative path names from #include files and instead point the compiler to the appropriate location.

#include "../AbstractDoubleInputPinCircuitComponent.hpp"
#include "net/coderodde/circuits/Circuit.hpp"

For gcc, you'd use -I. This makes the code less dependent on the actual file structure, and leaving such details in a single location: a Makefile or compiler configuration file.

Change the abstraction

Since it appears that you're only interested in simulating digital circuits (and only ones with 2 possible states, so no tri-state, for example), one could consider any component as being a translation of inputs to outputs. I'd start with a class that looks like this:

using logic = bool;
class Component {
public:
    virtual Component &operator++() = 0;
    virtual ~Component() = default;
};

I elected to use operator++ rather than your doCycle since I think it leads to a more natural syntax. Also all values of inputs and outputs are describe using the type logic so that if some other representation, such as a class, were chosen, nothing would need to change except the using statement. Here's a specialization for a Source which has outputs but no inputs:

template <unsigned numOutputs> 
class Source : public Component {
public:
    virtual ~Source() = default;
    void printOutputs(std::ostream &out) const {
        std::copy(output.cbegin(), output.cend(), std::ostream_iterator<logic>(out, " "));
    }
    std::reference_wrapper<const logic> out(unsigned n) const {
        return std::cref(output[n]);
    }
protected:
    std::array<logic, numOutputs> output;
};

Here's a specialization that has both inputs and outputs:

template <unsigned numInputs, unsigned numOutputs>
class IOComponent : public Component {
public:
    IOComponent(std::array<std::reference_wrapper<const logic>, numInputs> input) : input{input} {}
    virtual ~IOComponent() = default;
    void printOutputs(std::ostream &out) const {
        std::copy(output.cbegin(), output.cend(), std::ostream_iterator<logic>(out, " "));
    }
    void printInputs(std::ostream &out) const {
        std::copy(input.cbegin(), input.cend(), std::ostream_iterator<logic>(out, " "));
    }
    std::reference_wrapper<const logic> out(unsigned n) const {
        return std::cref(output[n]);
    }
protected:
    std::array<std::reference_wrapper<const logic>, numInputs> input;
    std::array<logic, numOutputs> output;
};

Now let's specialize these still further. The first is a templated AND gate that takes any number of inputs and produces a single output.

template <unsigned numInputs>
class AndGate : public IOComponent<numInputs, 1> {
    using IOComponent<numInputs, 1>::output; 
    using IOComponent<numInputs, 1>::input; 
public:
    AndGate(std::array<std::reference_wrapper<const logic>, numInputs> in) :
        IOComponent<numInputs, 1>{in}
    { }
    AndGate &operator++() {
        output[0] = std::all_of(input.cbegin(), input.cend(), [](logic in){return in;});
        return *this;
    }
};

Here's a simple symmetric clock in which the half period and phase (really only a half phase) may be specified by the user and produces a single output.

class SimpleClock : public Source<1> {
    using Source<1>::output;
public:
    SimpleClock(unsigned halfperiod = 1, unsigned phase = 0) :
        Source<1>{},
        reload{halfperiod},
        current{phase < halfperiod ? phase+1 : halfperiod}
    { 
        output[0] = !0;
    }
    SimpleClock &operator++() {
        if (--current == 0) {
            output[0] = !output[0];
            current = reload;
        }
        return *this;
    }
private:
    unsigned reload;
    unsigned current;
}; 

Now we can use all of this very simply:

int main() {
    SimpleClock C{2};
    SimpleClock D{1};
    AndGate<2> U1{{C.out(0),D.out(0)}};
    std::vector<Component *> circuit{&C, &D, &U1};
    std::cout << "i\tC D \tout\n"
                 "-\t- - \t---\n";
    for (int i=10; i; --i) {
        std::for_each(circuit.begin(), circuit.end(), [](Component *c){ ++(*c); });
        std::cout << i << '\t';
        U1.printInputs(std::cout);
        std::cout << '\t';
        U1.printOutputs(std::cout);
        std::cout << '\n';
    }
}

Here's what this simple program produces:

i   C D     and
-   - -     ---
10  0 0     0 
9   0 1     0 
8   1 0     0 
7   1 1     1 
6   0 0     0 
5   0 1     0 
4   1 0     0 
3   1 1     1 
2   0 0     0 
1   0 1     0

Note that the wiring is inherent in the construction of the circuit components. Inputs are references to previous outputs. This means that it won't be possible to construct a program that has an unconnected input. We can also easily specify sources that are always true or always false, like this:

const logic AlwaysTrue{true};

One could also implement a Sink template that's the reverse of Source in that a Sink has only inputs but no outputs (such as an LED).

\$\endgroup\$
5
\$\begingroup\$

Implementation

  • Circuit::~Circuit doesn't delete any other Circuit objects, even if it might be the last one to have a pointer. This might be the source of your memory leak.
  • Why are there Circuit::m_component_map and Circuit::m_component_set if both contain the same components? One would suffice.

Design

The logic around doCycles isn't sound. Some reasons off the head:

  • Updates propagate backwards. This can be fine if polled frequently enough, but it might be more efficient to propagate them forwards instead (e.g. if adding a clocked input, you'd only need to update the parts affected by the clock, not everything).
  • doCycles will crash for simple circular circuits (e.g. flipflops or latches). Why? As currently implemented, a logic component asks its predecessors to update to then give its update based on those results. As it is directly or indirectly its own predecessor, this will result in an infinite loop / stack overflow.
  • In other cases, some logic components might update multiple times per cycle (as their doCycle method gets called for each component that directly or indirectly comes after it).

The latter two issues can be fixed by splitting state and update functionality. The first one might not be an issue, but should be considered carefully if any clients of the library are going to build larger circuits.

Along the same lines, if I were to build complex circuits with your library, I'd expect there to be cycles, so why do you throw exceptions if you detect one in Circuit::dfsForwardVisit or Circuit::dfsBackwardVisit? Real circuits are not DAGs!

As another note, only allowing 1 or 2 input pins per logic component might hinder future additions (e.g. flipflops or latches might have more than just 2 inputs, and \$n\$-ary and-gates can be easier to reason about than \$n-1\$ nested binary ones).

Splitting files

Most files are short enough so for them I don't think splitting them into two files has much merit (unless you explicitly want to provide interface headers only).

However, then there's Circuit.hpp: It contains some very long methods (that might be refactored into shorter ones), so for those I would make an exception as it gets hard to see all the members of Circuit between those.

\$\endgroup\$
7
  • \$\begingroup\$ Propagating forward doesn't seem like an easy task. At least not with pin by pin basis, as pin doesn't reflect its owner. At least after 15 minutes of thought it didn't give much. \$\endgroup\$ Oct 14, 2017 at 14:45
  • \$\begingroup\$ @Incomputable: You'd need a queue of components to be processed and a set of components already processed. Only process a component if all inputs are no longer in the queue and it hasn't been processed already. At the start, add all changed inputs to the queue, the rest will be added as needed. Components left in the queue are up for the next round of updates. \$\endgroup\$
    – hoffmale
    Oct 14, 2017 at 15:00
  • \$\begingroup\$ Second bullet: m_component_set indeed contains all the components. What comes to m_component_map, it contains only named components, but BranchWires are not named and are added by Circuit in order for a component to have "multiple" output. \$\endgroup\$
    – coderodde
    Oct 14, 2017 at 17:43
  • \$\begingroup\$ Correction: \$n\$-ary and/or takes only \$n - 1\$ binary ones, not \$n^2 - 1\$. \$\endgroup\$
    – coderodde
    Oct 14, 2017 at 17:46
  • 1
    \$\begingroup\$ @coderodde: Also, regarding your issues with a fluent API: Show us the code you have (e.g. on stack overflow, since it would be offtopic here), and we will be happy to help! \$\endgroup\$
    – hoffmale
    Oct 15, 2017 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.