From 1747692434cece862d63a0f67decd810707b1508 Mon Sep 17 00:00:00 2001 From: Tiark Rompf Date: Wed, 14 Oct 2009 21:05:28 +0000 Subject: added methods updated +: :+ to SeqLike --- src/library/scala/collection/SeqLike.scala | 42 ++- src/library/scala/collection/SeqViewLike.scala | 2 + .../scala/collection/immutable/Vector.scala | 380 +++++++++++---------- 3 files changed, 240 insertions(+), 184 deletions(-) diff --git a/src/library/scala/collection/SeqLike.scala b/src/library/scala/collection/SeqLike.scala index 50ea0c3a5a..25be79b0d5 100644 --- a/src/library/scala/collection/SeqLike.scala +++ b/src/library/scala/collection/SeqLike.scala @@ -6,7 +6,7 @@ ** |/ ** \* */ -// $Id$ +// $Id: SeqLike.scala 18895 2009-10-02 17:57:16Z odersky $ package scala.collection @@ -133,7 +133,7 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self => * is O(length min len) instead of O(length). The method should be overwritten * if computing length is cheap. */ - def lengthCompare(len: Int): Int = { + def lengthCompare(len: Int): Int = { //TR: should use iterator? var i = 0 breakable { for (_ <- this) { @@ -157,7 +157,7 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self => * @param p the predicate * @param from the start index */ - def segmentLength(p: A => Boolean, from: Int): Int = { + def segmentLength(p: A => Boolean, from: Int): Int = { //TR: should use iterator? var result = 0 var i = 0 breakable { @@ -190,7 +190,7 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self => * @param p the predicate * @param from the start index */ - def indexWhere(p: A => Boolean, from: Int): Int = { + def indexWhere(p: A => Boolean, from: Int): Int = { //TR: should use iterator? var result = -1 var i = from breakable { @@ -460,7 +460,7 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self => */ def removeDuplicates: Repr = { val b = newBuilder - var seen = Set[A]() + var seen = Set[A]() //TR: should use mutable.HashSet? for (x <- this) { if (!(seen contains x)) { b += x @@ -483,6 +483,38 @@ trait SeqLike[+A, +Repr] extends IterableLike[A, Repr] { self => b.result } + /** Returns a copy of this sequence with the element at position `index` replaced by `elem`. + */ + def updated[B >: A, That](index: Int, elem: B)(implicit bf: BuilderFactory[B, That, Repr]): That = { + val b = bf(repr) + val (prefix, rest) = this.splitAt(index) + b ++= toCollection(prefix) + b += elem + b ++= toCollection(rest).view.tail + b.result + } + + /** Returns a new sequence consisting of `elem` followed by the elements of this sequence. + */ + def +:[B >: A, That](elem: B)(implicit bf: BuilderFactory[B, That, Repr]): That = { + val b = bf(repr) + b += elem + b ++= thisCollection + b.result + } + + /** Returns a new sequence consisting of the elements of this sequence followed by `elem`. + */ + def :+[B >: A, That](elem: B)(implicit bf: BuilderFactory[B, That, Repr]): That = { + val b = bf(repr) + b ++= thisCollection + b += elem + b.result + } + + + + /** Returns a new sequence of given length containing the elements of this sequence followed by zero * or more occurrences of given elements. */ diff --git a/src/library/scala/collection/SeqViewLike.scala b/src/library/scala/collection/SeqViewLike.scala index 38cfa7ba05..27389c8a5c 100644 --- a/src/library/scala/collection/SeqViewLike.scala +++ b/src/library/scala/collection/SeqViewLike.scala @@ -161,6 +161,8 @@ trait SeqViewLike[+A, // else super.patch[B, That](from, patch, replaced)(bf) } + //TR TODO: updated, +: ed :+ ed + override def padTo[B >: A, That](len: Int, elem: B)(implicit bf: BuilderFactory[B, That, This]): That = patch(length, fill(len - length)(elem), 0) diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index 30d766ee01..4b0cecf582 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -8,15 +8,14 @@ // $Id: Vector.scala 19072 2009-10-13 12:19:59Z rompf $ - -// Questions: how to name update, appendFront, appendBack? -// how to make them available? trait Vector? VectorLike? have another companion object VectorImpl? -// mix in LinearSeq as well? <-- not yet +// TODO: check overhead of builder factories for methods updated, +: and :+ package scala.collection package immutable import scala.annotation.unchecked.uncheckedVariance +import compat.Platform.arraycopy // FIXME: Platform.arraycopy is slower than System.arraycopy. + // Need to check why it isn't inlined. import scala.collection.generic._ import scala.collection.mutable.Builder @@ -39,7 +38,7 @@ trait Vector[+A] extends Seq[A] object Vector extends SeqFactory[Vector] { implicit def builderFactory[A]: BuilderFactory[A, Vector[A], Coll] = new VirtualBuilderFactory[A] - override def empty[A]: Vector[A] = NewVector.empty[A] + override def empty[A] = NewVector.empty[A] def newBuilder[A]: Builder[A, Vector[A]] = NewVector.newBuilder[A] } @@ -47,20 +46,22 @@ object Vector extends SeqFactory[Vector] { // implementation classes below - trait NewVector[+A] extends Vector[A] with GenericTraversableTemplate[A, NewVector] - with VectorLike[A, NewVector[A]] { + with VectorLike[A, NewVector[A]] + with SeqLike[A, NewVector[A]] { // use impl from SeqLike, not VectorLike override def companion: GenericCompanion[NewVector] = NewVector } object NewVector extends SeqFactory[NewVector] { + private[immutable] val bf = new VirtualBuilderFactory[Nothing] implicit def builderFactory[A]: BuilderFactory[A, NewVector[A], Coll] = - new VirtualBuilderFactory[A] + bf.asInstanceOf[BuilderFactory[A, NewVector[A], Coll]] def newBuilder[A]: Builder[A, NewVector[A]] = new NewVectorBuilder[A] + override def empty[A]: NewVector[A] = new NewVectorImpl[A](0, 0, 0) - // TODO: override object empty { } + // TODO: special-case empty vectors and empty builders } @@ -68,7 +69,7 @@ object NewVector extends SeqFactory[NewVector] { @serializable @SerialVersionUID(7129304555082767876L) -class NewVectorImpl[+A](startIndex: Int, endIndex: Int, focus: Int) extends NewVector[A] +private class NewVectorImpl[+A](startIndex: Int, endIndex: Int, focus: Int) extends NewVector[A] with NewVectorPointer[A @uncheckedVariance] { //assert(startIndex >= 0, startIndex+"<0") @@ -89,6 +90,12 @@ class NewVectorImpl[+A](startIndex: Int, endIndex: Int, focus: Int) extends NewV // TODO: reverse // TODO: reverseIterator + def apply(index: Int): A = { + val idx = checkRangeConvert(index) +// //println("get elem: "+index + "/"+idx + "(focus:" +focus+" xor:"+(idx^focus)+" depth:"+depth+")") + getElem(idx, idx ^ focus) + } + private def checkRangeConvert(index: Int) = { val idx = index + startIndex if (0 <= index && idx < endIndex) @@ -97,19 +104,22 @@ class NewVectorImpl[+A](startIndex: Int, endIndex: Int, focus: Int) extends NewV throw new IndexOutOfBoundsException(index.toString) } - def apply(index: Int): A = { - val idx = checkRangeConvert(index) -// //println("get elem: "+index + "/"+idx + "(focus:" +focus+" xor:"+(idx^focus)+" depth:"+depth+")") - getElem(idx, idx ^ focus) + + // SeqLike api + + override def updated[B >: A, That](index: Int, elem: B)(implicit bf: BuilderFactory[B, That, NewVector[A]]): That = { + // just ignore bf + updateAt(index, elem).asInstanceOf[That] } - def update[B>:A](index: Int, value: B): NewVector[B] = { - val idx = checkRangeConvert(index) - val s = new NewVectorImpl[B](startIndex, endIndex, idx) - s.initFrom(this) - s.gotoPosClean(focus, idx, focus ^ idx) - s.display0(idx & 0x1f) = value.asInstanceOf[AnyRef] - s + override def +:[B >: A, That](elem: B)(implicit bf: BuilderFactory[B, That, NewVector[A]]): That = { + // just ignore bf + appendFront(elem).asInstanceOf[That] + } + + override def :+[B >: A, That](elem: B)(implicit bf: BuilderFactory[B, That, NewVector[A]]): That = { + // just ignore bf + appendBack(elem).asInstanceOf[That] } override def take(n: Int): NewVector[A] = { @@ -145,168 +155,17 @@ class NewVectorImpl[+A](startIndex: Int, endIndex: Int, focus: Int) extends NewV } + // semi-private api - private def copyRange(array: Array[AnyRef], oldLeft: Int, newLeft: Int) = { - val elems = new Array[AnyRef](32) - System.arraycopy(array, oldLeft, elems, newLeft, 32 - Math.max(newLeft,oldLeft)) - elems - } - - private def shiftTopLevel(oldLeft: Int, newLeft: Int) = (depth - 1) match { - case 0 => - display0 = copyRange(display0, oldLeft, newLeft) - case 1 => - display1 = copyRange(display1, oldLeft, newLeft) - case 2 => - display2 = copyRange(display2, oldLeft, newLeft) - case 3 => - display3 = copyRange(display3, oldLeft, newLeft) - case 4 => - display4 = copyRange(display4, oldLeft, newLeft) - case 5 => - display5 = copyRange(display5, oldLeft, newLeft) - } - - private def cleanLeftEdge(cutIndex: Int) = (depth - 1) match { - case 5 => - for (i <- 0 until ((cutIndex >>> 25) & 0x1f)) display5(i) = null - for (i <- 0 until ((cutIndex >>> 20) & 0x1f)) display4(i) = null - for (i <- 0 until ((cutIndex >>> 15) & 0x1f)) display3(i) = null - for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null - for (i <- 0 until ((cutIndex >>> 5) & 0x1f)) display1(i) = null - for (i <- 0 until ((cutIndex >>> 0) & 0x1f)) display0(i) = null - case 4 => - display5 = null - for (i <- 0 until ((cutIndex >>> 20) & 0x1f)) display4(i) = null - for (i <- 0 until ((cutIndex >>> 15) & 0x1f)) display3(i) = null - for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null - for (i <- 0 until ((cutIndex >>> 5) & 0x1f)) display1(i) = null - for (i <- 0 until ((cutIndex >>> 0) & 0x1f)) display0(i) = null - case 3 => - display5 = null - display4 = null - for (i <- 0 until ((cutIndex >>> 15) & 0x1f)) display3(i) = null - for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null - for (i <- 0 until ((cutIndex >>> 5) & 0x1f)) display1(i) = null - for (i <- 0 until ((cutIndex >>> 0) & 0x1f)) display0(i) = null - case 2 => - display5 = null - display4 = null - display3 = null - for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null - for (i <- 0 until ((cutIndex >>> 5) & 0x1f)) display1(i) = null - for (i <- 0 until ((cutIndex >>> 0) & 0x1f)) display0(i) = null - case 1 => - display5 = null - display4 = null - display3 = null - display2 = null - for (i <- 0 until ((cutIndex >>> 5) & 0x1f)) display1(i) = null - for (i <- 0 until ((cutIndex >>> 0) & 0x1f)) display0(i) = null - case 0 => - display5 = null - display4 = null - display3 = null - display2 = null - display1 = null - for (i <- 0 until ((cutIndex >>> 0) & 0x1f)) display0(i) = null - } - - private def cleanRightEdge(cutIndex: Int) = (depth - 1) match { - case 5 => - for (i <- ((cutIndex >>> 25) & 0x1f) until 32) display5(i) = null - for (i <- ((cutIndex >>> 20) & 0x1f) until 32) display4(i) = null - for (i <- ((cutIndex >>> 15) & 0x1f) until 32) display3(i) = null - for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null - for (i <- ((cutIndex >>> 5) & 0x1f) until 32) display1(i) = null - for (i <- ((cutIndex >>> 0) & 0x1f) until 32) display0(i) = null - case 4 => - display5 = null - for (i <- ((cutIndex >>> 20) & 0x1f) until 32) display4(i) = null - for (i <- ((cutIndex >>> 15) & 0x1f) until 32) display3(i) = null - for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null - for (i <- ((cutIndex >>> 5) & 0x1f) until 32) display1(i) = null - for (i <- ((cutIndex >>> 0) & 0x1f) until 32) display0(i) = null - case 3 => - display5 = null - display4 = null - for (i <- ((cutIndex >>> 15) & 0x1f) until 32) display3(i) = null - for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null - for (i <- ((cutIndex >>> 5) & 0x1f) until 32) display1(i) = null - for (i <- ((cutIndex >>> 0) & 0x1f) until 32) display0(i) = null - case 2 => - display5 = null - display4 = null - display3 = null - for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null - for (i <- ((cutIndex >>> 5) & 0x1f) until 32) display1(i) = null - for (i <- ((cutIndex >>> 0) & 0x1f) until 32) display0(i) = null - case 1 => - display5 = null - display4 = null - display3 = null - display2 = null - for (i <- ((cutIndex >>> 5) & 0x1f) until 32) display1(i) = null - for (i <- ((cutIndex >>> 0) & 0x1f) until 32) display0(i) = null - case 0 => - display5 = null - display4 = null - display3 = null - display2 = null - display1 = null - for (i <- ((cutIndex >>> 0) & 0x1f) until 32) display0(i) = null - } - - private def requiredDepth(xor: Int) = { - if (xor < (1 << 5)) 1 - else if (xor < (1 << 10)) 2 - else if (xor < (1 << 15)) 3 - else if (xor < (1 << 20)) 4 - else if (xor < (1 << 25)) 5 - else if (xor < (1 << 30)) 6 - else throw new IllegalArgumentException() - } - - private def dropFront0(cutIndex: Int): NewVector[A] = { - var blockIndex = cutIndex & ~31 - var lo = cutIndex & 31 - - val xor = cutIndex ^ (endIndex - 1) - val d = requiredDepth(xor) - val shift = (cutIndex & ~((1 << (5*d))-1)) - - //println("cut front at " + cutIndex + ".." + endIndex + " (xor: "+xor+" shift: " + shift + " d: " + d +")") - - val s = new NewVectorImpl(cutIndex-shift, endIndex-shift, blockIndex-shift) - s.initFrom(this) - if (s.depth > 1) - s.gotoPos(blockIndex, focus ^ blockIndex) - s.depth = d - s.stabilize(blockIndex-shift) - s.cleanLeftEdge(cutIndex-shift) - s - } - - private def dropBack0(cutIndex: Int): NewVector[A] = { - var blockIndex = (cutIndex - 1) & ~31 - var lo = ((cutIndex - 1) & 31) + 1 - - val xor = startIndex ^ (cutIndex - 1) - val d = requiredDepth(xor) - - //println("cut back at " + startIndex + ".." + cutIndex + " (xor: "+xor+" d: " + d +")") - - val s = new NewVectorImpl(startIndex, cutIndex, blockIndex) + def updateAt[B >: A](index: Int, elem: B): NewVector[B] = { + val idx = checkRangeConvert(index) + val s = new NewVectorImpl[B](startIndex, endIndex, idx) s.initFrom(this) - if (s.depth > 1) - s.gotoPos(blockIndex, focus ^ blockIndex) - s.depth = d - s.stabilize(blockIndex) - s.cleanRightEdge(cutIndex) + s.gotoPosClean(focus, idx, focus ^ idx) + s.display0(idx & 0x1f) = elem.asInstanceOf[AnyRef] s } - def appendFront[B>:A](value: B): NewVector[B] = { if (endIndex != startIndex) { var blockIndex = (startIndex - 1) & ~31 @@ -474,6 +333,169 @@ class NewVectorImpl[+A](startIndex: Int, endIndex: Int, focus: Int) extends NewV } } + + // low-level implementation (needs cleanup) + + private def copyRange(array: Array[AnyRef], oldLeft: Int, newLeft: Int) = { + val elems = new Array[AnyRef](32) + arraycopy(array, oldLeft, elems, newLeft, 32 - Math.max(newLeft,oldLeft)) + elems + } + + private def shiftTopLevel(oldLeft: Int, newLeft: Int) = (depth - 1) match { + case 0 => + display0 = copyRange(display0, oldLeft, newLeft) + case 1 => + display1 = copyRange(display1, oldLeft, newLeft) + case 2 => + display2 = copyRange(display2, oldLeft, newLeft) + case 3 => + display3 = copyRange(display3, oldLeft, newLeft) + case 4 => + display4 = copyRange(display4, oldLeft, newLeft) + case 5 => + display5 = copyRange(display5, oldLeft, newLeft) + } + + private def cleanLeftEdge(cutIndex: Int) = (depth - 1) match { + case 5 => + for (i <- 0 until ((cutIndex >>> 25) & 0x1f)) display5(i) = null + for (i <- 0 until ((cutIndex >>> 20) & 0x1f)) display4(i) = null + for (i <- 0 until ((cutIndex >>> 15) & 0x1f)) display3(i) = null + for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null + for (i <- 0 until ((cutIndex >>> 5) & 0x1f)) display1(i) = null + for (i <- 0 until ((cutIndex >>> 0) & 0x1f)) display0(i) = null + case 4 => + display5 = null + for (i <- 0 until ((cutIndex >>> 20) & 0x1f)) display4(i) = null + for (i <- 0 until ((cutIndex >>> 15) & 0x1f)) display3(i) = null + for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null + for (i <- 0 until ((cutIndex >>> 5) & 0x1f)) display1(i) = null + for (i <- 0 until ((cutIndex >>> 0) & 0x1f)) display0(i) = null + case 3 => + display5 = null + display4 = null + for (i <- 0 until ((cutIndex >>> 15) & 0x1f)) display3(i) = null + for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null + for (i <- 0 until ((cutIndex >>> 5) & 0x1f)) display1(i) = null + for (i <- 0 until ((cutIndex >>> 0) & 0x1f)) display0(i) = null + case 2 => + display5 = null + display4 = null + display3 = null + for (i <- 0 until ((cutIndex >>> 10) & 0x1f)) display2(i) = null + for (i <- 0 until ((cutIndex >>> 5) & 0x1f)) display1(i) = null + for (i <- 0 until ((cutIndex >>> 0) & 0x1f)) display0(i) = null + case 1 => + display5 = null + display4 = null + display3 = null + display2 = null + for (i <- 0 until ((cutIndex >>> 5) & 0x1f)) display1(i) = null + for (i <- 0 until ((cutIndex >>> 0) & 0x1f)) display0(i) = null + case 0 => + display5 = null + display4 = null + display3 = null + display2 = null + display1 = null + for (i <- 0 until ((cutIndex >>> 0) & 0x1f)) display0(i) = null + } + + private def cleanRightEdge(cutIndex: Int) = (depth - 1) match { + case 5 => + for (i <- ((cutIndex >>> 25) & 0x1f) until 32) display5(i) = null + for (i <- ((cutIndex >>> 20) & 0x1f) until 32) display4(i) = null + for (i <- ((cutIndex >>> 15) & 0x1f) until 32) display3(i) = null + for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null + for (i <- ((cutIndex >>> 5) & 0x1f) until 32) display1(i) = null + for (i <- ((cutIndex >>> 0) & 0x1f) until 32) display0(i) = null + case 4 => + display5 = null + for (i <- ((cutIndex >>> 20) & 0x1f) until 32) display4(i) = null + for (i <- ((cutIndex >>> 15) & 0x1f) until 32) display3(i) = null + for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null + for (i <- ((cutIndex >>> 5) & 0x1f) until 32) display1(i) = null + for (i <- ((cutIndex >>> 0) & 0x1f) until 32) display0(i) = null + case 3 => + display5 = null + display4 = null + for (i <- ((cutIndex >>> 15) & 0x1f) until 32) display3(i) = null + for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null + for (i <- ((cutIndex >>> 5) & 0x1f) until 32) display1(i) = null + for (i <- ((cutIndex >>> 0) & 0x1f) until 32) display0(i) = null + case 2 => + display5 = null + display4 = null + display3 = null + for (i <- ((cutIndex >>> 10) & 0x1f) until 32) display2(i) = null + for (i <- ((cutIndex >>> 5) & 0x1f) until 32) display1(i) = null + for (i <- ((cutIndex >>> 0) & 0x1f) until 32) display0(i) = null + case 1 => + display5 = null + display4 = null + display3 = null + display2 = null + for (i <- ((cutIndex >>> 5) & 0x1f) until 32) display1(i) = null + for (i <- ((cutIndex >>> 0) & 0x1f) until 32) display0(i) = null + case 0 => + display5 = null + display4 = null + display3 = null + display2 = null + display1 = null + for (i <- ((cutIndex >>> 0) & 0x1f) until 32) display0(i) = null + } + + private def requiredDepth(xor: Int) = { + if (xor < (1 << 5)) 1 + else if (xor < (1 << 10)) 2 + else if (xor < (1 << 15)) 3 + else if (xor < (1 << 20)) 4 + else if (xor < (1 << 25)) 5 + else if (xor < (1 << 30)) 6 + else throw new IllegalArgumentException() + } + + private def dropFront0(cutIndex: Int): NewVector[A] = { + var blockIndex = cutIndex & ~31 + var lo = cutIndex & 31 + + val xor = cutIndex ^ (endIndex - 1) + val d = requiredDepth(xor) + val shift = (cutIndex & ~((1 << (5*d))-1)) + + //println("cut front at " + cutIndex + ".." + endIndex + " (xor: "+xor+" shift: " + shift + " d: " + d +")") + + val s = new NewVectorImpl(cutIndex-shift, endIndex-shift, blockIndex-shift) + s.initFrom(this) + if (s.depth > 1) + s.gotoPos(blockIndex, focus ^ blockIndex) + s.depth = d + s.stabilize(blockIndex-shift) + s.cleanLeftEdge(cutIndex-shift) + s + } + + private def dropBack0(cutIndex: Int): NewVector[A] = { + var blockIndex = (cutIndex - 1) & ~31 + var lo = ((cutIndex - 1) & 31) + 1 + + val xor = startIndex ^ (cutIndex - 1) + val d = requiredDepth(xor) + + //println("cut back at " + startIndex + ".." + cutIndex + " (xor: "+xor+" d: " + d +")") + + val s = new NewVectorImpl(startIndex, cutIndex, blockIndex) + s.initFrom(this) + if (s.depth > 1) + s.gotoPos(blockIndex, focus ^ blockIndex) + s.depth = d + s.stabilize(blockIndex) + s.cleanRightEdge(cutIndex) + s + } + } @@ -743,7 +765,7 @@ trait NewVectorPointer[T] { final def copyOf(a: Array[AnyRef]) = { // //println("copy") val b = new Array[AnyRef](a.length) - System.arraycopy(a, 0, b, 0, a.length) + arraycopy(a, 0, b, 0, a.length) b } -- cgit v1.2.3