/*

how can we generify IntSet?
need a way to specify that a type supplies a < method

Java: Interface like Comparable

Scala: trait  + type bounds
*/


/** A class for totally ordered data. */
trait Ordered[A] {
/** Result of comparing ‘this’ with operand ‘that’.
 * returns ‘x’ where
 * x < 0 iff this < that
 * x == 0 iff this == that
 * x > 0 iff this > that
*/
  def compare(that: A): Int
  def < (that: A): Boolean = (this compare that) < 0
  def > (that: A): Boolean = (this compare that) > 0
  def <= (that: A): Boolean = (this compare that) <= 0
  def >= (that: A): Boolean = (this compare that) >= 0
  def compareTo(that: A): Int = compare(that)
}


trait Set[A <: Ordered[A]] {
  def incl(x: A): Set[A]
  def contains(x: A): Boolean
}
  

class EmptySet[A <: Ordered[A]] extends Set[A] {
  def contains(x: A): Boolean = false
  def incl(x: A): Set[A] = new NonEmptySet(x, new EmptySet[A], new EmptySet[A])
}

class NonEmptySet[A <: Ordered[A]] (elem: A, left: Set[A], right: Set[A]) extends Set[A] {
  def contains(x: A): Boolean =
    if (x < elem) left contains x
    else if (x > elem) right contains x
    else true
  def incl(x: A): Set[A] =
    if (x < elem) new NonEmptySet(elem, left incl x, right)
    else if (x > elem) new NonEmptySet(elem, left, right incl x)
    else this
}


// use it like so:

case class Num(value: Double) extends Ordered[Num] {
  def compare(that: Num): Int =
    if (this.value < that.value) 1
    else if (this.value > that.value) 1
    else 0
}


val s = new EmptySet[Num].incl(Num(1.0)).incl(Num(2.0))
s.contains(Num(1.5))


// what if we "forget" to say "Num(value: Double) extends Ordered[Num]"
//
// Scala allows for the definition of implicit type conversions
// and so-called "view-bounds"

case class Num(value: Double)

trait Set[A <% Ordered[A]] ...

class EmptySet[A <% Ordered[A]] ...

class NonEmptySet[A <% Ordered[A]] ...


// "patch up" missing bits:

implicit def num2ordered(x: Num): Ordered[Num] = new Ordered[Num] {
 def compare(y: Num): Int =
   if (x.value < y.value) -1
   else if (x.value > y.value) 1
   else 0
}




/*

should  Stack[String]  be a subtype  of Stack[AnyRef],
as String is a subtype of AnyRef.
so-called "covariant" typing

Java -> yes
Scala -> default: no, but see below

fine for purely functional languages
problematic with updates

if Scala Arrays were covariant, you could do:

val x = new Array[String](2)
val y: Array[Any] = x
y(0) = new Rational(1, 2)
x(0) + x(1)  is ???


can specify covariance with a plus sign "+"

 class Stack[+A] {

but we cannot use A then as a type for formal parameters:

class Stack[+A] {
  def push(x: A): Stack[A] =
              ^ covariant type parameter A
              appears in contravariant position

use >: to define a lower bound:

class Stack[+A] {
  def push[B >: A](x: B): Stack[B] = new NonEmptyStack(x, this)

this is safe: why?

Is there a universal lower bound?   Nothing

object EmptyStack extends Stack[Nothing] { ... }


val s = EmptyStack.push("abc").push(new AnyRef())

what type is s?

fully generic Stack class:

*/

abstract class Stack[+A] {
  def push[B >: A](x: B): Stack[B] = new NonEmptyStack(x, this)
  def isEmpty: Boolean
  def top: A
  def pop: Stack[A]
}

object EmptyStack extends Stack[Nothing] {
  def isEmpty = true
  def top = error("EmptyStack.top")
  def pop = error("EmptyStack.pop")
}

class NonEmptyStack[+A](elem: A, rest: Stack[A]) extends Stack[A] {
  def isEmpty = false
  def top = elem
  def pop = rest
}


//======================================================================

// remember functions:  -A means "contra-variant" 
// Function1[Anyref,Int] is a subtype of  Function1[String,Int] 

trait Function1[-A, +B] {
  def apply(x: A): B
}

// so the following is type-safe

val f: (AnyRef => Int) = x => x.hashCode()

val g: (String => Int) = f

g("abc")