IntervalMapSuite.scala

// libraryDependencies += "com.rklaehn" %% "intervalset" % "0.2.0"

import java.time.Instant
import scala.collection.immutable.SortedSet
import com.rklaehn.interval.IntervalMap.{ Value, FromBool => IntervalMap }
import org.scalatest.FunSuite
import spire.algebra.Order
import spire.implicits.StringOrder
import spire.math.Interval
import spire.optional.genericEq.generic

final class IntervalMapSuite extends FunSuite {
  implicit def InstantOrder: Order[Instant] =
    Order.from((a, b) => a.compareTo(b))

  /**
   * A type-class for values which have an associated interval.
   */
  trait HasInterval[A] {
    def interval(a: A): Interval[Instant]
  }

  case class Foo(foo: String, interval: Interval[Instant])
  case class Bar(bar: String, interval: Interval[Instant])

  object Foo {
    implicit val FooHasInterval: HasInterval[Foo] = _.interval
  }

  object Bar {
    implicit val BarHasInterval: HasInterval[Bar] = _.interval
  }

  /**
   * Boilerplate that I don't yet know how to eliminate.
   */
  implicit def Tuple2Value[A, B](implicit A: Value[A], B: Value[B]): Value[(A, B)] =
    new Value[(A, B)] {
      override def eqv(a: (A, B), b: (A, B)) =
        A.eqv(a._1, b._1) && B.eqv(a._2, b._2)
      override def isOne(a: (A, B)) =
        A.isOne(a._1) && B.isOne(a._2)
      override def isZero(a: (A, B)) =
        A.isZero(a._1) && B.isZero(a._2)
      override def zero =
        (A.zero, B.zero)
      override def xor(a: (A, B), b: (A, B)) =
        (A.xor(a._1, b._1), B.xor(a._2, b._2))
      override def and(a: (A, B), b: (A, B)) =
        (A.and(a._1, b._1), B.and(a._2, b._2))
      override def or(a: (A, B), b: (A, B)) =
        (A.or(a._1, b._1), B.or(a._2, b._2))
    }

  implicit def Tuple3Value[A, B, C](implicit A: Value[A], B: Value[B], C: Value[C]): Value[(A, B, C)] =
    new Value[(A, B, C)] {
      override def eqv(a: (A, B, C), b: (A, B, C)) =
        A.eqv(a._1, b._1) && B.eqv(a._2, b._2) && C.eqv(a._3, b._3)
      override def isOne(a: (A, B, C)) =
        A.isOne(a._1) && B.isOne(a._2) && C.isOne(a._3)
      override def isZero(a: (A, B, C)) =
        A.isZero(a._1) && B.isZero(a._2) && C.isZero(a._3)
      override def zero =
        (A.zero, B.zero, C.zero)
      override def xor(a: (A, B, C), b: (A, B, C)) =
        (A.xor(a._1, b._1), B.xor(a._2, b._2), C.xor(a._3, b._3))
      override def and(a: (A, B, C), b: (A, B, C)) =
        (A.and(a._1, b._1), B.and(a._2, b._2), C.and(a._3, b._3))
      override def or(a: (A, B, C), b: (A, B, C)) =
        (A.or(a._1, b._1), B.or(a._2, b._2), C.or(a._3, b._3))
    }

  /**
   * Version A: associate each interval with a tuple of sets. This version
   * needs custom `Value` instances for each tuple arity. See `Tuple2Value`
   * above.
   *
   * The only constraints on `A` and `B` are the `HasInterval` ones.
   */
  def multiOverlapA2[A, B](as: Seq[A], bs: Seq[B])(implicit HA: HasInterval[A], HB: HasInterval[B]): Traversable[(Interval[Instant], A, B)] = {
    val aMaps = as.map { a => HA.interval(a) -> (Set(a) -> Set.empty[B]) }
    val bMaps = bs.map { b => HB.interval(b) -> (Set.empty[A] -> Set(b)) }

    IntervalMap(aMaps ++ bMaps : _*).entries.flatMap {
      case (interval, (as, bs)) =>
        for {
          a <- as
          b <- bs
        } yield (interval, a, b)
    }
  }

  /**
   * Version A for 3-tuples; see `Tuple3Value`.
   */
  def multiOverlapA3[A, B, C](as: Seq[A], bs: Seq[B], cs: Seq[C])(implicit HA: HasInterval[A], HB: HasInterval[B], HC: HasInterval[C]): Traversable[(Interval[Instant], A, B, C)] = {
    val aMaps = as.map { a => HA.interval(a) -> ((Set(a), Set.empty[B], Set.empty[C])) }
    val bMaps = bs.map { b => HB.interval(b) -> ((Set.empty[A], Set(b), Set.empty[C])) }
    val cMaps = cs.map { c => HC.interval(c) -> ((Set.empty[A], Set.empty[B], Set(c))) }

    IntervalMap(aMaps ++ bMaps ++ cMaps : _*).entries.flatMap {
      case (interval, (as, bs, cs)) =>
        for {
          a <- as
          b <- bs
          c <- cs
        } yield (interval, a, b, c)
    }
  }

  /**
   * Version B: associate each interval with a `Set` of 2-tuples of `Option`.
   */
  def multiOverlapB2[A, B](as: Seq[A], bs: Seq[B])(implicit HA: HasInterval[A], HB: HasInterval[B]): Traversable[(Interval[Instant], A, B)] = {
    val aMaps = as.map { a => HA.interval(a) -> Set(Option(a) -> Option.empty[B]) }
    val bMaps = bs.map { b => HB.interval(b) -> Set(Option.empty[A] -> Option(b)) }

    IntervalMap(aMaps ++ bMaps : _*).entries.flatMap {
      case (interval, values) =>
        val as = values.collect { case (Some(a), _) => a }
        val bs = values.collect { case (_, Some(b)) => b }
        for {
          a <- as
          b <- bs
        } yield (interval, a, b)
    }
  }

  /**
   * Version B for 3-tuples.
   */
  def multiOverlapB3[A, B, C](as: Seq[A], bs: Seq[B], cs: Seq[C])(implicit HA: HasInterval[A], HB: HasInterval[B], HC: HasInterval[C]): Traversable[(Interval[Instant], A, B, C)] = {
    val aMaps = as.map { a => HA.interval(a) -> Set((Option(a), Option.empty[B], Option.empty[C])) }
    val bMaps = bs.map { b => HB.interval(b) -> Set((Option.empty[A], Option(b), Option.empty[C])) }
    val cMaps = cs.map { c => HC.interval(c) -> Set((Option.empty[A], Option.empty[B], Option(c))) }

    IntervalMap(aMaps ++ bMaps ++ cMaps : _*).entries.flatMap {
      case (interval, values) =>
        val as = values.collect { case (Some(a), _, _) => a }
        val bs = values.collect { case (_, Some(b), _) => b }
        val cs = values.collect { case (_, _, Some(c)) => c }

        for {
          a <- as
          b <- bs
          c <- cs
        } yield (interval, a, b, c)
    }
  }

  test("generic, multi overlap") {
    val `00:00` = Instant.parse("2018-04-12T00:00:00Z")
    val `00:05` = Instant.parse("2018-04-12T00:05:00Z")
    val `00:10` = Instant.parse("2018-04-12T00:10:00Z")
    val `00:15` = Instant.parse("2018-04-12T00:15:00Z")

    val foo1 = Foo("foo 1", Interval.openUpper(`00:00`, `00:05`))
    val foo2 = Foo("foo 2", Interval.openUpper(`00:05`, `00:10`))
    val bar1 = Bar("bar 1", Interval.openUpper(`00:05`, `00:10`))
    val bar2 = Bar("bar 2", Interval.openUpper(`00:10`, `00:15`))

    val allA = multiOverlapA2(Seq(foo1, foo2), Seq(bar1, bar2))
    val allB = multiOverlapB2(Seq(foo1, foo2), Seq(bar1, bar2))

    val expected = Seq((Interval.openUpper(`00:05`, `00:10`), foo2, bar1))

    assert(allA == expected)
    assert(allB == expected)
  }

  test("two overlapping intervals") {
    val `00:00` = Instant.parse("2018-04-12T00:00:00Z")
    val `00:05` = Instant.parse("2018-04-12T00:05:00Z")
    val `00:10` = Instant.parse("2018-04-12T00:10:00Z")
    val `00:15` = Instant.parse("2018-04-12T00:15:00Z")

    val intervals = Seq(
      Interval(`00:00`, `00:10`) -> SortedSet("foo"),
      Interval(`00:05`, `00:15`) -> SortedSet("bar"),
    )

    val empty = IntervalMap.zero[Instant, SortedSet[String]]
    val all = intervals.map(IntervalMap(_)).foldLeft(empty)(_ | _)

    assert(all(`00:00`) == SortedSet("foo"))
    assert(all(`00:05`) == SortedSet("foo", "bar"))
    assert(all(`00:10`) == SortedSet("foo", "bar"))
    assert(all(`00:15`) == SortedSet("bar"))
  }
}