C# ciąg dalszy - układ logiczny i trochę obiektowości

Rozwiążmy następujące zadanie: Mamy dany układ bramek logicznych, np:

Naszym zadaniem jest obliczenie wartości na wyjściu (czyli stan przewodu P8) oraz czas obliczania - bo świat nie jest idealny i bramka logiczna potrzebuje "trochę" czasu, żeby "wypluć" wartość na wyjście. Przed przystąpieniem do kodzenia, założenia:

• Przygotujemy bramki OR (opóźnienie 10j) oraz AND (5j)
• Przygotujemy fabrykę, która będzie nam tworzyła elementy układu
• Stworzymy osobną klasę służącą do symulacji (przypisujemy jej przewody wejściowe, wyjściowe i przed każdą symulacją będziemy podawać stan przewodów na "wejściu")
• Elementy stworzone w rożnych fabrykach nie powinny móc tworzyć sieci
• Nie obsługujemy układów z cyklami

Workflow będzie wyglądał mniej-więcej tak: użytkownik tworzy przewody oraz bramki za pomocą fabryki. Powinien do bramki dodać przewody wejściowe oraz wyjściowy. W przewodzie powinien ustawić bramki które są "na końcu" przewodu (więc może być jednocześnie rozgałęziaczem). Symulacja będzie polegała na ustawieniu stanów na przewodach wejściowych całego układu. Te z kolei dodadzą bramki na swoich wyjściach do kolejki z odpowiednimi priorytetami. Priorytetem będzie moment, w którym bramka już będzie znała swoja wartość na wyjściu (zaczynami od momentu 0). Wtedy wyjmiemy je z kolejki i ustawimy ich przewody wyjściowe na odpowiednie stany. Te z kolei znów dodadzą do kolejki swoje bramki na wyjściu i tak, dopóki kolejka nie będzie pusta.

Stwórzmy projekt (Portable Class Library) nazywający się "LogicSystem". Niestety ten typ projektu nie posiada kilku dobrodziejstw (jak np. SortedDictionary) a my będziemy potrzebować kolejkę priorytetową. W takim układzie, musimy ją sami zaimplementować. W tym celu użyję kopca typu MIN reprezentowany przez tablicę (w tym przypadku dokładnie listę) (plik stworzony w katalogu Helpers):

namespace LogicSystem.Helpers
{
    using System;
    using System.Collections.Generic;
    
    public class MinHeap<TK, TV> where TK : IComparable<TK>
    {

        private readonly List<KeyValuePair<TK, TV>> heap;

        public MinHeap()
        {
            this.heap = new List<KeyValuePair<TK, TV>>();
        }

        public void Insert(TK key, TV value)
        {
            this.heap.Add(new KeyValuePair<TK, TV>(key, value));
            this.CascadeUp(this.heap.Count - 1);
        }

        public void Insert(IEnumerable<KeyValuePair<TK, TV>> items)
        {
            foreach (var item in items)
            {
                this.Insert(item.Key, item.Value);
            }
        }

        public KeyValuePair<TK, TV> Remove()
        {
            var node = this.heap[0];
            this.heap[0] = this.heap[this.heap.Count - 1];
            this.heap.RemoveAt(this.heap.Count - 1);

            if (this.heap.Count > 0)
            {
                this.CascadeDown(0);
            }

            return node;
        }

        public KeyValuePair<TK, TV> Top()
        {
            return this.heap[0];
        }

        public bool IsEmpty()
        {
            return this.heap.Count == 0;
        }

        internal void Clear()
        {
            this.heap.Clear();
        }

        protected void CascadeUp(int index)
        {
            var node = this.heap[index];

            var parent = (index - 1) / 2;
            while (index > 0 && this.heap[parent].Key.CompareTo(
                                    this.heap[index].Key) > 0)
            {
                this.heap[index] = this.heap[parent];
                index = parent;
                parent = (parent - 1) / 2;
            }

            this.heap[index] = node;
        }

        protected void CascadeDown(int index)
        {
            var node = this.heap[0];

            while (index < this.heap.Count / 2)
            {
                var leftChild = (2 * index) + 1;
                var rightChild = leftChild + 1;

                var smallerChild = rightChild < this.heap.Count &&
                                   this.heap[leftChild].Key.CompareTo(this.heap[rightChild].Key) > 0 ?
                                       rightChild : leftChild;

                if (node.Key.CompareTo(this.heap[smallerChild].Key) < 0)
                {
                    break;
                }

                this.heap[index] = this.heap[smallerChild];
                index = smallerChild;
            }

            this.heap[index] = node;
        }
    }
}

Następnie możemy przygotować kilka wyjątków, które się przydadzą:

Wyjątek rzucany, kiedy do symulacji podamy różną ilość stanów przewodów, niż mamy zdefiniowane (np. cały układ ma 3 przewody wejściowe, a my do symulacji podamy true, true - czyli dwóch)

namespace LogicSystem.Exceptions
{
    using System;

    public class ArgumentsQuantityDismatchException : Exception
    {
        public ArgumentsQuantityDismatchException()
            : base("Arguments quantity differs from input wires count.")
        {
        }
    }
}

Wyjątek rzucany, kiedy spróbujemy skompletować w sieć elementy, którezostały stworzone w różnych fabrykach:

public class LogicElementsFactoryDismatchException : Exception
{
    public LogicElementsFactoryDismatchException()
        : base("Cannot connect logic elements that was produced in different factory")
    {
    }
}

Teraz interfejsy:

ISimulatingEnvironment będzie definiował nam interfejs środowiska symulacyjnego. Umożliwi dodanie przewodom bramek do kolejki, przeprowadzenie symulacji oraz będzie przechowywać całkowity czas (całkowity czas potrzebny na wyliczenie układu).

public interface ISimulatingEnvironment<TK, TV> where TK : IComparable<TK>
{
    int TotalTime { get; set; }

    void Reset();

    void PushIntoHeap(TK key, TV value);

    void PushIntoHeap(IEnumerable<KeyValuePair<TK, TV>> items);

    KeyValuePair<TK, TV> Top();

    KeyValuePair<TK, TV> PopFromHeap();

    bool IsEmpty();
}

Przygotujmy narazie stub dla przewodu nazywający się Wire:

public class Wire
{
    public bool State { get; set; }
}

Teraz przyszedł czas na klasę bazową dla bramek:

public abstract class LogicGate
{
    internal LogicGate()
    {
        this.InputWires = new List<Wire>();
    }

    public abstract int Latency { get; }

    public Wire OutputWire { get; set; }

    internal ISimulatingEnvironment<int, LogicGate> SimulatingEnvironment { get; set; }

    internal List<Wire> InputWires { get; set; }

    public abstract bool ComputeOutput();

    public void Refresh()
    {
        this.OutputWire.State = this.ComputeOutput();
    }

    public void AddInputWires(params Wire[] wires)
    {
        this.InputWires.AddRange(wires);
    }

    public void AddInputWires(IEnumerable<Wire> wires)
    {
        this.AddInputWires(wires.ToArray());
    }
}

Pole SimulatingEnvironment będzie służyło do rozpoznawania, czy element został wyprodukowany w odpowiedniej fabryce (w klasie Wire znajdzie już szersze zastosowanie) - dlatego też jest internal - użytkownik nie musi mieć dostępu do niego.. Klasa nie robi nic ciekawego po za Refreshem, która ustawia na wyjście wyliczoną wartość. Wyliczenie oczywiście jest metodą abstrakcyjną (jak i opóźnienie potrzebne na wyliczenie), zależy bowiem od rodzaju bramki. A propo rodzajów:

public class GateAnd : LogicGate
{
    internal GateAnd()
    {
    }

    public override int Latency
    {
        get { return 5; }
    }

    public override bool ComputeOutput()
    {
        return this.InputWires.All(wire => wire.State);
    }
}

public class GateOr : LogicGate
{
    internal GateOr()
    {
    }

    public override int Latency
    {
        get { return 10; }
    }

    public override bool ComputeOutput()
    {
        return this.InputWires.Any(wire => wire.State);
    }
}

Pora na uzupełnienie klasy Wire:

public class Wire
{
    private List<LogicGate> outputGates;

    private bool state;

    internal Wire()
    {
    }

    public bool State 
    {
        get
        {
            return this.state;
        }

        set
        {
            this.state = value;

            foreach (var gate in this.Gates)
            {
                var totalTime = this.SimulatingEnvironment.TotalTime;
                this.SimulatingEnvironment.PushIntoHeap(totalTime + gate.Latency, gate);
            }
        }
    }

    internal ISimulatingEnvironment<int, LogicGate> SimulatingEnvironment { get; set; }

    private List<LogicGate> Gates
    {
        get
        {
            return this.outputGates ?? (this.outputGates = 
                                                Enumerable.Empty<LogicGate>().ToList());
        }
    }

    public void AddOutputGates(params LogicGate[] gates)
    {
        this.Gates.AddRange(gates);
    }

    public void AddOutputGates(IEnumerable<LogicGate> gates)
    {
        this.AddOutputGates(gates.ToArray());
    }
}

Najwięcej się dzieje w State'cie - skoro nam się zmienił stan, przydałoby się wrzucić bramki do kolejki, gdzie znajdują się bramki "do wyliczenia" - z odpowiednim oczywiście priorytetem.

Przyszedł czas na implementację "środowiska", które jest de facto opakowaniem naszego kopca:

internal class SimulatingEnvironment : ISimulatingEnvironment<int, LogicGate>
{
    internal SimulatingEnvironment()
    {
        this.Heap = new MinHeap<int, LogicGate>();
    }

    public int TotalTime { get; set; }

    private MinHeap<int, LogicGate> Heap { get; set; }

    public void Reset()
    {
        this.TotalTime = 0;
        this.Heap.Clear();
    }

    public void PushIntoHeap(int key, LogicGate value)
    {
        this.Heap.Insert(key, value); 
    }

    public void PushIntoHeap(IEnumerable<KeyValuePair<int, LogicGate>> items)
    {
        this.Heap.Insert(items);
    }

    public KeyValuePair<int, LogicGate> Top()
    {
        return this.Heap.Top();
    }

    public KeyValuePair<int, LogicGate> PopFromHeap()
    {
        return this.Heap.Remove();
    }

    public bool IsEmpty()
    {
        return this.Heap.IsEmpty();
    }
}

I teraz gwiazda programu: klasa, która przeprowadzi symulację:

public class LogicSystemSimulator
{
    public LogicSystemSimulator()
    {
        this.InputWires = Enumerable.Empty<Wire>().ToList();
    }

    public Wire OutputWire { get; set; }

    internal ISimulatingEnvironment<int, LogicGate> SimulatingEnvironment { get; set; }

    protected List<Wire> InputWires { get; set; }

    public void AddInputWires(params Wire[] wires)
    {
        if (wires.Any(wire => !ReferenceEquals(
                                wire.SimulatingEnvironment,
                                this.SimulatingEnvironment)))
        {
            throw new LogicElementsFactoryDismatchException();
        }

        this.InputWires.AddRange(wires);
    }

    public void AddInputWires(IEnumerable<Wire> wires)
    {
        this.AddInputWires(wires.ToArray());
    }

    public int Simulate(params bool[] inputStates)
    {
        if (inputStates.Count() != this.InputWires.Count())
        {
            throw new ArgumentsQuantityDismatchException();
        }

        this.CheckOriginFactory(this.InputWires);

        this.SimulatingEnvironment.Reset();

        for (var j = 0; j < this.InputWires.Count; j++)
        {
            this.InputWires[j].State = inputStates[j];
        }

        while (!this.SimulatingEnvironment.IsEmpty())
        {
            var gates = this.GetLowestPriority();
            var logicGates = gates as IList<LogicGate> ?? gates.ToList();

            this.CheckOriginFactory(logicGates);

            this.SimulatingEnvironment.TotalTime += logicGates.ElementAt(0).Latency;

            foreach (var gate in logicGates)
            {
                gate.Refresh();
            }
        }

        return this.SimulatingEnvironment.TotalTime;
    }

    public int Simulate(IEnumerable<bool> inputStates)
    {
        return this.Simulate(inputStates.ToArray());
    }

    private IEnumerable<LogicGate> GetLowestPriority()
    {
        var topPair = this.SimulatingEnvironment.PopFromHeap();

        var output = new List<LogicGate> { topPair.Value };

        while (!this.SimulatingEnvironment.IsEmpty() &&
                    this.SimulatingEnvironment.Top().Key == topPair.Key)
        {
            output.Add(this.SimulatingEnvironment.PopFromHeap().Value);
        }

        return output;
    }

    private void CheckOriginFactory(IEnumerable<Wire> wires)
    {
        if (wires.Any(wire => !ReferenceEquals(wire.SimulatingEnvironment, this.SimulatingEnvironment)))
        {
            throw new LogicElementsFactoryDismatchException();
        }
    }

    private void CheckOriginFactory(IEnumerable<LogicGate> gates)
    {
        var logicGates = gates as IList<LogicGate> ?? gates.ToList();
        if (logicGates.Any(gate => !ReferenceEquals(gate.SimulatingEnvironment, this.SimulatingEnvironment)))
        {
            throw new LogicElementsFactoryDismatchException();
        }

        foreach (var logicGate in logicGates)
        {
            this.CheckOriginFactory(logicGate.InputWires);
        }
    }

}

Pozostała jeszcze tylko fabryka "produkująca" elementy układu:

public class LogicElementsFactory
{
    private readonly SimulatingEnvironment simulatingEnvironment;

    public LogicElementsFactory()
    {
        this.simulatingEnvironment = new SimulatingEnvironment();
    }

    public LogicSystemSimulator CreateLogicSystemSimulator(Wire outputWire, IEnumerable<Wire> inputWires)
    {
        return this.CreateLogicSystemSimulator(outputWire, inputWires.ToArray());
    }

    public LogicSystemSimulator CreateLogicSystemSimulator(Wire outputWire, params Wire[] inputWires)
    {
        var lss = this.CreateLogicSystemSimulator();
        lss.AddInputWires(inputWires);
        lss.OutputWire = outputWire;

        return lss;
    }

    public LogicSystemSimulator CreateLogicSystemSimulator()
    {
        return new LogicSystemSimulator { SimulatingEnvironment = this.simulatingEnvironment };
    }

    public Wire CreateWire()
    {
        return new Wire { SimulatingEnvironment = this.simulatingEnvironment };
    }

    public LogicGate CreateGateAnd(Wire outputWire, IEnumerable<Wire> inputWires)
    {
        return this.CreateGateAnd(outputWire, inputWires.ToArray());
    }

    public LogicGate CreateGateAnd(Wire outputWire, params Wire[] inputWires)
    {
        var gate = this.CreateGateAnd();
        gate.AddInputWires(inputWires);
        gate.OutputWire = outputWire;

        return gate;
    }

    public LogicGate CreateGateAnd()
    {
        return new GateAnd { SimulatingEnvironment = this.simulatingEnvironment };
    }

    public LogicGate CreateGateOr(Wire outputWire, IEnumerable<Wire> inputWires)
    {
        return this.CreateGateOr(outputWire, inputWires.ToArray());
    }

    public LogicGate CreateGateOr(Wire outputWire, params Wire[] inputWires)
    {
        var gate = this.CreateGateOr();
        gate.AddInputWires(inputWires);
        gate.OutputWire = outputWire;

        return gate;
    }

    public LogicGate CreateGateOr()
    {
        return new GateOr { SimulatingEnvironment = this.simulatingEnvironment };
    }
}

oraz kilka testów:

[TestClass]
public class CrossFactoryTest
{
    [TestMethod]
    [ExpectedException(typeof(LogicElementsFactoryDismatchException))]
    public void AddingElementsFromDifferentFactories()
    {
        var factory1 = new LogicElementsFactory();
        var factory2 = new LogicElementsFactory();

        var gate = factory1.CreateGateAnd();
        var wire = factory2.CreateWire();
        var wireOut = factory1.CreateWire();

        gate.AddInputWires(wire);
        gate.AddInputWires(wireOut);
        wire.AddOutputGates(gate);

        factory1.CreateLogicSystemSimulator(wireOut, wire).Simulate(true);
    }
}

[TestClass]
public class SimpleLogicSystemTest
{
    public LogicSystemSimulator SystemSimulator { get; set; }

    [TestInitialize]
    public void Initialize()
    {
        var factory = new LogicElementsFactory();

        var p1 = factory.CreateWire();
        var p2 = factory.CreateWire();
        var p3 = factory.CreateWire();

        var andGate = factory.CreateGateAnd(p3, p1, p2);

        p1.AddOutputGates(andGate);
        p2.AddOutputGates(andGate);

        this.SystemSimulator = factory.CreateLogicSystemSimulator(p3, p1, p2);
    }

    [TestMethod]
    public void SimulatingTime()
    {
        Assert.AreEqual(5, this.SystemSimulator.Simulate(false, false));
    }

    [TestMethod]
    public void CheckGateReturnsTrue()
    {
        this.SystemSimulator.Simulate(true, true);
        Assert.AreEqual(true, this.SystemSimulator.OutputWire.State);
    }
    
    [TestMethod]
    public void CheckGateReturnsFalse()
    {
        this.SystemSimulator.Simulate(true, false);
        Assert.AreEqual(false, this.SystemSimulator.OutputWire.State);
    }
}

wraz z układem z obrazka na początku:

[TestClass]
public class ThreeAndOneOrGateTest
{
    public LogicSystemSimulator SystemSimulator { get; set; }

    [TestInitialize]
    public void Initialize()
    {
        var factory = new LogicElementsFactory();

        var wires = new Wire[9];
        for (var j = 0; j < 9; j++)
        {
            wires[j] = factory.CreateWire();
        }

        var and1 = factory.CreateGateAnd(wires[5], wires[0], wires[1]);
        var or1 = factory.CreateGateOr(wires[6], wires[2], wires[3]);
        var and2 = factory.CreateGateAnd(wires[7], wires[6], wires[4]);
        var and3 = factory.CreateGateAnd(wires[8], wires[5], wires[7]);

        wires[0].AddOutputGates(and1);
        wires[1].AddOutputGates(and1);

        wires[2].AddOutputGates(or1);
        wires[3].AddOutputGates(or1);

        wires[4].AddOutputGates(and2);
        wires[6].AddOutputGates(and2);

        wires[5].AddOutputGates(and3);
        wires[7].AddOutputGates(and3);

        this.SystemSimulator = factory.CreateLogicSystemSimulator(wires[8], wires.Take(5));
    }

    [TestMethod]
    public void SimulatingTimeTest()
    {
        Assert.AreEqual(25, this.SystemSimulator.Simulate(Enumerable.Repeat(false, 5)));
    }

    [TestMethod]
    public void OutputTrueTest()
    {
        this.SystemSimulator.Simulate(true, true, false, true, true);
        Assert.AreEqual(true, this.SystemSimulator.OutputWire.State);
    }
}

Całość: codeplex.com