Scala example source code file (AVLTree.scala)

This example Scala source code file (AVLTree.scala) is included in my "Source Code Warehouse" project. The intent of this project is to help you more easily find Scala source code examples by using tags.

All credit for the original source code belongs to scala-lang.org; I'm just trying to make examples easier to find. (For my Scala work, see my Scala examples and tutorials.)

Scala tags/keywords

a, avliterator, avltree, b, int, iterator, leaf, node, ordering, should

The AVLTree.scala Scala example source code

/*                     __                                               *\
**     ________ ___   / /  ___     Scala API                            **
**    / __/ __// _ | / /  / _ |    (c) 2003-2013, LAMP/EPFL             **
**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
** /____/\___/_/ |_/____/_/ | |                                         **
**                          |/                                          **
\*                                                                      */

package scala
package collection
package mutable

/**
 * An immutable AVL Tree implementation formerly used by mutable.TreeSet
 *
 * @author Lucien Pereira
 * @deprecated("AVLTree and its related classes are being removed from the standard library since they're not different enough from RedBlackTree to justify keeping them.", "2.11.0")
 */
private[mutable] sealed trait AVLTree[+A] extends Serializable {
  def balance: Int

  def depth: Int

  def iterator[B >: A]: Iterator[B] = Iterator.empty

  def contains[B >: A](value: B, ordering: Ordering[B]): Boolean = false

  /**
   * Returns a new tree containing the given element.
   * Thows an IllegalArgumentException if element is already present.
   *
   */
  def insert[B >: A](value: B, ordering: Ordering[B]): AVLTree[B] = Node(value, Leaf, Leaf)

  /**
   * Return a new tree which not contains given element.
   *
   */
  def remove[B >: A](value: B, ordering: Ordering[B]): AVLTree[A] =
    throw new NoSuchElementException(String.valueOf(value))

  /**
   * Return a tuple containing the smallest element of the provided tree
   * and a new tree from which this element has been extracted.
   *
   */
  def removeMin[B >: A]: (B, AVLTree[B]) = sys.error("Should not happen.")

  /**
   * Return a tuple containing the biggest element of the provided tree
   * and a new tree from which this element has been extracted.
   *
   */
  def removeMax[B >: A]: (B, AVLTree[B]) = sys.error("Should not happen.")

  def rebalance[B >: A]: AVLTree[B] = this

  def leftRotation[B >: A]: Node[B] = sys.error("Should not happen.")

  def rightRotation[B >: A]: Node[B] = sys.error("Should not happen.")

  def doubleLeftRotation[B >: A]: Node[B] = sys.error("Should not happen.")

  def doubleRightRotation[B >: A]: Node[B] = sys.error("Should not happen.")
}

/**
 * @deprecated("AVLTree and its related classes are being removed from the standard library since they're not different enough from RedBlackTree to justify keeping them.", "2.11.0")
 */
private case object Leaf extends AVLTree[Nothing] {
  override val balance: Int = 0

  override val depth: Int = -1
}

/**
 * @deprecated("AVLTree and its related classes are being removed from the standard library since they're not different enough from RedBlackTree to justify keeping them.", "2.11.0")
 */
private case class Node[A](data: A, left: AVLTree[A], right: AVLTree[A]) extends AVLTree[A] {
  override val balance: Int = right.depth - left.depth

  override val depth: Int = math.max(left.depth, right.depth) + 1

  override def iterator[B >: A]: Iterator[B] = new AVLIterator(this)

  override def contains[B >: A](value: B, ordering: Ordering[B]) = {
    val ord = ordering.compare(value, data)
    if (0 == ord)
      true
    else if (ord < 0)
      left.contains(value, ordering)
    else
      right.contains(value, ordering)
  }

  /**
   * Returns a new tree containing the given element.
   * Thows an IllegalArgumentException if element is already present.
   *
   */
  override def insert[B >: A](value: B, ordering: Ordering[B]) = {
    val ord = ordering.compare(value, data)
    if (0 == ord)
      throw new IllegalArgumentException()
    else if (ord < 0)
      Node(data, left.insert(value, ordering), right).rebalance
    else
      Node(data, left, right.insert(value, ordering)).rebalance
  }

  /**
   * Return a new tree which not contains given element.
   *
   */
  override def remove[B >: A](value: B, ordering: Ordering[B]): AVLTree[A] = {
    val ord = ordering.compare(value, data)
    if(ord == 0) {
      if (Leaf == left) {
        if (Leaf == right) {
          Leaf
        } else {
          val (min, newRight) = right.removeMin
          Node(min, left, newRight).rebalance
        }
      } else {
        val (max, newLeft) = left.removeMax
        Node(max, newLeft, right).rebalance
      }
    } else if (ord < 0) {
      Node(data, left.remove(value, ordering), right).rebalance
    } else {
      Node(data, left, right.remove(value, ordering)).rebalance
    }
  }

  /**
   * Return a tuple containing the smallest element of the provided tree
   * and a new tree from which this element has been extracted.
   *
   */
  override def removeMin[B >: A]: (B, AVLTree[B]) = {
    if (Leaf == left)
      (data, right)
    else {
      val (min, newLeft) = left.removeMin
      (min, Node(data, newLeft, right).rebalance)
    }
  }

  /**
   * Return a tuple containing the biggest element of the provided tree
   * and a new tree from which this element has been extracted.
   *
   */
  override def removeMax[B >: A]: (B, AVLTree[B]) = {
    if (Leaf == right)
      (data, left)
    else {
      val (max, newRight) = right.removeMax
      (max, Node(data, left, newRight).rebalance)
    }
  }

  override def rebalance[B >: A] = {
    if (-2 == balance) {
      if (1 == left.balance)
        doubleRightRotation
      else
        rightRotation
    } else if (2 == balance) {
      if (-1 == right.balance)
        doubleLeftRotation
      else
        leftRotation
    } else {
      this
    }
  }

  override def leftRotation[B >: A] = {
    if (Leaf != right) {
      val r: Node[A] = right.asInstanceOf[Node[A]]
      Node(r.data, Node(data, left, r.left), r.right)
    } else sys.error("Should not happen.")
  }

  override def rightRotation[B >: A] = {
    if (Leaf != left) {
      val l: Node[A] = left.asInstanceOf[Node[A]]
      Node(l.data, l.left, Node(data, l.right, right))
    } else sys.error("Should not happen.")
  }

  override def doubleLeftRotation[B >: A] = {
    if (Leaf != right) {
      val r: Node[A] = right.asInstanceOf[Node[A]]
      // Let's save an instanceOf by 'inlining' the left rotation
      val rightRotated = r.rightRotation
      Node(rightRotated.data, Node(data, left, rightRotated.left), rightRotated.right)
    } else sys.error("Should not happen.")
  }

  override def doubleRightRotation[B >: A] = {
    if (Leaf != left) {
      val l: Node[A] = left.asInstanceOf[Node[A]]
      // Let's save an instanceOf by 'inlining' the right rotation
      val leftRotated = l.leftRotation
      Node(leftRotated.data, leftRotated.left, Node(data, leftRotated.right, right))
    } else sys.error("Should not happen.")
  }
}

/**
 * @deprecated("AVLTree and its related classes are being removed from the standard library since they're not different enough from RedBlackTree to justify keeping them.", "2.11.0")
 */
private class AVLIterator[A](root: Node[A]) extends Iterator[A] {
  val stack = mutable.ArrayStack[Node[A]](root)
  diveLeft()

  private def diveLeft(): Unit = {
    if (Leaf != stack.head.left) {
      val left: Node[A] = stack.head.left.asInstanceOf[Node[A]]
      stack.push(left)
      diveLeft()
    }
  }

  private def engageRight(): Unit = {
    if (Leaf != stack.head.right) {
      val right: Node[A] = stack.head.right.asInstanceOf[Node[A]]
      stack.pop()
      stack.push(right)
      diveLeft()
    } else
      stack.pop()
  }

  override def hasNext: Boolean = !stack.isEmpty

  override def next(): A = {
    if (stack.isEmpty)
      throw new NoSuchElementException()
    else {
      val result = stack.head.data
      // Let's maintain stack for the next invocation
      engageRight()
      result
    }
  }
}