Range class for ranges [a, b], (a, b), (a, b], [a, b) where (a and b) may be unbounded

range.scala

package test

import scalaz._
import Scalaz._
import test.IRange.Increment

sealed trait Limit[+Z] {
  def open : Boolean
  def bound : Option[Z]
  final def closed = !open
}

sealed trait UpperBound[+Z] extends Limit[Z] {
  def ≥[ZZ >: Z : Order](p : => ZZ) : Boolean
  def ≤[ZZ >: Z : Order](p : => ZZ) : Boolean

  final def meets[ZZ >: Z : Order](lb : LowerBound[ZZ]) = (bound |@| lb.bound) { _ == _ } getOrElse false
  final def ≤[ZZ >: Z : Order](lower : LowerBound[ZZ]) : Boolean = lower.bound.forall(lb => this ≤ lb)
  final def ≥[ZZ >: Z : Order](lower : LowerBound[ZZ]) : Boolean = lower ≤ this
  final def ≥[ZZ >: Z : Order](that : UpperBound[ZZ]) : Boolean = that.bound.forall(tb => this ≥ tb || (this.bound.forall(tb==) && (this.closed || that.open)))
  final def intersects[ZZ >: Z : Order](lb : LowerBound[ZZ]) = meets(lb) && closed && lb.closed
}
sealed trait LowerBound[+Z] extends Limit[Z] {
  def ≥[ZZ >: Z : Order](p : => ZZ) : Boolean
  def ≤[ZZ >: Z : Order](p : => ZZ) : Boolean

  final def meets[ZZ >: Z : Order](ub : UpperBound[ZZ]) = (bound |@| ub.bound) { _ == _ } getOrElse false
  final def ≥[ZZ >: Z : Order](upper : UpperBound[ZZ]) : Boolean = upper.bound.forall(ub => this ≥ ub)
  final def ≤[ZZ >: Z : Order](upper : UpperBound[ZZ]) : Boolean = upper.bound.forall(ub => (this ≤ ub) && (!this.bound.forall(ub==) || (this.open || upper.closed)))
  final def ≤[ZZ >: Z : Order](that : LowerBound[ZZ]) : Boolean = that.bound.forall(tb => this ≤ tb || (this.bound.forall(tb==) && (this.closed || that.open)))
  final def intersects[ZZ >: Z : Order](ub : UpperBound[ZZ]) = meets(ub) && closed && ub.closed
}

private case object NoLowerBound extends LowerBound[⊥] {
  def open = true
  def bound = None
  
  def ≥[ZZ >: ⊥ : Order](p : => ZZ) : Boolean = false
  def ≤[ZZ >: ⊥ : Order](p : => ZZ) : Boolean = true
  override def toString = "(-"
}

private case object NoUpperBound extends UpperBound[⊥] {
  def open = true
  def bound = None
  
  def ≥[ZZ >: ⊥ : Order](p : => ZZ) : Boolean = true
  def ≤[ZZ >: ⊥ : Order](p : => ZZ) : Boolean = false
  override def toString = "-)"
}

private case class UpperLimit[Z : Order](point : Z, open : Boolean) extends UpperBound[Z] {
  def bound = some(point)

  def ≥[ZZ >: Z : Order](p : => ZZ) : Boolean = p ≨ point || (point == p && closed)
  def ≤[ZZ >: Z : Order](p : => ZZ) : Boolean = p ≩ point || (point == p && closed)
  override def toString = point.toString + (if (open) ")" else "]")
}

object IRange {
  trait Increment[I] {
    def increment(i : I) : I
  }
  object Increment {
    implicit val IntIncrement = new Increment[Int] {
      def increment(i : Int) = i + 1
    }
    implicit val LongIncrement = new Increment[Long] {
      def increment(l : Long) = l + 1L
    }
  }

  class RangeFactory[Z](lower : Z)(implicit order : Order[Z], inc : Increment[Z] = null) {
    def +:~:+(upper : Z) : IRange[Z] = ZRange(LowerLimit(lower, false), UpperLimit(upper, false))
    def -:~:+(upper : Z) : IRange[Z]= ZRange(LowerLimit(lower, true), UpperLimit(upper, false))
    def +:~:-(upper : Z) : IRange[Z]= ZRange(LowerLimit(lower, false), UpperLimit(upper, true))
    def -:~:-(upper : Z) : IRange[Z]= ZRange(LowerLimit(lower, true), UpperLimit(upper, true))

    def +:/ : IRange[Z]= ZRange(LowerLimit(lower, false), NoUpperBound)
    def +:\ : IRange[Z]= ZRange(NoLowerBound, UpperLimit(lower, false))
    def -:/ : IRange[Z]= ZRange(LowerLimit(lower, true), NoUpperBound)
    def -:\ : IRange[Z]= ZRange(NoLowerBound, UpperLimit(lower, true))
  }

  implicit def order2rangefactory[Z](lower : Z)(implicit order : Order[Z], inc : Increment[Z] = null) = new RangeFactory(lower)
  def point[Z](p : Z)(implicit order : Order[Z], inc : Increment[Z] = null) = p +:~:+ p
  def complete[Z](implicit order : Order[Z], inc : Increment[Z] = null) : IRange[Z] = ZRange(NoLowerBound, NoUpperBound)

  def empty[Z](implicit order : Order[Z], inc : Increment[Z] = null) : IRange[Z] = EmptyRange

  implicit def IRangeZero[A : Order] = new Zero[IRange[A]] {
    val zero = empty[A]
  }

  implicit def IRangeEqual[A : Equal] : Equal[IRange[A]] = equalA
}

sealed trait IRange[+Z] {
  def apply[ZZ >: Z : Order](z : ZZ) : Boolean
  def upperBound : Option[Z]
  def lowerBound : Option[Z]
  def closedAtUpper : Boolean
  def closedAtLower : Boolean
  def isEmpty : Boolean
  def contains[ZZ >: Z : Order](that : IRange[ZZ]) : Boolean
  def meetsAtPoint[ZZ >: Z : Order](that : IRange[ZZ]): Boolean
  def intersectsAtPoint[ZZ >: Z : Order](that : IRange[ZZ]) : Boolean
  def intersects[ZZ >: Z : Order](that : IRange[ZZ]) : Boolean
  def toStream[ZZ >: Z](implicit li : Increment[ZZ], order : Order[ZZ]) : Stream[ZZ]

  final def closed = closedAtUpper && closedAtLower
  final def boundedBelow  = lowerBound.isDefined
  final def boundedAbove  = upperBound.isDefined
  final def bounded = boundedBelow && boundedAbove
  final def isComplete = !boundedBelow && !boundedAbove
  final def nonEmpty = !isEmpty
  final def containedBy[ZZ >: Z : Order](that : IRange[ZZ]) = that contains this
  final def singlePoint = ~((lowerBound |@| upperBound) { _ == _ })
}

case object EmptyRange extends IRange[⊥] {
  def apply[ZZ >: ⊥ : Order](z : ZZ) : Boolean = false
  def isEmpty = true
  def closedAtLower = false
  def closedAtUpper = false
  def lowerBound = None
  def upperBound = None
  def apply(nothing : ⊥) = false
  def contains[Z >: ⊥ : Order](that : IRange[Z]) = false

  def toStream[Z >: ⊥](implicit li: Increment[Z], order : Order[Z]) = Stream.empty
  def intersects[Z >: ⊥ : Order](that: IRange[Z]) = false
  def intersectsAtPoint[Z >: ⊥ : Order](that: IRange[Z]) = false
  def meetsAtPoint[Z >: ⊥ : Order](that: IRange[Z]) = false

}

private case class LowerLimit[Z : Order](point : Z, open : Boolean) extends LowerBound[Z] {
  def bound = some(point)

  def ≤[ZZ >: Z : Order](p : => ZZ) = p ≩ point || (point == p && closed)
  def ≥[ZZ >: Z : Order](p : => ZZ) = p ≨ point || (point == p && closed)
  override def toString = (if (open) "(" else "[") + point.toString
}

case object ZRange {
  implicit def ZRangeShow[A] = new Show[ZRange[A]] {
    def show(a: ZRange[A]) = { (a.lowerLimit.toString + ", " + a.upperLimit.toString).toList}
  }

}

case class ZRange[Z] private[test](private val lowerLimit : LowerBound[Z], private val upperLimit : UpperBound[Z])(implicit order : Order[Z], inc : Increment[Z] = null)
  extends IRange[Z] {
  require(lowerLimit ≤ upperLimit, lowerLimit + ", " + upperLimit + " is not a valid range: (lb is not <= ub)")
  private def notEmptyIfIncrement = Option(inc).forall(inc => !(lowerLimit.open && upperLimit.open && ~((lowerBound |@| upperBound) { inc.increment(_) ≥ _  }) ))
  require(notEmptyIfIncrement, "Invalid Range (can contain no elements) on discrete element type: " + lowerLimit + ", " + upperLimit)

  def isEmpty = false
  def upperBound = upperLimit.bound
  def lowerBound = lowerLimit.bound
  def closedAtUpper = upperLimit.closed
  def closedAtLower = lowerLimit.closed

  override def apply[ZZ >: Z : Order](p: ZZ) = (lowerLimit ≤ p) && (upperLimit ≥ p)

  def contains[ZZ >: Z : Order](other : IRange[ZZ]) : Boolean = other match {
    case that : ZRange[ZZ] => (upperLimit ≥ that.upperLimit) && (lowerLimit ≤ that.lowerLimit)
    case _                 => true //empty
  }

  def entirelyBefore(that : ZRange[Z]) = !(that.lowerLimit ≥ upperLimit)
  def entirelyAfter(that : ZRange[Z]) = !(that.upperLimit ≤ lowerLimit)


  def meetsAtPoint[ZZ >: Z : Order](other : IRange[ZZ]) = other match {
    case that : ZRange[ZZ] => (lowerLimit meets that.upperLimit) || (upperLimit meets that.lowerLimit)
    case _                 => false //empty
  }
  def intersectsAtPoint[ZZ >: Z : Order](other : IRange[ZZ]) = other match {
    case that: ZRange[ZZ] => (lowerLimit intersects that.upperLimit) || (upperLimit intersects that.lowerLimit)
    case _                => false //empty
  }

  def intersects[ZZ >: Z : Order](other : IRange[ZZ]) = other match {
    case that : ZRange[ZZ] => this.upperLimit ≥ that.lowerLimit && this.lowerLimit ≤ that.upperLimit
    case _                 => false //empty
  }

  def toStream[ZZ >: Z](implicit li : Increment[ZZ], order : Order[ZZ]) : Stream[ZZ] = {
    def fromFirst(lb : Z) : Stream[ZZ] = {
      def first = {
        if (closedAtLower)
          lb
        else {
          val next = li.increment(lb)
          require(apply(next), "Invalid range: " + this)
          next
        }
      }
      first.iterate[Stream](z => li increment z)
    }
    (lowerBound -> upperBound) match {
      case (None, _)     => error("Cannot Stream range unbounded below: " + this)
      case (Some(lb), _) => fromFirst(lb) takeWhile (this apply _)
    }
  }
}

import org.scalatest._
import matchers._
class ZRangeSpec extends Spec with ShouldMatchers {
  import IRange._
  describe("ZRange") {

    it("should not allow discrete open unit ranges") {
      intercept[IllegalArgumentException](1 -:~:- 2)
    }
    

    it("should honour intersects at point") {
      point(1) intersectsAtPoint point(1) should be(true)
      point(1) intersectsAtPoint point(2) should be(false)
      point(2) intersectsAtPoint point(1) should be(false)
      point(1) intersectsAtPoint (1 +:~:+ 2) should be(true)
      (1 +:~:+ 2) intersectsAtPoint point(1) should be(true)

      point(1) intersectsAtPoint (1 +:/) should be(true)
      (1 +:/) intersectsAtPoint point(1) should be(true)
      point(1) intersectsAtPoint (1 +:\) should be(true)
      (1 +:\) intersectsAtPoint point(1) should be(true)

      point(1) intersectsAtPoint (1 -:/) should be(false)
      (1 -:/) intersectsAtPoint point(1) should be(false)
      point(1) intersectsAtPoint (1 -:\) should be(false)
      (1 -:\) intersectsAtPoint point(1) should be(false)

      (2 +:~:- 3) intersectsAtPoint (1 -:~:+ 2) should be(true)
      (1 -:~:+ 2) intersectsAtPoint (2 +:~:- 3) should be(true)

      (1 +:~:- 5) intersectsAtPoint (2 -:~:- 4) should be(false)
      (2 -:~:- 4) intersectsAtPoint (1 +:~:- 5) should be(false)
    }

    it("should honour meets at point") {
      point(1) meetsAtPoint point(1) should be(true)
      point(1) meetsAtPoint point(2) should be(false)
      point(2) meetsAtPoint point(1) should be(false)
      point(1) meetsAtPoint (1 +:~:+ 2) should be(true)
      (1 +:~:+ 2) meetsAtPoint point(1) should be(true)

      point(1) meetsAtPoint (1 +:/) should be(true)
      (1 +:/) meetsAtPoint point(1) should be(true)
      point(1) meetsAtPoint (1 +:\) should be(true)
      (1 +:\) meetsAtPoint point(1) should be(true)

      point(1) meetsAtPoint (1 -:/) should be(true)
      (1 -:/) meetsAtPoint point(1) should be(true)
      point(1) meetsAtPoint (1 -:\) should be(true)
      (1 -:\) meetsAtPoint point(1) should be(true)

      (2 +:~:- 3) meetsAtPoint (1 -:~:+ 2) should be(true)
      (1 -:~:+ 2) meetsAtPoint (2 +:~:- 3) should be(true)

      (1 +:~:- 5) meetsAtPoint (2 -:~:- 4) should be(false)
      (2 -:~:- 4) meetsAtPoint (1 +:~:- 5) should be(false)
    }

    it("should not allow zero-length open ranges") {
      intercept[IllegalArgumentException](1 -:~:- 1)
      intercept[IllegalArgumentException](1 +:~:- 1)
      intercept[IllegalArgumentException](1 -:~:+ 1)
    }

    it("should contain other ranges where appropriate") {
      (-2 +:~:+ 2) contains (-1 +:~:+ 1) should be(true)
      (-2 -:~:+ 2) contains (-1 +:~:+ 1) should be(true)
      (-2 +:~:- 2) contains (-1 +:~:+ 1) should be(true)
      (-2 -:~:- 2) contains (-1 +:~:+ 1) should be(true)

      (-2 +:~:+ 2) contains (-1 +:~:- 1) should be(true)
      (-2 -:~:+ 2) contains (-1 +:~:- 1) should be(true)
      (-2 +:~:- 2) contains (-1 +:~:- 1) should be(true)
      (-2 -:~:- 2) contains (-1 +:~:- 1) should be(true)

      (-2 +:~:+ 2) contains (-1 -:~:+ 1) should be(true)
      (-2 -:~:+ 2) contains (-1 -:~:+ 1) should be(true)
      (-2 +:~:- 2) contains (-1 -:~:+ 1) should be(true)
      (-2 -:~:- 2) contains (-1 -:~:+ 1) should be(true)

      (-2 +:~:+ 2) contains (-1 -:~:- 1) should be(true)
      (-2 -:~:+ 2) contains (-1 -:~:- 1) should be(true)
      (-2 +:~:- 2) contains (-1 -:~:- 1) should be(true)
      (-2 -:~:- 2) contains (-1 -:~:- 1) should be(true)

      (-1 +:~:+ 2) contains (-1 +:~:+ 1) should be(true)
      (-1 -:~:+ 2) contains (-1 +:~:- 1) should be(false)
      (-1 +:~:- 2) contains (-1 -:~:- 1) should be(true)
      (-2 -:~:- 2) contains (-1 +:~:+ 1) should be(true)

      (-1 +:~:+ 1) contains (-1 +:~:+ 1) should be(true)
      (-1 -:~:+ 1) contains (-1 +:~:+ 1) should be(false)
      (-1 +:~:- 1) contains (-1 +:~:+ 1) should be(false)
      (-1 -:~:- 1) contains (-1 +:~:+ 1) should be(false)

      (-1 +:~:+ 1) contains (-1 +:~:- 1) should be(true)
      (-1 -:~:+ 1) contains (-1 +:~:- 1) should be(false)
      (-1 +:~:- 1) contains (-1 +:~:- 1) should be(true)
      (-1 -:~:- 1) contains (-1 +:~:- 1) should be(false)

      (-1 +:~:+ 1) contains (-1 -:~:+ 1) should be(true)
      (-1 -:~:+ 1) contains (-1 -:~:+ 1) should be(true)
      (-1 +:~:- 1) contains (-1 -:~:+ 1) should be(false)
      (-1 -:~:- 1) contains (-1 -:~:+ 1) should be(false)

      (-1 +:~:+ 1) contains (-1 -:~:- 1) should be(true)
      (-1 -:~:+ 1) contains (-1 -:~:- 1) should be(true)
      (-1 +:~:- 1) contains (-1 -:~:- 1) should be(true)
      (-1 -:~:- 1) contains (-1 -:~:- 1) should be(true)
    }

    it("should intersect other bounded ranges") {
      (-2 +:~:+ 1) intersects (-1 +:~:+ 2) should be(true)
      (-1 +:~:+ 2) intersects (-2 +:~:+ 1) should be(true)
      (-2 -:~:+ 1) intersects (-1 +:~:+ 2) should be(true)
      (-1 +:~:+ 2) intersects (-2 -:~:+ 1) should be(true)
      (-2 +:~:- 1) intersects (-1 +:~:+ 2) should be(true)
      (-1 +:~:+ 2) intersects (-2 +:~:- 1) should be(true)
      (-2 -:~:- 1) intersects (-1 +:~:+ 2) should be(true)
      (-1 +:~:+ 2) intersects (-2 -:~:- 1) should be(true)
    }

    it("should not intersect with disjoint ranges") {
      (-2 +:~:+ -1) intersects (1 +:~:+ 2) should be(false)
      (-2 +:~:- -1) intersects (1 +:~:+ 2) should be(false)
      (-2 -:~:+ -1) intersects (1 +:~:+ 2) should be(false)
      (-3 -:~:- -1) intersects (1 +:~:+ 2) should be(false)

      (-1 +:~:+ 0) intersects (0 +:~:+ 1) should be(true)
      (-1 +:~:- 0) intersects (0 +:~:+ 1) should be(false)
      (-1 -:~:+ 0) intersects (0 -:~:+ 1) should be(false)
      (-2 -:~:- 0) intersects (0 -:~:+ 1) should be(false)

      (0 -:~:- 2) intersects (2 -:~:+ 4) should be(false)
    }

    it("should contain points") {
      (-1 +:~:+ 1) apply -1 should be(true)
      (-1 +:~:+ 1) apply 0 should be(true)
      (-1 +:~:+ 1) apply 1 should be(true)

      (-1 +:~:- 1) apply -1 should be(true)
      (-1 +:~:- 1) apply 0 should be(true)
      (-1 +:~:- 1) apply 1 should be(false)

      (-1 -:~:+ 1) apply -1 should be(false)
      (-1 -:~:+ 1) apply 0 should be(true)
      (-1 -:~:+ 1) apply 1 should be(true)

      (-1 -:~:- 1) apply -1 should be(false)
      (-1 -:~:- 1) apply 0 should be(true)
      (-1 -:~:- 1) apply 1 should be(false)
    }

    it("should have a complete range") {
      complete[Int].isComplete should be(true)
      complete[Int] contains complete[Int] should be(true)
      complete[Int] contains (-1 +:~:+ 1) should be(true)
      complete[Int] contains (-1 +:~:- 1) should be(true)
      complete[Int] contains (-1 -:~:+ 1) should be(true)
      complete[Int] contains (-1 -:~:- 1) should be(true)
      complete[Int] apply 0 should be(true)
    }

    it("should convert toStream") {
      import IRange.Increment._
      intercept[RuntimeException](complete[Int].toStream)
      intercept[RuntimeException]((0 +:\).toStream)
      intercept[RuntimeException]((0 -:\).toStream)
      (0 +:/).toStream.head should be(0)
      (0 -:/).toStream.head should be(1)

      (0 +:~:+ 5 ).toStream.toList should equal(List(0, 1, 2, 3, 4, 5))
      (0 -:~:+ 5 ).toStream.toList should equal(List(1, 2, 3, 4, 5))
      (0 +:~:- 5 ).toStream.toList should equal(List(0, 1, 2, 3, 4))
      (0 -:~:- 5 ).toStream.toList should equal(List(1, 2, 3, 4))

      IRange.empty[Int].toStream should equal(Stream.empty)
    }

    it("should have a sensible empty range") {
      empty[Int] apply 0 should be(false)

      empty[Int] contains (-1 -:~:- 1) should be(false)
      empty[Int] contains (-1 +:~:- 1) should be(false)
      empty[Int] contains (-1 -:~:+ 1) should be(false)
      empty[Int] contains (-1 +:~:+ 1) should be(false)

      (-1 -:~:- 1) contains empty[Int] should be(true)
      (-1 -:~:+ 1) contains empty[Int] should be(true)
      (-1 +:~:- 1) contains empty[Int] should be(true)
      (-1 +:~:+ 1) contains empty[Int] should be(true)


      empty[Int] intersects (-1 -:~:- 1) should be(false)
      empty[Int] intersects (-1 +:~:- 1) should be(false)
      empty[Int] intersects (-1 -:~:+ 1) should be(false)
      empty[Int] intersects (-1 +:~:+ 1) should be(false)
      (-1 -:~:- 1) intersects empty[Int] should be(false)
      (-1 -:~:+ 1) intersects empty[Int] should be(false)
      (-1 +:~:- 1) intersects empty[Int] should be(false)
      (-1 +:~:+ 1) intersects empty[Int] should be(false)

      empty[Int] meetsAtPoint (-1 -:~:- 1) should be(false)
      empty[Int] meetsAtPoint (-1 +:~:- 1) should be(false)
      empty[Int] meetsAtPoint (-1 -:~:+ 1) should be(false)
      empty[Int] meetsAtPoint  (-1 +:~:+ 1) should be(false)
      (-1 -:~:- 1) meetsAtPoint empty[Int] should be(false)
      (-1 -:~:+ 1) meetsAtPoint empty[Int] should be(false)
      (-1 +:~:- 1) meetsAtPoint empty[Int] should be(false)
      (-1 +:~:+ 1) meetsAtPoint empty[Int] should be(false)

      IRange.empty[Long].isEmpty should be(true)
      IRange.empty[Long].nonEmpty should be(false)

    }

    it("should be covariant in the element type") {
      def call(r : IRange[Any]) = r

      val ir: IRange[Int] = 1 +:~:- 2
      call(ir) should be(ir)

      val ar : IRange[AnyVal] = IRange.empty[Boolean]
      call(ar) should be(ar)
    }

  }
}