Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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)
- }
- }
- }
Add Comment
Please, Sign In to add comment