Created
March 20, 2019 16:02
-
-
Save shanecelis/71c4ceb1aa93db7b508fde8f97a489b3 to your computer and use it in GitHub Desktop.
A heterogeneously typed stack that preserves O(1) for Push<T>(T o) and Pop<T>() and maintains order for Push(object o) and Pop().
This file contains 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
/* Original code Copyright (c) 2019 Shane Celis[1] | |
Licensed under the MIT License[2] | |
Original code posted here[3]. | |
This comment generated by code-cite[4]. | |
[1]: https://github.com/shanecelis | |
[2]: https://opensource.org/licenses/MIT | |
[3]: https://github.com/shanecelis/push-forth-dotnet/ | |
[4]: https://github.com/shanecelis/code-cite | |
*/ | |
using System; | |
using System.Linq; | |
using System.Text; | |
using System.Diagnostics; | |
using System.Collections; | |
using System.Collections.Generic; | |
namespace PushForth { | |
/** | |
StackBag is a heterogeneously typed stack that preserves O(1) for Push<T>(T | |
o) and Pop<T>() and maintains order for Push(object o) and Pop(). | |
The StackBag class was designed to work with PushForth. PushForth's state was | |
previously stored in a `System.Stack`. The [push-forth | |
paper](https://www.lri.fr/~hansen/proceedings/2013/GECCO/companion/p1635.pdf) | |
describes an interpreter that traverses the stack to find appropriately typed | |
arguments. Although it makes for an elegant and parsimonious method, I found | |
this to be inefficient and the executions harder to follow. | |
StackBag brings PushForth's implementation closer to the efficiency of | |
[PshSharp's Push3 implementation](https://github.com/shanecelis/PshSharp), | |
which uses separate stacks for each data type; however, there are some | |
important differences. In PshSharp the stacks for various data types must be | |
pre-declared, and there is no ordering retained between separate stacks, so | |
there is only a set of stacks. | |
StackBag is a bag of stacks separated by type that maintains an ordering | |
between the stacks. The types do not need to be pre-declared. One can | |
manipulate each stack by type using `Push<T>(T item)` or `Pop<T>()`. Or one | |
can manipulate it as if it were one heterogenous stack using `Push(object | |
item)` or `Pop()`. And the push and pop operations of both kinds are still | |
O(1). | |
Typed Variables and Typed Values | |
-------------------------------- | |
In some ways the StackBag can be thought of as a big list of unnamed typed | |
variables and typed values. That does not strictly mean the variable types | |
and value types are the same. For instance a `object` variable can hold an | |
`int` type value. | |
``` | |
stack.Push<object>(1); // object a = 1; | |
stack.Push<int>(1); // int b = 1; | |
stack.Push(1); // int c = 1; // The compiler uses Push<int>(). | |
stack.Push(1f, typeof(float)); // float d = 1f; | |
``` | |
Future Work | |
----------- | |
There is no support for handling type hierarchies at the moment. Each type is | |
its own island. However, it seems reasonable to consider adding | |
`PopWithDescent<T>()` where type hierarchies are taken into account, which | |
ought to be maybe O(d) where d is the depth of the hierarchy. | |
*/ | |
public class StackBag : | |
// ICollection, | |
IEnumerable, | |
ICloneable { | |
/* Keep the "untyped" stack in a linked list */ | |
LinkedList<Entry> linkedList = new LinkedList<Entry>(); | |
/* The real trick here: Instead of keeping multiple stacks of just the entries, | |
``` | |
Dictionary<Type, Stack<Entry>> bag; | |
``` | |
we keep a stack of linked list nodes. | |
``` | |
Dictionary<Type, Stack<LinkedListNode<Entry>>> bag; | |
``` | |
That's how we can maintain O(1) on push and pops that reach deep into the | |
"untyped" stack. */ | |
Dictionary<Type, Stack<LinkedListNode<Entry>>> bag | |
= new Dictionary<Type, Stack<LinkedListNode<Entry>>>(); | |
public struct Entry { | |
public object item; | |
public Type type; // We need this type partly | |
} | |
public StackBag() { } | |
/** Pushes each item from enumerable onto the stack */ | |
public StackBag(IEnumerable enumerable) { | |
foreach (var x in enumerable) | |
Push(x); | |
} | |
/** Push first element then second element if reverse is false. Otherwise | |
push last element then second to last element if reverse is true. | |
Most useful for things like Clone: | |
``` | |
public object Clone() => new StackBag(ToArray(), true); | |
``` | |
*/ | |
public StackBag(object[] array, bool reverse = false) { | |
for (int i = 0; i < array.Length; i++) { | |
int j = i; | |
if (reverse) | |
j = array.Length - 1 - i; | |
Push(array[j]); | |
} | |
} | |
// It's a little tricky to find an item in a stack since the stacks aren't | |
// stacks of the entries but of the nodes instead. So count this as a | |
// downside. O(m) where m is all items (not just items of type t). | |
public bool Contains(object item, Type t) => linkedList.Contains(new Entry { item = item, type = t }); | |
public bool Contains<T>(T item) => Contains(item, typeof(T)); | |
public bool Contains(object item) => Contains(item, item != null ? item.GetType() : typeof(object)); | |
/** Push to a "typed" stack. */ | |
public void Push(object item, Type t) { | |
if (! t.IsInstanceOfType(item)) | |
throw new InvalidCastException($"Pushed item {item} is not an instance of type {t}."); | |
Stack<LinkedListNode<Entry>> s; | |
if (! bag.TryGetValue(t, out s)) { | |
s = bag[t] = new Stack<LinkedListNode<Entry>>(); | |
} | |
var entry = new Entry { item = item, type = t }; | |
var node = linkedList.AddFirst(entry); | |
s.Push(node); | |
} | |
/** Push to a "typed" stack. | |
Push an object using the compile-time type information. */ | |
public void Push<T>(T item) => Push(item, typeof(T)); | |
/** Push the item to a "typed" stack using its runtime type. | |
Nulls are typed as objects. | |
This seems to work despite it seeming confusing between `Push<object>(x)` | |
and `Push((object) x)`. The compiler doesn't seem confused. I'll probably | |
regret not renaming it, but going with it for now. | |
*/ | |
public void Push(object item) { | |
Type t = item == null ? typeof(object) : item.GetType(); | |
Push(item, t); | |
} | |
/** Pop from a "typed" stack. */ | |
public object Pop(Type t) { | |
if (bag.TryGetValue(t, out Stack<LinkedListNode<Entry>> s)) { | |
var node = s.Pop(); | |
var entry = node.Value; | |
linkedList.Remove(node); | |
return entry.item; | |
} else { | |
// throw new Exception("What would stack do?"); | |
throw new InvalidOperationException($"No items of type {t} to pop."); | |
} | |
} | |
/** Pop from a "typed" stack. */ | |
public T Pop<T>() => (T) Pop(typeof(T)); | |
// XXX Do I want to expose all these non-generic operations? Especially if | |
// Pop() is different from Pop<object>()? | |
public Entry PopEntry() { | |
var node = linkedList.First; | |
var entry = node.Value; | |
if (bag.TryGetValue(entry.type, out Stack<LinkedListNode<Entry>> s)) { | |
var _ = s.Pop(); | |
// Wow. This murders the test suite. No good. | |
// Debug.Assert(_.Equals(entry), "Entry from priority queue differs from stack."); | |
// entry == _ --should-be--> true | |
} | |
linkedList.RemoveFirst(); | |
return entry; | |
} | |
/** Pop from the "untyped" stack. */ | |
public object Pop() => PopEntry().item; | |
/** Peek from a "typed" stack. */ | |
public object Peek(Type t) { | |
if (bag.TryGetValue(t, out Stack<LinkedListNode<Entry>> s)) { | |
var node = s.Peek(); | |
var entry = node.Value; | |
return entry.item; | |
} else { | |
throw new InvalidOperationException($"No items of type {t} to peek."); | |
} | |
} | |
/** Peek from a "typed" stack. */ | |
public T Peek<T>() => (T) Peek(typeof(T)); | |
public Entry PeekEntry() { | |
var node = linkedList.First; | |
var entry = node.Value; | |
return entry; | |
} | |
/** Peek from the "untyped" stack. */ | |
public object Peek() => PeekEntry().item; | |
/** Clear one type of stack. | |
Performance consideration: This pops items one-by-one and removes O(1) | |
them from the linked list, so it's an O(m) operation. | |
*/ | |
protected void Clear(Type t) { | |
if (bag.TryGetValue(t, out Stack<LinkedListNode<Entry>> s)) { | |
while (s.Count > 0) { | |
var node = s.Pop(); | |
linkedList.Remove(node); | |
} | |
} | |
} | |
/** Clears the stack bag of one type. */ | |
public void Clear<T>() => Clear(typeof(T)); | |
/** Clears the whole stack bag. */ | |
public void Clear() { | |
bag.Clear(); | |
linkedList.Clear(); | |
} | |
/** Get count of typed stack. O(1). */ | |
public int Count(Type t) { | |
if (bag.TryGetValue(t, out Stack<LinkedListNode<Entry>> s)) { | |
return s.Count; | |
} else { | |
return 0; | |
} | |
} | |
/** Get count of typed stack. O(1). */ | |
public int Count<T>() => Count(typeof(T)); | |
/** Get count of all items in all stack. O(1). */ | |
public int Count() => linkedList.Count; | |
public bool Any(Type t) => Count(t) > 0; | |
public bool Any<T>() => Count<T>() > 0; | |
public bool Any() => Count() > 0; | |
/** Return one heterogeneous stack. */ | |
public Stack ToStack() { | |
var count = linkedList.Count; | |
var init = new object[linkedList.Count]; | |
int i = 0; | |
foreach (var entry in linkedList) { | |
init[count - 1 - i] = entry.item; | |
i++; | |
} | |
return new Stack(init); | |
} | |
/** Convert a stack into a StackBag. */ | |
public static StackBag FromStack(Stack s) { | |
var sb = new StackBag(); | |
var a = s.ToArray(); | |
for (int i = 0; i < a.Length; i++) { | |
object x = a[a.Length - 1 - i]; | |
if (x is Stack r) | |
x = FromStack(r); | |
sb.Push(x); | |
} | |
return sb; | |
} | |
/** Pushes each item from enumerable onto the stack */ | |
public static StackBag FromEnumerable<T>(IEnumerable<T> enumerable) { | |
var sb = new StackBag(); | |
foreach (var x in enumerable) | |
sb.Push<T>(x); | |
return sb; | |
} | |
/** Returns the items as if they were popped off in order. */ | |
public IEnumerator GetEnumerator() { | |
foreach (var entry in linkedList) | |
yield return entry.item; | |
} | |
/** Returns a shallow clone. */ | |
public object Clone() => new StackBag(ToArray(), true); | |
/** Returns the items as if they were popped off in order. */ | |
public object[] ToArray() { | |
object[] a = new object[Count()]; | |
var e = GetEnumerator(); | |
for (int i = 0; i < a.Length && e.MoveNext(); i++) { | |
a[i] = e.Current; | |
} | |
return a; | |
} | |
/** Returns a stack formatted like so "[a b c]" where "a" is the top of the | |
stack and "c" is the bottom. */ | |
public override string ToString() { | |
var sb = new StringBuilder(); | |
sb.Append("["); | |
bool first = true; | |
foreach (var item in this) { | |
if (! first) | |
sb.Append(" "); | |
else | |
first = false; | |
sb.Append(item.ToString()); | |
} | |
sb.Append("]"); | |
return sb.ToString(); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment