Strona używa cookies (ciasteczek). Dowiedz się więcej o celu ich używania i zmianach ustawień. Korzystając ze strony wyrażasz zgodę na używanie cookies, zgodnie z aktualnymi ustawieniami przeglądarki.    X

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 

programowanie hobby

Komentarze

0 nowych
  #1 28.05.2013 21:58

Mam podobne na układach cyfrowych :D

aeroflyluby   15 #2 28.05.2013 22:49

Piękne OOP. Nic tak nie utrudnia i nie komplikuje projektów jak dobre oop :)
C FOR LIFE