/**
 * Created by Nehoroshiy.
 * const.belev@ya.ru
 */

object Color extends Enumeration {
  type Color = Value
  val Black, Red = Value
}
import Color._
import scala.reflect.ClassTag
import scala.util.Random
import java.io._

case object Node {
  val sliceSize = 16
}

object Rope {
  def apply[A](nodes: Vector[Node[A]])(implicit m: ClassTag[A]): Node[A] = nodes match {
    case arr if arr.length == 0 => LeafNode(Vector[A]())
    case Vector(_) => nodes(0)
    case nodes if nodes.length % 2 == 0 => apply[A](nodes.sliding(2, 2).toList.map( x => InternalNode(Black, x(0), x(1))).toVector)
    case _ => {
      val arr = nodes.takeRight(3)
      if (Random.nextBoolean()) {
        apply(nodes.dropRight(3) :+ InternalNode(Black, arr(0), InternalNode(Red, arr(1), arr(2))))
      } else {
        apply(nodes.dropRight(3) :+ InternalNode(Black, InternalNode(Red, arr(0), arr(1)), arr(2)))
      }
      apply(nodes.dropRight(3) ++ nodes.takeRight(3))
    }
  }
}

class Rope[A](val node: Node[A]) {
  import Node.sliceSize

  def this(color: Color, left: Rope[A], right: Rope[A]) = this(InternalNode(color, left.node, right.node))

  def this(values: Vector[A])(implicit m: ClassTag[A]) =
    this(Rope.apply[A](values.iterator.sliding(Node.sliceSize, Node.sliceSize).toVector.map({ case x:Seq[A] => LeafNode(x.toVector) })))



  def blackHeight = node.blackHeight

  def len = node.len

  def values(implicit m: ClassTag[A]) = node.values()

  def left = new Rope(node.left)

  def right = new Rope(node.right)

  def append(other: Rope[A])(implicit m: ClassTag[A]): Rope[A] = {
    if (node.blackHeight == other.node.blackHeight) {
      new Rope(Black, this, other)
    } else if (blackHeight < other.blackHeight) {
      other.prependLow(this)
    } else {
      appendLow(other)
    }
  }

  def appendLow(other: Rope[A])(implicit m: ClassTag[A]) : Rope[A] = this.node match {
    case LeafNode(_) => {
      other.node match {
        case LeafNode(_) => {
          if (this.len + other.len <= Node.sliceSize)
            new Rope(this.values ++ other.values)
          else new Rope(Black, this, other)
        }
        case _ => throw new IllegalArgumentException("Internal node cannot be appendedLow to leaf node")
      }
    }
    case InternalNode(_,_,_) if blackHeight == other.blackHeight => {
      new Rope(Red, this, other)
    }
    case InternalNode(color,_,_) if blackHeight > other.blackHeight => {
      new Rope(color, left, right.appendLow(other)).balance()
    }
  }

  def prependLow(other: Rope[A])(implicit m: ClassTag[A]) : Rope[A] = this.node match {
    case LeafNode(_) => {
      other.node match {
        case LeafNode(_) => {
          if (this.len + other.len <= Node.sliceSize)
            new Rope(other.values ++ this.values)
          else new Rope(Black, other, this)
        }
        case _ => throw new IllegalArgumentException("Internal node cannot be prependedLow to leaf node")
      }
    }
    case InternalNode(_,_,_) if blackHeight == other.blackHeight => {
      new Rope(Red, other, this)
    }
    case InternalNode(_,_,_) if blackHeight > other.blackHeight => {
      new Rope(node.color, left.prependLow(other), right).balance()
    }
  }

  def balance(): Rope[A] = this.node match {
    case InternalNode(Black, InternalNode(Red, InternalNode(Red, a, b), c), d) => {
      new Rope(InternalNode(Red, InternalNode(Black, a, b), InternalNode(Black, c, d)))
    }
    case InternalNode(Black, InternalNode(Red, a, InternalNode(Red, b, c)), d) => {
      new Rope(InternalNode(Red, InternalNode(Black, a, b), InternalNode(Black, c, d)))
    }
    case InternalNode(Black, a, InternalNode(Red, InternalNode(Red, b, c), d)) => {
      new Rope(InternalNode(Red, InternalNode(Black, a, b), InternalNode(Black, c, d)))
    }
    case InternalNode(Black, a, InternalNode(Red, b, InternalNode(Red, c, d))) => {
      new Rope(InternalNode(Red, InternalNode(Black, a, b), InternalNode(Black, c, d)))
    }
    case _ =>  this
  }

  def dotPrint()(implicit m: ClassTag[A]) {
    val p = new java.io.PrintWriter(new File("test.dot"))
    p.write("digraph graphname {\n")
    val thisString = "xxx" + this.node.toString.replaceAll("[$ @]+", "")
    p.write(thisString + "[label=" + len + "];\n")
    if (node.color == Red)
      p.write(thisString + "[color=red];\n")
    dotPrintRecursive(p, this)
    p.write("}\n")
    p.close()
  }

  def dotPrintRecursive(p: java.io.PrintWriter, rope: Rope[A])(implicit m: ClassTag[A]):Unit = rope.node match {
    case LeafNode(values) if rope.node.isEmpty => {  }
    case LeafNode(values) => {
      val thisString = "xxx" + rope.node.toString.replaceAll("[$ @]+", "")
      p.write(thisString + " [shape=box];\n")
      p.write(thisString + " [label=\"[" + rope.values.head.toString + ":" + rope.values.takeRight(1).toString + "]\\nsize:" + len + "\\nbh:[" + blackHeight + "]\"];\n")
    }
    case InternalNode(_,_,_) => {
      val thisString = "xxx" + node.toString.replaceAll("[$ @]+", "")
      p.write(thisString + " [label=\"len:" + len + "\\nbh:[" + blackHeight + "]\"];\n")
      if (rope.node.color == Red) {
        p.write(thisString + "[color=red];\n")
      }
      if (rope.node.left != null) {
        val leftString = "xxx" + rope.node.left.toString.replaceAll("[$ @]+", "")
        dotPrintRecursive(p, rope.left)
        p.write(thisString + "->" + leftString + "\n")
      }
      if (rope.node.right != null) {
        val rightString = "xxx" + rope.node.right.toString.replaceAll("[$ @]+", "")
        dotPrintRecursive(p, rope.right)
        p.write(thisString + "->" + rightString + "\n")
      }
    }
  }
}

sealed trait Node[+A] {
  import Node.sliceSize

  def len : Int

  def blackHeight: Int

  def color: Color

  def left: Node[A]

  def right: Node[A]

  def isEmpty: Boolean = { len == 0 }

  def values() : Vector[A]
}

case class InternalNode[A](color: Color, left: Node[A], right: Node[A]) extends Node[A] {
  val len = left.len + right.len
  val blackHeight = if (color == Black) left.blackHeight + 1 else left.blackHeight
  def values(): Vector[A] = left.values ++ right.values
}

case class LeafNode[A](vals: Vector[A]) extends Node[A] {
  val color = Black
  val len = vals.length
  val blackHeight = 1
  val left, right = null
  def values = vals
}