diff options
| -rw-r--r-- | src/library/scala/collection/Searching.scala | 100 | ||||
| -rw-r--r-- | src/library/scala/collection/generic/IsSeqLike.scala | 38 | ||||
| -rw-r--r-- | test/files/run/search.check | 6 | ||||
| -rw-r--r-- | test/files/run/search.scala | 14 |
4 files changed, 158 insertions, 0 deletions
diff --git a/src/library/scala/collection/Searching.scala b/src/library/scala/collection/Searching.scala new file mode 100644 index 0000000000..d62421b486 --- /dev/null +++ b/src/library/scala/collection/Searching.scala @@ -0,0 +1,100 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2012, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.collection + +import scala.annotation.tailrec +import scala.collection.generic.IsSeqLike +import scala.math.Ordering + +/** A collection of wrappers that provide sequence classes with search functionality. + * + * Example usage: + * {{{ + * import scala.collection.Searching._ + * val l = List(1, 2, 3, 4, 5) + * l.search(3) + * // == 2 + * }}} + */ +object Searching { + class SearchImpl[A, Repr](val coll: SeqLike[A, Repr]) { + /** Search the sorted sequence for a specific element. + * + * The sequence should be sorted with the same `Ordering` before calling; otherwise, + * the results are undefined. + * + * @see [[scala.math.Ordering]] + * @see [[scala.collection.SeqLike]], method `sorted` + * + * @param elem the element to find. + * @param ord the ordering to be used to compare elements. + * @return a `Right` value containing the index corresponding to the element in the + * $coll, or a `Left` value containing the index where the element would be + * inserted if the element is not in the $coll. + */ + final def search[B >: A](elem: B)(implicit ord: Ordering[B]): Either[Int, Int] = + coll match { + case _: IndexedSeqLike[A, Repr] => binarySearch(elem, -1, coll.length)(ord) + case _ => linearSearch(coll.view, elem, 0)(ord) + } + + /** Search within an interval in the sorted sequence for a specific element. + * + * The sequence should be sorted with the same `Ordering` before calling; otherwise, + * the results are undefined. + * + * @see [[scala.math.Ordering]] + * @see [[scala.collection.SeqLike]], method `sorted` + * + * @param elem the element to find. + * @param from the index where the search starts. + * @param to the index following where the search ends. + * @param ord the ordering to be used to compare elements. + * @return a `Right` value containing the index corresponding to the element in the + * $coll, or a `Left` value containing the index where the element would be + * inserted if the element is not in the $coll. + */ + final def search[B >: A](elem: B, from: Int, to: Int) + (implicit ord: Ordering[B]): Either[Int, Int] = + coll match { + case _: IndexedSeqLike[A, Repr] => binarySearch(elem, from-1, to)(ord) + case _ => linearSearch(coll.view(from, to), elem, from)(ord) + } + + @tailrec + private def binarySearch[B >: A](elem: B, from: Int, to: Int) + (implicit ord: Ordering[B]): Either[Int, Int] = { + if ((to-from) == 1) Left(from) else { + val idx = (to+from)/2 + math.signum(ord.compare(elem, coll(idx))) match { + case -1 => binarySearch(elem, from, idx)(ord) + case 1 => binarySearch(elem, idx, to)(ord) + case _ => Right(idx) + } + } + } + + private def linearSearch[B >: A](c: SeqView[A, Repr], elem: B, offset: Int) + (implicit ord: Ordering[B]): Either[Int, Int] = { + var idx = offset + val it = c.iterator + while (it.hasNext) { + val cur = it.next() + if (ord.equiv(elem, cur)) return Right(idx) + else if (ord.lt(elem, cur)) return Left(idx-1) + idx += 1 + } + Left(idx) + } + + } + + implicit def search[Repr, A](coll: Repr) + (implicit fr: IsSeqLike[Repr]): SearchImpl[fr.A, Repr] = new SearchImpl(fr.conversion(coll)) +} diff --git a/src/library/scala/collection/generic/IsSeqLike.scala b/src/library/scala/collection/generic/IsSeqLike.scala new file mode 100644 index 0000000000..47e2924d34 --- /dev/null +++ b/src/library/scala/collection/generic/IsSeqLike.scala @@ -0,0 +1,38 @@ +/* __ *\ +** ________ ___ / / ___ Scala API ** +** / __/ __// _ | / / / _ | (c) 2003-2012, LAMP/EPFL ** +** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** +** /____/\___/_/ |_/____/_/ | | ** +** |/ ** +\* */ + +package scala.collection +package generic + +/** Type class witnessing that a collection representation type `Repr` has + * elements of type `A` and has a conversion to `SeqLike[A, Repr]`. + * + * @see [[scala.collection.generic.IsTraversableLike]] + */ +trait IsSeqLike[Repr] { + /** The type of elements we can traverse over. */ + type A + /** A conversion from the representation type `Repr` to a `SeqLike[A,Repr]`. */ + val conversion: Repr => SeqLike[A, Repr] +} + +object IsSeqLike { + import language.higherKinds + + implicit val stringRepr: IsSeqLike[String] { type A = Char } = + new IsSeqLike[String] { + type A = Char + val conversion = implicitly[String => SeqLike[Char, String]] + } + + implicit def seqLikeRepr[C[_], A0](implicit conv: C[A0] => SeqLike[A0,C[A0]]): IsSeqLike[C[A0]] { type A = A0 } = + new IsSeqLike[C[A0]] { + type A = A0 + val conversion = conv + } +} diff --git a/test/files/run/search.check b/test/files/run/search.check new file mode 100644 index 0000000000..3dc3c9d369 --- /dev/null +++ b/test/files/run/search.check @@ -0,0 +1,6 @@ +Right(2) +Right(4) +Left(9) +Right(2) +Right(4) +Left(9) diff --git a/test/files/run/search.scala b/test/files/run/search.scala new file mode 100644 index 0000000000..1e57fa2bf1 --- /dev/null +++ b/test/files/run/search.scala @@ -0,0 +1,14 @@ +object Test extends App { + import scala.collection.{LinearSeq, IndexedSeq} + import scala.collection.Searching._ + + val ls = LinearSeq(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13) + println(ls.search(3)) + println(ls.search(5, 3, 8)) + println(ls.search(12)) + + val is = IndexedSeq(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13) + println(is.search(3)) + println(is.search(5, 3, 8)) + println(is.search(12)) +} |