Rozwiążmy następujące zadanie: Mamy dany układ bramek logicznych, np:
Układ logicznyNaszym 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);
}
}
testyCałość: codeplex.com