Time Intervals in Scala

August 24, 2020

Having recent­ly felt com­pelled to start using tstzrange to rep­re­sent time inter­vals in Post­gres (instead of two sep­a­rate start and end columns), I’ve also had to grap­ple with writ­ing a custom Scala class for Jooq to know what kind of code to gen­er­ate to rep­re­sent the column.

This arti­cle is split into two parts. The first part talks about writ­ing such a class to rep­re­sent Post­gres’s tstzrange column. The second part talks about how to use that custom class with Jooq.

Why range types?

Range types offers better expres­siv­i­ty in the form of spe­cial­ized oper­a­tors. && checks for the inter­sec­tion between two ranges, >> checks if one range is strict­ly on the right of the other, -|- checks if two ranges are adja­cent. The full list of oper­a­tors can be found here.

Range types have built-in val­i­da­tion to make sure that the start cannot be greater than the end.

Range types can express the con­cept of inclu­sive and exclu­sive bounds. [3,4]::int4range includes both 3 and 4, [3,4)::int4range includes only 3.

Range types can be indexed mul­ti­di­men­sion­al­ly using GiST index­es, and can also option­al­ly com­bined with B-Tree index­es for queries involv­ing both range type columns and scalar columns.

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

This exam­ple con­straint main­tains the invari­ant that no room can be double-booked.

Dis­crete vs con­tin­u­ous ranges

Ranges can be dichotomized into dis­crete ranges and con­tin­u­ous ranges. Dis­crete ranges are ranges like int8range, whose ele­ment type have well-defined steps (in this case, the set of all 8-bit inte­gers). Con­tin­u­ous ranges are ranges like tstzrange and floatrange, where the ele­ment type does not have well-defined steps.

Dis­crete ranges can be canon­i­cal­ized into a [x,y) form, since for any x, we can iden­ti­fy its pre­de­ces­sor and suc­ces­sor values. Fur­ther­more, in dis­crete ranges, there exists the edge case of (x,x + delta) being equiv­a­lent to an empty inter­val, e.g. (3,4)::int4range. In con­tin­u­ous ranges, the only valid empty inter­val rep­re­sen­ta­tions are (x,x), [x,x), and (x,x] .

Rep­re­sent­ing tstzrange in Scala

With some of the con­text above, we can now dive into the imple­men­ta­tion proper.

One of the most impor­tant meth­ods to have on a poten­tial tstzrange class is overlaps, and as you will see, imple­ment­ing overlaps as a prim­i­tive will enable us to triv­ial­ly imple­ment contains (and a host of other meth­ods).

We need to handle five cases here.

Given two ranges A and B:

  1. Either A or B is an empty inter­val
  2. Either A or B is an infi­nite inter­val ((,))
  3. Either A or B is an unbound­ed inter­val ((x,) or (,x))
  4. Both A and B are unbound­ed inter­vals
  5. Both A and B are bound­ed inter­vals

This looks com­pli­cat­ed because we need to handle unbound­ed inter­vals and inclu­sive/​exclu­sive ranges (and since tstzrange is not a dis­crete range, we cannot canon­i­cal­ize it before­hand).

I’ve chosen to enforce the “start cannot greater than end” val­i­da­tion using a simple Scala requires, which will throw a run­time IllegalArgumentException. You may choose to over­ride the apply func­tion 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)
  }
}

Prop­er­ty test­ing tstzrange

Prop­er­ty test­ing is fun because it’s a chance to think out­side the box. It is also a rare exam­ple of a pro­gram­ming tech­nique that approach­es math­e­mat­ics in con­cise­ness and rigour. Prop­er­ty test­ing achieves this by del­e­gat­ing all of the heavy lift­ing to the test­ing library, which will gen­er­ate all sorts of test cases to “stress-test” your code.

We can posit prop­er­ties like these:

Given any three time­stamps f1, f2, and f3, if [f1,f2] con­tains f3, then f3 >= f1 and f3 <= f2. Else, f3 < f1 or f3 > f2.

Given any two time­stamps f1 and f2, if (,f1) over­laps (f2,), then f1 > f2. Else, f1 <= f2.

And they can be imple­ment­ed like so (note the usage of the scalacheck-toolbox library to assist in gen­er­at­ing time­stamps):

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.