Created
August 16, 2018 12:09
-
-
Save simonwittber/e66ebee2de254d26fc5d003423d6d6f7 to your computer and use it in GitHub Desktop.
Pooled Discrete Event Simulator in C#
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using System; | |
| using System.Collections.Generic; | |
| namespace Simulator | |
| { | |
| public class HeapQueue<T> where T : IComparable<T> | |
| { | |
| List<T> items; | |
| public int Count { get { return items.Count; } } | |
| public bool IsEmpty { get { return items.Count == 0; } } | |
| public T First { get { return items[0]; } } | |
| public void Clear() => items.Clear(); | |
| public bool Contains(T item) => items.Contains(item); | |
| public void Remove(T item) => items.Remove(item); | |
| public T Peek() => items[0]; | |
| public HeapQueue() | |
| { | |
| items = new List<T>(); | |
| } | |
| public void Push(T item) | |
| { | |
| //add item to end of tree to extend the list | |
| items.Add(item); | |
| //find correct position for new item. | |
| SiftDown(0, items.Count - 1); | |
| } | |
| public T Pop() | |
| { | |
| //if there are more than 1 items, returned item will be first in tree. | |
| //then, add last item to front of tree, shrink the list | |
| //and find correct index in tree for first item. | |
| T item; | |
| var last = items[items.Count - 1]; | |
| items.RemoveAt(items.Count - 1); | |
| if (items.Count > 0) | |
| { | |
| item = items[0]; | |
| items[0] = last; | |
| SiftUp(); | |
| } | |
| else | |
| { | |
| item = last; | |
| } | |
| return item; | |
| } | |
| int Compare(T A, T B) => A.CompareTo(B); | |
| void SiftDown(int startpos, int pos) | |
| { | |
| //preserve the newly added item. | |
| var newitem = items[pos]; | |
| while (pos > startpos) | |
| { | |
| //find parent index in binary tree | |
| var parentpos = (pos - 1) >> 1; | |
| var parent = items[parentpos]; | |
| //if new item precedes or equal to parent, pos is new item position. | |
| if (Compare(parent, newitem) <= 0) | |
| break; | |
| //else move parent into pos, then repeat for grand parent. | |
| items[pos] = parent; | |
| pos = parentpos; | |
| } | |
| items[pos] = newitem; | |
| } | |
| void SiftUp() | |
| { | |
| var endpos = items.Count; | |
| var startpos = 0; | |
| //preserve the inserted item | |
| var newitem = items[0]; | |
| var childpos = 1; | |
| var pos = 0; | |
| //find child position to insert into binary tree | |
| while (childpos < endpos) | |
| { | |
| //get right branch | |
| var rightpos = childpos + 1; | |
| //if right branch should precede left branch, move right branch up the tree | |
| if (rightpos < endpos && Compare(items[rightpos], items[childpos]) <= 0) | |
| childpos = rightpos; | |
| //move child up the tree | |
| items[pos] = items[childpos]; | |
| pos = childpos; | |
| //move down the tree and repeat. | |
| childpos = 2 * pos + 1; | |
| } | |
| //the child position for the new item. | |
| items[pos] = newitem; | |
| SiftDown(startpos, pos); | |
| } | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using System; | |
| using System.Collections.Generic; | |
| namespace Simulator | |
| { | |
| public static partial class Simulation | |
| { | |
| static HeapQueue<IEvent> eventQueue = new HeapQueue<IEvent>(); | |
| static int currentTick = -1; | |
| public static void Clear() | |
| { | |
| currentTick = -1; | |
| eventQueue.Clear(); | |
| } | |
| static public Event<T> Schedule<T>(int tick) where T : Event<T>, new() | |
| { | |
| var ev = Event<T>.TakeFromPool(); | |
| ev.Tick = currentTick + tick; | |
| eventQueue.Push(ev); | |
| return ev; | |
| } | |
| static public T Get<T>() where T : class, new() | |
| { | |
| return InstanceRegister<T>.instance; | |
| } | |
| static public int Tick(int maxEvents = 0) | |
| { | |
| currentTick++; | |
| var executedEventCount = 0; | |
| while (eventQueue.Count > 0 && eventQueue.Peek().Tick <= currentTick) | |
| { | |
| var ev = eventQueue.Pop(); | |
| ev.Execute(); | |
| var d = ev as IDisposable; | |
| if (d != null) d.Dispose(); | |
| ev.ReturnToPool(); | |
| executedEventCount++; | |
| if (executedEventCount > maxEvents) | |
| break; | |
| } | |
| return eventQueue.Count; | |
| } | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using System; | |
| using System.Collections.Generic; | |
| namespace Simulator | |
| { | |
| public static partial class Simulation | |
| { | |
| public interface IEvent : System.IComparable<IEvent> | |
| { | |
| int Tick { get; } | |
| void Execute(); | |
| void ReturnToPool(); | |
| } | |
| public abstract class Event<T> : IEvent where T : Event<T>, new() | |
| { | |
| public int Tick { get; internal set; } | |
| static Stack<Event<T>> stack; | |
| static Event() | |
| { | |
| stack = new Stack<Event<T>>(8); | |
| stack.Push(new T()); | |
| } | |
| public static int PoolCount { get { return stack.Count; } } | |
| public static void ClearPool() => stack.Clear(); | |
| public static Event<T> TakeFromPool() => stack.Count > 0 ? stack.Pop() : new T(); | |
| public void ReturnToPool() => stack.Push(this); | |
| public int CompareTo(IEvent other) | |
| { | |
| return Tick.CompareTo(other.Tick); | |
| } | |
| public abstract void Execute(); | |
| } | |
| } | |
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| namespace Simulator | |
| { | |
| public static partial class Simulation | |
| { | |
| static class InstanceRegister<T> where T : class, new() | |
| { | |
| public static readonly T instance = new T(); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment