diff options
| -rw-r--r-- | src/library/scala/Seq.scala | 72 | ||||
| -rw-r--r-- | test/files/run/t1323.check | 18 | ||||
| -rw-r--r-- | test/files/run/t1323.scala | 25 |
3 files changed, 95 insertions, 20 deletions
diff --git a/src/library/scala/Seq.scala b/src/library/scala/Seq.scala index dcfc2ad451..211b737c04 100644 --- a/src/library/scala/Seq.scala +++ b/src/library/scala/Seq.scala @@ -434,11 +434,21 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Collection[A] { true } - /** @return true if this sequence start with that sequences - * @see String.startsWith + /** + * Checks whether the argument sequence is contained at the + * specified index within the receiver object. + * + * If the both the receiver object, <code>this</code> and + * the argument, <code>that</code> are infinite sequences + * this method may not terminate. + * + * @return true if <code>that</code> is contained in + * <code>this</code>, at the specified index, otherwise false + * + * @see String.startsWith */ - def startsWith[B](that: Seq[B]): Boolean = { - val i = elements + def startsWith[B](that: Seq[B], offset: Int): Boolean = { + val i = elements.drop(offset) val j = that.elements var result = true while (j.hasNext && i.hasNext && result) @@ -446,6 +456,17 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Collection[A] { result && !j.hasNext } + /** + * Check whether the receiver object starts with the argument sequence. + * + * @return true if <code>that</code> is a prefix of <code>this</code>, + * otherwise false + * + * @see Seq.startsWith + */ + def startsWith[B](that: Seq[B]): Boolean = startsWith(that, 0) + + /** @return true if this sequence end with that sequence * @see String.endsWith */ @@ -459,25 +480,36 @@ trait Seq[+A] extends AnyRef with PartialFunction[Int, A] with Collection[A] { result && !j.hasNext } - /** @return -1 if <code>that</code> not contained in this, otherwise the - * index where <code>that</code> is contained - * @see String.indexOf + /** + * Searches for the argument sequence in the receiver object, returning + * the smallest index where a match occurs. + * + * If the receiver object, <code>this</code>, is an infinite sequence + * this method will not terminate if there is no match. Similarly, if + * the both the receiver object and the argument, <code>that</code> are + * infinite sequences this method will not terminate. + * + * Because both the receiver object and the argument can both potentially + * be an infinite sequences, we do not attempt to use an optimized + * searching algorithm. Therefore, the running time will be proportional + * to the length of the receiver object and the argument. Subclasses and + * traits can potentially provide an optimized implementation. + * + * @return -1 if <code>that</code> not contained in <code>this</code>, + * otherwise the smallest index where <code>that</code> is found. + * + * @see String.indexOf */ def indexOf[B >: A](that: Seq[B]): Int = { - val i = this.elements - var idx = 0 - var j = that.elements - var jdx = -1 - while (i.hasNext && j.hasNext) { - idx = idx + 1 - if (i.next != j.next) { - j = that.elements - jdx = -1 - } else if (jdx == -1) { - jdx = idx - 1 - } + val e = this.elements + // Offset into e + var i = 0 + if (that.isEmpty) return 0 + while (e.hasNext) { + if (this.startsWith(that, i)) return i + e.next; i += 1 } - jdx + -1 } /** Is <code>that</code> a slice in this? diff --git a/test/files/run/t1323.check b/test/files/run/t1323.check new file mode 100644 index 0000000000..0d540f71b5 --- /dev/null +++ b/test/files/run/t1323.check @@ -0,0 +1,18 @@ + 1:-1 + 2:0 + 3:1 + 4:2 + 5:-1 + 6:-1 + 7:-1 + 8:-1 + 9:-1 +10:0 +11:-1 +12:-1 +13:-1 +14:0 +15:0 +16:-1 +17:-1 +18:3 diff --git a/test/files/run/t1323.scala b/test/files/run/t1323.scala new file mode 100644 index 0000000000..7a68482101 --- /dev/null +++ b/test/files/run/t1323.scala @@ -0,0 +1,25 @@ +object Test extends Application { + println(" 1:" + List(1,2,3,4).indexOf(List(0,1))) // -1 + println(" 2:" + List(1,2,3,4).indexOf(List(1,2))) // 0 + println(" 3:" + List(1,2,3,4).indexOf(List(2,3))) // 1 + println(" 4:" + List(1,2,3,4).indexOf(List(3,4))) // 2 + println(" 5:" + List(1,2,3,4).indexOf(List(4,5))) // -1 + println(" 6:" + List(1,2,3,4).indexOf(List(2,4))) // -1 + println(" 7:" + List(1,2,3,4).indexOf(List(4,3))) // -1 + println(" 8:" + List(1,2,3,4).indexOf(List(1,3))) // -1 + println(" 9:" + List(1,2,3,4).indexOf(List(1,3))) // -1 + println("10:" + List(1,2,3,4).indexOf(List(1,2,3,4))) // 0 + println("11:" + List(1,2,3,4).indexOf(List(4,3,2,1))) // -1 + println("12:" + List(1,2,3,4).indexOf(List(1,2,3,4,5))) // -1 + println("13:" + List(1,2,3,4).indexOf(List(5,4,3,2,1))) // -1 + println("14:" + List(1,2,3,4).indexOf(List())) // 0 + println("15:" + List().indexOf(List())) // 0 + println("16:" + List().indexOf(List(1,2,3,4))) // -1 + + // Do some testing with infinite sequences + def from(n: Int): Stream[Int] = Stream.cons(n, from(n + 1)) + + println("17:" + List(1,2,3,4).indexOf(from(1))) // -1 + println("18:" + from(1).indexOf(List(4,5,6))) // 3 +} + |