package pl.edu.pw.mini.game.flipit.deterministic.noinfo

final class SortedList[T, O <: Ordering[T]] private(
  val innerList: List[T],
) {
  def merge(other: SortedList[T, O])(implicit ord: O) : SortedList[T, O] = {
    def m(l1: List[T], l2: List[T]) : List[T] = {
      (l1, l2) match {
        case (Nil, ll2) => ll2
        case (ll1, Nil) => ll1
        case (x::xx, y::yy) if ord.equiv(x, y) => x::m(xx, yy)
        case (x::xx, y::yy) if ord.lt(x, y) => x::m(xx, l2)
        case (x::xx, y::yy) => y::m(l1, yy)
      }
    }
    new SortedList[T, O](m(innerList, other.innerList))
  }

  override def equals(other: Any): Boolean = other match {
    case sl: SortedList[T, O] => sl.innerList == innerList
    case _ => false
  }

  override val hashCode: Int = innerList.##
}

object SortedList {
  def apply[T,O <: Ordering[T]](list: List[T])(implicit ord: O) =
    new SortedList[T, O](list.sorted)
}
