Scala RandomAccessList

RandomAccessListApp.scala

trait Node[+T] {
  val index: Int
  val left: Node[T]
  val right: Node[T]
  val len: Int
  def apply(index: Int): T = ???
  def update[X >: T](index: Int, value: X): Node[X] = ???
}

case object NullNode extends Node[Nothing] {
  override val len: Int = 0
  override val index: Int = -1
  override val left: Node[Nothing] = this
  override val right: Node[Nothing] = this
}

case class ValueNode[T](index: Int, value: T, left: Node[T], right: Node[T]) extends Node[T] {

  val len: Int = left.len + right.len + 1

  override def apply(index: Int): T =
    if (index == this.index) value
    else if (index <= right.index) right(index)
    else left(index)

  override def update[X >: T](index: Int, value: X): ValueNode[X] =
    if (index == this.index) ValueNode(index, value, left, right)
    else if (index <= right.index) ValueNode(index, value, left, right.update(index, value))
    else ValueNode(index, value, left.update(index, value), right)

}

trait RandomAccessList[+T] {
  val head: Node[T]
  val right: RandomAccessList[T]
  def len: Int
  def apply(index: Int): T = ???
  def update[X >: T](index: Int, value: X): RandomAccessList[X] = ???
  def append[X >: T](value: X): RandomAccessList[X] = this
}

case object NilRandomAccessList extends RandomAccessList[Nothing] {
  override val head: Node[Nothing] = NullNode
  override val right: RandomAccessList[Nothing] = this
  override val len: Int = 0
}

case class VRandomAccessList[T](head: Node[T], right: RandomAccessList[T]) extends RandomAccessList[T] {

  override def apply(index: Int): T =
    if (index > this.right.head.index) this.head(index)
    else right(index)

  override def update[X >: T](index: Int, value: X): RandomAccessList[X] =
    if (index > right.head.index)
      VRandomAccessList(head.update(index, value), right)
    else
      VRandomAccessList(head, right.update(index, value))

  override def append[X >: T](value: X): RandomAccessList[X] =
    if (firstTwoTreesEqualHeight)
      VRandomAccessList(ValueNode(head.index + 1, value, head, right.head), right.right)
    else
      VRandomAccessList(ValueNode(head.index + 1, value, NullNode, NullNode), this)

  private val firstTwoTreesEqualHeight =
    right.head.len == head.len && right.head.len > 0

  override def len: Int = head.len + right.len
}

object RandomAccessListApp extends App{
  val nElements = 1000 * 1000 * 10

  val emptyList: RandomAccessList[Int] = VRandomAccessList[Int](NullNode, NilRandomAccessList)

  val list = (0 until nElements).foldLeft(emptyList)(_ append _)

  println(list.len)
  println(list(50000))
}

RandomAccessListFastApp.scala

object FastNode {
  def len[T](fastNode: FastNode[T]): Int = if (fastNode == null) 0 else fastNode.len
}

case class FastNode[+T](index: Int, value: T, left: FastNode[T], right: FastNode[T]) {

  val len: Int =
    (if (left == null) 0 else left.len) +
      (if (right == null) 0 else right.len) +
      1

  def apply(index: Int): T =
    if (index == this.index) value
    else if (index <= right.index) right(index)
    else left(index)

  def update[X >: T](index: Int, value: X): FastNode[X] =
    if (index == this.index) FastNode(index, value, left, right)
    else if (index <= right.index) FastNode(index, value, left, right.update(index, value))
    else FastNode(index, value, left.update(index, value), right)
}

object FastRandomAccessList {
  def len[T](fastRandomAccessList: FastRandomAccessList[T]) = if (fastRandomAccessList == null) 0 else fastRandomAccessList.len
}

case class FastRandomAccessList[+T](head: FastNode[T], right: FastRandomAccessList[T]) {

  def apply(index: Int): T =
    if (right.head == null || index > right.head.index) head(index)
    else right(index)

  def update[X >: T](index: Int, value: X): FastRandomAccessList[X] =
    if (index > right.head.index)
      FastRandomAccessList(head.update(index, value), right)
    else
      FastRandomAccessList(head, right.update(index, value))

  def append[X >: T](value: X): FastRandomAccessList[X] =
    if (firstTwoTreesEqualHeight)
      FastRandomAccessList(FastNode(head.index + 1, value, head, right.head), right.right)
    else
      FastRandomAccessList(
        FastNode(
          if (head != null) head.index + 1 else 0,
          value, null, null),
        this)

  private val firstTwoTreesEqualHeight =
    if (head == null) false
    else FastNode.len(right.head) == FastNode.len(head) && FastNode.len(right.head) > 0

  val len: Int = FastNode.len(head) + FastRandomAccessList.len(right)
}

object FastRandomAccessListFastApp extends App {
  val nElements = 1000 * 1000 * 10
  val emptyList: FastRandomAccessList[Int] = FastRandomAccessList[Int](null, null)

  val list = (0 until nElements).foldLeft(emptyList)(_ append _)

  println(list.len)
  println(list(49876))
}