Skip to content

Instantly share code, notes, and snippets.

@simonwittber
Created August 16, 2018 12:09
Show Gist options
  • Select an option

  • Save simonwittber/e66ebee2de254d26fc5d003423d6d6f7 to your computer and use it in GitHub Desktop.

Select an option

Save simonwittber/e66ebee2de254d26fc5d003423d6d6f7 to your computer and use it in GitHub Desktop.
Pooled Discrete Event Simulator in C#
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);
}
}
}
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;
}
}
}
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();
}
}
}
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