From 42acd55bf9aba878254849c3d07ab78f3bcd2f3d Mon Sep 17 00:00:00 2001 From: dk14 Date: Tue, 6 Oct 2015 21:39:50 +0700 Subject: explicitly specify insertion-order feature in docs --- src/library/scala/collection/immutable/ListMap.scala | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/library') diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala index 7c40e84280..1eedf93269 100644 --- a/src/library/scala/collection/immutable/ListMap.scala +++ b/src/library/scala/collection/immutable/ListMap.scala @@ -32,7 +32,7 @@ object ListMap extends ImmutableMapFactory[ListMap] { private object EmptyListMap extends ListMap[Any, Nothing] { } } -/** This class implements immutable maps using a list-based data structure. +/** This class implements immutable maps using a list-based data structure, which preserves insertion order. * Instances of `ListMap` represent empty maps; they can be either created by * calling the constructor directly, or by applying the function `ListMap.empty`. * -- cgit v1.2.3 From b19a07ed15f8a633e0463e52839c956963a9c2f9 Mon Sep 17 00:00:00 2001 From: Janek Bogucki Date: Wed, 7 Oct 2015 20:32:49 +0100 Subject: Rename forall, exists and find predicate and operator params. Align parameters names to use p for predicates and op for combining operations. Based on #4760. Extended to include, - Tuple2Zipped - Tuple3Zipped - Either The original author was vsalvis. --- .../scala/collection/GenTraversableOnce.scala | 23 +++++-- .../scala/collection/LinearSeqOptimized.scala | 8 +-- src/library/scala/collection/TraversableLike.scala | 2 +- .../scala/collection/immutable/RedBlackTree.scala | 4 +- src/library/scala/collection/immutable/Set.scala | 74 +++++++++++----------- .../collection/parallel/ParIterableLike.scala | 18 +++--- src/library/scala/runtime/Tuple2Zipped.scala | 8 +-- src/library/scala/runtime/Tuple3Zipped.scala | 8 +-- src/library/scala/util/Either.scala | 12 ++-- 9 files changed, 86 insertions(+), 71 deletions(-) (limited to 'src/library') diff --git a/src/library/scala/collection/GenTraversableOnce.scala b/src/library/scala/collection/GenTraversableOnce.scala index f77462ce88..a45ec965f5 100644 --- a/src/library/scala/collection/GenTraversableOnce.scala +++ b/src/library/scala/collection/GenTraversableOnce.scala @@ -393,20 +393,35 @@ trait GenTraversableOnce[+A] extends Any { */ def minBy[B](f: A => B)(implicit cmp: Ordering[B]): A - def forall(pred: A => Boolean): Boolean + /** Tests whether a predicate holds for all elements of this $coll. + * + * $mayNotTerminateInf + * + * @param p the predicate used to test elements. + * @return `true` if this $coll is empty or the given predicate `p` + * holds for all elements of this $coll, otherwise `false`. + */ + def forall(@deprecatedName('pred) p: A => Boolean): Boolean - def exists(pred: A => Boolean): Boolean + /** Tests whether a predicate holds for at least one element of this $coll. + * + * $mayNotTerminateInf + * + * @param p the predicate used to test elements. + * @return `true` if the given predicate `p` is satisfied by at least one element of this $coll, otherwise `false` + */ + def exists(@deprecatedName('pred) p: A => Boolean): Boolean /** Finds the first element of the $coll satisfying a predicate, if any. * * $mayNotTerminateInf * $orderDependent * - * @param pred the predicate used to test elements. + * @param p the predicate used to test elements. * @return an option value containing the first element in the $coll * that satisfies `p`, or `None` if none exists. */ - def find(pred: A => Boolean): Option[A] + def find(@deprecatedName('pred) p: A => Boolean): Option[A] /** Copies values of this $coll to an array. * Fills the given array `xs` with values of this $coll. diff --git a/src/library/scala/collection/LinearSeqOptimized.scala b/src/library/scala/collection/LinearSeqOptimized.scala index 9c336e8e31..b426061537 100644 --- a/src/library/scala/collection/LinearSeqOptimized.scala +++ b/src/library/scala/collection/LinearSeqOptimized.scala @@ -117,20 +117,20 @@ trait LinearSeqOptimized[+A, +Repr <: LinearSeqOptimized[A, Repr]] extends Linea } override /*TraversableLike*/ - def foldLeft[B](z: B)(f: (B, A) => B): B = { + def foldLeft[B](z: B)(@deprecatedName('f) op: (B, A) => B): B = { var acc = z var these = this while (!these.isEmpty) { - acc = f(acc, these.head) + acc = op(acc, these.head) these = these.tail } acc } override /*IterableLike*/ - def foldRight[B](z: B)(f: (A, B) => B): B = + def foldRight[B](z: B)(@deprecatedName('f) op: (A, B) => B): B = if (this.isEmpty) z - else f(head, tail.foldRight(z)(f)) + else op(head, tail.foldRight(z)(op)) override /*TraversableLike*/ def reduceLeft[B >: A](f: (B, A) => B): B = diff --git a/src/library/scala/collection/TraversableLike.scala b/src/library/scala/collection/TraversableLike.scala index 96374ef653..04ae8c8aff 100644 --- a/src/library/scala/collection/TraversableLike.scala +++ b/src/library/scala/collection/TraversableLike.scala @@ -357,7 +357,7 @@ trait TraversableLike[+A, +Repr] extends Any result } - /** Tests whether a predicate holds for some of the elements of this $coll. + /** Tests whether a predicate holds for at least one element of this $coll. * * $mayNotTerminateInf * diff --git a/src/library/scala/collection/immutable/RedBlackTree.scala b/src/library/scala/collection/immutable/RedBlackTree.scala index 7e8cfcc902..afb4c9c552 100644 --- a/src/library/scala/collection/immutable/RedBlackTree.scala +++ b/src/library/scala/collection/immutable/RedBlackTree.scala @@ -409,11 +409,11 @@ object RedBlackTree { def cons[B](x: B, xs: NList[B]): NList[B] = new NList(x, xs) - def foldLeft[A, B](xs: NList[A], z: B)(f: (B, A) => B): B = { + def foldLeft[A, B](xs: NList[A], z: B)(op: (B, A) => B): B = { var acc = z var these = xs while (these ne null) { - acc = f(acc, these.head) + acc = op(acc, these.head) these = these.tail } acc diff --git a/src/library/scala/collection/immutable/Set.scala b/src/library/scala/collection/immutable/Set.scala index a115469b83..031e5248c1 100644 --- a/src/library/scala/collection/immutable/Set.scala +++ b/src/library/scala/collection/immutable/Set.scala @@ -33,7 +33,7 @@ trait Set[A] extends Iterable[A] with Parallelizable[A, ParSet[A]] { override def companion: GenericCompanion[Set] = Set - + /** Returns this $coll as an immutable set, perhaps accepting a * wider range of elements. Since it already is an @@ -63,7 +63,7 @@ trait Set[A] extends Iterable[A] object Set extends ImmutableSetFactory[Set] { /** $setCanBuildFromInfo */ implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Set[A]] = setCanBuildFrom[A] - + /** An optimized representation for immutable empty sets */ private object EmptySet extends AbstractSet[Any] with Set[Any] with Serializable { override def size: Int = 0 @@ -71,7 +71,7 @@ object Set extends ImmutableSetFactory[Set] { def + (elem: Any): Set[Any] = new Set1(elem) def - (elem: Any): Set[Any] = this def iterator: Iterator[Any] = Iterator.empty - override def foreach[U](f: Any => U): Unit = {} + override def foreach[U](f: Any => U): Unit = () override def toSet[B >: Any]: Set[B] = this.asInstanceOf[Set[B]] } private[collection] def emptyInstance: Set[Any] = EmptySet @@ -90,17 +90,17 @@ object Set extends ImmutableSetFactory[Set] { else this def iterator: Iterator[A] = Iterator(elem1) - override def foreach[U](f: A => U): Unit = { + override def foreach[U](f: A => U): Unit = { f(elem1) } - override def exists(f: A => Boolean): Boolean = { - f(elem1) + override def exists(@deprecatedName('f) p: A => Boolean): Boolean = { + p(elem1) } - override def forall(f: A => Boolean): Boolean = { - f(elem1) + override def forall(@deprecatedName('f) p: A => Boolean): Boolean = { + p(elem1) } - override def find(f: A => Boolean): Option[A] = { - if (f(elem1)) Some(elem1) + override def find(@deprecatedName('f) p: A => Boolean): Option[A] = { + if (p(elem1)) Some(elem1) else None } // Why is Set1 non-final? Need to fix that! @@ -124,18 +124,18 @@ object Set extends ImmutableSetFactory[Set] { else this def iterator: Iterator[A] = Iterator(elem1, elem2) - override def foreach[U](f: A => U): Unit = { + override def foreach[U](f: A => U): Unit = { f(elem1); f(elem2) } - override def exists(f: A => Boolean): Boolean = { - f(elem1) || f(elem2) + override def exists(@deprecatedName('f) p: A => Boolean): Boolean = { + p(elem1) || p(elem2) } - override def forall(f: A => Boolean): Boolean = { - f(elem1) && f(elem2) + override def forall(@deprecatedName('f) p: A => Boolean): Boolean = { + p(elem1) && p(elem2) } - override def find(f: A => Boolean): Option[A] = { - if (f(elem1)) Some(elem1) - else if (f(elem2)) Some(elem2) + override def find(@deprecatedName('f) p: A => Boolean): Option[A] = { + if (p(elem1)) Some(elem1) + else if (p(elem2)) Some(elem2) else None } // Why is Set2 non-final? Need to fix that! @@ -159,19 +159,19 @@ object Set extends ImmutableSetFactory[Set] { else this def iterator: Iterator[A] = Iterator(elem1, elem2, elem3) - override def foreach[U](f: A => U): Unit = { + override def foreach[U](f: A => U): Unit = { f(elem1); f(elem2); f(elem3) } - override def exists(f: A => Boolean): Boolean = { - f(elem1) || f(elem2) || f(elem3) + override def exists(@deprecatedName('f) p: A => Boolean): Boolean = { + p(elem1) || p(elem2) || p(elem3) } - override def forall(f: A => Boolean): Boolean = { - f(elem1) && f(elem2) && f(elem3) + override def forall(@deprecatedName('f) p: A => Boolean): Boolean = { + p(elem1) && p(elem2) && p(elem3) } - override def find(f: A => Boolean): Option[A] = { - if (f(elem1)) Some(elem1) - else if (f(elem2)) Some(elem2) - else if (f(elem3)) Some(elem3) + override def find(@deprecatedName('f) p: A => Boolean): Option[A] = { + if (p(elem1)) Some(elem1) + else if (p(elem2)) Some(elem2) + else if (p(elem3)) Some(elem3) else None } // Why is Set3 non-final? Need to fix that! @@ -196,20 +196,20 @@ object Set extends ImmutableSetFactory[Set] { else this def iterator: Iterator[A] = Iterator(elem1, elem2, elem3, elem4) - override def foreach[U](f: A => U): Unit = { + override def foreach[U](f: A => U): Unit = { f(elem1); f(elem2); f(elem3); f(elem4) } - override def exists(f: A => Boolean): Boolean = { - f(elem1) || f(elem2) || f(elem3) || f(elem4) + override def exists(@deprecatedName('f) p: A => Boolean): Boolean = { + p(elem1) || p(elem2) || p(elem3) || p(elem4) } - override def forall(f: A => Boolean): Boolean = { - f(elem1) && f(elem2) && f(elem3) && f(elem4) + override def forall(@deprecatedName('f) p: A => Boolean): Boolean = { + p(elem1) && p(elem2) && p(elem3) && p(elem4) } - override def find(f: A => Boolean): Option[A] = { - if (f(elem1)) Some(elem1) - else if (f(elem2)) Some(elem2) - else if (f(elem3)) Some(elem3) - else if (f(elem4)) Some(elem4) + override def find(@deprecatedName('f) p: A => Boolean): Option[A] = { + if (p(elem1)) Some(elem1) + else if (p(elem2)) Some(elem2) + else if (p(elem3)) Some(elem3) + else if (p(elem4)) Some(elem4) else None } // Why is Set4 non-final? Need to fix that! diff --git a/src/library/scala/collection/parallel/ParIterableLike.scala b/src/library/scala/collection/parallel/ParIterableLike.scala index 016255dca4..e7b022b895 100644 --- a/src/library/scala/collection/parallel/ParIterableLike.scala +++ b/src/library/scala/collection/parallel/ParIterableLike.scala @@ -520,22 +520,22 @@ self: ParIterableLike[T, Repr, Sequential] => * * $abortsignalling * - * @param pred a predicate used to test elements + * @param p a predicate used to test elements * @return true if `p` holds for all elements, false otherwise */ - def forall(pred: T => Boolean): Boolean = { - tasksupport.executeAndWaitResult(new Forall(pred, splitter assign new DefaultSignalling with VolatileAbort)) + def forall(@deprecatedName('pred) p: T => Boolean): Boolean = { + tasksupport.executeAndWaitResult(new Forall(p, splitter assign new DefaultSignalling with VolatileAbort)) } /** Tests whether a predicate holds for some element of this $coll. * * $abortsignalling * - * @param pred a predicate used to test elements + * @param p a predicate used to test elements * @return true if `p` holds for some element, false otherwise */ - def exists(pred: T => Boolean): Boolean = { - tasksupport.executeAndWaitResult(new Exists(pred, splitter assign new DefaultSignalling with VolatileAbort)) + def exists(@deprecatedName('pred) p: T => Boolean): Boolean = { + tasksupport.executeAndWaitResult(new Exists(p, splitter assign new DefaultSignalling with VolatileAbort)) } /** Finds some element in the collection for which the predicate holds, if such @@ -546,11 +546,11 @@ self: ParIterableLike[T, Repr, Sequential] => * * $abortsignalling * - * @param pred predicate used to test the elements + * @param p predicate used to test the elements * @return an option value with the element if such an element exists, or `None` otherwise */ - def find(pred: T => Boolean): Option[T] = { - tasksupport.executeAndWaitResult(new Find(pred, splitter assign new DefaultSignalling with VolatileAbort)) + def find(@deprecatedName('pred) p: T => Boolean): Option[T] = { + tasksupport.executeAndWaitResult(new Find(p, splitter assign new DefaultSignalling with VolatileAbort)) } /** Creates a combiner factory. Each combiner factory instance is used diff --git a/src/library/scala/runtime/Tuple2Zipped.scala b/src/library/scala/runtime/Tuple2Zipped.scala index 512c4fbc27..4109f5cb4b 100644 --- a/src/library/scala/runtime/Tuple2Zipped.scala +++ b/src/library/scala/runtime/Tuple2Zipped.scala @@ -84,12 +84,12 @@ final class Tuple2Zipped[El1, Repr1, El2, Repr2](val colls: (TraversableLike[El1 (b1.result(), b2.result()) } - def exists(f: (El1, El2) => Boolean): Boolean = { + def exists(@deprecatedName('f) p: (El1, El2) => Boolean): Boolean = { val elems2 = colls._2.iterator for (el1 <- colls._1) { if (elems2.hasNext) { - if (f(el1, elems2.next())) + if (p(el1, elems2.next())) return true } else return false @@ -97,8 +97,8 @@ final class Tuple2Zipped[El1, Repr1, El2, Repr2](val colls: (TraversableLike[El1 false } - def forall(f: (El1, El2) => Boolean): Boolean = - !exists((x, y) => !f(x, y)) + def forall(@deprecatedName('f) p: (El1, El2) => Boolean): Boolean = + !exists((x, y) => !p(x, y)) def foreach[U](f: (El1, El2) => U): Unit = { val elems2 = colls._2.iterator diff --git a/src/library/scala/runtime/Tuple3Zipped.scala b/src/library/scala/runtime/Tuple3Zipped.scala index ffd44acf81..cde7699d40 100644 --- a/src/library/scala/runtime/Tuple3Zipped.scala +++ b/src/library/scala/runtime/Tuple3Zipped.scala @@ -90,13 +90,13 @@ final class Tuple3Zipped[El1, Repr1, El2, Repr2, El3, Repr3](val colls: (Travers result } - def exists(f: (El1, El2, El3) => Boolean): Boolean = { + def exists(@deprecatedName('f) p: (El1, El2, El3) => Boolean): Boolean = { val elems2 = colls._2.iterator val elems3 = colls._3.iterator for (el1 <- colls._1) { if (elems2.hasNext && elems3.hasNext) { - if (f(el1, elems2.next(), elems3.next())) + if (p(el1, elems2.next(), elems3.next())) return true } else return false @@ -104,8 +104,8 @@ final class Tuple3Zipped[El1, Repr1, El2, Repr2, El3, Repr3](val colls: (Travers false } - def forall(f: (El1, El2, El3) => Boolean): Boolean = - !exists((x, y, z) => !f(x, y, z)) + def forall(@deprecatedName('f) p: (El1, El2, El3) => Boolean): Boolean = + !exists((x, y, z) => !p(x, y, z)) def foreach[U](f: (El1, El2, El3) => U): Unit = { val elems2 = colls._2.iterator diff --git a/src/library/scala/util/Either.scala b/src/library/scala/util/Either.scala index e196d403c2..32b7ec4487 100644 --- a/src/library/scala/util/Either.scala +++ b/src/library/scala/util/Either.scala @@ -329,8 +329,8 @@ object Either { * }}} * */ - def forall(f: A => Boolean) = e match { - case Left(a) => f(a) + def forall(@deprecatedName('f) p: A => Boolean) = e match { + case Left(a) => p(a) case Right(_) => true } @@ -345,8 +345,8 @@ object Either { * }}} * */ - def exists(f: A => Boolean) = e match { - case Left(a) => f(a) + def exists(@deprecatedName('f) p: A => Boolean) = e match { + case Left(a) => p(a) case Right(_) => false } @@ -507,9 +507,9 @@ object Either { * Left(12).right.exists(_ > 10) // false * }}} */ - def exists(f: B => Boolean) = e match { + def exists(@deprecatedName('f) p: B => Boolean) = e match { case Left(_) => false - case Right(b) => f(b) + case Right(b) => p(b) } /** -- cgit v1.2.3 From 1fb32fcf04386f52e72522bd688e69edafd95414 Mon Sep 17 00:00:00 2001 From: Performant Data LLC Date: Sat, 10 Oct 2015 00:02:25 -0700 Subject: SI-9513 decrement "deleted" count in OpenHashMap.put() when slot reused --- .../scala/collection/mutable/OpenHashMap.scala | 6 +++- .../scala/collection/mutable/OpenHashMapTest.scala | 42 ++++++++++++++++++++++ 2 files changed, 47 insertions(+), 1 deletion(-) create mode 100644 test/junit/scala/collection/mutable/OpenHashMapTest.scala (limited to 'src/library') diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala index 24f5761cf5..094f7eb63e 100644 --- a/src/library/scala/collection/mutable/OpenHashMap.scala +++ b/src/library/scala/collection/mutable/OpenHashMap.scala @@ -136,7 +136,11 @@ extends AbstractMap[Key, Value] None } else { val res = entry.value - if (entry.value == None) { size += 1; modCount += 1 } + if (entry.value == None) { + size += 1 + deleted -= 1 + modCount += 1 + } entry.value = Some(value) res } diff --git a/test/junit/scala/collection/mutable/OpenHashMapTest.scala b/test/junit/scala/collection/mutable/OpenHashMapTest.scala new file mode 100644 index 0000000000..5e72727183 --- /dev/null +++ b/test/junit/scala/collection/mutable/OpenHashMapTest.scala @@ -0,0 +1,42 @@ +package scala.collection.mutable + +import org.junit.Test +import org.junit.Assert._ +import org.junit.runner.RunWith +import org.junit.runners.JUnit4 + +/** Tests for [[OpenHashMap]]. */ +@RunWith(classOf[JUnit4]) +class OpenHashMapTest { + /** Test that an [[OpenHashMap]] correctly maintains its internal `deleted` count. */ + @Test + def maintainsDeletedCount { + import scala.reflect.runtime.{universe => ru} + + val m = OpenHashMap.empty[Int, Int] + + // Reflect to get the private `deleted` field's value, which should be zero. + + /* TODO Doesn't work, due to SI-9306. + val mirror = ru.runtimeMirror(m.getClass.getClassLoader) + val mapType = ru.typeOf[OpenHashMap[Int, Int]] + val termSym = mapType.decls + .filterNot { s => s.isMethod } + .filter { s => s.fullName.endsWith("deleted") } + .head.asTerm + + val fieldMirror = mirror.reflect(m).reflectField(termSym) + */ + // Use Java reflection instead for now. + val field = m.getClass.getDeclaredField("scala$collection$mutable$OpenHashMap$$deleted") + field.setAccessible(true) + + m.put(0, 0) + m.remove(0) + assertEquals(1, field.getInt(m)) + + m.put(0, 0) // Add an entry with the same key + // TODO assertEquals(0, fieldMirror.get.asInstanceOf[Int]) + assertEquals(0, field.getInt(m)) + } +} -- cgit v1.2.3 From 30d704df5c66986b82cd3158e8e36a0f1b5284ab Mon Sep 17 00:00:00 2001 From: Performant Data LLC Date: Sat, 10 Oct 2015 00:04:09 -0700 Subject: Document some OpenHashMap internal methods. --- src/library/scala/collection/mutable/OpenHashMap.scala | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'src/library') diff --git a/src/library/scala/collection/mutable/OpenHashMap.scala b/src/library/scala/collection/mutable/OpenHashMap.scala index 094f7eb63e..5f8f5b9a0a 100644 --- a/src/library/scala/collection/mutable/OpenHashMap.scala +++ b/src/library/scala/collection/mutable/OpenHashMap.scala @@ -81,6 +81,9 @@ extends AbstractMap[Key, Value] h ^ (h >>> 7) ^ (h >>> 4) } + /** Increase the size of the table. + * Copy only the occupied slots, effectively eliminating the deleted slots. + */ private[this] def growTable() = { val oldSize = mask + 1 val newSize = 4 * oldSize @@ -92,8 +95,18 @@ extends AbstractMap[Key, Value] deleted = 0 } + /** Return the index of the first slot in the hash table (in probe order) + * that either is empty, or is or was last occupied by the given key. + */ private[this] def findIndex(key: Key) : Int = findIndex(key, hashOf(key)) + /** Return the index of the first slot in the hash table (in probe order) + * that either is empty, or is or was last occupied by the given key. + * + * This method is an optimization for when the hash value is in hand. + * + * @param hash hash value for `key` + */ private[this] def findIndex(key: Key, hash: Int): Int = { var j = hash -- cgit v1.2.3