diff options
author | Matthias Zenger <mzenger@gmail.com> | 2004-05-03 20:19:00 +0000 |
---|---|---|
committer | Matthias Zenger <mzenger@gmail.com> | 2004-05-03 20:19:00 +0000 |
commit | 927dadef1009442fda637bfe568616630dbec6d0 (patch) | |
tree | 35999aefdb673ba344849765152e6ebc92f929c1 | |
parent | 0c42b4a80bdd112f14925ef5d2e202575536e307 (diff) | |
download | scala-927dadef1009442fda637bfe568616630dbec6d0.tar.gz scala-927dadef1009442fda637bfe568616630dbec6d0.tar.bz2 scala-927dadef1009442fda637bfe568616630dbec6d0.zip |
New collection class.
6 files changed, 488 insertions, 115 deletions
diff --git a/sources/scala/collection/immutable/Order.scala b/sources/scala/collection/immutable/Order.scala deleted file mode 100644 index 3b3ca009c6..0000000000 --- a/sources/scala/collection/immutable/Order.scala +++ /dev/null @@ -1,115 +0,0 @@ -/* __ *\ -** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** -** __\ \/ /__/ __ |/ /__/ __ | ** -** /____/\___/_/ |_/____/_/ | | ** -** |/ ** -** $Id$ -\* */ - -package scala.collection.immutable; - -/** The object Order provides constructors for orderings between -* objects. -*/ -object Order { - /** - * Creates an Order given a predicate - * (<code>inferiority(e1,e2)</code>). - * The predicate is true iff e1 is less than - * e2. The ordinary equality operator == will be used for - * equality by the order. - */ - def make[A](inferiority:(A,A) => Boolean) = - new Order[A](inferiority,(e1:A,e2:A) => e1 == e2); - /** - * Creates an Order given two predicates - * (<code>inferiority(e1,e2)</code> and - * <code>equality(e1,e2)</code>). The first is true iff e1 is less than - * e2 and the second predicate is true when e1 is equal to e2. - */ - def make[A](inferiority:(A,A) => Boolean, equality:(A,A) => Boolean) = - new Order[A](inferiority,equality); - - /** - * Creates a 'standard' order between objects. - * <strong>NOTE:</strong> - * The order is arbitrary and uses the <code>hashCode()</code> of - * objects which might mean that the order is not really total - * for some objects - * <code>(!(e1 < e2) && !(e2 < e1) && !(e1==e2))</code> - * is true. This function should only be used when no other - * comparision predicates can be defined. - */ - def make = - new Order[Any]( - (e1:Any,e2:Any) => - e1.match { - case x:Int => { - e2.match { - case y:Int => x < y; - case y:Double => x < y; - case y:Float => x < y; - case y:Long => x < y; - case _ => true; - } - } - case x:Double => { - e2.match { - case y:Int => x < y; - case y:Double => x < y; - case y:Float => x < y; - case y:Long => x < y; - case _ => true; - } - } - case x:Float => { - e2.match { - case y:Int => x < y; - case y:Double => x < y - case y:Float => x < y;; - case y:Long => x < y; - case _ => true; - } - } - case x:Long => { - e2.match { - case y:Int => x < y; - case y:Double => x < y - case y:Float => x < y;; - case y:Long => x < y; - case _ => true; - } - } - case x:AnyRef => { - e2.match { - case y:AnyVal => false; - case y:AnyRef => x.hashCode() < y.hashCode(); - } - } - }, - (e1:Any,e2:Any) => e1 == e2); -} - - -/** The class Order[A] defines an order between objects of - * type A, given two predicates (<code>inferiority(e1,e2)</code> and - * <code>equality(e1,e2)</code>). The first is true iff e1 is less than - * e2 and the second predicate is true when e1 is equal to e2. - * An Order object can be used for ordered trees, maps, and sets. - * In order to use the order with the given - * TreeMap and TreeSet implementations the definition of the - * predicates <code>inferiority</code> and <code>equality</code> - * should be total. They predicate should - * also define a true total ordering (i.e., inferiority should be - * transitive, non-reflexive and asymmetric, and equality should be - * transitive, reflexive and symetric.) - */ -class Order[A](inferiority:(A,A) => Boolean, equality:(A,A) => Boolean) { - def < (e1:A, e2:A) = inferiority(e1,e2); - def <= (e1:A, e2:A) = inferiority(e1,e2) || equality(e1,e2); - def > (e1:A, e2:A) = inferiority(e2,e1); - def >= (e1:A, e2:A) = ! inferiority(e1,e2); - def == (e1:A, e2:A) = equality(e1,e2); - def != (e1:A, e2:A) = ! equality(e1,e2); -} diff --git a/sources/scala/collection/mutable/PriorityQueue.scala b/sources/scala/collection/mutable/PriorityQueue.scala new file mode 100644 index 0000000000..848069a918 --- /dev/null +++ b/sources/scala/collection/mutable/PriorityQueue.scala @@ -0,0 +1,150 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala.collection.mutable; + + +/** This class implements priority queues using a heap. The + * elements of the queue have to be ordered in terms of the + * <code>Ordered[T]</code> trait. + * + * @author Matthias Zenger + * @version 1.0, 03/05/2004 + */ +class PriorityQueue[A <% Ordered[A]] extends ResizableArray[A] { + size = size + 1; // we do not use array(0) + + protected def fixUp(as: Array[A], m: Int): Unit = { + var k: Int = m; + while ((k > 1) && (as(k / 2) < as(k))) { + swap(k, k / 2); + k = k / 2; + } + } + + protected def fixDown(as: Array[A], m: Int, n: Int): Unit = { + var k: Int = m; + var loop: Boolean = true; + while (loop && (n >= 2 * k)) { + var j = 2 * k; + if ((j < n) && (as(j) < as(j + 1))) + j = j + 1; + if (!(as(k) < as(j))) + loop = false; + else { + val h = as(k); + as(k) = as(j); + as(j) = h; + k = j; + } + } + } + + /** Checks if the queue is empty. + * + * @return true, iff there is no element in the queue. + */ + def isEmpty: Boolean = size < 2; + + /** Inserts a single element into the priority queue. + * + * @param elem the element to insert + */ + def +=(elem: A): Unit = { + ensureSize(1); + array(size) = elem; + fixUp(array, size); + size = size + 1; + } + + /** Adds all elements provided by an <code>Iterable</code> object + * into the priority queue. + * + * @param iter an iterable object + */ + def ++=(iter: Iterable[A]): Unit = iter.elements.foreach(e => this += e); + + /** Adds all elements to the queue. + * + * @param elems the elements to add. + */ + def enqueue(elems: A*): Unit = (this ++= elems); + + /** Returns the element with the highest priority in the queue, + * and removes this element from the queue. + * + * @return the element with the highest priority. + */ + def dequeue: A = { + if (size > 1) { + size = size - 1; + swap(1, size); + fixDown(array, 1, size - 1); + array(size) + } else + error("no element to remove from heap"); + } + + /** Returns the element with the highest priority in the queue, + * or throws an error if there is no element contained in the queue. + * + * @return the element with the highest priority. + */ + def max: A = if (size > 1) array(1) else error("queue is empty"); + + /** Removes all elements from the queue. After this operation is completed, + * the queue will be empty. + */ + def clear: Unit = { + size = 1; + } + + /** Returns an iterator which yiels all the elements of the priority + * queue in descending priority order. + * + * @return an iterator over all elements sorted in descending order. + */ + override def elements: Iterator[A] = new Iterator[A] { + val as: Array[A] = new Array[A](size); + java.lang.System.arraycopy(array, 0, as, 0, size); + var i = size - 1; + def hasNext: Boolean = i > 0; + def next: A = { + val res = as(1); + as(1) = as(i); + i = i - 1; + fixDown(as, 1, i); + res + } + } + + /** Checks if two queues are structurally identical. + * + * @return true, iff both queues contain the same sequence of elements. + */ + override def equals(that: Any): Boolean = + that.isInstanceOf[PriorityQueue[A]] && + { val other = that.asInstanceOf[PriorityQueue[A]]; + elements.zip(other.elements).forall { + case Pair(thiselem, thatelem) => thiselem == thatelem; + }}; + + /** The hashCode method always yields an error, since it is not + * safe to use mutable queues as keys in hash tables. + * + * @return never. + */ + override def hashCode(): Int = error("unsuitable as hash key"); + + /** Returns a textual representation of a queue as a string. + * + * @return the string representation of this queue. + */ + override def toString() = toList.mkString("PriorityQueue(", ", ", ")"); +} diff --git a/sources/scala/collection/mutable/ResizableArray.scala b/sources/scala/collection/mutable/ResizableArray.scala new file mode 100644 index 0000000000..08ff972fc0 --- /dev/null +++ b/sources/scala/collection/mutable/ResizableArray.scala @@ -0,0 +1,61 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala.collection.mutable; + + +/** This class is used internally to implement data structures that + * are based on resizable arrays. + * + * @author Matthias Zenger + * @version 1.0, 03/05/2004 + */ +abstract class ResizableArray[A] with Iterable[A] { + import java.lang.System.arraycopy; + + protected val initialSize: Int = 16; + protected var array: Array[A] = new Array[A](initialSize); + protected var size: Int = 0; + + /** Extends the internal array if more elements are needed. + */ + protected def ensureSize(n: Int): Unit = { + if ((size + n) > array.length) { + val newar: Array[A] = new Array(array.length * 2); + arraycopy(array, 0, newar, 0, size); + array = newar; + } + } + + /** Swap two elements of this array. + */ + protected def swap(a: Int, b: Int): Unit = { + val h = array(a); + array(a) = array(b); + array(b) = h; + } + + /** Move parts of the array. + */ + protected def copy(m: Int, n: Int, len: Int) = { + arraycopy(array, m, array, n, len); + } + + /** Returns the length of this resizable array. + */ + def length: Int = size; + + /** Returns a new iterator over all elements of this resizable array. + */ + def elements: Iterator[A] = new Iterator[A] { + var i = 0; + def hasNext: Boolean = i < size; + def next: A = { i = i + 1; array(i - 1) } + } +} diff --git a/sources/scala/collection/mutable/SynchronizedPriorityQueue.scala b/sources/scala/collection/mutable/SynchronizedPriorityQueue.scala new file mode 100644 index 0000000000..1afcb8171a --- /dev/null +++ b/sources/scala/collection/mutable/SynchronizedPriorityQueue.scala @@ -0,0 +1,91 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala.collection.mutable; + + +/** This class implements synchronized priority queues using a heap. + * The elements of the queue have to be ordered in terms of the + * <code>Ordered[T]</code> trait. + * + * @author Matthias Zenger + * @version 1.0, 03/05/2004 + */ +class SynchronizedPriorityQueue[A <% Ordered[A]] extends PriorityQueue[A] { + + /** Checks if the queue is empty. + * + * @return true, iff there is no element in the queue. + */ + override def isEmpty: Boolean = synchronized { super.isEmpty; } + + /** Inserts a single element into the priority queue. + * + * @param elem the element to insert + */ + override def +=(elem: A): Unit = synchronized { super.+=(elem); } + + /** Adds all elements provided by an <code>Iterable</code> object + * into the priority queue. + * + * @param iter an iterable object + */ + override def ++=(iter: Iterable[A]): Unit = synchronized { super.++=(iter); } + + /** Adds all elements to the queue. + * + * @param elems the elements to add. + */ + override def enqueue(elems: A*): Unit = synchronized { super.++=(elems); } + + /** Returns the element with the highest priority in the queue, + * and removes this element from the queue. + * + * @return the element with the highest priority. + */ + override def dequeue: A = synchronized { super.dequeue; } + + /** Returns the element with the highest priority in the queue, + * or throws an error if there is no element contained in the queue. + * + * @return the element with the highest priority. + */ + override def max: A = synchronized { super.max; } + + /** Removes all elements from the queue. After this operation is completed, + * the queue will be empty. + */ + override def clear: Unit = synchronized { super.clear; } + + /** Returns an iterator which yiels all the elements of the priority + * queue in descending priority order. + * + * @return an iterator over all elements sorted in descending order. + */ + override def elements: Iterator[A] = synchronized { super.elements; } + + /** Checks if two queues are structurally identical. + * + * @return true, iff both queues contain the same sequence of elements. + */ + override def equals(that: Any): Boolean = synchronized { super.equals(that); } + + /** The hashCode method always yields an error, since it is not + * safe to use mutable queues as keys in hash tables. + * + * @return never. + */ + override def hashCode(): Int = synchronized { super.hashCode(); } + + /** Returns a textual representation of a queue as a string. + * + * @return the string representation of this queue. + */ + override def toString(): String = synchronized { super.toString(); } +} diff --git a/sources/scala/collection/mutable/SynchronizedQueue.scala b/sources/scala/collection/mutable/SynchronizedQueue.scala new file mode 100644 index 0000000000..caf17d91d2 --- /dev/null +++ b/sources/scala/collection/mutable/SynchronizedQueue.scala @@ -0,0 +1,85 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala.collection.mutable; + + +/** This is a synchronized version of the <code>Queue[T]</code> class. It + * implements a data structure that allows one to insert and retrieve + * elements in a first-in-first-out (FIFO) manner. + * + * @author Matthias Zenger + * @version 1.0, 03/05/2004 + */ +class SynchronizedQueue[A] extends Queue[A] { + + /** Checks if the queue is empty. + * + * @return true, iff there is no element in the queue. + */ + override def isEmpty: Boolean = synchronized { super.isEmpty; } + + /** Inserts a single element at the end of the queue. + * + * @param elem the element to insert + */ + override def +=(elem: A): Unit = synchronized { super.+=(elem); } + + /** Adds all elements provided by an <code>Iterable</code> object + * at the end of the queue. The elements are prepended in the order they + * are given out by the iterator. + * + * @param iter an iterable object + */ + override def ++=(iter: Iterable[A]): Unit = synchronized { super.++=(iter); } + + /** Adds all elements to the queue. + * + * @param elems the elements to add. + */ + override def enqueue(elems: A*): Unit = synchronized { super.++=(elems); } + + /** Returns the first element in the queue, and removes this element + * from the queue. + * + * @return the first element of the queue. + */ + override def dequeue: A = synchronized { super.dequeue; } + + /** Returns the first element in the queue, or throws an error if there + * is no element contained in the queue. + * + * @return the first element. + */ + override def front: A = synchronized { super.front; } + + /** Removes all elements from the queue. After this operation is completed, + * the queue will be empty. + */ + override def clear: Unit = synchronized { super.clear; } + + /** Checks if two queues are structurally identical. + * + * @return true, iff both queues contain the same sequence of elements. + */ + override def equals(that: Any): Boolean = synchronized { super.equals(that); } + + /** The hashCode method always yields an error, since it is not + * safe to use mutable queues as keys in hash tables. + * + * @return never. + */ + override def hashCode(): Int = synchronized { super.hashCode(); } + + /** Returns a textual representation of a queue as a string. + * + * @return the string representation of this queue. + */ + override def toString() = synchronized { super.toString(); } +} diff --git a/sources/scala/collection/mutable/SynchronizedStack.scala b/sources/scala/collection/mutable/SynchronizedStack.scala new file mode 100644 index 0000000000..2469b20d67 --- /dev/null +++ b/sources/scala/collection/mutable/SynchronizedStack.scala @@ -0,0 +1,101 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala.collection.mutable; + + +/** This is a synchronized version of the <code>Stack[T]</code> class. It + * implements a data structure which allows to store and retrieve + * objects in a last-in-first-out (LIFO) fashion. + * + * @author Matthias Zenger + * @version 1.0, 03/05/2004 + */ +class SynchronizedStack[A] extends Stack[A] { + + /** Checks if the stack is empty. + * + * @return true, iff there is no element on the stack + */ + override def isEmpty: Boolean = synchronized { super.isEmpty } + + /** Pushes a single element on top of the stack. + * + * @param elem the element to push onto the stack + */ + override def +=(elem: A): Unit = synchronized { super.+=(elem); } + + /** Pushes all elements provided by an <code>Iterable</code> object + * on top of the stack. The elements are pushed in the order they + * are given out by the iterator. + * + * @param iter an iterable object + */ + override def ++=(iter: Iterable[A]): Unit = synchronized { super.++=(iter); } + + /** Pushes a sequence of elements on top of the stack. The first element + * is pushed first, etc. + * + * @param elems a sequence of elements + */ + override def push(elems: A*): Unit = synchronized { super.++=(elems); } + + /** Returns the top element of the stack. This method will not remove + * the element from the stack. An error is signaled if there is no + * element on the stack. + * + * @return the top element + */ + override def top: A = synchronized { super.top; } + + /** Removes the top element from the stack. + */ + override def pop: A = synchronized { super.pop; } + + /** + * Removes all elements from the stack. After this operation completed, + * the stack will be empty. + */ + override def clear: Unit = synchronized { super.clear; } + + /** Returns an iterator over all elements on the stack. This iterator + * is stable with respect to state changes in the stack object; i.e. + * such changes will not be reflected in the iterator. The iterator + * issues elements in the order they were inserted into the stack + * (FIFO order). + * + * @return an iterator over all stack elements. + */ + override def elements: Iterator[A] = synchronized { super.elements; } + + /** Creates a list of all stack elements in FIFO order. + * + * @return the created list. + */ + override def toList: List[A] = synchronized { super.toList; } + + /** Checks if two stacks are structurally identical. + * + * @return true, iff both stacks contain the same sequence of elements. + */ + override def equals(that: Any): Boolean = synchronized { super.equals(that); } + + /** The hashCode method always yields an error, since it is not + * safe to use mutable stacks as keys in hash tables. + * + * @return never. + */ + override def hashCode(): Int = synchronized { super.hashCode(); } + + /** Returns a textual representation of a stack as a string. + * + * @return the string representation of this stack. + */ + override def toString() = synchronized { super.toString(); } +} |