diff options
Diffstat (limited to 'src/library')
| -rw-r--r-- | src/library/scala/Enumeration.scala | 4 | ||||
| -rw-r--r-- | src/library/scala/Predef.scala | 2 | ||||
| -rw-r--r-- | src/library/scala/collection/immutable/HashMap.scala | 6 | ||||
| -rw-r--r-- | src/library/scala/collection/immutable/HashSet.scala | 127 | ||||
| -rw-r--r-- | src/library/scala/collection/immutable/Stream.scala | 18 | ||||
| -rw-r--r-- | src/library/scala/collection/immutable/StringLike.scala | 4 | ||||
| -rw-r--r-- | src/library/scala/collection/mutable/AVLTree.scala | 10 | ||||
| -rw-r--r-- | src/library/scala/collection/mutable/ArrayOps.scala | 52 | ||||
| -rw-r--r-- | src/library/scala/io/Position.scala | 4 | ||||
| -rw-r--r-- | src/library/scala/reflect/package.scala | 15 | ||||
| -rw-r--r-- | src/library/scala/util/matching/Regex.scala | 8 |
11 files changed, 199 insertions, 51 deletions
diff --git a/src/library/scala/Enumeration.scala b/src/library/scala/Enumeration.scala index 59be0cdfa3..d4b9c17eab 100644 --- a/src/library/scala/Enumeration.scala +++ b/src/library/scala/Enumeration.scala @@ -11,7 +11,7 @@ package scala import scala.collection.{ mutable, immutable, generic, SortedSetLike, AbstractSet } import java.lang.reflect.{ Modifier, Method => JMethod, Field => JField } import scala.reflect.NameTransformer._ -import java.util.regex.Pattern +import scala.util.matching.Regex /** Defines a finite set of values specific to the enumeration. Typically * these values enumerate all possible forms something can take and provide @@ -64,7 +64,7 @@ abstract class Enumeration (initial: Int) extends Serializable { */ override def toString = ((getClass.getName stripSuffix MODULE_SUFFIX_STRING split '.').last split - Pattern.quote(NAME_JOIN_STRING)).last + Regex.quote(NAME_JOIN_STRING)).last /** The mapping from the integer used to identify values to the actual * values. */ diff --git a/src/library/scala/Predef.scala b/src/library/scala/Predef.scala index 8900450fa3..ec587c158d 100644 --- a/src/library/scala/Predef.scala +++ b/src/library/scala/Predef.scala @@ -95,8 +95,6 @@ object Predef extends LowPriorityImplicits with DeprecatedPredef { type Set[A] = immutable.Set[A] val Map = immutable.Map val Set = immutable.Set - // @deprecated("Use scala.AnyRef instead", "2.10.0") - // def AnyRef = scala.AnyRef // Manifest types, companions, and incantations for summoning @annotation.implicitNotFound(msg = "No ClassManifest available for ${T}.") diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala index fb0a34e64d..0a8524c139 100644 --- a/src/library/scala/collection/immutable/HashMap.scala +++ b/src/library/scala/collection/immutable/HashMap.scala @@ -59,7 +59,6 @@ class HashMap[A, +B] extends AbstractMap[A, B] override def + [B1 >: B] (elem1: (A, B1), elem2: (A, B1), elems: (A, B1) *): HashMap[A, B1] = this + elem1 + elem2 ++ elems - // TODO: optimize (might be able to use mutable updates) def - (key: A): HashMap[A, B] = removed0(key, computeHash(key), 0) @@ -168,8 +167,6 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { } } - // TODO: add HashMap2, HashMap3, ... - class HashMap1[A,+B](private[collection] val key: A, private[collection] val hash: Int, private[collection] val value: (B @uV), private[collection] var kv: (A,B @uV)) extends HashMap[A,B] { override def size = 1 @@ -277,7 +274,6 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { elems(index & 0x1f).get0(key, hash, level + 5) } else if ((bitmap & mask) != 0) { val offset = Integer.bitCount(bitmap & (mask-1)) - // TODO: might be worth checking if sub is HashTrieMap (-> monomorphic call site) elems(offset).get0(key, hash, level + 5) } else None @@ -289,7 +285,6 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { val offset = Integer.bitCount(bitmap & (mask-1)) if ((bitmap & mask) != 0) { val sub = elems(offset) - // TODO: might be worth checking if sub is HashTrieMap (-> monomorphic call site) val subNew = sub.updated0(key, hash, level + 5, value, kv, merger) if(subNew eq sub) this else { val elemsNew = new Array[HashMap[A,B1]](elems.length) @@ -312,7 +307,6 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { val offset = Integer.bitCount(bitmap & (mask-1)) if ((bitmap & mask) != 0) { val sub = elems(offset) - // TODO: might be worth checking if sub is HashTrieMap (-> monomorphic call site) val subNew = sub.removed0(key, hash, level + 5) if (subNew eq sub) this else if (subNew.isEmpty) { diff --git a/src/library/scala/collection/immutable/HashSet.scala b/src/library/scala/collection/immutable/HashSet.scala index 9eaceccd9f..115be09502 100644 --- a/src/library/scala/collection/immutable/HashSet.scala +++ b/src/library/scala/collection/immutable/HashSet.scala @@ -12,9 +12,9 @@ package scala package collection package immutable -import scala.annotation.unchecked.{ uncheckedVariance => uV } import generic._ import scala.collection.parallel.immutable.ParHashSet +import scala.collection.GenSet /** This class implements immutable sets using a hash trie. * @@ -54,11 +54,34 @@ class HashSet[A] extends AbstractSet[A] def contains(e: A): Boolean = get0(e, computeHash(e), 0) + override def subsetOf(that: GenSet[A]) = that match { + case that:HashSet[A] => + // call the specialized implementation with a level of 0 since both this and that are top-level hash sets + subsetOf0(that, 0) + case _ => + // call the generic implementation + super.subsetOf(that) + } + + /** + * A specialized implementation of subsetOf for when both this and that are HashSet[A] and we can take advantage + * of the tree structure of both operands and the precalculated hashcodes of the HashSet1 instances. + * @param that the other set + * @param level the level of this and that hashset + * The purpose of level is to keep track of how deep we are in the tree. + * We need this information for when we arrive at a leaf and have to call get0 on that + * The value of level is 0 for a top-level HashSet and grows in increments of 5 + * @return true if all elements of this set are contained in that set + */ + protected def subsetOf0(that: HashSet[A], level: Int) = { + // The default implementation is for the empty set and returns true because the empty set is a subset of all sets + true + } + override def + (e: A): HashSet[A] = updated0(e, computeHash(e), 0) override def + (elem1: A, elem2: A, elems: A*): HashSet[A] = this + elem1 + elem2 ++ elems - // TODO: optimize (might be able to use mutable updates) def - (e: A): HashSet[A] = removed0(e, computeHash(e), 0) @@ -128,14 +151,20 @@ object HashSet extends ImmutableSetFactory[HashSet] { } } - // TODO: add HashSet2, HashSet3, ... - class HashSet1[A](private[HashSet] val key: A, private[HashSet] val hash: Int) extends HashSet[A] { override def size = 1 override def get0(key: A, hash: Int, level: Int): Boolean = (hash == this.hash && key == this.key) + override def subsetOf0(that: HashSet[A], level: Int) = { + // check if that contains this.key + // we use get0 with our key and hash at the correct level instead of calling contains, + // which would not work since that might not be a top-level HashSet + // and in any case would be inefficient because it would require recalculating the hash code + that.get0(key, hash, level) + } + override def updated0(key: A, hash: Int, level: Int): HashSet[A] = if (hash == this.hash && key == this.key) this else { @@ -162,6 +191,14 @@ object HashSet extends ImmutableSetFactory[HashSet] { override def get0(key: A, hash: Int, level: Int): Boolean = if (hash == this.hash) ks.contains(key) else false + override def subsetOf0(that: HashSet[A], level: Int) = { + // we have to check each element + // we use get0 with our hash at the correct level instead of calling contains, + // which would not work since that might not be a top-level HashSet + // and in any case would be inefficient because it would require recalculating the hash code + ks.forall(key => that.get0(key, hash, level)) + } + override def updated0(key: A, hash: Int, level: Int): HashSet[A] = if (hash == this.hash) new HashSetCollision1(hash, ks + key) else makeHashTrieSet(this.hash, this, hash, new HashSet1(key, hash), level) @@ -197,6 +234,42 @@ object HashSet extends ImmutableSetFactory[HashSet] { } + /** + * A branch node of the HashTrieSet with at least one and up to 32 children. + * + * @param bitmap encodes which element corresponds to which child + * @param elems the up to 32 children of this node. + * the number of children must be identical to the number of 1 bits in bitmap + * @param size0 the total number of elements. This is stored just for performance reasons. + * @tparam A the type of the elements contained in this hash set. + * + * How levels work: + * + * When looking up or adding elements, the part of the hashcode that is used to address the children array depends + * on how deep we are in the tree. This is accomplished by having a level parameter in all internal methods + * that starts at 0 and increases by 5 (32 = 2^5) every time we go deeper into the tree. + * + * hashcode (binary): 00000000000000000000000000000000 + * level=0 (depth=0) ^^^^^ + * level=5 (depth=1) ^^^^^ + * level=10 (depth=2) ^^^^^ + * ... + * + * Be careful: a non-toplevel HashTrieSet is not a self-contained set, so e.g. calling contains on it will not work! + * It relies on its depth in the Trie for which part of a hash to use to address the children, but this information + * (the level) is not stored due to storage efficiency reasons but has to be passed explicitly! + * + * How bitmap and elems correspond: + * + * A naive implementation of a HashTrieSet would always have an array of size 32 for children and leave the unused + * children empty (null). But that would be very wasteful regarding memory. Instead, only non-empty children are + * stored in elems, and the bitmap is used to encode which elem corresponds to which child bucket. The lowest 1 bit + * corresponds to the first element, the second-lowest to the second, etc. + * + * bitmap (binary): 00010000000000000000100000000000 + * elems: [a,b] + * children: ---b----------------a----------- + */ class HashTrieSet[A](private val bitmap: Int, private[collection] val elems: Array[HashSet[A]], private val size0: Int) extends HashSet[A] { assert(Integer.bitCount(bitmap) == elems.length) @@ -212,7 +285,6 @@ object HashSet extends ImmutableSetFactory[HashSet] { elems(index & 0x1f).get0(key, hash, level + 5) } else if ((bitmap & mask) != 0) { val offset = Integer.bitCount(bitmap & (mask-1)) - // TODO: might be worth checking if sub is HashTrieSet (-> monomorphic call site) elems(offset).get0(key, hash, level + 5) } else false @@ -223,7 +295,6 @@ object HashSet extends ImmutableSetFactory[HashSet] { val mask = (1 << index) val offset = Integer.bitCount(bitmap & (mask-1)) if ((bitmap & mask) != 0) { - // TODO: might be worth checking if sub is HashTrieSet (-> monomorphic call site) val sub = elems(offset) val subNew = sub.updated0(key, hash, level + 5) if (sub eq subNew) this @@ -249,7 +320,6 @@ object HashSet extends ImmutableSetFactory[HashSet] { val offset = Integer.bitCount(bitmap & (mask-1)) if ((bitmap & mask) != 0) { val sub = elems(offset) - // TODO: might be worth checking if sub is HashTrieMap (-> monomorphic call site) val subNew = sub.removed0(key, hash, level + 5) if (sub eq subNew) this else if (subNew.isEmpty) { @@ -279,6 +349,49 @@ object HashSet extends ImmutableSetFactory[HashSet] { } } + override def subsetOf0(that: HashSet[A], level: Int): Boolean = if (that eq this) true else that match { + case that: HashTrieSet[A] if this.size0 <= that.size0 => + // create local mutable copies of members + var abm = this.bitmap + val a = this.elems + var ai = 0 + val b = that.elems + var bbm = that.bitmap + var bi = 0 + if ((abm & bbm) == abm) { + // I tried rewriting this using tail recursion, but the generated java byte code was less than optimal + while(abm!=0) { + // highest remaining bit in abm + val alsb = abm ^ (abm & (abm - 1)) + // highest remaining bit in bbm + val blsb = bbm ^ (bbm & (bbm - 1)) + // if both trees have a bit set at the same position, we need to check the subtrees + if (alsb == blsb) { + // we are doing a comparison of a child of this with a child of that, + // so we have to increase the level by 5 to keep track of how deep we are in the tree + if (!a(ai).subsetOf0(b(bi), level + 5)) + return false + // clear lowest remaining one bit in abm and increase the a index + abm &= ~alsb; ai += 1 + } + // clear lowermost remaining one bit in bbm and increase the b index + // we must do this in any case + bbm &= ~blsb; bi += 1 + } + true + } else { + // the bitmap of this contains more one bits than the bitmap of that, + // so this can not possibly be a subset of that + false + } + case _ => + // if the other set is a HashTrieSet but has less elements than this, it can not be a subset + // if the other set is a HashSet1, we can not be a subset of it because we are a HashTrieSet with at least two children (see assertion) + // if the other set is a HashSetCollision1, we can not be a subset of it because we are a HashTrieSet with at least two different hash codes + // if the other set is the empty set, we are not a subset of it because we are not empty + false + } + override def iterator = new TrieIterator[A](elems.asInstanceOf[Array[Iterable[A]]]) { final override def getElem(cc: AnyRef): A = cc.asInstanceOf[HashSet1[A]].key } diff --git a/src/library/scala/collection/immutable/Stream.scala b/src/library/scala/collection/immutable/Stream.scala index a82e31f5da..49c3b4c3cd 100644 --- a/src/library/scala/collection/immutable/Stream.scala +++ b/src/library/scala/collection/immutable/Stream.scala @@ -960,14 +960,16 @@ self => * }}} */ override def flatten[B](implicit asTraversable: A => /*<:<!!!*/ GenTraversableOnce[B]): Stream[B] = { - def flatten1(t: Traversable[B]): Stream[B] = - if (!t.isEmpty) - cons(t.head, flatten1(t.tail)) - else - tail.flatten - - if (isEmpty) Stream.empty - else flatten1(asTraversable(head).seq.toTraversable) + var st: Stream[A] = this + while (st.nonEmpty) { + val h = asTraversable(st.head) + if (h.isEmpty) { + st = st.tail + } else { + return h.toStream #::: st.tail.flatten + } + } + Stream.empty } override def view = new StreamView[A, Stream[A]] { diff --git a/src/library/scala/collection/immutable/StringLike.scala b/src/library/scala/collection/immutable/StringLike.scala index 5a0d24ddd2..43d46cf4d0 100644 --- a/src/library/scala/collection/immutable/StringLike.scala +++ b/src/library/scala/collection/immutable/StringLike.scala @@ -164,8 +164,8 @@ self => * @return the resulting string */ def replaceAllLiterally(literal: String, replacement: String): String = { - val arg1 = java.util.regex.Pattern.quote(literal) - val arg2 = java.util.regex.Matcher.quoteReplacement(replacement) + val arg1 = Regex.quote(literal) + val arg2 = Regex.quoteReplacement(replacement) toString.replaceAll(arg1, arg2) } diff --git a/src/library/scala/collection/mutable/AVLTree.scala b/src/library/scala/collection/mutable/AVLTree.scala index d2205f9994..de09bb2040 100644 --- a/src/library/scala/collection/mutable/AVLTree.scala +++ b/src/library/scala/collection/mutable/AVLTree.scala @@ -11,10 +11,10 @@ package collection package mutable /** - * An immutable AVL Tree implementation used by mutable.TreeSet + * 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") + * @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[mutable] sealed trait AVLTree[+A] extends Serializable { def balance: Int @@ -65,7 +65,7 @@ private[mutable] sealed trait AVLTree[+A] extends Serializable { } /** - * @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") + * @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 @@ -74,7 +74,7 @@ private case object Leaf extends AVLTree[Nothing] { } /** - * @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") + * @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 @@ -211,7 +211,7 @@ private case class Node[A](data: A, left: AVLTree[A], right: AVLTree[A]) extends } /** - * @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") + * @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) diff --git a/src/library/scala/collection/mutable/ArrayOps.scala b/src/library/scala/collection/mutable/ArrayOps.scala index e1f18a7036..e342e134b4 100644 --- a/src/library/scala/collection/mutable/ArrayOps.scala +++ b/src/library/scala/collection/mutable/ArrayOps.scala @@ -53,14 +53,14 @@ trait ArrayOps[T] extends Any with ArrayLike[T, Array[T]] with CustomParalleliza super.toArray[U] } - def :+[B >: T: scala.reflect.ClassTag](elem: B): Array[B] = { + def :+[B >: T: ClassTag](elem: B): Array[B] = { val result = Array.ofDim[B](repr.length + 1) Array.copy(repr, 0, result, 0, repr.length) result(repr.length) = elem result } - def +:[B >: T: scala.reflect.ClassTag](elem: B): Array[B] = { + def +:[B >: T: ClassTag](elem: B): Array[B] = { val result = Array.ofDim[B](repr.length + 1) result(0) = elem Array.copy(repr, 0, result, 1, repr.length) @@ -107,6 +107,54 @@ trait ArrayOps[T] extends Any with ArrayLike[T, Array[T]] with CustomParalleliza bb.result() } } + + /** Converts an array of pairs into an array of first elements and an array of second elements. + * + * @tparam T1 the type of the first half of the element pairs + * @tparam T2 the type of the second half of the element pairs + * @param asPair an implicit conversion which asserts that the element type + * of this Array is a pair. + * @return a pair of Arrays, containing, respectively, the first and second half + * of each element pair of this Array. + */ + def unzip[T1: ClassTag, T2: ClassTag](implicit asPair: T => (T1, T2)): (Array[T1], Array[T2]) = { + val a1 = new Array[T1](length) + val a2 = new Array[T2](length) + var i = 0 + while (i < length) { + val e = apply(i) + a1(i) = e._1 + a2(i) = e._2 + i += 1 + } + (a1, a2) + } + + /** Converts an array of triples into three arrays, one containing the elements from each position of the triple. + * + * @tparam T1 the type of the first of three elements in the triple + * @tparam T2 the type of the second of three elements in the triple + * @tparam T3 the type of the third of three elements in the triple + * @param asTriple an implicit conversion which asserts that the element type + * of this Array is a triple. + * @return a triple of Arrays, containing, respectively, the first, second, and third + * elements from each element triple of this Array. + */ + def unzip3[T1: ClassTag, T2: ClassTag, T3: ClassTag](implicit asTriple: T => (T1, T2, T3)): (Array[T1], Array[T2], Array[T3]) = { + val a1 = new Array[T1](length) + val a2 = new Array[T2](length) + val a3 = new Array[T3](length) + var i = 0 + while (i < length) { + val e = apply(i) + a1(i) = e._1 + a2(i) = e._2 + a3(i) = e._3 + i += 1 + } + (a1, a2, a3) + } + def seq = thisCollection diff --git a/src/library/scala/io/Position.scala b/src/library/scala/io/Position.scala index 85149223ee..011d0f17af 100644 --- a/src/library/scala/io/Position.scala +++ b/src/library/scala/io/Position.scala @@ -34,7 +34,7 @@ package io * @author Burak Emir (translated from work by Matthias Zenger and others) */ @deprecated("This class will be removed.", "2.10.0") -abstract class Position { +private[scala] abstract class Position { /** Definable behavior for overflow conditions. */ def checkInput(line: Int, column: Int): Unit @@ -68,7 +68,7 @@ abstract class Position { def toString(pos: Int): String = line(pos) + ":" + column(pos) } -object Position extends Position { +private[scala] object Position extends Position { def checkInput(line: Int, column: Int) { if (line < 0) throw new IllegalArgumentException(line + " < 0") diff --git a/src/library/scala/reflect/package.scala b/src/library/scala/reflect/package.scala index 74c1f2172c..509d181d87 100644 --- a/src/library/scala/reflect/package.scala +++ b/src/library/scala/reflect/package.scala @@ -61,21 +61,6 @@ package object reflect { // using the mechanism implemented in `scala.tools.reflect.FastTrack` // todo. once we have implicit macros for tag generation, we can remove this anchor private[scala] def materializeClassTag[T](): ClassTag[T] = macro ??? - - @deprecated("Use `@scala.beans.BeanDescription` instead", "2.10.0") - type BeanDescription = scala.beans.BeanDescription - @deprecated("Use `@scala.beans.BeanDisplayName` instead", "2.10.0") - type BeanDisplayName = scala.beans.BeanDisplayName - @deprecated("Use `@scala.beans.BeanInfo` instead", "2.10.0") - type BeanInfo = scala.beans.BeanInfo - @deprecated("Use `@scala.beans.BeanInfoSkip` instead", "2.10.0") - type BeanInfoSkip = scala.beans.BeanInfoSkip - @deprecated("Use `@scala.beans.BeanProperty` instead", "2.10.0") - type BeanProperty = scala.beans.BeanProperty - @deprecated("Use `@scala.beans.BooleanBeanProperty` instead", "2.10.0") - type BooleanBeanProperty = scala.beans.BooleanBeanProperty - @deprecated("Use `@scala.beans.ScalaBeanInfo` instead", "2.10.0") - type ScalaBeanInfo = scala.beans.ScalaBeanInfo } /** An exception that indicates an error during Scala reflection */ diff --git a/src/library/scala/util/matching/Regex.scala b/src/library/scala/util/matching/Regex.scala index 22dbb37789..86132bb876 100644 --- a/src/library/scala/util/matching/Regex.scala +++ b/src/library/scala/util/matching/Regex.scala @@ -704,6 +704,14 @@ object Regex { def replace(rs: String) = matcher.appendReplacement(sb, rs) } + /** Quotes strings to be used literally in regex patterns. + * + * All regex metacharacters in the input match themselves literally in the output. + * + * @example {{{List("US$", "CAN$").map(Regex.quote).mkString("|").r}}} + */ + def quote(text: String): String = Pattern quote text + /** Quotes replacement strings to be used in replacement methods. * * Replacement methods give special meaning to backslashes (`\`) and |