diff options
author | Matthias Zenger <mzenger@gmail.com> | 2003-08-08 13:01:56 +0000 |
---|---|---|
committer | Matthias Zenger <mzenger@gmail.com> | 2003-08-08 13:01:56 +0000 |
commit | 912a3dcbea224c5e8492ec9f252d2f1edf70d9f5 (patch) | |
tree | fbf057156cc5f7231298b28ebe28a8096438ee35 /sources | |
parent | 7dc777e6198d01286002db45554737b7def4e3fb (diff) | |
download | scala-912a3dcbea224c5e8492ec9f252d2f1edf70d9f5.tar.gz scala-912a3dcbea224c5e8492ec9f252d2f1edf70d9f5.tar.bz2 scala-912a3dcbea224c5e8492ec9f252d2f1edf70d9f5.zip |
Added support for structural equality in mutabl...
Added support for structural equality in mutable data structures. Added
documentation. Cleaned up code.
Diffstat (limited to 'sources')
-rw-r--r-- | sources/scala/Cell.scala | 18 | ||||
-rw-r--r-- | sources/scala/Iterator.scala | 12 | ||||
-rw-r--r-- | sources/scala/List.scala | 2 | ||||
-rw-r--r-- | sources/scala/Ord.scala | 19 | ||||
-rw-r--r-- | sources/scala/Stream.scala | 10 | ||||
-rw-r--r-- | sources/scala/StructuralEquality.scala | 41 | ||||
-rw-r--r-- | sources/scala/Symbol.scala | 20 | ||||
-rw-r--r-- | sources/scala/collection/Map.scala | 100 | ||||
-rw-r--r-- | sources/scala/collection/Set.scala | 45 | ||||
-rw-r--r-- | sources/scala/collection/immutable/Queue.scala | 163 | ||||
-rw-r--r-- | sources/scala/collection/immutable/Stack.scala | 8 |
11 files changed, 317 insertions, 121 deletions
diff --git a/sources/scala/Cell.scala b/sources/scala/Cell.scala index 8336704eb7..8a5146a3a3 100644 --- a/sources/scala/Cell.scala +++ b/sources/scala/Cell.scala @@ -1,2 +1,20 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + package scala; + + +/** A <code>Cell</code> is a generic wrapper which completely + * hides the functionality of the wrapped object. The wrapped + * object is accessible via the <code>elem</code> accessor method. + * + * @author Martin Odersky + * @version 1.0, 08/08/2003 + */ case class Cell[+T](elem: T); diff --git a/sources/scala/Iterator.scala b/sources/scala/Iterator.scala index adcc2cf746..58b2c399fa 100644 --- a/sources/scala/Iterator.scala +++ b/sources/scala/Iterator.scala @@ -65,6 +65,18 @@ trait Iterator[+a] with Iterable[a] { def foreach(f: a => Unit): Unit = while (hasNext) { f(next) } + def forall(p: a => Boolean): Boolean = { + var res = true; + while (res && hasNext) { res = p(next); } + res; + } + + def exists(p: a => Boolean): Boolean = { + var res = false; + while (!res && hasNext) { res = p(next); } + res; + } + def take(n: Int) = new Iterator[a] { var remaining = n; def hasNext = remaining > 0 && Iterator.this.hasNext; diff --git a/sources/scala/List.scala b/sources/scala/List.scala index a952b05ac5..cda726f112 100644 --- a/sources/scala/List.scala +++ b/sources/scala/List.scala @@ -71,7 +71,7 @@ object List { * @author Martin Odersky * @version 1.0, 16/07/2003 */ -trait List[+a] extends Seq[a] { +trait List[+a] extends Seq[a] with StructuralEquality[List[a]] { /** Tests if this list is empty. * @return true, iff the list contains no element. diff --git a/sources/scala/Ord.scala b/sources/scala/Ord.scala index bfe845c615..aa55504c39 100644 --- a/sources/scala/Ord.scala +++ b/sources/scala/Ord.scala @@ -1,3 +1,12 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + package scala; trait Ord[t <: Ord[t]]: t { @@ -6,3 +15,13 @@ trait Ord[t <: Ord[t]]: t { def > (that: t): Boolean = that < this; def >=(that: t): Boolean = that <= this; } + +/* Shall we use a covariant Ord? + +trait Ord[+T <: Ord[T]] { + def < [S >: T <: Ord[S]](that: S): Boolean; + def <=[S >: T <: Ord[S]](that: S): Boolean = this < that || this == that; + def > [S >: T <: Ord[S]](that: S): Boolean = that < this; + def >=[S >: T <: Ord[S]](that: S): Boolean = that <= this; +} +*/ diff --git a/sources/scala/Stream.scala b/sources/scala/Stream.scala index aa7fe82db7..6fe7ab1aa5 100644 --- a/sources/scala/Stream.scala +++ b/sources/scala/Stream.scala @@ -1,5 +1,15 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + package scala; + trait Stream[+a] extends Seq[a] { def isEmpty: Boolean; diff --git a/sources/scala/StructuralEquality.scala b/sources/scala/StructuralEquality.scala new file mode 100644 index 0000000000..38e0b6a44c --- /dev/null +++ b/sources/scala/StructuralEquality.scala @@ -0,0 +1,41 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + +package scala; + + +/** Collection classes supporting this trait provide a method + * <code>elements</code> which returns an iterator over all the + * elements contained in the collection. + * + * @author Matthias Zenger + * @version 1.0, 16/07/2003 + */ +trait StructuralEquality[+A <: StructuralEquality[A]] { + + /** Compares this object with the provided object structurally; + * i.e. by looking at the internal structure of aggregated objects. + * <code>===</code> does not have to be compatible with the + * <code>hashCode</code> method. + * + * @param that the other object + * @returns true, iff <code>this</code> and <code>that</code> are + * structurally equivalent. + */ + def ===[B >: A](that: B): Boolean = (this == that); + + /** Compares this object with the provided object structurally + * and returns true, iff the two objects differ. + * + * @param that the other object + * @returns false, iff <code>this</code> and <code>that</code> are + * structurally equivalent. + */ + def !==[B >: A](that: B): Boolean = !(this === that); +} diff --git a/sources/scala/Symbol.scala b/sources/scala/Symbol.scala index a02abaffa3..7df7099ae1 100644 --- a/sources/scala/Symbol.scala +++ b/sources/scala/Symbol.scala @@ -1,6 +1,24 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +** $Id$ +\* */ + package scala; + +/** Instances of <code>Symbol</code> can be created easily with + * Scala's built-in quote mechanism. For instance, the Scala term + * <code>'mysym</code> will invoke the constructor of the + * <code>Symbol</code> class in the following way: + * <code>new Symbol("mysym")</code>. + * + * @author Martin Odersky + * @version 1.0, 08/08/2003 + */ case class Symbol(name: String) { override def toString() = "'" + name; } - diff --git a/sources/scala/collection/Map.scala b/sources/scala/collection/Map.scala index f478146190..14c2f3ef1a 100644 --- a/sources/scala/collection/Map.scala +++ b/sources/scala/collection/Map.scala @@ -25,38 +25,83 @@ package scala.collection; * @version 1.0, 08/07/2003 */ trait Map[A, +B] with PartialFunction[A, B] - with Iterable[Pair[A, B]] { + with Iterable[Pair[A, B]] + with StructuralEquality[Map[A, B]]{ + /** Compute the number of key-to-value mappings. + * + * @returns the number of mappings + */ def size: Int; + /** Check if this map maps <code>key</code> to a value and return the + * value if it exists. + * + * @param key the key of the mapping of interest + * @returns the value of the mapping, if it exists + */ def get(key: A): Option[B]; + /** Is this an empty map? + * + * @returns true, iff the map is empty. + */ def isEmpty: Boolean = (size == 0); + /** Retrieve the value which is associated with the given key. This + * method throws an exception if there is no mapping from the given + * key to a value. + * + * @param key the key + * @returns the value associated with the given key. + */ def apply(key: A): B = get(key) match { case None => error("key not found") case Some(value) => value } + /** Is the given key mapped to a value by this map? + * + * @param key the key + * @returns true, iff there is a mapping for key in this map + */ def contains(key: A): Boolean = get(key) match { case None => false case Some(_) => true } + /** Does this map contain a mapping from the given key to a value? + * + * @param key the key + * @returns true, iff there is a mapping for key in this map + */ def isDefinedAt(key: A) = contains(key); + /** Creates an iterator for all keys. + * + * @returns an iterator over all keys. + */ def keys: Iterator[A] = new Iterator[A] { val iter = Map.this.elements; def hasNext = iter.hasNext; def next = iter.next._1; } + /** Creates an iterator for a contained values. + * + * @returns an iterator over all values. + */ def values: Iterator[B] = new Iterator[B] { val iter = Map.this.elements; def hasNext = iter.hasNext; def next = iter.next._2; } + /** Executes the given function for all (key, value) pairs + * contained in this map. + * + * @param f the function to execute. + */ def foreach(f: (A, B) => Unit) = { val iter = elements; while (iter.hasNext) { @@ -65,15 +110,60 @@ trait Map[A, +B] with PartialFunction[A, B] } } + /** Applies the given predicate to all (key, value) mappings + * contained in this map and returns true if this predicate + * yields true for all mappings. + * + * @param p the predicate + * @returns true, iff p yields true for all mappings. + */ + def forall(p: (A, B) => Boolean): Boolean = elements.forall { + case Pair(key, value) => p(key, value) + } + + /** Applies the given predicate to all (key, value) mappings + * contained in this map and returns true if there is at least + * one mapping for which this predicate yields true. + * + * @param p the predicate + * @returns true, iff there is at least one mapping for which + * p yields true. + */ + def exists(p: (A, B) => Boolean): Boolean = elements.exists { + case Pair(key, value) => p(key, value) + } + + /** Creates a list of all (key, value) mappings. + * + * @returns the list of all mappings + */ def toList: List[Pair[A, B]] = { var res: List[Pair[A, B]] = Nil; - val iter = elements; - while (iter.hasNext) { - res = iter.next :: res; - } + elements.foreach { mapping => res = mapping :: res; }; res; } + /** Compares two maps structurally; i.e. checks if all mappings + * contained in this map are also contained in the other map, + * and vice versa. + * + * @returns true, iff both maps contain exactly the same mappings. + */ + override def ===[C >: Map[A, B]](that: C): Boolean = + that.isInstanceOf[Map[A, B]] && + { val other = that.asInstanceOf[Map[A, B]]; + this.size == other.size && + this.elements.forall { + case Pair(key, value) => other.get(key) match { + case None => false; + case Some(otherval) => value == otherval; + } + }}; + + /** Creates a string representation for this map. + * + * @returns a string showing all mappings + */ override def toString() = if (size == 0) "{}" diff --git a/sources/scala/collection/Set.scala b/sources/scala/collection/Set.scala index 4e5b020167..76dd891f47 100644 --- a/sources/scala/collection/Set.scala +++ b/sources/scala/collection/Set.scala @@ -23,49 +23,36 @@ package scala.collection; * @author Matthias Zenger * @version 1.0, 08/07/2003 */ -trait Set[A] with Iterable[A] { +trait Set[A] with Iterable[A] + with StructuralEquality[Set[A]] { def size: Int; + def contains(elem: A): Boolean; + def isEmpty: Boolean = (size == 0); - def contains(elem: A): Boolean; + def subsetOf(that: Set[A]): Boolean = forall(that.contains); - def subsetOf(that: Set[A]): Boolean = { - val iter = elements; - var res = true; - while (res && iter.hasNext) { - res = that.contains(iter.next); - } - res - } + def foreach(f: A => Unit): Unit = elements.foreach(f); - def foreach(f: A => Unit): Unit = { - val iter = elements; - while (iter.hasNext) { - f(iter.next); - } - } + def forall(p: A => Boolean): Boolean = elements.forall(p); - def exists(p: A => Boolean): Boolean = { - val iter = elements; - var res = false; - while (!res && iter.hasNext) { - if (p(iter.next)) { res = true; } - } - res; - } + def exists(p: A => Boolean): Boolean = elements.exists(p); def toList: List[A] = { var res: List[A] = Nil; - val iter = elements; - while (iter.hasNext) { - res = iter.next :: res; - } + elements.foreach { elem => res = elem :: res; } res; } - override def toString() = + override def ===[B >: Set[A]](that: B): Boolean = + that.isInstanceOf[Set[A]] && + { val other = that.asInstanceOf[Set[A]]; + this.size == other.size && + this.elements.forall(other.contains) }; + + override def toString(): String = if (size == 0) "{}" else diff --git a/sources/scala/collection/immutable/Queue.scala b/sources/scala/collection/immutable/Queue.scala index 99171e1497..a3291d46e4 100644 --- a/sources/scala/collection/immutable/Queue.scala +++ b/sources/scala/collection/immutable/Queue.scala @@ -20,16 +20,19 @@ object Queue { val Empty:Queue[All] = new Queue(Nil, Nil); } -class Queue[+A](in:List[A],out:List[A]) extends Seq[A] { - /** Returns the <code>n</code>-th element of this queue. - * The first element is at position 0. - * @param n index of the element to return - * @return the element at position <code>n</code> in this list. - * @throws java.lang.RuntimeException if the list is too short. - */ +class Queue[+A](in: List[A], out: List[A]) extends Seq[A] + with StructuralEquality[Queue[A]] { + + /** Returns the <code>n</code>-th element of this queue. + * The first element is at position 0. + * + * @param n index of the element to return + * @return the element at position <code>n</code> in this list. + * @throws java.lang.RuntimeException if the list is too short. + */ def apply(n: Int): A = - if (n < out.length) out.apply(n) - else (in.reverse).apply(n - out.length); + if (n < out.length) out.apply(n) + else in.reverse.apply(n - out.length); /** Returns the elements in the list as an iterator */ @@ -50,9 +53,7 @@ class Queue[+A](in:List[A],out:List[A]) extends Seq[A] { * * @param elem the element to insert */ - def +[B >: A](elem: B):Queue[B] = { - new Queue(elem::in,out); - } + def +[B >: A](elem: B):Queue[B] = new Queue(elem::in,out); /** Returns a new que with all all elements provided by * an <code>Iterable</code> object added at the end of @@ -63,9 +64,9 @@ class Queue[+A](in:List[A],out:List[A]) extends Seq[A] { * @param iter an iterable object */ def +[B >: A](iter: Iterable[B]) = { - var q:List[B] = in; - iter.elements.foreach(e => q = (e::q)); - new Queue(q,out); + var q:List[B] = in; + iter.elements.foreach(e => q = (e::q)); + new Queue(q,out); } /** Returns a new queue with all elements added. @@ -80,81 +81,79 @@ class Queue[+A](in:List[A],out:List[A]) extends Seq[A] { * @returns the first element of the queue. */ def dequeue: Pair[A,Queue[A]] = { - var newOut:List[A]=Nil; - var newIn:List[A]=Nil; - if (out.isEmpty) { - newOut = in.reverse; - newIn = Nil; - } else { - newOut = out; - newIn = in; - } - if (newOut.isEmpty) - error("queue empty"); - else { + var newOut:List[A]=Nil; + var newIn:List[A]=Nil; + if (out.isEmpty) { + newOut = in.reverse; + newIn = Nil; + } else { + newOut = out; + newIn = in; + } + if (newOut.isEmpty) + error("queue empty"); + else Pair(newOut.head,new Queue(newIn,newOut.tail)); - } } - /** Returns the first element in the queue, or throws an error if there + /** Returns the first element in the queue, or throws an error if there * is no element contained in the queue. * * @returns the first element. */ - def front: A = { - if (out.isEmpty) { - if (in.isEmpty) { - error("queue empty"); - } else {in.last;} - } else - out.head; - } + def front: A = + if (out.isEmpty) { + if (in.isEmpty) error("queue empty") else in.last; + } else + out.head; + + /** Returns a string representation of this queue. The resulting string + * begins with the string <code>start</code> and is finished by the string + * <code>end</code>. Inside, the string representations of elements (w.r.t. + * the method <code>toString()</code>) are separated by the string + * <code>sep</code>. + * <p> + * Ex: <br> + * <code>Queue(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code> + * @param start starting string. + * @param sep separator string. + * @param end ending string. + * @return a string representation of this list. + */ + def mkString(start: String, sep: String, end: String): String = + (out ::: (in.reverse)).mkString(start,sep,end); - /** Returns a string representation of this queue. The resulting string - * begins with the string <code>start</code> and is finished by the string - * <code>end</code>. Inside, the string representations of elements (w.r.t. - * the method <code>toString()</code>) are separated by the string - * <code>sep</code>. - * <p> - * Ex: <br> - * <code>Queue(1, 2, 3).mkString("(", "; ", ")") = "(1; 2; 3)"</code> - * @param start starting string. - * @param sep separator string. - * @param end ending string. - * @return a string representation of this list. - */ - def mkString(start: String, sep: String, end: String): String = - (out:::(in.reverse)).mkString(start,sep,end); - - /** Returns a string representation of this queue. - */ - override def toString() = (out:::(in.reverse)).mkString("Queue(", ",", ")"); - - /** Compares two queues for equality by comparing - * each element in the queues. - */ - override def equals(o :Any) = o match { - case q: Queue[Any] => - /* A function that compares the element at - position index in q with the element at - the same position in this (queue). - If they are equal the next element is - compared. */ - def eqe(index: int):Boolean = { - /* If all elements are compared - the queues are equal. */ - index >= this.length || - /* Otherwise: compare the elements */ - (q.apply(index) == this.apply(index) && - /* if they are equal compare the rest. */ - eqe(index+1)) - } - /* If the length of the ques are the same, - compare each element, starting at index 0. */ - (q.length == this.length) && eqe(0); - - case _ => false; /* o is not a queue: not equal to this. */ - } + /** Returns a string representation of this queue. + */ + override def toString() = (out ::: (in.reverse)).mkString("Queue(", ",", ")"); + + /** Compares two queues for equality by comparing + * each element in the queues. + * + * @returns true, iff the two queues are structurally equal. + */ + override def equals(o: Any): Boolean = o match { + case q: Queue[Any] => + /* A function that compares the element at + position index in q with the element at + the same position in this (queue). + If they are equal the next element is + compared. */ + def eqe(index: int):Boolean = { + /* If all elements are compared + the queues are equal. */ + index >= this.length || + /* Otherwise: compare the elements */ + (q.apply(index) == this.apply(index) && + /* if they are equal compare the rest. */ + eqe(index+1)) + } + /* If the length of the ques are the same, + compare each element, starting at index 0. */ + (q.length == this.length) && eqe(0); + + case _ => false; /* o is not a queue: not equal to this. */ + } } diff --git a/sources/scala/collection/immutable/Stack.scala b/sources/scala/collection/immutable/Stack.scala index fdb9b03b37..1c63d3d69d 100644 --- a/sources/scala/collection/immutable/Stack.scala +++ b/sources/scala/collection/immutable/Stack.scala @@ -22,7 +22,7 @@ object Stack { * @author Matthias Zenger * @version 1.0, 10/07/2003 */ -class Stack[+A] with Seq[A] { +class Stack[+A] with Seq[A] with StructuralEquality[Stack[A]] { /** Checks if this stack is empty. * @@ -105,8 +105,10 @@ class Stack[+A] with Seq[A] { * same elements in the same order. */ override def equals(obj: Any): Boolean = - if (obj is Stack[A]) toList.equals((obj as Stack[A]).toList); - else false; + if (obj.isInstanceOf[Stack[A]]) + toList.equals((obj.asInstanceOf[Stack[A]]).toList); + else + false; /** Returns the hash code for this stack. * |