/**
* 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
}