diff options
author | Paul Phillips <paulp@improving.org> | 2009-09-09 03:19:07 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2009-09-09 03:19:07 +0000 |
commit | d4716791267b2f39ebb746e142de773f173c7198 (patch) | |
tree | f114b437ae9addb325874f4376acdb20b734477b /src | |
parent | 39023c4346f1940289c7cd663b7dd382ca7c6f0e (diff) | |
download | scala-d4716791267b2f39ebb746e142de773f173c7198.tar.gz scala-d4716791267b2f39ebb746e142de773f173c7198.tar.bz2 scala-d4716791267b2f39ebb746e142de773f173c7198.zip |
Created plausibly sensible equals and hashCode ...
Created plausibly sensible equals and hashCode methods in
collection.{ Set, Map, Sequence } and made sure that none
of the derived collections is getting too excited about doing
its own thing and in so doing either breaking equals/hashCode
consistency or creating an asymmetric equals (or both.)
Diffstat (limited to 'src')
18 files changed, 65 insertions, 133 deletions
diff --git a/src/library/scala/collection/Sequence.scala b/src/library/scala/collection/Sequence.scala index b0c507f088..9fb39c0cae 100644 --- a/src/library/scala/collection/Sequence.scala +++ b/src/library/scala/collection/Sequence.scala @@ -35,7 +35,9 @@ trait Sequence[+A] extends PartialFunction[Int, A] override def companion: Companion[Sequence] = Sequence } -object Sequence extends SequenceFactory[Sequence] { +object Sequence extends SequenceFactory[Sequence] +{ + private[collection] val hashSeed = "Sequence".hashCode implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Sequence[A]] = immutable.Sequence.newBuilder[A] diff --git a/src/library/scala/collection/Set.scala b/src/library/scala/collection/Set.scala index 05124bf712..a5147b992e 100644 --- a/src/library/scala/collection/Set.scala +++ b/src/library/scala/collection/Set.scala @@ -32,18 +32,3 @@ object Set extends SetFactory[Set] { override def empty[A]: Set[A] = immutable.Set.empty[A] implicit def builderFactory[A]: BuilderFactory[A, Set[A], Coll] = setBuilderFactory[A] } - -/* !!! what to do about this? -override def hashCode() = - (0 /: this)((hash, e) => hash + e.hashCode()) - - override def toArray[B >: A]: Array[B] = { - val result = new Array[B](size) - copyToArray(result, 0) - result - } - - /** Defines the prefix of this object's <code>toString</code> representation. - */ - override protected def stringPrefix : String = "Set" -*/ diff --git a/src/library/scala/collection/generic/IterableTemplate.scala b/src/library/scala/collection/generic/IterableTemplate.scala index acdbc695d2..35210e036d 100644 --- a/src/library/scala/collection/generic/IterableTemplate.scala +++ b/src/library/scala/collection/generic/IterableTemplate.scala @@ -274,6 +274,8 @@ trait IterableTemplate[+A, +This <: IterableTemplate[A, This] with Iterable[A]] */ override def view(from: Int, until: Int) = view.slice(from, until) + protected def anyEq(that: Any) = this eq that.asInstanceOf[AnyRef] + @deprecated("use `head' instead") def first: A = head /** <code>None</code> if traversable is empty. */ diff --git a/src/library/scala/collection/generic/LinearSequenceTemplate.scala b/src/library/scala/collection/generic/LinearSequenceTemplate.scala index 002ab6130e..1e667f1e10 100644 --- a/src/library/scala/collection/generic/LinearSequenceTemplate.scala +++ b/src/library/scala/collection/generic/LinearSequenceTemplate.scala @@ -372,9 +372,4 @@ trait LinearSequenceTemplate[+A, +This <: LinearSequenceTemplate[A, This] with L } last } - - override def equals(that: Any): Boolean = that match { - case that: LinearSequence[_] => this sameElements that - case _ => super.equals(that) - } } diff --git a/src/library/scala/collection/generic/MapTemplate.scala b/src/library/scala/collection/generic/MapTemplate.scala index 5ad959ae60..9d441028d7 100644 --- a/src/library/scala/collection/generic/MapTemplate.scala +++ b/src/library/scala/collection/generic/MapTemplate.scala @@ -8,9 +8,10 @@ // $Id$ - package scala.collection.generic + import scala.collection._ +import PartialFunction._ /** <p> * A generic template for maps from keys of type <code>A</code> to values @@ -254,6 +255,17 @@ self => override def addString(b: StringBuilder, start: String, sep: String, end: String): StringBuilder = this.iterator.map { case (k, v) => k+" -> "+v }.addString(b, start, sep, end) + /** Defines the prefix of this object's <code>toString</code> representation. + */ + override def stringPrefix: String = "Map" + + /** Need to override string, so that it's not the Function1's string that gets mixed in. + */ + override def toString = super[IterableTemplate].toString + + override def hashCode() = this map (_.hashCode) sum + override def canEqualCollection(that: Any) = that.isInstanceOf[Map[_, _]] + /** Compares two maps structurally; i.e. checks if all mappings * contained in this map are also contained in the other map, * and vice versa. @@ -262,28 +274,10 @@ self => * @return <code>true</code> iff both maps contain exactly the * same mappings. */ - override def equals(that: Any): Boolean = that match { - case other: Map[a, b] => - if (this.size == other.size) - try { // can we find a safer way to do this? - this forall { - case (key, value) => other.get(key.asInstanceOf[a]) match { - case None => false - case Some(otherval) => value == otherval - } - } - } catch { - case ex: ClassCastException => false - } - else false - case _ => false - } - - /** Defines the prefix of this object's <code>toString</code> representation. - */ - override def stringPrefix: String = "Map" - - /** Need to override string, so that it's not the Function1's string that gets mixed in. - */ - override def toString = super[IterableTemplate].toString + override def equals(that: Any): Boolean = + anyEq(that) || (cond(that) { + case x: Map[A, _] if x.canEqualCollection(this) && size == x.size => + try this forall { case (k, v) => x.get(k.asInstanceOf[A]) == Some(v) } + catch { case ex: ClassCastException => false } + }) } diff --git a/src/library/scala/collection/generic/SequenceTemplate.scala b/src/library/scala/collection/generic/SequenceTemplate.scala index 7c88e0b404..9b919375fe 100644 --- a/src/library/scala/collection/generic/SequenceTemplate.scala +++ b/src/library/scala/collection/generic/SequenceTemplate.scala @@ -16,6 +16,7 @@ import mutable.{ListBuffer, HashMap} // import immutable.{List, Nil, ::} import generic._ +import PartialFunction._ /** Class <code>Sequence[A]</code> represents sequences of elements * of type <code>A</code>. @@ -440,15 +441,17 @@ trait SequenceTemplate[+A, +This <: SequenceTemplate[A, This] with Sequence[A]] override def view(from: Int, until: Int) = view.slice(from, until) - override def equals(that: Any): Boolean = that match { - case that: Sequence[_] => this sameElements that - case _ => false - } - /** Need to override string, so that it's not the Function1's string that gets mixed in. */ override def toString = super[IterableTemplate].toString + override def hashCode() = (Sequence.hashSeed /: this)(_ * 41 + _.hashCode) + override def canEqualCollection(that: Any) = that.isInstanceOf[Sequence[_]] + override def equals(that: Any): Boolean = + anyEq(that) || (cond(that) { + case x: Sequence[_] if (x canEqualCollection this) => this sameElements x + }) + /** Returns index of the last element satisying a predicate, or -1. */ @deprecated("use `lastIndexWhere' instead") def findLastIndexOf(p: A => Boolean): Int = lastIndexWhere(p) diff --git a/src/library/scala/collection/generic/SetTemplate.scala b/src/library/scala/collection/generic/SetTemplate.scala index e7f93e2701..9a11283641 100644 --- a/src/library/scala/collection/generic/SetTemplate.scala +++ b/src/library/scala/collection/generic/SetTemplate.scala @@ -10,6 +10,7 @@ package scala.collection.generic import scala.collection._ +import PartialFunction._ /** <p> * A generic template for sets of type <code>A</code>.<br/> @@ -153,6 +154,18 @@ self => */ def subsetOf(that: Set[A]): Boolean = forall(that.contains) + /** Defines the prefix of this object's <code>toString</code> representation. + */ + override def stringPrefix: String = "Set" + + /** Need to override string, so that it's not the Function1's string that gets mixed in. + */ + override def toString = super[IterableTemplate].toString + + // override def hashCode() = (this map (_.hashCode)).foldLeft(0)(_ + _) + override def hashCode() = this map (_.hashCode) sum + override def canEqualCollection(that: Any) = that.isInstanceOf[Set[_]] + /** Compares this set with another object and returns true, iff the * other object is also a set which contains the same elements as * this set. @@ -162,27 +175,10 @@ self => * @return <code>true</code> iff this set and the other set * contain the same elements. */ - override def equals(that: Any): Boolean = that match { - case other: Set[_] => - if (this.size == other.size) - try { // can we find a safer way to do this? - subsetOf(other.asInstanceOf[Set[A]]) - } catch { - case ex: ClassCastException => false - } - else false - case _ => - false - } - - /** Defines the prefix of this object's <code>toString</code> representation. - */ - override def stringPrefix: String = "Set" - - /** Need to override string, so that it's not the Function1's string that gets mixed in. - */ - override def toString = super[IterableTemplate].toString + override def equals(that: Any): Boolean = anyEq(that) || (cond(that) { + case x: Set[A] if (x canEqualCollection this) && size == x.size => + // can we find a safer way to do this? + try this subsetOf x.asInstanceOf[Set[A]] + catch { case ex: ClassCastException => false } + }) } - - - diff --git a/src/library/scala/collection/generic/TraversableTemplate.scala b/src/library/scala/collection/generic/TraversableTemplate.scala index 10cb92916e..3f99a17132 100644 --- a/src/library/scala/collection/generic/TraversableTemplate.scala +++ b/src/library/scala/collection/generic/TraversableTemplate.scala @@ -819,6 +819,8 @@ self => override def toString = mkString(stringPrefix + "(", ", ", ")") + def canEqualCollection(other: Any) = true + /** Defines the prefix of this object's <code>toString</code> representation. */ def stringPrefix : String = { diff --git a/src/library/scala/collection/generic/VectorTemplate.scala b/src/library/scala/collection/generic/VectorTemplate.scala index c56076de37..19e6cfb19c 100644 --- a/src/library/scala/collection/generic/VectorTemplate.scala +++ b/src/library/scala/collection/generic/VectorTemplate.scala @@ -260,7 +260,7 @@ trait VectorTemplate[+A, +This <: VectorTemplate[A, This] with Vector[A]] extend super.endsWith(that) } - + // only optimization override def equals(that: Any): Boolean = that match { case that: Vector[_] => this.length == that.length && startsWith(that, 0) case _ => super.equals(that) diff --git a/src/library/scala/collection/immutable/IntMap.scala b/src/library/scala/collection/immutable/IntMap.scala index 88e17ea09b..19ebbdfac4 100644 --- a/src/library/scala/collection/immutable/IntMap.scala +++ b/src/library/scala/collection/immutable/IntMap.scala @@ -44,8 +44,11 @@ object IntMap{ def apply[T](elems : (Int, T)*) : IntMap[T] = elems.foldLeft(empty[T])((x, y) => x.updated(y._1, y._2)); - - private[immutable] case object Nil extends IntMap[Nothing]{ + private[immutable] case object Nil extends IntMap[Nothing] { + // Important! Without this equals method in place, an infinite + // loop from Map.equals => size => pattern-match-on-Nil => equals + // develops. Case objects and custom equality don't mix without + // careful handling. override def equals(that : Any) = that match { case (that : AnyRef) if (this eq that) => true; case (that : IntMap[_]) => false; // The only empty IntMaps are eq Nil diff --git a/src/library/scala/collection/immutable/LongMap.scala b/src/library/scala/collection/immutable/LongMap.scala index e1758d11a7..2be51e7577 100644 --- a/src/library/scala/collection/immutable/LongMap.scala +++ b/src/library/scala/collection/immutable/LongMap.scala @@ -45,8 +45,8 @@ object LongMap{ def apply[T](elems : (Long, T)*) : LongMap[T] = elems.foldLeft(empty[T])((x, y) => x.updated(y._1, y._2)); - - private[immutable] case object Nil extends LongMap[Nothing]{ + private[immutable] case object Nil extends LongMap[Nothing] { + // Important, don't remove this! See IntMap for explanation. override def equals(that : Any) = that match { case (that : AnyRef) if (this eq that) => true; case (that : LongMap[_]) => false; // The only empty LongMaps are eq Nil diff --git a/src/library/scala/collection/immutable/Map.scala b/src/library/scala/collection/immutable/Map.scala index 5b3bbc91b4..1117496b81 100644 --- a/src/library/scala/collection/immutable/Map.scala +++ b/src/library/scala/collection/immutable/Map.scala @@ -27,11 +27,6 @@ trait Map[A, +B] extends Iterable[(A, B)] override def updated [B1 >: B](key: A, value: B1): Map[A, B1] def + [B1 >: B](kv: (A, B1)): Map[A, B1] - /** A hash method compatible with <code>equals</code> - */ - override def hashCode() = - (Map.hashSeed /: this) (_ * 41 + _.hashCode) - /** The same map with a given default function !!! todo: move to general maps? */ def withDefault[B1 >: B](d: A => B1): Map[A, B1] = new Map.WithDefault[A, B1](this, d) @@ -40,7 +35,6 @@ trait Map[A, +B] extends Iterable[(A, B)] } object Map extends ImmutableMapFactory[Map] { - private val hashSeed = "Map".hashCode implicit def builderFactory[A, B]: BuilderFactory[(A, B), Map[A, B], Coll] = new MapBuilderFactory[A, B] def empty[A, B]: Map[A, B] = new EmptyMap[A, B] diff --git a/src/library/scala/collection/immutable/Queue.scala b/src/library/scala/collection/immutable/Queue.scala index 1ba58f8df0..0daa31af77 100644 --- a/src/library/scala/collection/immutable/Queue.scala +++ b/src/library/scala/collection/immutable/Queue.scala @@ -127,18 +127,4 @@ class Queue[+A] protected( /** Returns a string representation of this queue. */ override def toString() = mkString("Queue(", ", ", ")") - - /** Compares two queues for equality by comparing - * each element in the queues. - * - * @return true, iff the two queues are structurally equal. - */ - override def equals(o: Any): Boolean = o match { - case q: Queue[_] => this sameElements q - case _ => false - } - - override lazy val hashCode: Int = - if (isEmpty) 0 - else dequeue match { case (x,y) => x.hashCode + y.hashCode } } diff --git a/src/library/scala/collection/immutable/Sequence.scala b/src/library/scala/collection/immutable/Sequence.scala index b58f8e16cf..7663b9c3ce 100644 --- a/src/library/scala/collection/immutable/Sequence.scala +++ b/src/library/scala/collection/immutable/Sequence.scala @@ -18,12 +18,9 @@ trait Sequence[+A] extends Iterable[A] with TraversableClass[A, Sequence] with SequenceTemplate[A, Sequence[A]] { override def companion: Companion[Sequence] = Sequence - - override def hashCode = (Sequence.hashSeed /: this)(_ * 41 + _.hashCode) } object Sequence extends SequenceFactory[Sequence] { - private val hashSeed = "Sequence".hashCode implicit def builderFactory[A]: BuilderFactory[A, Sequence[A], Coll] = new VirtualBuilderFactory[A] def newBuilder[A]: Builder[A, Sequence[A]] = new mutable.ListBuffer } diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala index e03c232850..e9e492baa4 100644 --- a/src/library/scala/collection/immutable/Set.scala +++ b/src/library/scala/collection/immutable/Set.scala @@ -35,7 +35,6 @@ trait Set[A] extends Iterable[A] with SetClass[A, Set] with SetTemplate[A, Set[A]] { override def companion: Companion[Set] = Set - override def hashCode = (Set.hashSeed /: this)(_ * 41 + _.hashCode) } object Set extends SetFactory[Set] { diff --git a/src/library/scala/collection/immutable/TreeHashMap.scala b/src/library/scala/collection/immutable/TreeHashMap.scala index 76ce1ab16e..0310088ccd 100644 --- a/src/library/scala/collection/immutable/TreeHashMap.scala +++ b/src/library/scala/collection/immutable/TreeHashMap.scala @@ -59,18 +59,6 @@ class TreeHashMap[Key, +Value] private (private val underlying : IntMap[AssocMap override lazy val size = underlying.values.foldLeft(0)((x, y) => x + y.size); - // todo: probably drop to make conform with general equals/hashcode policy - override def equals(that : Any) = that match { - case (that : TreeHashMap[_, _]) => - if (this eq that) true - else if (this.size != that.size) false; - else this.underlying == that.underlying; - case _ => false - } - - // todo: probably drop to make conform with general equals/hashcode policy - override def hashCode = underlying.hashCode - override def foreach[U](f : ((Key, Value)) => U) = underlying.foreachValue(_.foreach(f)); override def toList : List[(Key, Value)] = { @@ -223,15 +211,6 @@ private[collection] sealed abstract class AssocMap[Key, +Value] extends immutabl } } - override def equals(that : Any) = - if (this eq that.asInstanceOf[AnyRef]) true; - else that match { - case (that : AssocMap[_, _]) => - if (this.size != that.size) false; - else this.sameMappings(that); - case _ => false; - } - final def merge[S >: Value](that : AssocMap[Key, S]) : AssocMap[Key, S] = (this, that) match { case (Nil(), that) => that; case (_, Nil()) => this; diff --git a/src/library/scala/collection/mutable/ObjectArrayVector.scala b/src/library/scala/collection/mutable/ObjectArrayVector.scala index aee89a3cb4..48cfb204d3 100755 --- a/src/library/scala/collection/mutable/ObjectArrayVector.scala +++ b/src/library/scala/collection/mutable/ObjectArrayVector.scala @@ -29,14 +29,5 @@ final class ObjectArrayVector[A <: AnyRef](val value: Array[AnyRef], val elemMan } def unbox(elemClass: Class[_]): AnyRef = value - -/* - override def equals(other: Any): Boolean = - (value eq other.asInstanceOf[AnyRef]) || - other.isInstanceOf[ObjectArrayVector[_]] && (value eq other.asInstanceOf[ObjectArrayVector[_]].value) - - override def hashCode(): Int = (value.asInstanceOf[AnyRef]).hashCode() -*/ - } diff --git a/src/library/scala/collection/mutable/PriorityQueue.scala b/src/library/scala/collection/mutable/PriorityQueue.scala index b1bc75f762..0e2d8cf7f6 100644 --- a/src/library/scala/collection/mutable/PriorityQueue.scala +++ b/src/library/scala/collection/mutable/PriorityQueue.scala @@ -160,6 +160,10 @@ class PriorityQueue[A](implicit ord: Ordering[A]) * * @return true, iff both queues contain the same sequence of elements. */ + override def canEqualCollection(that: Any) = that.isInstanceOf[PriorityQueue[_]] + // !!! At this writing this is the only sequence which imposes stricter + // equality requirements, if there is some logic behind this we should + // document it. override def equals(obj: Any): Boolean = obj match { case that: PriorityQueue[_] => (this.iterator zip that.iterator) forall { case (x, y) => x == y } case _ => false |