| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
| |
The previous implementation has a major bug - although `clear()` sets the root node to `null`, the `size` attribute of the `Tree` was not updated. This effectively meant that even after a `map.clear()`, a call to `map.size` would still yield the old size of the map.
The scalacheck test suite was updated to contemplate this issue.
|
| |\
| |
| | |
SI-4147 Add an implementation of `mutable.TreeMap`
|
| | |
| |
| |
| |
| |
| |
| |
| |
| |
| | |
This commit contains an implementation of a mutable red-black tree with focus on performance. It also contains a new `mutable.TreeMap` Scala collection that is backed by the aforementioned tree. The common generic factories and traits related to mutable sorted maps didn't exist yet, so this commit also adds them.
Regarding performance, `TreeMap` overrides (from `MapLike` and `SortedMapLike`) all of the most common methods for maps and also those whose default implementations are asymptotically worse than direct red-black tree algorithms (e.g. `last`, `clear`).
The `rangeImpl` method of `TreeMap` returns an instance of `TreeMapView`, an inner class of `TreeMap`. This view is backed by the same `RedBlackTree.Tree` instance, and therefore changes to the original map are reflected in the view and vice-versa. The semantics of mutating a view by adding and removing keys outside the view's range are the same of the current `mutable.TreeSet`. A bit less focus was given on the performance of views - in particular, getting the `size` of a `TreeMapView` is O(n) on the number of elements inside the view bounds. That can be improved in the future.
In a future commit, `mutable.TreeSet` can be changed to be backed by this red-black tree implementation.
|
| |\ \
| | |
| | | |
Documentation for split [ci: last-only]
|
| | |/
| |
| |
| |
| |
| | |
Reverts to calling String.split(re: String), but change escape to
always put us on the JDK7 fast-path if possible, which is for everything
but Chars representing surrogate codeunits
|
| |\ \
| |/
|/| |
|
| | |\
| | |
| | | |
Fix 25 typos (g-i)
|
| | | | |
|
| | |\ \
| | |/
| |/| |
SI-9206 Fix REPL code indentation
|
| | | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
Previously, handy `sys.BooleanProp.keyExists` ignored the
property value. While trying not to make any real estate puns,
this commit will let it go false if a value is supplied that
is not true in the usual Java sense. But what is truth?
Allows `scala -Dscala.color=off`, for example.
|
| | | | |
|
| | |\ \
| | |/
| |/| |
SI-8930 - Vector updated, +:, and :+ slow when typed as Seq[A]
|
| | | |
| | |
| | |
| | |
| | |
| | | |
Vector was intercepting only the IndexedSeq CanBuildFrom to quickly generate new vectors. Now it intercepts immutable.Seq and collection.Seq as well.
There are other possibilities (collection.IndexedSeq), but they will probably arise rarely, and to avoid an absurdly long set of checks we would need a marker trait (that is not binary compatible).
|
| | |\ \
| | | |
| | | | |
Doc fixes
|
| | | | | |
|
| | | | | |
|
| | |\ \ \
| | | | |
| | | | | |
SI-9354 ScalaDoc members added via by-name view
|
| | | |/ /
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | | |
Eligible views were looked up by exact from type without
including the by-name dodge.
By-name views are now included without consideration whether
ScalaDoc processes possible duplicates correctly.
|
| | |\ \ \
| | |_|/
| |/| | |
fix BigDecimal losing MathContext
|
| | | | | |
|
| | |\ \ \
| | | | |
| | | | | |
Improve API documentation for ListBuffer and Try
|
| | | | | | |
|
| | |\ \ \ \
| | | | | |
| | | | | | |
SI-9348 Fix missing last element in exclusive floating point ranges
|
| | | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | | |
Fix exclusive floating point ranges to contain also the last element
when the end-start difference is not an integer multiple of step.
|
| | |\ \ \ \ \
| | |/ / / /
| |/| | | | |
SI-8254 List SerializationProxy fails to default(Read/Write)Object
|
| | | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | | |
Added `defaultWriteObject` to the beginning of `writeObject` and `defaultReadObject` to the beginning of `readObject` as required by specs:
[writing](http://docs.oracle.com/javase/6/docs/platform/serialization/spec/output.html#861), [reading](http://docs.oracle.com/javase/6/docs/platform/serialization/spec/input.html#2971).
Verified that it is a no-op in terms of serialization stream (but it provides hooks that Infinispan and others may use).
No explicit tests. If there is a change in serialization, t8549 will catch it.
|
| | |\ \ \ \ \
| | |_|/ / /
| |/| | | | |
Clean implementation of sorts for scala.util.Sorting.
|
| | | | |_|/
| | |/| |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | | |
Removed code based on Sun JDK sorts and implemented new (basic) sorts from
scratch. Deferred to Java Arrays.sort whenever practical. Behavior of
`scala.util.Sorting` should be unchanged, but changed documentation to
specify when the Java methods are being used (as they're typically very fast).
A JUnit test is provided.
Performance is important for sorts. Everything is better with this patch,
though it could be better yet, as described below.
Below are sort times (in microseconds, SEM < 5%) for various 1024-element
arrays of small case classes that compare on an int field (quickSort), or
int arrays that use custom ordering (stableSort). Note: "degenerate"
means there are only 16 values possible, so there are lots of ties.
Times are all with fresh data (no re-using cache from run to run).
Results:
```
random sorted reverse degenerate big:64k tiny:16
Old Sorting.quickSort 234 181 178 103 25,700 1.4
New Sorting.quickSort 170 27 115 74 18,600 0.8
Old Sorting.stableSort 321 234 236 282 32,600 2.1
New Sorting.stableSort 239 16 194 194 25,100 1.2
java.util.Arrays.sort 124 4 8 105 13,500 0.8
java.util.Arrays.sort|Box 126 15 13 112 13,200 0.9
```
The new versions are uniformly faster, but uniformly slower than Java sorting. scala.util.Sorting has use cases that don't map easily in to Java unless everything is pre-boxed, but the overhead of pre-boxing is minimal compared to the sort.
A snapshot of some of my benchmarking code is below.
(Yes, lots of repeating myself--it's dangerous not to when trying to get
somewhat accurate benchmarks.)
```
import java.util.Arrays
import java.util.Comparator
import math.Ordering
import util.Sorting
import reflect.ClassTag
val th = ichi.bench.Thyme.warmed()
case class N(i: Int, j: Int) {}
val a = Array.fill(1024)( Array.tabulate(1024)(i => N(util.Random.nextInt, i)) )
var ai = 0
val b = Array.fill(1024)( Array.tabulate(1024)(i => N(i, i)) )
var bi = 0
val c = Array.fill(1024)( Array.tabulate(1024)(i => N(1024-i, i)) )
var ci = 0
val d = Array.fill(1024)( Array.tabulate(1024)(i => N(util.Random.nextInt(16), i)) )
var di = 0
val e = Array.fill(16)( Array.tabulate(65536)(i => N(util.Random.nextInt, i)) )
var ei = 0
val f = Array.fill(65535)( Array.tabulate(16)(i => N(util.Random.nextInt, i)) )
var fi = 0
val o = new Ordering[N]{ def compare(a: N, b: N) = if (a.i < b.i) -1 else if (a.i > b.i) 1 else 0 }
for (s <- Seq("one", "two", "three")) {
println(s)
th.pbench{ val x = a(ai).clone; ai = (ai+1)%a.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = b(bi).clone; bi = (bi+1)%b.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = c(ci).clone; ci = (ci+1)%c.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = d(di).clone; di = (di+1)%d.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = e(ei).clone; ei = (ei+1)%e.length; Sorting.quickSort(x)(o); x(x.length/3) }
th.pbench{ val x = f(fi).clone; fi = (fi+1)%f.length; Sorting.quickSort(x)(o); x(x.length/3) }
}
def ix(ns: Array[N]) = {
val is = new Array[Int](ns.length)
var i = 0
while (i < ns.length) {
is(i) = ns(i).i
i += 1
}
is
}
val p = new Ordering[Int]{ def compare(a: Int, b: Int) = if (a > b) 1 else if (a < b) -1 else 0 }
for (s <- Seq("one", "two", "three")) {
println(s)
val tag: ClassTag[Int] = implicitly[ClassTag[Int]]
th.pbench{ val x = ix(a(ai)); ai = (ai+1)%a.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(b(bi)); bi = (bi+1)%b.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(c(ci)); ci = (ci+1)%c.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(d(di)); di = (di+1)%d.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(e(ei)); ei = (ei+1)%e.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
th.pbench{ val x = ix(f(fi)); fi = (fi+1)%f.length; Sorting.stableSort(x)(tag, p); x(x.length/3) }
}
for (s <- Seq("one", "two", "three")) {
println(s)
th.pbench{ val x = a(ai).clone; ai = (ai+1)%a.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = b(bi).clone; bi = (bi+1)%b.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = c(ci).clone; ci = (ci+1)%c.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = d(di).clone; di = (di+1)%d.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = e(ei).clone; ei = (ei+1)%e.length; Arrays.sort(x, o); x(x.length/3) }
th.pbench{ val x = f(fi).clone; fi = (fi+1)%f.length; Arrays.sort(x, o); x(x.length/3) }
}
def bx(is: Array[Int]): Array[java.lang.Integer] = {
val Is = new Array[java.lang.Integer](is.length)
var i = 0
while (i < is.length) {
Is(i) = java.lang.Integer.valueOf(is(i))
i += 1
}
Is
}
def xb(Is: Array[java.lang.Integer]): Array[Int] = {
val is = new Array[Int](Is.length)
var i = 0
while (i < is.length) {
is(i) = Is(i).intValue
i += 1
}
is
}
val q = new Comparator[java.lang.Integer]{
def compare(a: java.lang.Integer, b: java.lang.Integer) = o.compare(a.intValue, b.intValue)
}
for (s <- Seq("one", "two", "three")) {
println(s)
val tag: ClassTag[Int] = implicitly[ClassTag[Int]]
th.pbench{ val x = bx(ix(a(ai))); ai = (ai+1)%a.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(b(bi))); bi = (bi+1)%b.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(c(ci))); ci = (ci+1)%c.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(d(di))); di = (di+1)%d.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(e(ei))); ei = (ei+1)%e.length; Arrays.sort(x, q); xb(x)(x.length/3) }
th.pbench{ val x = bx(ix(f(fi))); fi = (fi+1)%f.length; Arrays.sort(x, q); xb(x)(x.length/3) }
}
```
|
| | | | | | |
|
| | |/ / / |
|
| | | | |
| | | |
| | | |
| | | |
| | | |
| | | |
| | | | |
The queue is only used when the prefix is drained by finish.
Since a finished flag has been introduced, distinguish between
the drained state and using the underlying (buffered) iterator.
|
| | | |/
| |/|
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
Since the leading and trailing iterators returned by span
share the underlying iterator, the leading iterator must
flag when it is exhausted (when the span predicate fails)
since the trailing iterator will advance the underlying
iterator.
It would also be possible to leave the failing element in
the leading lookahead buffer, where it would forever fail
the predicate, but that entails evaluating the predicate
twice, on both enqueue and dequeue.
|
| | | | |
|
| | | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
Remove object allocation overhead by peeling off abstraction layer,
revealing that the `ArrayOps` implicit conversions in `Predef`
return value classes.
d3f879a6b0 turned `ArrayOps.of<???>` into value classes,
but the non-`AnyVal` result type of the corresponding
`<???>arrayOps` implicit conversions (`ArrayOps[_]`) caused boxing anyway.
The optimized versions are introduced under a new name,
so that the old ones (without `implicit`) can be kept
for binary compatibility, for now.
|
| |\| | |
|
| | | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
Similarly to GenSeqLike.apply, GenSeqLike.updated can throw
IndexOutOfBoundsException.
For example, the following throws IndexOutOfBoundsException:
Vector.empty[String].updated(0, "foo")
|
| | | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | | |
Previously, the flag caused any elidable to be elided.
This commit simply sets -Xelide-below to ASSERTION + 1.
The flag is useful because there's no mnemonic for specifying
the magic constant as an option argument. `-Xelide-below ASSERTION`
means asserts are enabled.
|
| | |\ \
| | | |
| | | | |
Remove references to the old PDF version of the specification
|
| | | | | |
|
| | |\ \ \
| | | | |
| | | | | |
Fix scaladoc of Try#failed
|
| | | | | |
| | | | |
| | | | |
| | | | |
| | | | | |
The documentation stated that it returns a Success[Throwable] regardless, either containing the failure or an UnsupportedOperationException. However only Failure#failed returns a success; Success#failed returns a Failure.
Also the phrasing of "Completes this `Try`" and "that `Try` failed with" sounds like it was copy-pasted from Future? Trys don't complete, nor fail, they are immutable.
|
| | |/ / /
| | | |
| | | | |
Assertions can be elided at compile time; they generate no runtime conditional code and are in fact run unconditionally if not elided during compilation. Updated documentation to reflect that.
|
| |\| | |
| | | |
| | | |
| | | | |
merge/2.11.x-to-2.12.x-20150501
|
| | |\ \ \
| | | | |
| | | | | |
SI-9254 UnrolledBuffer appends in wrong position
|
| | | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | | |
Fixed two bugs in insertion (insertAll of Unrolled):
1. Incorrect recursion leading to an inability to insert past the first chunk
2. Incorect repositioning of `lastptr` leading to strange `append` behavior after early insertion
Added tests checking that both of these things now work.
Also added a comment that "waterlineDelim" is misnamed. But we can't fix it now--it's part of the public API. (Shouldn't be, but it is.)
|
| | |\ \ \ \
| | | | | |
| | | | | | |
SI-9197 Duration.Inf not a singleton when deserialized
|
| | | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | | |
Made `Duration.Undefined`, `.Inf`, and `.MinusInf` all give back the singleton instance instead of creating a new copy by overriding readResolve.
This override can be (and is) private, which at least on Sun's JDK8 doesn't mess with the auto-generated SerialVersionUIDs.
Thus, the patch should make things strictly better: if you're on 2.11.7+ on JVMs which pick the same SerialVersionUIDs, you can recover singletons. Everywhere else you were already in trouble anyway.
|
| | | | | | |
| | | | | |
| | | | | |
| | | | | |
| | | | | | |
This commit corrects many typos found in scaladocs and comments.
There's also fixed the name of a private method in ICodeCheckers.
|
| | | | | | | |
|
| | | | | | | |
|
