package DataStructures.Lists

import DataStructures.MiscellaneousTypes.Version
import annotation.tailrec
import scala.Predef._
import DataStructures.NodeTypes.TemporalNode

trait SinglyLinkedTemporal[T] extends DataStructures.NodeTypes.TemporalNode {
  val vrsn: Version;

  def right: SinglyLinkedTemporal[T] = super.get(1,vrsn.current).asInstanceOf[SinglyLinkedTemporal[T]]
  def right_=(input: SinglyLinkedTemporal[T]) = super.set(1,input,vrsn++)

  // allows me to do something like class.data
  def data: T = {
    super.get(0,vrsn.current) match {
      case x: T => x
      case _ => throw new Exception("Somehow, an invalid type crept into field 1")
    }
  }

  // allows me to do something like class.data = 5 with 5 being mapped to input.
  def data_=(input: T) = super.set(0,input,vrsn++)

  // changes the version of the list.
  def changeVersion(version: Int) {vrsn.changeVersion(version)}

  // tells you what the latest version of the list is.
  def newestVersion = vrsn.newest

  // tells you if this is the last node in the list.
  def last = right == null

  final def fold[U](z: U)(f: (U, T) => U): U = foldLeft(z)(f)

  //@tailrec forces the recursive function below it to be written in a way where
  // it can be called infinitely without causing a stack overflow. The
  // compiler will complain if this condition is not met.
  // foldLeft applies a function to each element in the list in left to right order.
  // An initial value is supplied (z), and that value as the first parameter to
  // the function, while the second is the current element of the list. Can be used
  // to create one line summation functions and other nice features.
  @tailrec
  final def foldLeft[U](z: U)(f: (U, T) => U): U = {
    if (last) f(z,data) else right.foldLeft(f(z, data))(f)
  }
}

class SinglyLinkedList[T](d: T, t: SinglyLinkedTemporal[T], version: Version = new Version()) extends
 TemporalNode(Array(d,t).asInstanceOf[Array[AnyRef]]) with SinglyLinkedTemporal[T] {

  // Used to keep track of the master version of the list. Each node has a pointer to
  // this object.
  val vrsn = version

  // Inserts a node in front of the current node by creating a copy of the current node
  // after this one and rewriting this node to the value supplied.
  def +:(input: T) {
    right = new SinglyLinkedList[T](data,right,vrsn)
    data = input
  }

  // Helper function for traversing the list to reach the node specified by position.
  // Could use a recursive function to do this more succinctly, but this is a bit
  // faster.
  private def getNode(position: Int):SinglyLinkedTemporal[T] = {
    var i = position
    var ptr:SinglyLinkedTemporal[T] = this

    while(i != 0) {
      ptr = ptr.right
      i-=1
    }

    ptr
  }

  // Returns data from the position specified.
  def apply(position: Int): T = {
    getNode(position).data
  }

  // Lets me do something like List(5) = 6 to change element 5 in a list to the value 6.
  def update(position: Int, input: T) {
    getNode(position).data = input
  }

  // Uses fold left to summate the string values of each element of the list, creating a
  // nicely formatted representation of the linked list.
  override def toString: String = {
    val ret = SinglyLinkedList.name
    ret + "(" + foldLeft("")((a, b) => a + b.toString + ", ").stripSuffix(", ") + ")"
  }
}

object SinglyLinkedList {
  protected val name = "SinglyLinkedList"

  //Used to instatiate the class. Used like "SinglyLinkedList(1,2,3,4,5)" to instantly
    create a linked list of ints with that structure. Calls the constructor below
    to instatiate a class.
  def apply[T](data: T*): SinglyLinkedList[T] = {
    this(data.toList)
  }

  // Another constructor, but this one lets me do "SinglyLinkedList(1 to 15)" instead.
  def apply[T](seq: List[T]): SinglyLinkedList[T] = {
    val version = new Version
    seq.foldRight(null: SinglyLinkedList[T])(new SinglyLinkedList[T](_,_,version))
  }
}