Skip to content

Instantly share code, notes, and snippets.

@shanecelis
Created March 20, 2019 16:02
Show Gist options
  • Save shanecelis/71c4ceb1aa93db7b508fde8f97a489b3 to your computer and use it in GitHub Desktop.
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().
/* 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