// Includes Node, Singly Linked List, Stack

type Node = {
     isNone->Boolean
     getOrElse(_:Node)->Node
     ==(_:Node)->Boolean
     asString->String
     elt->Dynamic
     setElt(_:Dynamic)->Void
     next->Node
     setNext(_:Node)->Void
     at(_:Number)->Node
     indexOf(_:Dynamic)->Number
     firstNodeWithProp(_:TestNode)->Node
     firstNodeWithVal(_:Dynamic)->Node}

type TestNode = {
     apply(_:Node)->Boolean}

type Iterator = {
     reset->Void
     hasNext->Boolean
     next->T
     get->T}

type Collection = {
    size->Number
    isEmpty->Boolean
    clear->Void
    contains(_:T)->Boolean
    addFirst(_:T)->Void
    addLast(_:T)->Void
    firstElement->T
    lastElement->T
    removeFirst->T
    removeLast->T
    removeValue(_:T)->Dynamic
    indexOf(_:T)->Number
    at(_:Number)->T
    setValue(_:T)at(_:Number)->T
    add(_:T)at(_:Number)->Void
    removeFromIndex(_:Number)->T
    iterator->Iterator
    asString->String
    forEachDo(_:Block)->Void
    map(_:Block)->Collection}

type SinglyLinkedList = Collection & {}

type Stack = {
    push(_:T)->Void
    pop->T
    peek->T
    size->Number
    clear->Void
    contains(_:T)->Boolean
    isEmpty->Boolean
    iterator->Iterator
    asString->String}

type Set = {
    clear->Void
    isEmpty->Void
    add(_:T)->Void
    removeValue(_:T)->T
    contains(_:T)->Boolean
    containsAll(_:Set)->Boolean
    clone->Set
    addAll(_:Set)->Void
    retainAll(_:Set)->Void
    removeAll(_:Set)->Void
    iterator->Iterator
    size->Number
    asString->String}

def missing:Dynamic is public, readable = object{
    method asString->String{"empty"}
}

// ==================== NODE ========================
// Class supporting singly linked list element. Each element
// contains value and maintains single reference to next node
// in list.

// Constructs EmptyNode
method emptyNode->Node is public{EmptyNode}

// Constructs Node with value v, linked to EmptyNode
method nodeWithValue(v)->Node is public{NodeClass.new(v, EmptyNode)}

// Constructs Node with value v, linked to Node n
method nodeWithValue(v)next(n:Node)->Node is public{NodeClass.new(v, n)}

// Instance of Node with no value, linked to itself. Should
// only have single instance of EmptyNode, which all references 
// point to.
def EmptyNode:Node = object{

    method isNone->Boolean is public{true}

    method getOrElse(default:Node)->Node is public{default}

    method ==(other:Node)->Boolean is public{other.isNone}

    method asString->String is public{""}

    method elt->Dynamic is public{missing}

    method setElt(_:Dynamic)->Void is public{}

    method next->Node is public{self}

    method setNext(_:Node)->Void is public{}

    method at(_:Number)->Node is public{self}

    method indexOf(_:Dynamic)->Number is public{-1}

    method firstNodeWithProp(_:TestNode)->Node is public{self}

    method firstNodeWithVal(_:Dynamic)->Node is public{self}
}

class NodeClass.new(x:Dynamic, nextNode:Node){

      // Data value stored in this node
      var elt:Dynamic is readable := x

      // Reference to next node in list
      var next:Node is readable:= nextNode
      
      // @post @return true iff node is empty
      method isNone->Boolean is public{false}

      // @post @return this node if not empty, otherwise s
      // @param s the node to return if this is empty
      method getOrElse(s:Node)->Node is public{self}

      // @post @return true iff other has same value as this and 
      // links to equivalent node
      // Dangerous! Only call when no chance of infinite loop
      method ==(other:Node)->Boolean is public{ // change when generic types implemented
          if(other.isNone) then {false}
          else{(elt == other.elt) && (next == other.next)} 
      }

      // @post sets value associated with node
      // @param s is the new value to be associated w/ node
      method setElt(s:Dynamic)->Void is public{elt := s}

      // @post sets reference to new next value
      // @param next the new value of next node reference
      method setNext(n:Node)->Void is public{next := n}

      // @post @return the node with index count relative to this node,
      // or EmptyNode if no such node
      // @param count the index of the node sought
      method at(count:Number)->Node is public{
          if(count == 1) then {self}
          else{next.at(count-1)}
      }

      // @post @return first node found for which meth is true, or
      // EmptyNode if no such node
      // @param meth a block that takes a Node and returns Boolean
      method firstNodeWithProp(meth:TestNode)->Node is public{
          var returnN:Node := self
          if(!meth.apply(self)) then {next.firstNodeWithProp(meth)}
          returnN
      }

      // @post @return first node with value val, or EmptyNode
      // if no such node
      // @param value the value sought
      method firstNodeWithVal(value:Dynamic)->Node is public{
          def hasVal:TestNode = {nd-> nd.elt == value}
          firstNodeWithProp(hasVal)}

      // @post @return index of first instance of node with value
      // relative to this node
      // @param value the value of the node whose index is sought
      method indexOf(value:Dynamic)->Number is public{
          var ans:Number := 1
          if(elt == value) then {ans := 1}
          else{
              var preIndex:Number := next.indexOf(value)
              if(preIndex == -1) then {ans := -1}
              else{ans := 1 + preIndex}
          }
          ans}

      // @post @return string representation of node
      method asString->String is public{""}        
}

//================SINGLY LINKED LIST==================

// Constructs an empty list
method newList->SinglyLinkedList is public{LinkedListClass.new}

class LinkedListClass.new{

      // Number of elements in list
      var count:Number is readable:= 0

      // Reference to first element of list
      var head:Node is readable:= EmptyNode

      // @post value is added to beginning of list
      // @param value the value to be added
      method addFirst(value:Dynamic)->Void is public{
          head := nodeWithValue(value)next(head)
          count := count + 1}

      // @post value is added to end of list
      // @param value the value to be added
      method addLast(value:Dynamic)->Void is public{add(value)at(size + 1)}
      
      // @post @return the head of the list
      method firstElement->Dynamic is public{head.elt}

      // @post @return the tail of the list
      method lastElement->Dynamic is public{at(size)}

      // @pre list is not empty
      // @post removes and returns value at head of list
      // @return value actually removed
      method removeFirst->Dynamic is public{
          var temp:Node := head
          head := head.next
          count := count - 1
          return temp.elt}
          
      // @pre list is not empty
      // @post removes and returns value at tail of list
      // @return value actually removed
      method removeLast->Dynamic is public{removeFromIndex(size)}

      // @pre value is not "missing"
      // @post removes first element with matching value
      // @param val the value to be removed
      // @return the value removed, or misssing if no such
      // value in list
      method removeValue(val:Dynamic)->Dynamic is public{
          var index:Number := indexOf(val)
          if(index > 0) then {removeFromIndex(index)}
          else{
              //print "No instance of {val} in list"
              return missing}
      }

      // @post @return number of elements in list
      method size->Number is public{count}

      // @pot @return true iff no elements in list
      method isEmpty->Boolean is public{size == 0}

      // @post removes all values from list
      method clear->Void is public{
          head := EmptyNode
          count := 0}

      // @pre 1 <= i <= size
      // @post @return value at location i
      // @param i the position of value to be retrieved
      method at(i:Number)->Dynamic is public{nodeAt(i).elt}

      // @pre 1 <= i <= size
      // @post @return node at location i
      // @param i the position of node to be retrieved
      method nodeAt(i:Number)->Node is confidential{head.at(i)}

      // @pre 1 <= i <= size
      // @post sets ith entry of list to newValue
      // @param i location of entry to be changed
      // @param newValue the new value
      // @return former value of entry to be changed
      method setValue(newValue:Dynamic)at(i:Number)->Dynamic is public{
          if(head.isNone || head.at(i).isNone) then {return missing}
          else{
              var oldVal:Dynamic := head.at(i).elt
              head.at(i).setElt(newValue)
              oldVal}
      }
      
      // @pre 1 <= i <= size + 1
      // @post inserts value at i
      // @param i the index of the new value
      // @param value the value to be stored
      method add(value:Dynamic)at(i:Number)->Void is public{
          if(i == 1) then{addFirst(value)}
          else{
              var prev:Node := nodeAt(i-1)
              if(!prev.isNone) then{
                  var nNode:Node := NodeClass.new(value, prev.next)
                  count := count + 1
                  prev.setNext(nNode)}
          }
      }

      // @pre 1 <= i <= size
      // @post removes value at location i
      // @param i position of value to be retrieved
      // @return value removed
      method removeFromIndex(i:Number)->Dynamic is public{
          if(i == 1) then{removeFirst}
          else{
              var prev:Node := nodeAt(i - 1)
              var target:Node := prev.next
              if(prev.isNone || target.isNone) then {return missing}
              else{
                  count := count - 1
                  prev.setNext(target.next)
                  target.elt}
          }
      }

      // @pre value is not "missing"
      // @post @return first location of value in list, or -1
      // if value not found
      // @param value the value sought
      method indexOf(value:Dynamic)->Number is public{head.indexOf(value)}

      // @post @return iterator to traverse list from head to tail
      method iterator->Iterator is public{LLIterator.new(head)}

      // @post @return string representation of list
      method asString->String is public{
          var str:String := "["
          var finger:Node := head
          while{!finger.isNone} do{
              str := str ++ finger.elt ++ ", "
              finger := finger.next}
          str ++ "]"}

      // @pre value is not "missing"
      // @post @return true iff value found in list
      // @param value the value sought
      method contains(value:Dynamic)->Boolean is public{indexOf(value) != -1}

      // @post applies closure to each element of list
      // @param closure is a block that takes element of
      // whatever type current list contains
      method forEachDo(closure:Block)->Void is public{
          for(1..size) do {i->
              closure.apply(at(i))}
      }

      // @post @return list containing elements of this list with
      // function mapped to them
      // @param function is a block that takes element of whatever
      // type current list contains
      method map(function:Block)->SinglyLinkedList is public{
          var result:SinglyLinkedList := LinkedListClass.new
          for(1..size) do {i->
             result.addLast(function.apply(at(i)))}
      }
}

class LLIterator.new(t:Node){

    var head:Node is readable := t

    var current:Node is readable := head

    method reset->Void is public{current := head}

    method hasNext->Boolean is public{!current.isNone}

    method next->Dynamic is public{
        var value:Dynamic := current.elt
        current := current.next
        value}

    method get->Dynamic is public{current.elt}
}

//================== STACK =========================

// Constructs empty stack
method newStack->Stack is public{StackClass.new}

class StackClass.new{

      // list that maintains stack data
      var data:SinglyLinkedList is readable := newList

      // @post adds element to top of stack
      // @param item the value to be added
      method push(item:Dynamic)->Void is public{data.addFirst(item)}

      // @pre stack is not empty
      // @post removes top element from stack
      /// @return value removed
      method pop->Dynamic is public{
             if (size > 0) then {data.removeFirst}
             else{ 
                 print "Can't pop from empty stack"
                 missing}
      }

      // @pre stack is not empty
      // @post @return top element of stack
      method peek->Dynamic is public{data.firstElement}
      
      // @post @return number of elements in stack     
      method size->Number is public{data.size}

      // @post removes all elements from stack
      method clear->Void is public{data.clear}

      // @post @return true iff val is element of stack
      // @param val the value sought
      method contains(val:Dynamic)->Boolean is public{data.contains(val)}

      // @post @return true iff no elements in stack
      method isEmpty->Boolean is public{size == 0}

      // @post @return iterator to traverse stack, starting at top
      method iterator->Iterator is public{data.iterator}

      // @post @return string representation of stack
      method asString->String is public{""}
}

//================== SET LIST ======================

// Constructs empty set
method newSet->Set is public{SetList.new}

class SetList.new{
    // Underlying structure to hold elements of set
    var data:SinglyLinkedList is readable := newList

    // @post removes all elements of set
    method clear->Void is public{data.clear}

    // @post @return true iff no elements in set
    method isEmpty->Boolean is public{data.isEmpty}

    // @pre e is not "missing"
    // @post adds e to set
    // @param e the new value to be added
    method add(e:Dynamic)->Void is public{
        if(!data.contains(e)) then{data.addLast(e)}
    }

    // @pre e is not "missing"
    // @post e is removed from set
    // @param e the element to be removed
    // @return value actually removed
    method removeValue(e:Dynamic)->Void is public{data.removeValue(e)}

    // @pre e is not "missing"
    // @post @return true iff e is in set
    // @param e the element sought
    method contains(e:Dynamic)->Boolean is public{data.contains(e)}

    // @post @return true iff this set is subset of other
    // @param other the potential superset
    method containsAll(other:Set)->Boolean is public{
        var myElements:Iterator := data.iterator
        while{myElements.hasNext} do {
            if(!other.contains(myElements.next)) then{return false}
        }
        return true}

    // @post @return a shallow clone of this set
    method clone->Set is public{
        var result:Set := SetList.new
        var myElements:Iterator := iterator
        while{myElements.hasNext} do{
            result.add(myElements.next)}
        result}

    // @post adds all elements of other to this
    // @param other set to be unioned with this
    method addAll(other:Set)->Void is public{
        var yourElements:Iterator := other.iterator
        while{yourElements.hasNext} do{add(yourElements.next)}
    }

    // @post removes items of this that are not in other
    // @param other the set to be intersected with this
    method retainAll(other:Set)->Void is public{
        var temp:Set := SetList.new
        var myElements:Iterator := data.iterator
        while{myElements.hasNext} do{
            var v:Dynamic := myElements.next
            if(other.contains(v)) then{temp.add(v)}
        }
        clear
        addAll(temp)}

    // @post removes members of other from this
    // @param other the set whose values are to be 
    // eliminated from this
    method removeAll(other:Set)->Void is public{
        var yourElements:Iterator := other.iterator
        while{yourElements.hasNext} do{
            removeValue(yourElements.next)}
    }

    // @post @return iterator to traverse elements
    // of set in no particular order
    method iterator->Iterator is public{data.iterator}

    // @post @return number of elements in set
    method size->Number is public{data.size}
    
    // @post @return string representation of set
    method asString->String is public{""}
}