diff options
Diffstat (limited to 'src/library')
19 files changed, 339 insertions, 107 deletions
diff --git a/src/library/rootdoc.txt b/src/library/rootdoc.txt index 0722d808bf..4795a47efe 100644 --- a/src/library/rootdoc.txt +++ b/src/library/rootdoc.txt @@ -2,21 +2,54 @@ This is the documentation for the Scala standard library. == Package structure == -The [[scala]] package contains core types. - -[[scala.collection `scala.collection`]] and its subpackages contain a collections framework with higher-order functions for manipulation. Both [[scala.collection.immutable `scala.collection.immutable`]] and [[scala.collection.mutable `scala.collection.mutable`]] data structures are available, with immutable as the default. The [[scala.collection.parallel `scala.collection.parallel`]] collections provide automatic parallel operation. - -Other important packages include: - - - [[scala.actors `scala.actors`]] - Concurrency framework inspired by Erlang. - - [[scala.io `scala.io`]] - Input and output. - - [[scala.math `scala.math`]] - Basic math functions and additional numeric types. - - [[scala.sys `scala.sys`]] - Interaction with other processes and the operating system. - - [[scala.util.matching `scala.util.matching`]] - Pattern matching in text using regular expressions. - - [[scala.util.parsing.combinator `scala.util.parsing.combinator`]] - Composable combinators for parsing. - - [[scala.xml `scala.xml`]] - XML parsing, manipulation, and serialization. - -Many other packages exist. See the complete list on the left. +The [[scala]] package contains core types like [[scala.Int `Int`]], [[scala.Float `Float`]], [[scala.Array `Array`]] +or [[scala.Option `Option`]] which are accessible in all Scala compilation units without explicit qualification or +imports. + +Notable packages include: + + - [[scala.collection `scala.collection`]] and its sub-packages contain Scala's collections framework + - [[scala.collection.immutable `scala.collection.immutable`]] - Immutable, sequential data-structures such as + [[scala.collection.immutable.Vector `Vector`]], [[scala.collection.immutable.List `List`]], + [[scala.collection.immutable.Range `Range`]], [[scala.collection.immutable.HashMap `HashMap`]] or + [[scala.collection.immutable.HashSet `HasSet`]] + - [[scala.collection.mutable `scala.collection.mutable`]] - Mutable, sequential data-structures such as + [[scala.collection.mutable.ArrayBuffer `ArrayBuffer`]], + [[scala.collection.mutable.StringBuilder `StringBuilder`]], + [[scala.collection.mutable.HashMap `HashMap`]] or [[scala.collection.mutable.HashSet `HashSet`]] + - [[scala.collection.concurrent `scala.collection.concurrent`]] - Mutable, concurrent data-structures such as + [[scala.collection.concurrent.TrieMap `TrieMap`]] + - [[scala.collection.parallel.immutable `scala.collection.parallel.immutable`]] - Immutable, parallel + data-structures such as [[scala.collection.parallel.immutable.ParVector `ParVector`]], + [[scala.collection.parallel.immutable.ParRange `ParRange`]], + [[scala.collection.parallel.immutable.ParHashMap `ParHashMap`]] or + [[scala.collection.parallel.immutable.ParHashSet `ParHashSet`]] + - [[scala.collection.parallel.mutable `scala.collection.parallel.mutable`]] - Mutable, parallel + data-structures such as [[scala.collection.parallel.mutable.ParArray `ParArray`]], + [[scala.collection.parallel.mutable.ParHashMap `ParHashMap`]], + [[scala.collection.parallel.mutable.ParTrieMap `ParTrieMap`]] or + [[scala.collection.parallel.mutable.ParHashSet `ParHashSet`]] + - [[scala.concurrent `scala.concurrent`]] - Primitives for concurrent programming such as + [[scala.concurrent.Future `Futures`]] and [[scala.concurrent.Promise `Promises`]] + - [[scala.io `scala.io`]] - Input and output operations + - [[scala.math `scala.math`]] - Basic math functions and additional numeric types like + [[scala.math.BigInt `BigInt`]] and [[scala.math.BigDecimal `BigDecimal`]] + - [[scala.sys `scala.sys`]] - Interaction with other processes and the operating system + - [[scala.util.matching `scala.util.matching`]] - [[scala.util.matching.Regex Regular expressions]] + +Other packages exist. See the complete list on the left. + +Additional parts of the standard library are shipped as separate libraries. These include: + + - [[scala.reflect `scala.reflect`]] - Scala's reflection API (scala-reflect.jar) + - [[scala.xml `scala.xml`]] - XML parsing, manipulation, and serialization (scala-xml.jar) + - [[scala.swing `scala.swing`]] - A convenient wrapper around Java's GUI framework called Swing (scala-swing.jar) + - [[scala.util.continuations `scala.util.continuations`]] - Delimited continuations using continuation-passing-style + (scala-continuations-library.jar, scala-continuations-plugin.jar) + - [[scala.util.parsing `scala.util.parsing`]] - [[scala.util.parsing.combinator Parser combinators]], including an + example implementation of a [[scala.util.parsing.json JSON parser]] (scala-parser-combinators.jar) + - [[scala.actors `scala.actors`]] - Actor-based concurrency (deprecated and replaced by Akka actors, + scala-actors.jar) == Automatic imports == diff --git a/src/library/scala/AnyVal.scala b/src/library/scala/AnyVal.scala index 9def6cb054..ff62948413 100644 --- a/src/library/scala/AnyVal.scala +++ b/src/library/scala/AnyVal.scala @@ -33,7 +33,7 @@ package scala * * User-defined value classes which avoid object allocation... * - * - must have a single, public `val` parameter that is the underlying runtime representation. + * - must have a single `val` parameter that is the underlying runtime representation. * - can define `def`s, but no `val`s, `var`s, or nested `traits`s, `class`es or `object`s. * - typically extend no other trait apart from `AnyVal`. * - cannot be used in type tests or pattern matching. diff --git a/src/library/scala/App.scala b/src/library/scala/App.scala index 90a8977e81..ef39ee2134 100644 --- a/src/library/scala/App.scala +++ b/src/library/scala/App.scala @@ -28,9 +28,8 @@ import scala.collection.mutable.ListBuffer * functionality, which means that fields of the object will not have been initialized * before the main method has been executed.''''' * - * It should also be noted that the `main` method will not normally need to be overridden: - * the purpose is to turn the whole class body into the “main method”. You should only - * chose to override it if you know what you are doing. + * It should also be noted that the `main` method should not be overridden: + * the whole class body becomes the “main method”. * * @author Martin Odersky * @version 2.1, 15/02/2011 @@ -61,11 +60,12 @@ trait App extends DelayedInit { } /** The main method. - * This stores all argument so that they can be retrieved with `args` - * and the executes all initialization code segments in the order they were - * passed to `delayedInit` + * This stores all arguments so that they can be retrieved with `args` + * and then executes all initialization code segments in the order in which + * they were passed to `delayedInit`. * @param args the arguments passed to the main method */ + @deprecatedOverriding("main should not be overridden", "2.11.0") def main(args: Array[String]) = { this._args = args for (proc <- initCode) proc() 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/collection/GenSeqLike.scala b/src/library/scala/collection/GenSeqLike.scala index 27b75c0491..c3bad60072 100644 --- a/src/library/scala/collection/GenSeqLike.scala +++ b/src/library/scala/collection/GenSeqLike.scala @@ -38,8 +38,8 @@ trait GenSeqLike[+A, +Repr] extends Any with GenIterableLike[A, Repr] with Equal * Example: * * {{{ - * scala> val x = LinkedList(1, 2, 3, 4, 5) - * x: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2, 3, 4, 5) + * scala> val x = List(1, 2, 3, 4, 5) + * x: List[Int] = List(1, 2, 3, 4, 5) * * scala> x(3) * res1: Int = 4 @@ -190,7 +190,7 @@ trait GenSeqLike[+A, +Repr] extends Any with GenIterableLike[A, Repr] with Equal */ def lastIndexWhere(p: A => Boolean, end: Int): Int - /** Returns new $coll wih elements in reversed order. + /** Returns new $coll with elements in reversed order. * * $willNotTerminateInf * @@ -302,14 +302,14 @@ trait GenSeqLike[+A, +Repr] extends Any with GenIterableLike[A, Repr] with Equal * * Example: * {{{ - * scala> val x = LinkedList(1) - * x: scala.collection.mutable.LinkedList[Int] = LinkedList(1) + * scala> val x = List(1) + * x: List[Int] = List(1) * * scala> val y = 2 +: x - * y: scala.collection.mutable.LinkedList[Int] = LinkedList(2, 1) + * y: List[Int] = List(2, 1) * * scala> println(x) - * LinkedList(1) + * List(1) * }}} * * @return a new $coll consisting of `elem` followed @@ -335,17 +335,14 @@ trait GenSeqLike[+A, +Repr] extends Any with GenIterableLike[A, Repr] with Equal * * Example: * {{{ - * scala> import scala.collection.mutable.LinkedList - * import scala.collection.mutable.LinkedList - * - * scala> val a = LinkedList(1) - * a: scala.collection.mutable.LinkedList[Int] = LinkedList(1) - * + * scala> val a = List(1) + * a: List[Int] = List(1) + * * scala> val b = a :+ 2 - * b: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2) - * + * b: List[Int] = List(1, 2) + * * scala> println(a) - * LinkedList(1) + * List(1) * }}} * * @return a new $coll consisting of diff --git a/src/library/scala/collection/GenTraversableLike.scala b/src/library/scala/collection/GenTraversableLike.scala index a0c519884c..ca098e57b9 100644 --- a/src/library/scala/collection/GenTraversableLike.scala +++ b/src/library/scala/collection/GenTraversableLike.scala @@ -267,20 +267,20 @@ trait GenTraversableLike[+A, +Repr] extends Any with GenTraversableOnce[A] with * * Example: * {{{ - * scala> val a = LinkedList(1) - * a: scala.collection.mutable.LinkedList[Int] = LinkedList(1) - * - * scala> val b = LinkedList(2) - * b: scala.collection.mutable.LinkedList[Int] = LinkedList(2) - * + * scala> val a = List(1) + * a: List[Int] = List(1) + * + * scala> val b = List(2) + * b: List[Int] = List(2) + * * scala> val c = a ++ b - * c: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2) - * - * scala> val d = LinkedList('a') - * d: scala.collection.mutable.LinkedList[Char] = LinkedList(a) - * + * c: List[Int] = List(1, 2) + * + * scala> val d = List('a') + * d: List[Char] = List(a) + * * scala> val e = c ++ d - * e: scala.collection.mutable.LinkedList[AnyVal] = LinkedList(1, 2, a) + * e: List[AnyVal] = List(1, 2, a) * }}} * * @return a new $coll which contains all elements of this $coll diff --git a/src/library/scala/collection/GenTraversableOnce.scala b/src/library/scala/collection/GenTraversableOnce.scala index a9fe279599..01d179aeb6 100644 --- a/src/library/scala/collection/GenTraversableOnce.scala +++ b/src/library/scala/collection/GenTraversableOnce.scala @@ -130,8 +130,8 @@ trait GenTraversableOnce[+A] extends Any { * * Note that the folding function used to compute b is equivalent to that used to compute c. * {{{ - * scala> val a = LinkedList(1,2,3,4) - * a: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2, 3, 4) + * scala> val a = List(1,2,3,4) + * a: List[Int] = List(1, 2, 3, 4) * * scala> val b = (5 /: a)(_+_) * b: Int = 15 @@ -167,8 +167,8 @@ trait GenTraversableOnce[+A] extends Any { * * Note that the folding function used to compute b is equivalent to that used to compute c. * {{{ - * scala> val a = LinkedList(1,2,3,4) - * a: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2, 3, 4) + * scala> val a = List(1,2,3,4) + * a: List[Int] = List(1, 2, 3, 4) * * scala> val b = (a :\ 5)(_+_) * b: Int = 15 diff --git a/src/library/scala/collection/TraversableOnce.scala b/src/library/scala/collection/TraversableOnce.scala index 26af32046c..072fd3da44 100644 --- a/src/library/scala/collection/TraversableOnce.scala +++ b/src/library/scala/collection/TraversableOnce.scala @@ -320,14 +320,14 @@ trait TraversableOnce[+A] extends Any with GenTraversableOnce[A] { * Example: * * {{{ - * scala> val a = LinkedList(1,2,3,4) - * a: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2, 3, 4) - * + * scala> val a = List(1,2,3,4) + * a: List[Int] = List(1, 2, 3, 4) + * * scala> val b = new StringBuilder() - * b: StringBuilder = - * - * scala> a.addString(b, "LinkedList(", ", ", ")") - * res1: StringBuilder = LinkedList(1, 2, 3, 4) + * b: StringBuilder = + * + * scala> a.addString(b , "List(" , ", " , ")") + * res5: StringBuilder = List(1, 2, 3, 4) * }}} * * @param b the string builder to which elements are appended. @@ -362,9 +362,9 @@ trait TraversableOnce[+A] extends Any with GenTraversableOnce[A] { * Example: * * {{{ - * scala> val a = LinkedList(1,2,3,4) - * a: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2, 3, 4) - * + * scala> val a = List(1,2,3,4) + * a: List[Int] = List(1, 2, 3, 4) + * * scala> val b = new StringBuilder() * b: StringBuilder = * @@ -385,14 +385,14 @@ trait TraversableOnce[+A] extends Any with GenTraversableOnce[A] { * Example: * * {{{ - * scala> val a = LinkedList(1,2,3,4) - * a: scala.collection.mutable.LinkedList[Int] = LinkedList(1, 2, 3, 4) - * + * scala> val a = List(1,2,3,4) + * a: List[Int] = List(1, 2, 3, 4) + * * scala> val b = new StringBuilder() * b: StringBuilder = * * scala> val h = a.addString(b) - * b: StringBuilder = 1234 + * h: StringBuilder = 1234 * }}} * @param b the string builder to which elements are appended. diff --git a/src/library/scala/collection/convert/Wrappers.scala b/src/library/scala/collection/convert/Wrappers.scala index 56f1802509..14ae57c43a 100644 --- a/src/library/scala/collection/convert/Wrappers.scala +++ b/src/library/scala/collection/convert/Wrappers.scala @@ -102,8 +102,14 @@ private[collection] trait Wrappers { override def clone(): JListWrapper[A] = JListWrapper(new ju.ArrayList[A](underlying)) } + // Note various overrides to avoid performance gotchas. class SetWrapper[A](underlying: Set[A]) extends ju.AbstractSet[A] { self => + override def contains(o: Object): Boolean = { + try { underlying.contains(o.asInstanceOf[A]) } + catch { case cce: ClassCastException => false } + } + override def isEmpty = underlying.isEmpty def size = underlying.size def iterator = new ju.Iterator[A] { val ui = underlying.iterator 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/NumericRange.scala b/src/library/scala/collection/immutable/NumericRange.scala index 486c2b6c8f..249d76584d 100644 --- a/src/library/scala/collection/immutable/NumericRange.scala +++ b/src/library/scala/collection/immutable/NumericRange.scala @@ -175,9 +175,36 @@ extends AbstractSeq[T] with IndexedSeq[T] with Serializable { catch { case _: ClassCastException => false } final override def sum[B >: T](implicit num: Numeric[B]): B = { - if (isEmpty) this.num fromInt 0 - else if (numRangeElements == 1) head - else ((this.num fromInt numRangeElements) * (head + last) / (this.num fromInt 2)) + // arithmetic series formula can be used for regular addition + if ((num eq scala.math.Numeric.IntIsIntegral)|| + (num eq scala.math.Numeric.BigIntIsIntegral)|| + (num eq scala.math.Numeric.ShortIsIntegral)|| + (num eq scala.math.Numeric.ByteIsIntegral)|| + (num eq scala.math.Numeric.CharIsIntegral)|| + (num eq scala.math.Numeric.LongIsIntegral)|| + (num eq scala.math.Numeric.FloatAsIfIntegral)|| + (num eq scala.math.Numeric.BigDecimalIsFractional)|| + (num eq scala.math.Numeric.DoubleAsIfIntegral)) { + val numAsIntegral = num.asInstanceOf[Integral[B]] + import numAsIntegral._ + if (isEmpty) num fromInt 0 + else if (numRangeElements == 1) head + else ((num fromInt numRangeElements) * (head + last) / (num fromInt 2)) + } else { + // user provided custom Numeric, we cannot rely on arithmetic series formula + if (isEmpty) num.zero + else { + var acc = num.zero + var i = head + var idx = 0 + while(idx < length) { + acc = num.plus(acc, i) + i = i + step + idx = idx + 1 + } + acc + } + } } override lazy val hashCode = super.hashCode() diff --git a/src/library/scala/collection/immutable/PagedSeq.scala b/src/library/scala/collection/immutable/PagedSeq.scala index 589661a343..3a64820be6 100644 --- a/src/library/scala/collection/immutable/PagedSeq.scala +++ b/src/library/scala/collection/immutable/PagedSeq.scala @@ -188,7 +188,10 @@ extends scala.collection.AbstractSeq[T] val s = start + _start val e = if (_end == UndeterminedEnd) _end else start + _end var f = first1 - while (f.end <= s && !f.isLast) f = f.next + while (f.end <= s && !f.isLast) { + if (f.next eq null) f.addMore(more) + f = f.next + } new PagedSeq(more, f, s, e) } diff --git a/src/library/scala/collection/immutable/Range.scala b/src/library/scala/collection/immutable/Range.scala index 00f398a4b0..786b18cd21 100644 --- a/src/library/scala/collection/immutable/Range.scala +++ b/src/library/scala/collection/immutable/Range.scala @@ -259,9 +259,24 @@ extends scala.collection.AbstractSeq[Int] final def contains(x: Int) = isWithinBoundaries(x) && ((x - start) % step == 0) final override def sum[B >: Int](implicit num: Numeric[B]): Int = { - if (isEmpty) 0 - else if (numRangeElements == 1) head - else (numRangeElements.toLong * (head + last) / 2).toInt + if (num eq scala.math.Numeric.IntIsIntegral) { + // this is normal integer range with usual addition. arithmetic series formula can be used + if (isEmpty) 0 + else if (numRangeElements == 1) head + else (numRangeElements.toLong * (head + last) / 2).toInt + } else { + // user provided custom Numeric, we cannot rely on arithmetic series formula + if (isEmpty) num.toInt(num.zero) + else { + var acc = num.zero + var i = head + while(i != terminalElement) { + acc = num.plus(acc, i) + i = i + step + } + num.toInt(acc) + } + } } override def toIterable = this 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/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/runtime/AbstractPartialFunction.scala b/src/library/scala/runtime/AbstractPartialFunction.scala index 7129f22f60..986cd0390f 100644 --- a/src/library/scala/runtime/AbstractPartialFunction.scala +++ b/src/library/scala/runtime/AbstractPartialFunction.scala @@ -35,15 +35,3 @@ abstract class AbstractPartialFunction[@specialized(scala.Int, scala.Long, scala // let's not make it final so as not to confuse anyone /*final*/ def apply(x: T1): R = applyOrElse(x, PartialFunction.empty) } - -// Manual stand-ins for formerly specialized variations. -// Not comprehensive, only sufficent to run scala-check built scala 2.11.0-M5 -// TODO Scala 2.10.0.M6 Remove this once scalacheck is published against M6. -private[runtime] abstract class AbstractPartialFunction$mcIL$sp extends scala.runtime.AbstractPartialFunction[Any, Int] { - override def apply(x: Any): Int = apply$mcIL$sp(x) - def apply$mcIL$sp(x: Any): Int = applyOrElse(x, PartialFunction.empty) -} -private[runtime] abstract class AbstractPartialFunction$mcFL$sp extends scala.runtime.AbstractPartialFunction[Any, Float] { - override def apply(x: Any): Float = apply$mcIL$sp(x) - def apply$mcIL$sp(x: Any): Float = applyOrElse(x, PartialFunction.empty) -} diff --git a/src/library/scala/util/Properties.scala b/src/library/scala/util/Properties.scala index 13f2362d00..d597feb898 100644 --- a/src/library/scala/util/Properties.scala +++ b/src/library/scala/util/Properties.scala @@ -173,7 +173,7 @@ private[scala] trait PropertiesTrait { * isJavaAtLeast("1.6") // true * isJavaAtLeast("1.7") // true * isJavaAtLeast("1.8") // false - * }} + * }}} */ def isJavaAtLeast(version: String): Boolean = { def parts(x: String) = { 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 |