From 3355ead4eb75d2bc1f02300b82d154c76191a48a Mon Sep 17 00:00:00 2001
From: Paul Phillips <paulp@improving.org>
Date: Fri, 17 Jul 2009 15:04:53 +0000
Subject: A start on a more comprehensive test suite for ...

A start on a more comprehensive test suite for sequences. It performs
3600 different tests attempting to exercise the potentially buggy
variations of startsWith, endsWith, indexOfSeq, and sameElements.

And, a KMP implementation of indexOfSeq which in addition to being a
lot faster for definite sized sequences, should give the wrong answer
somewhat less frequently.
---
 src/library/scala/collection/SequenceProxy.scala   |  4 +-
 .../collection/generic/SequenceTemplate.scala      | 97 ++++++++++++++++++++--
 .../scala/collection/generic/VectorTemplate.scala  | 12 +--
 3 files changed, 97 insertions(+), 16 deletions(-)

(limited to 'src/library')

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] =>
-- 
cgit v1.2.3