diff options
author | Seth Tisue <seth@tisue.net> | 2016-01-13 19:16:02 -0500 |
---|---|---|
committer | Seth Tisue <seth@tisue.net> | 2016-01-13 19:16:02 -0500 |
commit | 9a2e71258df2e0d7b105b062dfecfb4fb19e9af4 (patch) | |
tree | 317c1ed8d98405eda5fe5faae3bee8fd01adc526 | |
parent | 0875d92954c43d9e9fec341263fc2a71f31f067c (diff) | |
parent | 070234218cf57b516ba908f9738ae4e17edce5f8 (diff) | |
download | scala-9a2e71258df2e0d7b105b062dfecfb4fb19e9af4.tar.gz scala-9a2e71258df2e0d7b105b062dfecfb4fb19e9af4.tar.bz2 scala-9a2e71258df2e0d7b105b062dfecfb4fb19e9af4.zip |
Merge pull request #4902 from ruippeixotog/issue/9605
SI-9605 Searching does not use binary search for Array
-rw-r--r-- | src/library/scala/collection/Searching.scala | 12 | ||||
-rw-r--r-- | test/junit/scala/collection/SearchingTest.scala | 48 |
2 files changed, 54 insertions, 6 deletions
diff --git a/src/library/scala/collection/Searching.scala b/src/library/scala/collection/Searching.scala index b68124b3f8..25e8b5e253 100644 --- a/src/library/scala/collection/Searching.scala +++ b/src/library/scala/collection/Searching.scala @@ -36,12 +36,12 @@ object Searching { class SearchImpl[A, Repr](val coll: SeqLike[A, Repr]) { /** Search the sorted sequence for a specific element. If the sequence is an - * `IndexedSeq`, a binary search is used. Otherwise, a linear search is used. + * `IndexedSeqLike`, a binary search is used. Otherwise, a linear search is used. * * The sequence should be sorted with the same `Ordering` before calling; otherwise, * the results are undefined. * - * @see [[scala.collection.IndexedSeq]] + * @see [[scala.collection.IndexedSeqLike]] * @see [[scala.math.Ordering]] * @see [[scala.collection.SeqLike]], method `sorted` * @@ -54,18 +54,18 @@ object Searching { */ final def search[B >: A](elem: B)(implicit ord: Ordering[B]): SearchResult = coll match { - case _: IndexedSeq[A] => binarySearch(elem, 0, coll.length)(ord) + case _: IndexedSeqLike[A, Repr] => binarySearch(elem, 0, coll.length)(ord) case _ => linearSearch(coll.view, elem, 0)(ord) } /** Search within an interval in the sorted sequence for a specific element. If the - * sequence is an IndexedSeq, a binary search is used. Otherwise, a linear search + * sequence is an `IndexedSeqLike`, a binary search is used. Otherwise, a linear search * is used. * * The sequence should be sorted with the same `Ordering` before calling; otherwise, * the results are undefined. * - * @see [[scala.collection.IndexedSeq]] + * @see [[scala.collection.IndexedSeqLike]] * @see [[scala.math.Ordering]] * @see [[scala.collection.SeqLike]], method `sorted` * @@ -81,7 +81,7 @@ object Searching { final def search[B >: A](elem: B, from: Int, to: Int) (implicit ord: Ordering[B]): SearchResult = coll match { - case _: IndexedSeq[A] => binarySearch(elem, from, to)(ord) + case _: IndexedSeqLike[A, Repr] => binarySearch(elem, from, to)(ord) case _ => linearSearch(coll.view(from, to), elem, from)(ord) } diff --git a/test/junit/scala/collection/SearchingTest.scala b/test/junit/scala/collection/SearchingTest.scala new file mode 100644 index 0000000000..2f939d625e --- /dev/null +++ b/test/junit/scala/collection/SearchingTest.scala @@ -0,0 +1,48 @@ +package scala.collection + +import org.junit.runner.RunWith +import org.junit.runners.JUnit4 +import org.junit.Assert._ +import org.junit.Test +import scala.collection.Searching._ + +@RunWith(classOf[JUnit4]) +class SearchingTest { + + @Test + def doesLinearSearchOnLinearSeqs() { + + class TestSeq[A](list: List[A]) extends SeqLike[A, TestSeq[A]] { + var elementsAccessed = Set.empty[Int] + + protected[this] def newBuilder = ??? // not needed for this test + def seq = list + def iterator = list.iterator + def length = list.length + def apply(idx: Int) = { elementsAccessed += idx; list(idx) } + } + + val coll = new TestSeq((0 to 6).toList) + + assertEquals(Found(5), coll.search(5)) + assertEquals(Set.empty, coll.elementsAccessed) // linear search should not access elements via apply() + } + + @Test + def doesBinarySearchOnIndexedSeqs() { + + class TestIndexedSeq[A](vec: Vector[A]) extends IndexedSeqLike[A, TestIndexedSeq[A]] { + var elementsAccessed = Set.empty[Int] + + protected[this] def newBuilder = ??? // not needed for this test + def seq = vec + def length = vec.length + def apply(idx: Int) = { elementsAccessed += idx; vec(idx) } + } + + val coll = new TestIndexedSeq((0 to 6).toVector) + + assertEquals(Found(5), coll.search(5)) + assertEquals(Set(3, 5), coll.elementsAccessed) + } +} |