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}

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

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

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

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

// Constructs Node with value v, linked to Node n
method withValue(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{""}        
}