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 /src/library | |
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 'src/library')
-rw-r--r-- | src/library/scala/collection/Searching.scala | 12 |
1 files changed, 6 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) } |