diff options
| -rw-r--r-- | src/library/scala/collection/mutable/AVLTree.scala | 250 | ||||
| -rw-r--r-- | test/files/scalacheck/avl.scala | 112 |
2 files changed, 0 insertions, 362 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 - } - } -} diff --git a/test/files/scalacheck/avl.scala b/test/files/scalacheck/avl.scala deleted file mode 100644 index 4cfacaf407..0000000000 --- a/test/files/scalacheck/avl.scala +++ /dev/null @@ -1,112 +0,0 @@ -import org.scalacheck.Gen -import org.scalacheck.Prop.forAll -import org.scalacheck.Properties - -package scala.collection.mutable { - - /** - * Property of an AVL Tree : Any node of the tree has a balance value beetween in [-1; 1] - */ - abstract class AVLTreeTest(name: String) extends Properties(name) { - - def `2^`(n: Int) = (1 to n).fold(1)((a, b) => b*2) - - def capacityMax(depth: Int): Int = `2^`(depth+1) - 1 - - def minDepthForCapacity(x: Int): Int = { - var depth = 0 - while(capacityMax(depth) < x) - depth += 1 - depth - } - - def numberOfElementsInLeftSubTree(n: Int): collection.immutable.IndexedSeq[Int] = { - val mid = n/2 + n%2 - ((1 until mid) - .filter { i => math.abs(minDepthForCapacity(i) - minDepthForCapacity(n-i)) < 2 } - .flatMap { i => Seq(i, n-(i+1)) }).toIndexedSeq.distinct - } - - def makeAllBalancedTree[A](elements: List[A]): List[AVLTree[A]] = elements match { - case Nil => Leaf::Nil - case first::Nil => Node(first, Leaf, Leaf)::Nil - case first::second::Nil => Node(second, Node(first, Leaf, Leaf), Leaf)::Node(first, Leaf, Node(second, Leaf, Leaf))::Nil - case first::second::third::Nil => Node(second, Node(first, Leaf, Leaf), Node(third, Leaf, Leaf))::Nil - case _ => { - val combinations = for { - left <- numberOfElementsInLeftSubTree(elements.size) - root = elements(left) - right = elements.size - (left + 1) - } yield (root, left, right) - (combinations.flatMap(triple => for { - l <- makeAllBalancedTree(elements.take(triple._2)) - r <- makeAllBalancedTree(elements.takeRight(triple._3)) - } yield Node(triple._1, l, r))).toList - } - } - - def genInput: org.scalacheck.Gen[(Int, List[AVLTree[Int]])] = for { - size <- org.scalacheck.Gen.choose(20, 25) - elements <- org.scalacheck.Gen.listOfN(size, org.scalacheck.Gen.choose(0, 1000)) - selected <- org.scalacheck.Gen.choose(0, 1000) - } yield { - // selected mustn't be in elements already - val list = makeAllBalancedTree(elements.sorted.distinct.map(_*2)) - (selected*2+1, list) - } - - def genInputDelete: org.scalacheck.Gen[(Int, List[AVLTree[Int]])] = for { - size <- org.scalacheck.Gen.choose(20, 25) - elements <- org.scalacheck.Gen.listOfN(size, org.scalacheck.Gen.choose(0, 1000)) - e = elements.sorted.distinct - selected <- org.scalacheck.Gen.choose(0, e.size-1) - } yield { - // selected must be in elements already - val list = makeAllBalancedTree(e) - (e(selected), list) - } - } - - trait AVLInvariants { - self: AVLTreeTest => - - def isBalanced[A](t: AVLTree[A]): Boolean = t match { - case node: Node[A] => math.abs(node.balance) < 2 && (List(node.left, node.right) forall isBalanced) - case Leaf => true - } - - def setup(invariant: AVLTree[Int] => Boolean) = forAll(genInput) { - case (selected: Int, trees: List[AVLTree[Int]]) => - trees.map(tree => invariant(tree)).fold(true)((a, b) => a && b) - } - - property("Every tree is initially balanced.") = setup(isBalanced) - } - - object TestInsert extends AVLTreeTest("Insert") with AVLInvariants { - import math.Ordering.Int - property("`insert` creates a new tree containing the given element. The tree remains balanced.") = forAll(genInput) { - case (selected: Int, trees: List[AVLTree[Int]]) => - trees.map(tree => { - val modifiedTree = tree.insert(selected, Int) - modifiedTree.contains(selected, Int) && isBalanced(modifiedTree) - }).fold(true)((a, b) => a && b) - } - } - - object TestRemove extends AVLTreeTest("Remove") with AVLInvariants { - import math.Ordering.Int - property("`remove` creates a new tree without the given element. The tree remains balanced.") = forAll(genInputDelete) { - case (selected: Int, trees: List[AVLTree[Int]]) => - trees.map(tree => { - val modifiedTree = tree.remove(selected, Int) - tree.contains(selected, Int) && !modifiedTree.contains(selected, Int) && isBalanced(modifiedTree) - }).fold(true)((a, b) => a && b) - } - } -} - -object Test extends Properties("AVL") { - include(scala.collection.mutable.TestInsert) - include(scala.collection.mutable.TestRemove) -} |