<commit_before>/*                     __                                               *\
**     ________ ___   / /  ___     Scala API                            **
**    / __/ __// _ | / /  / _ |    (c) 2003-2013, LAMP/EPFL             **
**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
** /____/\___/_/ |_/____/_/ | |                                         **
**                          |/                                          **
\*                                                                      */

package scala
package collection

import scala.language.implicitConversions
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)
  *    // == Found(2)
  * }}}
  */
object Searching {
  sealed abstract class SearchResult {
    def insertionPoint: Int
  }

  case class Found(foundIndex: Int) extends SearchResult {
    override def insertionPoint = foundIndex
  }
  case class InsertionPoint(insertionPoint: Int) extends SearchResult

  class SearchImpl[A, Repr](val coll: SeqLike[A, Repr]) {
    /** Search the sorted sequence for a specific element. If the 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.IndexedSeqLike]]
      * @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 `Found` value containing the index corresponding to the element in the
      *         sequence, or the `InsertionPoint` where the element would be inserted if
      *         the element is not in the sequence.
      */
    final def search[B >: A](elem: B)(implicit ord: Ordering[B]): SearchResult =
      coll match {
        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 `IndexedSeqLike`, a binary search is used. Otherwise, a linear search
      * is used.
      *<commit_msg>Make SearchImpl a value class to improve performance<commit_after>/*                     __                                               *\
**     ________ ___   / /  ___     Scala API                            **
**    / __/ __// _ | / /  / _ |    (c) 2003-2013, LAMP/EPFL             **
**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
** /____/\___/_/ |_/____/_/ | |                                         **
**                          |/                                          **
\*                                                                      */

package scala
package collection

import scala.language.implicitConversions
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)
  *    // == Found(2)
  * }}}
  */
object Searching {
  sealed abstract class SearchResult {
    def insertionPoint: Int
  }

  case class Found(foundIndex: Int) extends SearchResult {
    override def insertionPoint = foundIndex
  }
  case class InsertionPoint(insertionPoint: Int) extends SearchResult

  class SearchImpl[A, Repr](val coll: SeqLike[A, Repr]) extends AnyVal {
    /** Search the sorted sequence for a specific element. If the 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.IndexedSeqLike]]
      * @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 `Found` value containing the index corresponding to the element in the
      *         sequence, or the `InsertionPoint` where the element would be inserted if
      *         the element is not in the sequence.
      */
    final def search[B >: A](elem: B)(implicit ord: Ordering[B]): SearchResult =
      coll match {
        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 `IndexedSeqLike`, a binary search is used. Otherwise, a linear search
      * is used.
      *
{'fraction_non_alphanumeric': 0.10218978102189781, 'fraction_numerical': 0.006530925854782943, 'mean_word_length': 1.7844919786096256, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5516887', 'n_tokens_mistral': 1440, 'n_tokens_neox': 1387, 'n_words': 447}