fork download 
  1. #include <memory>
  2. #include <deque>
  3. #include <vector>
  4. #include <unordered_set>
  5. #include <unordered_map>
  6. #include <string>
  7. #include <utility>
  8. #include <algorithm>
  9. #include <limits>
  10. #include <iostream>
  11.  
  12. using Pin = size_t;
  13.  
  14. class Circuit;
  15. class LogicComponent;
  16.  
  17. struct Connection {
  18.     LogicComponent *component;
  19.     Pin pin;
  20.  
  21.     Connection() : component(nullptr), pin(std::numeric_limits<Pin>::max()) {}
  22.     Connection(LogicComponent *comp, Pin p) : component(comp), pin(p) {}
  23. };
  24.  
  25. class LogicComponent {
  26.     friend class Circuit;
  27.  
  28. protected:
  29.     std::unordered_map<Pin, Connection> inputs;
  30.     std::unordered_map<Pin, Connection> outputs;
  31.  
  32. public:
  33.     LogicComponent() : inputs(), outputs() {}
  34.     virtual ~LogicComponent() {}
  35.  
  36.     virtual void update() = 0;
  37.     virtual bool state(Pin output_pin) = 0;
  38.     virtual Pin max_inputs() = 0;
  39.     virtual Pin max_outputs() = 0;
  40. };
  41.  
  42. class InputGate : public LogicComponent {
  43.     bool input;
  44. public:
  45.     void update() override {}
  46.  
  47.     bool state(Pin output_pin) override {
  48.         return input;
  49.     }
  50.  
  51.     Pin max_inputs() override {
  52.         return 0;
  53.     }
  54.  
  55.     Pin max_outputs() override {
  56.         return std::numeric_limits<Pin>::max();
  57.     }
  58.  
  59.     void set(bool value) {
  60.         input = value;
  61.     }
  62. };
  63.  
  64. class OutputGate : public LogicComponent {
  65. public:
  66.     void update() override {}
  67.  
  68.     bool state(Pin output_pin) override {
  69.         throw std::runtime_error("no output pins");
  70.     }
  71.  
  72.     Pin max_inputs() override {
  73.         return 1;
  74.     }
  75.  
  76.     Pin max_outputs() override {
  77.         return 0;
  78.     }
  79.  
  80.     bool get() {
  81.         auto in = inputs[0];
  82.         if(in.component != nullptr) {
  83.             return in.component->state(in.pin);
  84.         }
  85.         return false;
  86.     }
  87. };
  88.  
  89. class Circuit {
  90.     std::unordered_map<std::string, std::unique_ptr<LogicComponent>> components;
  91.     std::vector<std::unique_ptr<InputGate>> inputs;
  92.     std::vector<std::unique_ptr<OutputGate>> outputs;
  93.     std::deque<LogicComponent*> changed; // would use std::queue if it supported iterators
  94.  
  95.     bool check_input(LogicComponent* current, const std::unordered_set<LogicComponent*>& visited, const std::deque<LogicComponent*>& queue) {
  96.         for(auto entry : current->inputs) {
  97.             auto connection = entry.second;
  98.             if(std::find(std::begin(queue), std::end(queue), connection.component) != std::end(queue)) return false;
  99.         }
  100.  
  101.         if(visited.find(current) != visited.end()) return false;
  102.  
  103.         return true;
  104.     }
  105.  
  106.     void perform_update(std::deque<LogicComponent*> queue) {
  107.         auto visited = std::unordered_set<LogicComponent*>();
  108.  
  109.         while(!queue.empty()) {
  110.             auto current = queue.front();
  111.             queue.pop_front();
  112.  
  113.             if(!check_input(current, visited, queue)) continue; // already processed current or an input is waiting to be processed
  114.  
  115.             current->update();
  116.  
  117.             visited.insert(current);
  118.  
  119.             for(auto entry : current->outputs) {
  120.                 auto connection = entry.second;
  121.                 if(visited.find(connection.component) != visited.end()) { // if already processed connected component...
  122.                     changed.push_back(connection.component); // ...update it again during the next partial update
  123.                 } else {
  124.                     queue.push_back(connection.component); // else update it during this update
  125.                 }
  126.             }
  127.         }
  128.     }
  129.  
  130.     LogicComponent *lookup(std::string name) {
  131.         auto component = components[name].get();
  132.         if(component == nullptr) throw std::runtime_error("unknown component");
  133.  
  134.         return component;
  135.     }
  136.  
  137. public:
  138.     Circuit() : components(), inputs(), outputs(), changed() {}
  139.  
  140.     void update_all() {
  141.         changed.clear();
  142.  
  143.         auto queue = std::deque<LogicComponent*>();
  144.         for(auto& input : inputs) {
  145.             queue.push_back(input.get());
  146.         }
  147.  
  148.         perform_update(queue);
  149.     }
  150.  
  151.     void update() {
  152.         auto queue = std::deque<LogicComponent*>(std::begin(changed), std::end(changed));
  153.         changed.clear();
  154.  
  155.         perform_update(queue);
  156.     }
  157.  
  158.     void create_inputs(size_t count) {
  159.         for(auto i = 0; i < count; ++i) {
  160.             inputs.push_back(std::make_unique<InputGate>());
  161.         }
  162.     }
  163.  
  164.     void create_outputs(size_t count) {
  165.         for(auto i = 0; i < count; ++i) {
  166.             outputs.push_back(std::make_unique<OutputGate>());
  167.         }
  168.     }
  169.  
  170.     void set_input(size_t input, bool value) {
  171.         inputs[input]->set(value);
  172.         changed.push_back(inputs[input].get());
  173.     }
  174.  
  175.     bool get_output(size_t output) {
  176.         return outputs[output]->get();
  177.     }
  178.  
  179.     template<typename TComponentType, typename... Args>
  180.     void create_component(std::string name, Args&&... args) {
  181.         if(components.find(name) != components.end()) throw std::runtime_error("component with same name already exists!");
  182.  
  183.         components[name] = std::make_unique<TComponentType>(std::forward<Args>(args)...);
  184.     }
  185.  
  186.     bool can_connect(std::string name_a, Pin output_pin, std::string name_b, Pin input_pin) {
  187.         auto compA = lookup(name_a);
  188.         auto compB = lookup(name_b);
  189.  
  190.         bool a_has_output = (compA->outputs.find(output_pin) != compA->outputs.end());
  191.         bool b_has_input = (compB->inputs.find(input_pin) != compB->inputs.end());
  192.         bool valid_connection = output_pin < compA->max_outputs() && input_pin < compB->max_inputs();
  193.  
  194.         return !a_has_output && !b_has_input;
  195.     }
  196.  
  197.     void connect(std::string name_a, Pin output_pin, std::string name_b, Pin input_pin) {
  198.         if(!can_connect(name_a, output_pin, name_b, input_pin)) throw std::runtime_error("cannot connect components");
  199.  
  200.         auto compA = lookup(name_a);
  201.         auto compB = lookup(name_b);
  202.  
  203.         compA->outputs[output_pin] = Connection{ compB, input_pin };
  204.         compB->inputs[input_pin] = Connection{ compA, output_pin };
  205.     }
  206.  
  207.     void connect_input(size_t input, std::string name, Pin input_pin) {
  208.         auto component = lookup(name);
  209.  
  210.         inputs[input]->outputs[0] = Connection{ component, input_pin };
  211.         component->inputs[input_pin] = Connection{ inputs[input].get(), 0 };
  212.     }
  213.  
  214.     void connect_output(size_t output, std::string name, Pin output_pin) {
  215.         auto component = lookup(name);
  216.  
  217.         outputs[output]->inputs[0] = Connection{ component, output_pin };
  218.         component->outputs[output_pin] = Connection{ outputs[output].get(), 0 };
  219.     }
  220.  
  221.     void disconnect_output(std::string name, Pin output_pin) {
  222.         auto component = lookup(name);
  223.  
  224.         auto connection = component->outputs[output_pin];
  225.         component->outputs.erase(output_pin);
  226.  
  227.         if(connection.component != nullptr) {
  228.             connection.component->inputs.erase(connection.pin);
  229.         }
  230.     }
  231.  
  232.     void disconnect_input(std::string name, Pin input_pin) {
  233.         auto component = lookup(name);
  234.  
  235.         auto connection = component->inputs[input_pin];
  236.         component->inputs.erase(input_pin);
  237.  
  238.         if(connection.component != nullptr) {
  239.             connection.component->outputs.erase(connection.pin);
  240.         }
  241.     }
  242. };
  243.  
  244. // implement other logic components as needed, e.g. and:
  245.  
  246. template<size_t Arity>
  247. class AndGate : public LogicComponent {
  248.     bool value = false;
  249.  
  250. public:
  251.     void update() override {
  252.         value = true;
  253.  
  254.         for(auto i = 0u; i < Arity; ++i) {
  255.             auto input = inputs[i];
  256.             if(input.component != nullptr) {
  257.                 value = value && input.component->state(input.pin);
  258.             } else {
  259.                 value = false; // change this if unset input should be assumed to be set
  260.             }
  261.         }
  262.     }
  263.  
  264.     bool state(Pin output_pin) override {
  265.         if(output_pin >= max_outputs()) throw std::runtime_error("output pin too high!");
  266.         return value;
  267.     }
  268.  
  269.     Pin max_inputs() override {
  270.         return Arity;
  271.     }
  272.  
  273.     Pin max_outputs() override {
  274.         return 1;
  275.     }
  276. };
  277.  
  278. class NotGate : public LogicComponent {
  279.     bool value = false;
  280. public:
  281.     void update() override {
  282.         auto input = inputs[0];
  283.         if(input.component != nullptr) {
  284.             value = !input.component->state(input.pin);
  285.         }
  286.     }
  287.  
  288.     bool state(Pin output_pin) override {
  289.         return value;
  290.     }
  291.  
  292.     Pin max_inputs() override {
  293.         return 1;
  294.     }
  295.  
  296.     Pin max_outputs() override {
  297.         return 1;
  298.     }
  299. };
  300.  
  301. class Wire : public LogicComponent {
  302.     bool value = false;
  303. public:
  304.     void update() override {
  305.         value = false;
  306.         for(auto entry : inputs) {
  307.             auto connection = entry.second;
  308.         	if(connection.component != nullptr) value = value || connection.component->state(connection.pin);
  309.         }
  310.     }
  311.  
  312.     bool state(Pin output_pin) override {
  313.         return value;
  314.     }
  315.  
  316.     Pin max_inputs() override {
  317.         return std::numeric_limits<Pin>::max();
  318.     }
  319.  
  320.     Pin max_outputs() override {
  321.         return std::numeric_limits<Pin>::max();
  322.     }
  323. };
  324.  
  325.  
  326. // same for OrGate, XorGate, Clocks, ...
  327.  
  328. // usage example
  329. int main() {
  330.     Circuit circuit;
  331.  
  332.     circuit.create_component<AndGate<2>>("and1");
  333.     circuit.create_component<NotGate>("not1");
  334.     circuit.create_component<Wire>("wire1");
  335.  
  336.     circuit.create_inputs(1);
  337.     circuit.create_outputs(1);
  338.  
  339.     circuit.connect("and1", 0, "not1", 0);
  340.  
  341.     circuit.connect("not1", 0, "wire1", 0);
  342.  
  343.     circuit.connect("wire1", 0, "and1", 0);
  344.  
  345.     circuit.connect_input(0, "and1", 1);
  346.     circuit.connect_output(0, "wire1", 1);
  347.  
  348.     circuit.set_input(0, true);
  349.     for(auto i = 0; i < 10; ++i) {
  350.         circuit.update();
  351.         std::cout << "output 0: " << (circuit.get_output(0) ? "1" : "0") << "\n";
  352.     }
  353. }
Success #stdin #stdout 0s 16088KB
comments (?)
stdin 
Standard input is empty
stdout 
output 0: 1
output 0: 0
output 0: 1
output 0: 0
output 0: 1
output 0: 0
output 0: 1
output 0: 0
output 0: 1
output 0: 0
https://ideone.com/lxVgsQ
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!