LARA

object RangeLattice extends Lattice {
  sealed abstract class Range
  case object Empty extends Range // {}
  case class Bounded(a : Int, b : Int) extends Range // [a,b]
  { assert (a <= b) }
  case class LeftUnbounded(b : Int) extends Range // (-inf,b]
  case class RightUnbounded(a : Int) extends Range // [a,+inf)
  case object Full extends Range // (-inf,+inf)
 
  type Elem = Range
  def leq(x : Range, y : Range) = (x,y) match {
    case (Empty,_) => true
    case (_,Full) => true
    case (Bounded(a1,b1),Bounded(a2,b2)) => (a2 <= a1 && b1 <= b2)
      //  a2...a1...b1...b2
    case (Bounded(a1,b1),LeftUnbounded(b2)) => (b1 <= b2)
    case (Bounded(a1,b1),RightUnbounded(a2)) => (a2 <= a1)
    case (LeftUnbounded(b1),LeftUnbounded(b2)) => (b1 <= b2)
    case (RightUnbounded(a1),RightUnbounded(a2)) => (a2 <= a1)
    case _ => false
  }
 
  val top = Full
  val bottom = Empty
 
  def join(x : Range, y : Range) = {
    import Math.{min,max}
      (x,y) match {
        case (Empty,_) => y
        case (_,Empty) => x
        case (Full,_) => Full
        case (_,Full) => Full
        case (Bounded(a1,b1),Bounded(a2,b2)) => 
          Bounded(min(a1,a2), max(b1,b2))
        case (LeftUnbounded(b1),LeftUnbounded(b2)) => 
          LeftUnbounded(max(b1,b2))
        case (RightUnbounded(a1),RightUnbounded(a2)) =>
          RightUnbounded(min(a1,a2))
        case (LeftUnbounded(_),RightUnbounded(_)) => Full
        case (RightUnbounded(_),LeftUnbounded(_)) => Full
        case (Bounded(a1,b1),LeftUnbounded(b2)) => 
          LeftUnbounded(max(b1,b2))
        case (LeftUnbounded(b2),Bounded(a1,b1)) => 
          LeftUnbounded(max(b1,b2))
        case (Bounded(a1,b1),RightUnbounded(a2)) => 
          RightUnbounded(min(a1,a2))
        case (RightUnbounded(a2),Bounded(a1,b1)) => 
          RightUnbounded(min(a1,a2))
      }
  }
  def meet(x : Range, y : Range) = {
    import Math.{min,max}
      (x,y) match {
        case (Empty,_) => Empty
        case (_,Empty) => Empty
        case (Full,_) => y
        case (_,Full) => x
	case (Bounded(a1,b1),Bounded(a2,b2)) => {
	  val a = max(a1,a2)
	  val b = min(b1,b2)
	  if (a <= b) Bounded(a,b) else Empty
	}
	case (LeftUnbounded(b1),LeftUnbounded(b2)) => 
	  LeftUnbounded(min(b1,b2))
        case _ => error("PLEASE COMPLETE")
      }
  }
}