summaryrefslogtreecommitdiff
path: root/src/library/scala/collection/mutable/AVLTree.scala
diff options
context:
space:
mode:
Diffstat (limited to 'src/library/scala/collection/mutable/AVLTree.scala')
-rw-r--r--src/library/scala/collection/mutable/AVLTree.scala250
1 files changed, 0 insertions, 250 deletions
diff --git a/src/library/scala/collection/mutable/AVLTree.scala b/src/library/scala/collection/mutable/AVLTree.scala
deleted file mode 100644
index b63d0aae33..0000000000
--- a/src/library/scala/collection/mutable/AVLTree.scala
+++ /dev/null
@@ -1,250 +0,0 @@
-/* __ *\
-** ________ ___ / / ___ 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.2")
-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.
- * Throws 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.
- * Throws 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
- }
- }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-03 15:06:13 +0000