1  package frost.collections
  2  
  3  ====================================================================================================
  4  An implementation of the stack abstract data type. A stack is a collection of elements which
  5  operates in "LIFO" (last in, first out) order; that is, the element most recently added to the stack
  6  is the first one retrieved.
  7  ====================================================================================================
  8  class Stack<T> : Iterable<T> {
  9      @private
 10      class StackIterator<T> : Iterator<T> {
 11          def stack:Stack<T>
 12  
 13          var index := 0
 14  
 15          init(stack:Stack<T>) {
 16              self.stack := stack
 17          }
 18  
 19          @override
 20          function get_done():Bit {
 21              return index >= stack.count
 22          }
 23  
 24          @override
 25          method next():T {
 26              def result := stack[index]
 27              index += 1
 28              return result
 29          }
 30      }
 31  
 32      @private
 33      def contents := Array<T>()
 34  
 35      ================================================================================================
 36      The number of elements on the stack.
 37      ================================================================================================
 38      property count:Int
 39  
 40      ================================================================================================
 41      Pushes a new element onto the stack.
 42      ================================================================================================
 43      method push(v:T) {
 44          contents.add(v)
 45      }
 46  
 47      ================================================================================================
 48      Pops the top value from the stack and returns it.
 49      ================================================================================================
 50      @pre(count > 0)
 51      method pop():T {
 52          assert contents.count > 0
 53          def result := contents[contents.count - 1]
 54          contents.removeIndex(contents.count - 1)
 55          return result
 56      }
 57  
 58      ================================================================================================
 59      Inserts a new element at the specified depth. A depth of `0` is equivalent to [push].
 60      ================================================================================================
 61      method insert(depth:Int, value:T) {
 62          contents.insert(contents.count - 1 - depth, value)
 63      }
 64  
 65      method removeIndex(depth:Int):T {
 66          return contents.removeIndex(contents.count - 1 - depth)
 67      }
 68  
 69      ================================================================================================
 70      Returns the value at the given depth in the stack. The top element (most recently pushed) is
 71      element 0, and the bottom element (earliest pushed) is element `count - 1`.
 72      ================================================================================================
 73      @pre(depth >= 0 & depth < count)< count)
 74      function [](depth:Int):T {
 75          assert contents.count > depth
 76          return contents[contents.count - 1 - depth]
 77      }
 78  
 79      ================================================================================================
 80      Removes all elements from the stack.
 81      ================================================================================================
 82      method clear() {
 83          contents.clear()
 84      }
 85  
 86      ================================================================================================
 87      Returns an iterator which returns elements from the stack, starting from the top and working
 88      down to the bottom. Iterating over the stack does not modify it.
 89      ================================================================================================
 90      @override
 91      function get_iterator():Iterator<T> {
 92          return StackIterator<T>(self)
 93      }
 94  
 95      function get_count():Int {
 96          return contents.count
 97      }
 98  
 99      @override
100      function get_toString():String {
101          return contents.toString
102      }
103  }