[scala] Odering/Ordered (sorted, sortBy, sortWith), TreeMap

scala의 컬렉션에서는 정렬을 메소드로 지원한다. 

println(List(2000, 1000, 500, 3000).sorted)

결과는 다음과 같다.

List(500, 1000, 2000, 3000)

sorted 메소드 원형은 바로 Ordering 이라는 트레이트를 사용한다. 

def sorted[B >: A](implicit ord: Ordering[B]): Repr = {

Ordering 트레이트는 java.util.Comparator를 상속한다. 

trait Ordering[T] extends Comparator[T] 
                      with PartialOrdering[T] with Serializable {

Ordering에 대한 자세한 내용은 추후 살펴보고 우선 컬렉션 정렬을 살펴보자. 

sortWith 메소드에 함수 매개변수를 사용하면 더 풍부해진다. 

println(List(2000, 1000, 500, 3000).sortWith((x, y) => x > y))

println(List(2000, 1000, 500, 3000).sortWith(_ > _))

결과는 다음과 같다.

List(3000, 2000, 1000, 500)

함수 원형은 다음과 같다. sorted 메소드에 함수를 전달한다. 

def sortWith(lt: (A, A) => Boolean): Repr = sorted(Ordering fromLessThan lt)

sortWith에 _ > _ 대신 하나의 함수를 추가할 수 있다. 동일한 기능을 하는 함수를 만들어 전달한다. 

def sortByDesc(x: Int, y: Int) : Boolean = {
  if (Ordering.Int.compare(x, y) == 1) true else false
}

println(List(2000, 1000, 500, 3000).sortWith(sortByDesc))

결과는 이전 예시의 결과와 동일하다.

List(3000, 2000, 1000, 500)

이제는 클래스 정렬 부분에 대한 정렬이다. 

List(Price(1), Price(2)).sorted를 실행할 수 없다. Price에 대한 implict Ordering이 없기 때문이다. 

implict을 잘 모르면,  List(Price(1), Price(2)).sortWith(_.value < _.value) 이렇게 개발해야 한다. 

Price에 대한 implicit Ordering을 추가할 수 있는 여러 방법이 있는 듯 하다. 

Price 오브젝트에 Ordering 타입의 implicit val을 따로 선언하는 방식을 사용해봤다. 

예시는 다음과 같다. 

case class Price(value: Int) extends AnyVal
object Price {
  implicit val ordering: Ordering[Price] = new Ordering[Price] {
    def compare(x: Price, y: Price): Int =
      Ordering.Int.compare(y.value, x.value)
  }
}

object Main extends App {
  val list = List(Price(2000), Price(1000), Price(500), Price(3000))
  println(list.sorted)
}

결과는 다음과 같다.

List(Price(500), Price(1000), Price(2000), Price(3000))

sortBy 메소드도 존재한다. 

def sortBy[B](f: A => B)(implicit ord: Ordering[B]): Repr = sorted(ord on f)

println(List(2000, 1000, 500, 3000).sortBy((x: Int) => x))

TreeSet과..

object TreeSet extends ImmutableSortedSetFactory[TreeSet] {
  implicit def implicitBuilder[A](implicit ordering: Ordering[A]): Builder[A, TreeSet[A]] = newBuilder[A](ordering)
  override def newBuilder[A](implicit ordering: Ordering[A]): Builder[A, TreeSet[A]] =
    new SetBuilder(empty[A](ordering))

TreeMap에서 implicit으로 Ordering을 쓰고 있다. 

object TreeMap extends ImmutableSortedMapFactory[TreeMap] {
  def empty[A, B](implicit ord: Ordering[A]) = new TreeMap[A, B]()(ord)
  /** $sortedMapCanBuildFromInfo */
  implicit def canBuildFrom[A, B](implicit ord: Ordering[A]): CanBuildFrom[Coll, (A, B), TreeMap[A, B]] = new SortedMapCanBuildFrom[A, B]
}

간단한 예시를 보면, 다음과 같다. 

println(TreeSet(6,3,2,1))
println(TreeSet(3->'c', 1->'a', 2->'b'))

println(TreeMap(3->'c', 1->'a', 2->'b'))

결과는 다음과 같다.

TreeSet(1, 2, 3, 6)

TreeSet((1,a), (2,b), (3,c))

Map(1 -> a, 2 -> b, 3 -> c)

TreeMap을 좀 더 살펴보면..

Ordering 클래스는 A 타입의 엘리먼트를 자연적인 정렬에 대한 규칙을 정의한 타입 클래스이다.

따라서, 순서대로 엘리먼트를 순회할 때 뛰어난 성능을 제공한다. 

class TreeMap[A, +B] private (tree: RB.Tree[A, B])
                             (implicit val ordering: Ordering[A])

Ordering은 Compartator 계열이고, 콜렉션에서 사용된다. 

Ordered는 Comparable 계열이고, 여러 클래스에서 묵시적으로 사용하고 있다.

클래스간에 비교를 하려면, 에러가 발생한다. 

Price(10) < Price(20)

이를 가능하게 하는 것이 Ordered이다. Price라는 케이스 클래스에 Ordered 트레이트를 상속받고 compare(x)를 구현한다. 바로 이때 Ordered 트레이트를 사용한다. 

case class Price(value: Int) extends Ordered[Price] {
  def compare(x: Price): Int =
    Ordering.Int.compare(value, x.value)
}

object Main extends App {
  println(Price(10) < Price(100))
}

결과는 true가 발생한다!!

코드가 정말 간결해질 것 같다. 

if (Price(x) < Price(y)) {

  // code

}

참고로 Ordered 트레이트의 원형은 다음과 같다. - 이런건 안된다. 

trait Ordered[A] extends Any with java.lang.Comparable[A] {

  /** Result of comparing `this` with operand `that`.
   *
   * Implement this method to determine how instances of A will be sorted.
   *
   * Returns `x` where:
   *
   *   - `x < 0` when `this < that`
   *
   *   - `x == 0` when `this == that`
   *
   *   - `x > 0` when  `this > that`
   *
   */
  def compare(that: A): Int

  /** Returns true if `this` is less than `that`
    */
  def <  (that: A): Boolean = (this compare that) <  0

  /** Returns true if `this` is greater than `that`.
    */
  def >  (that: A): Boolean = (this compare that) >  0

  /** Returns true if `this` is less than or equal to `that`.
    */
  def <= (that: A): Boolean = (this compare that) <= 0

  /** Returns true if `this` is greater than or equal to `that`.
    */
  def >= (that: A): Boolean = (this compare that) >= 0

  /** Result of comparing `this` with operand `that`.
    */
  def compareTo(that: A): Int = compare(that)
}