AND Gate with delayed inputs in C#

Question

I am trying to implement a boolean AND gate with multiple inputs. Each input has an integer identifying it. Input signals arrive randomly, and are stored at the gate (so it's not a pure AND gate, but one with delayed inputs). Only when all the input signals have arrived, does the gate fire.

Note: 2 signals arriving at the same input do not count as two.



I figured I'd create a Dictionary which will store the inputs, and when stimulus arrives, update the Value for that particular input's Id Key, then AND all values. If the result is 1, then fire the gate and reset all Values of the Dictionary to 0 and wait again.



Something doesn't sound right with my approach, and I have a feeling there must be something more elegant and performant (.Net).

Answer 1

If the input ID are sequencial, you could probably use a bool[] instead of a dictionary.

   bool[] inputs = new bool[10];

   void SetInput(int id, bool val)
   {
       inputs[id] = val;
   }

   bool trigger()
   {
        return inputs.All(b => b);
   }

   void reset()
   {
        Array.Clear(input, 0, inputs.Length);
   }

Answer 2

Storing the input information seems unnecessary to me. Whenever a signal arrives just check if it is zero make sure the result will be zero. If it is one, do nothing specific. Then you just need to check if all the input signals have arrived.

Answer 3

EDITED:

Oh, I get it now, by "multiple" you meant "more than two", and the values don't have integer identifiers, the input lines do. Okay, let's start over.

Do you really need to store the inputs? If any input is false, the output is false, so just output true as long as you have at least one (or two, if you prefer) inputs that are true and until you get an input that is false.

Oh, but you said "two signals arriving at the same input do not count as two." In order to enforce this, you have to track (but not necessarily store) the inputs. This is what it really comes down to.

So the real question is: How do I efficiently store (and retrieve) a sparse array of integers in C#?

A dictionary (hash table) certainly is the obvious choice whenever you're talking about sparse arrays. But in this case, you only need a boolean for each entry, and a Dictionary<int, bool> is indeed somewhat wasteful.

What is the max range of input line IDs? Is it [int.MinValue, int.MaxValue], or something in a more manageable range? If the maximum range of identifiers is relatively small, you might want to look into System.Collections.BitArray or System.Collections.Specialized.BitVector32.

If you use one of these bit collections, you have two choices:

1. Use two BitArrays/BitVector32s: one to store the input values and the other to store whether or not a signal has arrived on that line.
2. Use just one BitArray/BitVector32. Use it to store whether or not a signal has arrived on a given line, and keep a separate bool value that will be anded with each new input. This option doesn't afford resetting a false input on a line to a true input on the same line.

Assuming 32 or fewer input lines, an efficient BitVector32 implementation of option 1 above would be something like this:

class AndGate{
    BitVector32 activeLines;
    BitVector32 inputValues;

    public void Reset(){
        activeLines[-1] = inputValues[-1] = false; 
    }
    public void Input(int line, bool value){
        if(line < 0 || line > 31)
            throw new ArgumentOutOfRangeException("line");

        activeLines[1 << line] = true;
        inputValues[1 << line] = value;
    }
    public bool GetOutput(bool reset){
        bool rtn = activeLines.Data == inputValues.Data;
        if(reset)
            Reset();
        return rtn;
    }
}

If you need more than 32 lines, then an equivalent implementation with BitArray would be similar, except that GetOutput would be more complicated and less efficient. You might be better off rolling your own BitArray equivalent using BitVector32s (or plain int/uints).

EDIT2:

Given the OPs objection, I can only assume that expected line IDs are in [int.MinValue, int.MaxValue], and that lines may be switched from false to true. If this is indeed the case, a dense implementation such as what I've outlined above is not practical.

So we're back to Dictionary<,>. There are, however, still a couple of optimizations we can make over Dictionary<int, bool>.

1. One is to use SortedList<,>, instead. If a very large number of inputs may be given, a SortedList<,> will use significantly less memory than a Dictionary<,>.

   For example, in a Dictionary<int, bool>, each entry would use at least 17 bytes of memory. SortedList<int, bool> would use just 5.

   The biggest disadvantage¹ is that adding a new entry to a SortedList<,> is generally significantly slower than adding an entry to a Dictionary<,>, because other entries whose keys compare greater than the added entry must be shifted down to make room for the new entry. I would recommend profiling with expected inputs to compare both memory usage and CPU smokage between SortedList<,> and Dictionary<,>.

2. The other optimization is to combine the BitVector32 approach I mentioned above with a Dictionary<,>/SortedList<,>. This potentially² prevents a lot of wasted space from storing a boolean value in 8 bits, and of storing lots of keys and (if applicable) hash table overhead.

A sample implementation, allowing both of these concepts, follows:

class AndGate{

    struct AndEntry{
        BitVector32 activeLines;
        BitVector32 inputValues;

        public bool Output{get{return activeLines.Data == inputValues.Data;}}

        public void Input(int line, bool value){
            activeLines[1 << line] = true;
            inputValues[1 << line] = value;
        }
    }

    IDictionary<int, AndEntry> entries;

    public AndGate(bool useSortedList){
        if(useSortedList)
            entries = new SortedList<int, AndEntry>();
        else entries = new Dictionary<int, AndEntry>();
    }

    public void Reset(){entries.Clear();}

    public bool Input(int line, bool value){
        AndEntry entry;
        entries.TryGetValue(line / 32, out entry);
        /* no need to handle the not found case, since AndEntry is a struct */

        entry.Input(line & 31, value);
        entries[line / 32] = entry;
    }

    public bool GetOutput(bool reset){
        bool rtn = true;
        foreach(AndEntry value in entries.Values)
            if(!value.Output){
                rtn = false;
                break;
            }

        if(reset)
            Reset();
        return rtn;
    }
}

Keep in mind that the only benefit to these optimizations is to use less memory. This only matters if you expect many inputs. What exactly "many" means is hard to peg down, but call it 20 bytes for each entry (to account for overhead) for the simple Dictionary<int, bool> implementation. So divide the amount of memory you're willing to use by 20. This is what "many" is. But beware of the trade-off between CPU and memory.

_{¹ Before somebody naïvely argues that the real disadvantage to a sorted list over a hash table (which is how Dictionary<,> is implemented) is that lookups are slower in a sorted list versus a hash table, don't. "But lookups are O(log N) in a sorted list, and only O(1) in a hash table", they will say. Whoop-de-freakin-do. For one, hash tables potentially degrade to O(N), whereas a sorted list is always O(log N). For two, even if you have a billion items, 30 integer comparisons (as it would be in this case) just don't cost that much. What with hash table overhead, many people are surprised to find out how often sorted lists outperform hash tables on lookup.}

_{² Again, it depends on your inputs. If lineID & ~31 doesn't frequently overlap (so most AndEntry objects end up storing only one line) then this solution will use more memory, not less. If instead, some other set of 27 bits within lineID tended to overlap, then different masks in Input() would be more effective.}

Answer 4

I may be a bit off base, but this looks like something the Rx Framework would be well suited for. With this, you move to a purely reactive form of programming, where you can declare that your output not be sent until all inputs are received. To the outside consumer, your gate would function as an IObservable<bool>, which is somewhat equivalent to an IEnumerable<bool>. Any observer simply sees an enumeration of outputs, which occur in delay to how the inputs are received.

The main benefit here is that you can chain observables. So, if you want to chain the output of an AND gate to the input of an OR gate, you can do that with a single line of code. To me, Rx is the perfect framework for modeling how an electrical circuit would work, since the results of each observable play a role in the input to the next observable.

To get started, I'd recommend viewing the series of videos on Channel9.