diff options
Diffstat (limited to 'src')
3 files changed, 97 insertions, 16 deletions
diff --git a/src/library/scala/collection/SequenceProxy.scala b/src/library/scala/collection/SequenceProxy.scala index fa3d939e72..a3e9497029 100644 --- a/src/library/scala/collection/SequenceProxy.scala +++ b/src/library/scala/collection/SequenceProxy.scala @@ -14,8 +14,8 @@ package scala.collection import generic._ -/** This trait implements a proxy for iterable objects. It forwards - * all calls to a different iterable object +/** This trait implements a proxy for sequence objects. It forwards + * all calls to a different sequence object. * * @author Martin Odersky * @version 2.8 diff --git a/src/library/scala/collection/generic/SequenceTemplate.scala b/src/library/scala/collection/generic/SequenceTemplate.scala index df49b442bb..ee0f94a583 100644 --- a/src/library/scala/collection/generic/SequenceTemplate.scala +++ b/src/library/scala/collection/generic/SequenceTemplate.scala @@ -317,15 +317,24 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]] * index where <code>that</code> is contained * @see String.indexOf */ - def indexOfSeq[B >: A](that: Sequence[B]): Int = { - var i = 0 - var s: Sequence[A] = thisCollection - while (!s.isEmpty && !(s startsWith that)) { - i += 1 - s = s.tail + def indexOfSeq[B >: A](that: Sequence[B]): Int = indexOfSeq(that, 0) + + def indexOfSeq[B >: A](that: Sequence[B], fromIndex: Int): Int = + if (that.hasDefiniteSize) + indexOf_KMP(thisCollection, 0, length, that, 0, that.length, fromIndex) + else { + var i = fromIndex + var s: Sequence[A] = thisCollection drop i + while (!s.isEmpty) { + if (s startsWith that) + return i + + i += 1 + s = s.tail + } + -1 } - if (!s.isEmpty || that.isEmpty) i else -1 - } + /** Tests if the given value <code>elem</code> is a member of this * sequence. @@ -479,6 +488,78 @@ trait SequenceTemplate[+A, +This <: IterableTemplate[A, This] with Sequence[A]] override def view(from: Int, until: Int) = view.slice(from, until) + // KMP implementation by paulp, based on the undoubtedly reliable wikipedia entry + private def KMP[B](S: Seq[B], W: Seq[B]): Option[Int] = { + // trivial cases + if (W.isEmpty) return Some(0) + else if (W drop 1 isEmpty) return S.indexOf(W(0)) match { + case -1 => None + case x => Some(x) + } + + val T: Array[Int] = { + val arr = new Array[Int](W.length) + var pos = 2 + var cnd = 0 + arr(0) = -1 + arr(1) = 0 + while (pos < W.length) { + if (W(pos - 1) == W(cnd)) { + arr(pos) = cnd + 1 + pos += 1 + cnd += 1 + } + else if (cnd > 0) { + cnd = arr(cnd) + } + else { + arr(pos) = 0 + pos += 1 + } + } + arr + } + + var m, i = 0 + def mi = m + i + + while (mi < S.length) { + if (W(i) == S(mi)) { + i += 1 + if (i == W.length) + return Some(m) + } + else { + m = mi - T(i) + if (i > 0) + i = T(i) + } + } + None + } + private def indexOf_KMP[B]( + source: Seq[B], sourceOffset: Int, sourceCount: Int, + target: Seq[B], targetOffset: Int, targetCount: Int, + fromIndex: Int): Int = + KMP(source.slice(sourceOffset, sourceCount) drop fromIndex, target.slice(targetOffset, targetCount)) match { + case None => -1 + case Some(x) => x + fromIndex + } + + private def lastIndexOf_KMP[B]( + source: Seq[B], sourceOffset: Int, sourceCount: Int, + target: Seq[B], targetOffset: Int, targetCount: Int, + fromIndex: Int): Int = { + val src = (source.slice(sourceOffset, sourceCount) take fromIndex).reverse + val tgt = target.slice(targetOffset, targetCount).reverse + + KMP(src, tgt) match { + case None => -1 + case Some(x) => (src.length - tgt.length - x) + sourceOffset + } + } + + override def equals(that: Any): Boolean = that match { case that1: Sequence[a] => val these = this.iterator diff --git a/src/library/scala/collection/generic/VectorTemplate.scala b/src/library/scala/collection/generic/VectorTemplate.scala index f8be15016a..31f728e835 100644 --- a/src/library/scala/collection/generic/VectorTemplate.scala +++ b/src/library/scala/collection/generic/VectorTemplate.scala @@ -257,12 +257,12 @@ trait VectorTemplate[+A, +This <: VectorTemplate[A, This] with Vector[A]] extend super.endsWith(that) } - override def indexOfSeq[B >: A](that: Sequence[B]): Int = { - var i = 0 - val last = length - that.length - while (i <= last && !startsWith(that, i)) i += 1 - negLength(i) - } + // override def indexOfSeq[B >: A](that: Sequence[B]): Int = { + // var i = 0 + // val last = length - that.length + // while (i <= last && !startsWith(that, i)) i += 1 + // negLength(i) + // } override def equals(that: Any): Boolean = that match { case that1: Vector[a] => |