IsSortedExample.scala

package com.twitter.mrosenthal.timelines.adhoc.dataset_transform

import scala.collection.{GenTraversableOnce, SeqLike}
import scala.math.Ordering

object IsSortedExample extends App {

  implicit class RichGenTraversableOnce[A](val trav: GenTraversableOnce[A]) extends AnyVal {
    /**
     * O(1) space, O(n) time. Stops as soon as it finds an unsorted pair.
     */
    def isSorted[B >: A](implicit ord: Ordering[B]): Boolean =
      !trav.toIterator.sliding(2).exists {
        case Seq(l, r) => ord.gt(l, r)
        case _ => false
      }
  }

  implicit class RichSeqLike[A, Repr](val seq: SeqLike[A, Repr]) extends AnyVal {

    /**
     * Note: Static return type is Repl, which is usually the same type as seq  
     */
    def sortIfNeeded[B >: A](implicit ord: Ordering[B]): Repr =
      if(seq.isSorted(ord)) seq.repr else seq.sorted(ord)
  }
  
  println(Vector(1, 2, 5).sortIfNeeded)
  println(List(1, 3, 2).sortIfNeeded)
}