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().

StackBag.cs

/* 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();
  }
}

}