/*
   Copyright 2010 Aaron J. Radke

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/
package cc.drx
import cc.drx._

// import scala.annotation.unchecked
// import scala.language.higherKinds

/**Generic container of a list of types
 * for now this can be a tree which has children a root that only has children*/
trait Forest[+T] extends Any{  //+ covariance is nice to get inferred types
  //necessary
  def get(i:Int):Option[T] //get the i'th element

  //default implementation can be overridden by a more efficient version
  def trees:Iterable[T] = {
    @tailrec def next(i:Int, ts:List[T]):List[T] = {
      get(i) match {
        case Some(t) => next(i+1, t :: ts)
        case _ => ts
      }
    }
    next(0,Nil).reverse //could be optimized better to not need a reverse
  }
}
object Forest{
  def apply[A](trees:A*):Forest[A] = new VectorForest(trees.toVector)
  def apply[A](trees:Iterable[A]):Forest[A] = new VectorForest(trees.toVector)
  def empty[A]:Forest[A] = new EmptyForest[A]
  class EmptyForest[A] extends Forest[A]{
    def get(i:Int):Option[A] = None
    override def toString = "EmptyForest"
  }

  implicit class VectorForest[+A](override val trees:Vector[A]) extends AnyVal with Forest[A]{
    //!!!! this is a crazy problem that enters an infinite loop when looking for the implementation of get recursively
    //def get(i:Int):Option[A] = {println(s"get $i from VectoryForest"); trees.get(i)}
    //override def get(i:Int):Option[A] = {println(s"get $i from VectoryForest"); trees.get(i)}
    //def get(i:Int):Option[A] = {println(s"get $i from VectoryForest"); trees.get(i)}
    //@native def get(i:Int):Option[A]// = {println(s"get $i from VectoryForest"); trees.get(i)}
    def get(i:Int):Option[A] = if(i < trees.size) Some(trees(i)) else None // = {println(s"get $i from VectoryForest"); trees.get(i)}
    override def toString = "Forest("+ trees.mkString(", ") +")"
  }

  /*
  implicit class ArrayForest[A](val trees:Array[A]) extends AnyVal with Forest[A]{
    def get(i:Int):Option[A] = trees.get(i)
    override def toString = "Forest("+ trees.mkString(", ") +")"
  }
  */
}

/**homogeneous value type tree with index optimized children */
trait Tree[+A,+B <: Tree[A,B]] extends Any with Forest[B]{ //this: B =>  //this this `self-type` to ensure that subtypes are type B
  //necessary
  def value:A

  //optimize-able
  def isLeaf:Boolean = get(0) == None

  //TODO make stack safe tree traversal
  private def breadthFirstRec:Iterable[A] =
    trees.map{_.value} ++ trees.flatMap{_.breadthFirstRec}
  def breadthFirst:Iterable[A] =
    Iterable(value) ++ breadthFirstRec

  def depthFirst:Iterable[A] =
    Iterable(value) ++ trees.flatMap{_.depthFirst}

  //TODO maybe make use of a TreeIterator[A]
  // class DepthIterator extends Iterator[A]{
  //   def next:A = ???
  //   def hasNext:Boolean = ???
  // }
}


//--simple BTree
sealed trait BTree[+A] extends Any with Tree[A,BTree[A]]
object BTree{
  /**make a leaf (BTree)*/
  def apply[A](value:A) = Leaf(value)
  /**make a node (BTree)*/
  def apply[A](value:A, left:BTree[A], right:BTree[A]) = Node(value, left, right)

  case class Node[+A](value:A, left:BTree[A],right:BTree[A]) extends BTree[A]{
    def get(i:Int):Option[BTree[A]] = if(i==0) Some(left) else if(i==1) Some(right) else None
  }
  case class Leaf[+A](value:A) extends AnyVal with BTree[A]{
    def get(i:Int):Option[BTree[A]] = None
    override def isLeaf:Boolean = true
  }
}

//--MTree or Multiway tree or Rose Tree
sealed trait MTree[+A] extends Any with Tree[A,MTree[A]]
object MTree{
  /**make a leaf (MTree)*/
  def apply[A](value:A):Leaf[A] = new Leaf(value)
  /**make a node (MTree)*/
  def apply[A](value:A, trees:Forest[MTree[A]]):Node[A] = new Node(value, trees)

  //def leaves[A](values:A*):Forest[MTree[A]] = Forest(values map {v => new Leaf(v)})
  // def leaves[A](values:A*):Forest[MTree[A]] = Forest(values map {v => Leaf(v)})
  // def leaves[A](values:A*):Forest[MTree[A]] = Forest(values map mkLeaf)
  // private def mkLeaf[A](v:A) = new Leaf(v)
  // def leaves[A](values:A*):Forest[Leaf[A]] = Forest(values map mkLeaf)

  /**group elements into levels, assuming elems are sorted by depth first order*/
  def nest[A](elems:Iterable[A])(isChild:(A,A)=>Boolean):Forest[MTree[A]] = {
    def nestForest(elems:Iterable[A]):Forest[MTree[A]] =
      Forest( nestInner(elems) )
    def nestInner(elems:Iterable[A]):List[MTree[A]] = {
      if(elems.isEmpty) Nil
      else {
         val l = elems.head
         val ls = elems.tail
         val (children,peers) = ls span {c => isChild(l,c)}
         val node = new Node(l, nestForest(children))
         if(peers.isEmpty) List(node)
         else node :: nestInner(peers)
      }
    }
    nestForest(elems)
  }
  /**
   * Form a linked forest, given a function for determining child links.
   * largely followed from https://github.com/lightbend/paradox/blob/master/core/src/main/scala/com/lightbend/paradox/tree/Tree.scala
   */
  def link[A](pairs:Iterable[(A,A)]): Forest[MTree[A]] = {
    import scala.collection.mutable //mutable code is made referenctially transparent with the final toVector
    val links = mutable.Map.empty[A, Set[A]].withDefaultValue(Set.empty)
    for((a,b) <- pairs) {
      links(a) = links(a) + b
      links(b) = links(b)
    }
    link(links.keys, links.apply _)
  }
  def link[A](values: Iterable[A], links: A => Iterable[A]): Forest[MTree[A]] = {
    import scala.collection.mutable //mutable code is made referenctially transparent with the final toVector
    val seen = mutable.HashSet.empty[A]
    val completed = mutable.HashSet.empty[A]
    val roots = mutable.Map.empty[A, MTree[A]]
    def visit(value: A): Unit = {
      if (!seen(value)) {
        // println(s"$value: ${links(value)}")
        seen(value) = true;
        val linked = links(value).toVector
        linked foreach visit
        // println(s"rootsBefore:$roots")
        val children = linked flatMap roots.remove
        roots += value -> MTree(value, children)
        // println(s"rootsAfter:$roots")
        completed(value) = true
      } else if (!completed(value)) {
        throw new RuntimeException("Cycle found at: " + value)
      }
    }
    values foreach visit //WARNING roots is changed here as a side-effect in mutable code
    Forest(roots.values)
    // new Forest.VectorForest(roots.values.toVector) //implicit conversion to a VectorForest
  }

  case class Node[+A](val value:A, forest:Forest[MTree[A]]) extends MTree[A]{
    def get(i:Int):Option[MTree[A]] = forest.get(i)
  }
  case class Leaf[+A](val value:A) extends AnyVal with MTree[A]{
    def get(i:Int):Option[MTree[A]] = None
    override def isLeaf:Boolean = true
  }

  /**TODO try to generalize this Zipper to the different kinds of trees instead of just the MTree
   *         -  a alternate type indexer
   *         -  use a Either based Index-er
   *TODO try to add some variance to this zipper type
  */
  case class Zipper[A](family:MTree[A], index:Int=0, parents:List[Zipper[A]]=Nil){
     private type ZOpt[A] = Option[Zipper[A]]
     def node:MTree[A] = family.get(index).get
     def value:A = node.value
     // def apply(i:Int):Zipper[A] = copy(index=i)
     def sibling(i:Int):ZOpt[A] = family.get(i) map {_ => copy(index=i) }
     def right:ZOpt[A] = sibling(index+1)
     def left:ZOpt[A] = sibling(index-1)
     def depth:Int = parents.size
     def parent:ZOpt[A] = parents.headOption
     def up:ZOpt[A] = parents.headOption
     //TODO shouldn't have to wrap the child in a Forest here since the family is known, this suggests the Tree should not extend Family... rather tree.kids should return the Forest
     def down(i:Int):ZOpt[A] = for(child <- family get i) yield Zipper[A](child, i, this::parents)

     def next:ZOpt[A] = down(0) orElse right orElse parent.flatMap(_.right)  //go to first child down(0) if exists otherwise next sibling

     override def toString = "Zipper("+ (parents.map{_.index}:+index).mkString("/","/","#") + value.toString +")"

     private def ksonLine = "  "*depth + node.value.toString //TODO generalize this kind of toString from the family Forest type
     def toKson:String = {
         val acc = new StringBuilder //Ugh! ugly mutable logic is clearer and more performant
         acc ++= ksonLine
         @tailrec def show(zipper:Zipper[A]):Unit = {
           acc ++= "\n" + zipper.ksonLine
           zipper.next match { case Some(z) => show(z); case _ => } //zipper.next foreach show //non-tailrecursive version
         }
         show(this)
         acc.toString
     }
  }
}

//--TTree or MMTree, or thorned tree, variation of a rose tree where the root/label/value node is itself can be a MTree forest
sealed trait TTree[+A] extends Any with Tree[Forest[MTree[A]],TTree[A]]
object TTree{
  /**make a leaf (TTree)*/
  def apply[A](value:MTree[A]) = new Leaf(Forest(value))
  /**make a node (TTree)*/
  def apply[A](value:Forest[MTree[A]], trees:Forest[TTree[A]]) = new Node(value, trees)
  /**make a leaf (TTree)*/
  def apply[A](value:A) = new Leaf(Forest(new MTree.Leaf(value)))

  case class Node[+A](val value:Forest[MTree[A]], forest:Forest[TTree[A]]) extends TTree[A]{
    def get(i:Int):Option[TTree[A]] = forest.get(i)
  }
  case class Leaf[+A](val value:Forest[MTree[A]]) extends AnyVal with TTree[A]{
    def get(i:Int):Option[TTree[A]] = None
    override def isLeaf:Boolean = true
  }
}