diff options
author | Rui Gonçalves <ruippeixotog@gmail.com> | 2016-01-12 21:59:13 +0000 |
---|---|---|
committer | Rui Gonçalves <ruippeixotog@gmail.com> | 2016-01-12 23:40:12 +0000 |
commit | 070234218cf57b516ba908f9738ae4e17edce5f8 (patch) | |
tree | 235381cff11b706236b96b6240cb366ad5171b5b /test | |
parent | 6792b57152e70fd818db84829c0fb3d8e3899c26 (diff) | |
download | scala-070234218cf57b516ba908f9738ae4e17edce5f8.tar.gz scala-070234218cf57b516ba908f9738ae4e17edce5f8.tar.bz2 scala-070234218cf57b516ba908f9738ae4e17edce5f8.zip |
SI-9605 Searching does not use binary search for Array
Binary search should be used for every `IndexedSeqLike` instance and not only for `IndexedSeq`. According the Scaladoc, it is `IndexedSeqLike` that guarantees "constant-time or near constant-time element access and length computation".
Diffstat (limited to 'test')
-rw-r--r-- | test/junit/scala/collection/SearchingTest.scala | 48 |
1 files changed, 48 insertions, 0 deletions
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) + } +} |