From 3355ead4eb75d2bc1f02300b82d154c76191a48a Mon Sep 17 00:00:00 2001 From: Paul Phillips 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 +- test/files/run/sequenceComparisons.check | 1 + test/files/run/sequenceComparisons.scala | 123 +++++++++++++++++++++ 5 files changed, 221 insertions(+), 16 deletions(-) create mode 100644 test/files/run/sequenceComparisons.check create mode 100644 test/files/run/sequenceComparisons.scala 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 that 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 elem 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] => diff --git a/test/files/run/sequenceComparisons.check b/test/files/run/sequenceComparisons.check new file mode 100644 index 0000000000..bb7669b154 --- /dev/null +++ b/test/files/run/sequenceComparisons.check @@ -0,0 +1 @@ +All 3600 tests passed. diff --git a/test/files/run/sequenceComparisons.scala b/test/files/run/sequenceComparisons.scala new file mode 100644 index 0000000000..ee4df8e40e --- /dev/null +++ b/test/files/run/sequenceComparisons.scala @@ -0,0 +1,123 @@ +import scala.collection.{ mutable, immutable } +import collection.{ Sequence, Traversable } + +object Test { + // TODO: + // + // SequenceProxy + // SequenceForwarder + // the commented out ones in seqMakers + + val seqMakers = List[List[Int] => Sequence[Int]]( + mutable.ArrayBuffer(_: _*), + // mutable.ArrayStack(_: _*), + mutable.Buffer(_: _*), + mutable.LinearSequence(_: _*), + // null on Nil + // mutable.LinkedList(_: _*), + mutable.ListBuffer(_: _*), + // immutable.Queue(_: _*), + // mutable.Queue(_: _*), + immutable.Sequence(_: _*), + mutable.Sequence(_: _*), + // immutable.Stack(_: _*), + // mutable.Stack(_: _*), + immutable.Vector(_: _*), + mutable.Vector(_: _*), + immutable.List(_: _*), + immutable.Stream(_: _*) + ) + + abstract class Data[T] { + val seq: Sequence[T] + // _1 is inputs which must be true, _2 which must be false + type Inputs = (List[List[T]], List[List[T]]) + case class Method( + f: (Sequence[T], Sequence[T]) => Boolean, + inputs: Inputs, + descr: String + ) { + def trueList = inputs._1 + def falseList = inputs._2 + } + + val startsWithInputs: Inputs + lazy val startsWith = Method(_ startsWith _, startsWithInputs, "%s startsWith %s") + + val endsWithInputs: Inputs + lazy val endsWith = Method(_ endsWith _, endsWithInputs, "%s endsWith %s") + + val indexOfSeqInputs: Inputs + private def subseqTest(s1: Sequence[T], s2: Sequence[T]) = (s1 indexOfSeq s2) != -1 + lazy val indexOfSeq = Method(subseqTest _, indexOfSeqInputs, "(%s indexOfSeq %s) != -1") + + val sameElementsInputs: Inputs + lazy val sameElements = Method(_ sameElements _, sameElementsInputs, "%s sameElements %s") + + def methodList = List(startsWith, endsWith, indexOfSeq, sameElements) + } + + object test1 extends Data[Int] { + val seq = List(1,2,3,4,5) + + val startsWithInputs = ( + List(Nil, List(1), List(1,2), seq), + List(List(1,2,3,4,6), seq ::: List(5), List(0)) + ) + + val endsWithInputs = ( + List(Nil, List(5), List(4,5), seq), + List(0 :: seq, List(5,2,3,4,5), List(3,4), List(5,6)) + ) + + val indexOfSeqInputs = ( + List(Nil, List(1), List(3), List(5), List(1,2), List(2,3,4), List(4,5), seq), + List(List(1,2,3,5), List(6), List(5,4,3,2,1), List(2,1)) + ) + + val sameElementsInputs = ( + List(List(1,2,3,4,5)), + List(Nil, List(1), List(1,2), List(2,3,4), List(2,3,4,5), List(2,3,4,5,1), List(1,2,3,5,4), seq reverse) + ) + } + + val failures = new mutable.ListBuffer[String] + var testCount = 0 + + def assertOne(op1: Any, op2: Any, res: Boolean, str: String) { + testCount += 1 + val resStr = str.format(op1, op2) + // println(resStr) + if (!res) + failures += ("FAIL: " + resStr) + // assert(res, resStr) + } + + def runSeqs() = { + for (s1f <- seqMakers ; s2f <- seqMakers ; testData <- List(test1)) { + import testData._ + val scrut = s1f(seq) + + // for (s <- starters ; val rhs = s2f(s)) + // assertOne(scrut, rhs, scrut startsWith rhs, "%s startsWith %s") + // + // for (ns <- nonStarters ; val rhs = s2f(ns)) + // assertOne(scrut, rhs, !(scrut startsWith rhs), "!(%s startsWith %s)") + + for (Method(f, (trueList, falseList), descr) <- methodList) { + for (s <- trueList; val rhs = s2f(s)) + assertOne(scrut, rhs, f(scrut, rhs), descr) + + for (s <- falseList; val rhs = s2f(s)) + assertOne(scrut, rhs, !f(scrut, rhs), "!(" + descr + ")") + } + } + } + + def main(args: Array[String]): Unit = { + runSeqs() + + if (failures.isEmpty) println("All %d tests passed.".format(testCount)) + else failures foreach println + } +} \ No newline at end of file -- cgit v1.2.3