/**
* 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._
object Node {
val sliceSize = 16
def apply[A, B <: Node[A]](nodes: Array[B])(implicit m: ClassTag[A], n: ClassTag[B]): Node[A] = nodes match {
case arr if arr.length == 0 => EmptyLeaf
case Array(_) => nodes(0)
case nodes if nodes.length % 2 == 0 => apply(nodes.sliding(2, 2).toList.map( x => InternalNode(Black, x(0), x(1))).toArray)
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))
}
}
}
object Rope
class Rope[A](val node: Node[A]) {
def this(values: Array[A])(implicit m: ClassTag[A])= this(apply(values.sliding(sliceSize, sliceSize).toList map { x => LeafNode[A](x) } toArray))
}
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 apply[A, B <: Node[A]](nodes: Array[B])(implicit m: ClassTag[A], n: ClassTag[B]): Node[A] = nodes match {
case arr if arr.length == 0 => EmptyLeaf
case Array(_) => nodes(0)
case nodes if nodes.length % 2 == 0 => apply(nodes.sliding(2, 2).toList.map( x => InternalNode(Black, x(0), x(1))).toArray)
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))
}
}
def apply[A](values: Array[A])(implicit m: ClassTag[A]): Node[A] = apply(values.sliding(sliceSize, sliceSize).toList map { x => LeafNode[A](x) } toArray)
def balance(): Node[A] = this match {
case InternalNode(Black, InternalNode(Red, InternalNode(Red, a, b), c), d) => {
InternalNode(Red, InternalNode(Black, a, b), InternalNode(Black, c, d))
}
case InternalNode(Black, InternalNode(Red, a, InternalNode(Red, b, c)), d) => {
InternalNode(Red, InternalNode(Black, a, b), InternalNode(Black, c, d))
}
case InternalNode(Black, a, InternalNode(Red, InternalNode(Red, b, c), d)) => {
InternalNode(Red, InternalNode(Black, a, b), InternalNode(Black, c, d))
}
case InternalNode(Black, a, InternalNode(Red, b, InternalNode(Red, c, d))) => {
InternalNode(Red, InternalNode(Black, a, b), InternalNode(Black, c, d))
}
case _ => this
}
def append[B >: A](other: Node[B])(implicit m: ClassTag[A], n: ClassTag[B]): Node[B] = {
if (blackHeight == other.blackHeight) {
InternalNode(Black, this, other)
} else if (blackHeight < other.blackHeight) {
other.prependLow(this)
} else {
appendLow(other)
}
}
def appendLow[B >: A](other: Node[B])(implicit m: ClassTag[A], n: ClassTag[B]) : Node[B] = this match {
case LeafNode(_) => {
other match {
case LeafNode(_) => {
if (this.len + other.len <= Node.sliceSize)
LeafNode(this.values ++ other.values)
else InternalNode(Black, this, other)
}
case _ => throw new IllegalArgumentException("Internal node cannot be appendedLow to leaf node")
}
}
case InternalNode(_,_,_) if blackHeight == other.blackHeight => {
InternalNode(Red, this, other)
}
case InternalNode(_,_,_) if blackHeight > other.blackHeight => {
InternalNode(color, left, right.appendLow(other)).balance()
}
}
def prependLow[B >: A](other: Node[B])(implicit m: ClassTag[A], n: ClassTag[B]) : Node[B] = this match {
case LeafNode(_) => {
right match {
case LeafNode(_) => {
if (this.len + other.len <= Node.sliceSize)
LeafNode(other.values ++ this.values)
else InternalNode(Black, other, this)
}
}
}
case InternalNode(_,_,_) if blackHeight == other.blackHeight => {
InternalNode(Red, other, this)
}
case InternalNode(_,_,_) if blackHeight > other.blackHeight => {
InternalNode(color, left.prependLow(other), right).balance()
}
}
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.toString.replaceAll("[$ @]+", "")
p.write(thisString + "[label=" + len + "];\n")
if (color == Red)
p.write(thisString + "[color=red];\n")
dotPrintRecursive(p, this)
p.write("}\n")
p.close()
}
def dotPrintRecursive(p: java.io.PrintWriter, node: Node[A])(implicit m: ClassTag[A]):Unit = node match {
case LeafNode(values) => {
val thisString = "xxx" + node.toString.replaceAll("[$ @]+", "")
p.write(thisString + " [shape=box];\n")
p.write(thisString + " [label=\"[" + this.values().head.toString + ":" + this.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 (node.color == Red) {
p.write(thisString + "[color=red];\n")
}
if (node.left != null) {
val leftString = "xxx" + node.left.toString.replaceAll("[$ @]+", "")
dotPrintRecursive(p, node.left)
p.write(thisString + "->" + leftString + "\n")
}
if (node.right != null) {
val rightString = "xxx" + node.right.toString.replaceAll("[$ @]+", "")
dotPrintRecursive(p, node.right)
p.write(thisString + "->" + rightString + "\n")
}
}
}
def values()(implicit m: ClassTag[A]) : Array[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()(implicit m: ClassTag[A]): Array[A] = {
left.values ++ right.values
}
}
case class LeafNode[A](vals: Array[A]) extends Node[A] {
val color = Black
val len = vals.length
val blackHeight = 1
val left, right = null
def values()(implicit m: ClassTag[A]) = values
}
case object EmptyLeaf extends Node[Nothing] {
val isEmpty = true
}