# Time Intervals in Scala

August 24, 2020

Having recently felt compelled to start using `tstzrange`

to represent time intervals in Postgres (instead of two separate `start`

and `end`

columns), I’ve also had to grapple with writing a custom Scala class for Jooq to know what kind of code to generate to represent the column.

This article is split into two parts. The first part talks about writing such a class to represent Postgres’s `tstzrange`

column. The second part talks about how to use that custom class with Jooq.

# Why range types?

Range types offers better expressivity in the form of specialized operators. `&&`

checks for the intersection between two ranges, `>>`

checks if one range is strictly on the right of the other, `-|-`

checks if two ranges are adjacent. The full list of operators can be found here.

Range types have built-in validation to make sure that the start cannot be greater than the end.

Range types can express the concept of inclusive and exclusive bounds. `[3,4]::int4range`

includes both 3 and 4, `[3,4)::int4range`

includes only 3.

Range types can be indexed multidimensionally using GiST indexes, and can also optionally combined with B-Tree indexes for queries involving both range type columns and scalar columns.

`ALTER TABLE reservation ADD EXCLUDE USING GIST (room_id WITH =, booked_time WITH &&);`

This example constraint maintains the invariant that no room can be double-booked.

# Discrete vs continuous ranges

Ranges can be dichotomized into discrete ranges and continuous ranges. Discrete ranges are ranges like `int8range`

, whose element type have well-defined steps (in this case, the set of all 8-bit integers). Continuous ranges are ranges like `tstzrange`

and `floatrange`

, where the element type does not have well-defined steps.

Discrete ranges can be canonicalized into a `[x,y)`

form, since for any `x`

, we can identify its predecessor and successor values. Furthermore, in discrete ranges, there exists the edge case of `(x,x + delta)`

being equivalent to an empty interval, e.g. `(3,4)::int4range`

. In continuous ranges, the only valid empty interval representations are `(x,x)`

, `[x,x)`

, and `(x,x]`

.

# Representing `tstzrange`

in Scala

With some of the context above, we can now dive into the implementation proper.

One of the most important methods to have on a potential `tstzrange`

class is `overlaps`

, and as you will see, implementing `overlaps`

as a primitive will enable us to trivially implement `contains`

(and a host of other methods).

We need to handle five cases here.

Given two ranges A and B:

- Either A or B is an empty interval
- Either A or B is an infinite interval (
`(,)`

) - Either A or B is an unbounded interval (
`(x,)`

or`(,x)`

) - Both A and B are unbounded intervals
- Both A and B are bounded intervals

This looks complicated because we need to handle unbounded intervals and inclusive/exclusive ranges (and since `tstzrange`

is not a discrete range, we cannot canonicalize it beforehand).

I’ve chosen to enforce the “start cannot greater than end” validation using a simple Scala `requires`

, which will throw a runtime `IllegalArgumentException`

. You may choose to override the `apply`

function with one that returns an `Option[TsTzRange]`

instead, if so desired.

```
import java.time.Instant
import scala.math.Ordering.Implicits._
case class TsTzRange(
start: Option[Instant],
end: Option[Instant],
startInclusive: Boolean = true,
endInclusive: Boolean = true) {
// if start and end are specified, start must be less than or equal to end
require((for { s <- start; e <- end} yield { s <= e}).getOrElse(true))
def zero: Boolean = this.bounded && this.start == this.end && !this.startInclusive || !this.endInclusive
def infinite: Boolean = this.start.isEmpty && this.end.isEmpty
// unbounded in this context refers to an interval that is only unbounded on one side
def unbounded: Boolean = leftUnbounded || rightUnbounded
def leftUnbounded: Boolean = this.start.isEmpty && this.end.nonEmpty
def rightUnbounded: Boolean = this.start.nonEmpty && this.end.isEmpty
def bounded: Boolean = this.start.nonEmpty && this.end.nonEmpty
private def touchingEdges(left: TsTzRange, right: TsTzRange): Boolean =
left.end == right.start && left.endInclusive && right.startInclusive
// Checks if the end of bounded2 lies anywhere within bounded1
private def boundedCheckLeftOverlap(bounded1: TsTzRange, bounded2: TsTzRange): Boolean =
bounded2.end > bounded1.start && bounded2.end <= bounded1.end
// Checks if the start of bounded2 lies anywhere within bounded1
private def boundedCheckRightOverlap(bounded1: TsTzRange, bounded2: TsTzRange): Boolean =
bounded2.start >= bounded1.start && bounded2.start < bounded1.end
// boundedCheck assumes both intervals are bounded
private def boundedCheck(bounded1: TsTzRange, bounded2: TsTzRange): Boolean =
boundedCheckLeftOverlap(bounded1, bounded2) ||
boundedCheckRightOverlap(bounded1, bounded2) ||
touchingEdges(bounded2, bounded1) ||
touchingEdges(bounded1, bounded2)
// checks if both ranges are unbounded in opposite directions, and check overlap if so
private def oppositeUnboundedCheck(leftUnbounded: TsTzRange, rightUnbounded: TsTzRange): Boolean =
leftUnbounded.leftUnbounded &&
rightUnbounded.rightUnbounded &&
(leftUnbounded.end > rightUnbounded.start || touchingEdges(leftUnbounded, rightUnbounded))
// checks if both ranges are unbounded in the same direction
private def sameUnboundedCheck(unbounded1: TsTzRange, unbounded2: TsTzRange): Boolean =
(unbounded1.leftUnbounded && unbounded2.leftUnbounded) ||
(unbounded1.rightUnbounded && unbounded2.rightUnbounded)
private def doubleUnboundedCheck(unbounded1: TsTzRange, unbounded2: TsTzRange): Boolean =
sameUnboundedCheck(unbounded1, unbounded2) ||
oppositeUnboundedCheck(unbounded1, unbounded2) ||
oppositeUnboundedCheck(unbounded2, unbounded1)
private def singleUnboundedLeftUnboundedCheck(bounded: TsTzRange, leftUnbounded: TsTzRange): Boolean =
leftUnbounded.leftUnbounded && leftUnbounded.end > bounded.start
private def singleUnboundedRightUnboundedCheck(bounded: TsTzRange, rightUnbounded: TsTzRange): Boolean =
rightUnbounded.rightUnbounded && rightUnbounded.start < bounded.end
// if only one of the intervals is bounded
private def singleUnboundedCheck(bounded: TsTzRange, unbounded: TsTzRange): Boolean =
singleUnboundedLeftUnboundedCheck(bounded, unbounded) ||
singleUnboundedRightUnboundedCheck(bounded, unbounded) ||
touchingEdges(bounded, unbounded) ||
touchingEdges(unbounded, bounded)
def overlaps(other: TsTzRange): Boolean = {
// if any of the intervals are zero, return false early
!(this.zero || other.zero) &&
// if any of the intervals are infinite, return true early
(this.infinite || other.infinite) ||
// otherwise, depending on the boundedness of the 2 intervals, check accordingly
(this.unbounded && other.unbounded && doubleUnboundedCheck(this, other)) ||
(!this.unbounded && !other.unbounded && boundedCheck(this, other)) ||
(!this.unbounded && other.unbounded && singleUnboundedCheck(this, other)) ||
(this.unbounded && !other.unbounded && singleUnboundedCheck(other, this))
}
def contains(other: Instant): Boolean = {
overlaps(TsTzRange(Some(other), Some(other)))
}
// returns true if it overlaps with the current time
def isCurrent: Boolean = {
this.contains(Instant.now)
}
}
```

# Property testing `tstzrange`

Property testing is fun because it’s a chance to think outside the box. It is also a rare example of a programming technique that approaches mathematics in conciseness and rigour. Property testing achieves this by delegating all of the heavy lifting to the testing library, which will generate all sorts of test cases to “stress-test” your code.

We can posit properties like these:

Given any three timestamps

`f1`

,`f2`

, and`f3`

, if`[f1,f2]`

contains`f3`

, then`f3 >= f1`

and`f3 <= f2`

. Else,`f3 < f1`

or`f3 > f2`

.

Given any two timestamps

`f1`

and`f2`

, if`(,f1)`

overlaps`(f2,)`

, then`f1 > f2`

. Else,`f1 <= f2`

.

And they can be implemented like so (note the usage of the `scalacheck-toolbox`

library to assist in generating timestamps):

```
import scala.math.Ordering.Implicits._
import com.fortysevendeg.scalacheck.datetime.instances.jdk8._
import com.fortysevendeg.scalacheck.datetime.jdk8.GenJdk8.genZonedDateTime
import org.scalatest.flatspec.AnyFlatSpec
import org.scalatest.matchers.should.Matchers
import org.scalatestplus.scalacheck.ScalaCheckDrivenPropertyChecks
class TsTzRangeSpec extends AnyFlatSpec with Matchers with ScalaCheckDrivenPropertyChecks {
"TsTzRange's contains" should "work correctly" in {
forAll(genZonedDateTime, genZonedDateTime, genZonedDateTime) {(f1, f2, f3) =>
if (f1 <= f2) {
if (TsTzRange(Some(f1.toInstant), Some(f2.toInstant), false, false).contains(f3.toInstant)) {
f1 should be < f3
f3 should be < f2
} else {
f3 should (be <= f1 or be >= f2)
}
}
}
}
"TsTzRange" should "handle unbounded ranges correctly" in {
forAll(genZonedDateTime, genZonedDateTime) {(f1, f2) => {
if (TsTzRange(None, Some(f1.toInstant), false, false).overlaps(TsTzRange(Some(f2.toInstant), None, false, false))) {
f1 should be > f2
} else {
f1 should be <= f2
}
}}
}
}
```

In the next post, we’ll see how to hook this Scala class up to Jooq.