import node

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 & {}

def missing is public, readable = node.missing

// Constructs an empty list
method new->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:= node.empty

      // @post value is added to beginning of list
      // @param value the value to be added
      method addFirst(value:Dynamic)->Void is public{
          head := node.withValue(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 := node.empty
          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 := node.withValue(value)next(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}
}