BinaryTransformation.java

/**
 * A base-preserving map out of the product of two pointed sets.
 *
 * The basepoint of a product is the pair of their basepoints. Only this point needs to be sent
 * to the target set's basepoint. If one or both elements of the tuple are defined, the transformation
 * can do whatever it likes.
 */
public interface BinaryTransformation<A, B, C> {
  // When only one value is present
  Optional<C> left(A left);
  Optional<C> right(B right);
  // When both values are present
  Optional<C> combine(A left, B right);
  // When no values are present, the transformation always produces `empty`.

  static <A, B, C> BinaryTransformation<A, B, C> from(final BiFunction<Optional<A>, Optional<B>, Optional<C>> f) {
    return new BinaryTransformation<>() {
      @Override
      public Optional<C> combine(final A left, final B right) {
        return f.apply(Optional.of(left), Optional.of(right));
      }

      @Override
      public Optional<C> left(final A left) {
        return f.apply(Optional.of(left), Optional.empty());
      }

      @Override
      public Optional<C> right(final B right) {
        return f.apply(Optional.empty(), Optional.of(right));
      }
    };
  }

  static <A, B, C> BinaryTransformation<A, B, C> byCases(
      final Function<A, Optional<C>> left,
      final Function<B, Optional<C>> right,
      final BiFunction<A, B, Optional<C>> combine
  ) {
    return new BinaryTransformation<>() {
      @Override
      public Optional<C> combine(final A a, final B b) {
        return combine.apply(a, b);
      }

      @Override
      public Optional<C> left(final A a) {
        return left.apply(a);
      }

      @Override
      public Optional<C> right(final B b) {
        return right.apply(b);
      }
    };
  }
}

IntervalMap.java

/** An immutable association of values to points on a dense timeline. */
public final class IntervalMap<V> implements Iterable<Segment<V>> {
  private record Transition<V>(Duration startTime, Window.Inclusivity inclusivity, Optional<V> value) {
    public Window upTo(final Transition<V> other) {
      return Window.between(this.startTime, this.inclusivity, other.startTime, other.inclusivity.opposite());
    }
  }

  // INVARIANT: `transitions` is in strictly increasing order by `startTime`.
  //   Two adjacent transitions imply a "segment"; any other order makes segment extraction difficult.
  // INVARIANT: If `transitions` is not empty, its final transition is to `Optional.empty()`.
  //   This ensures that all segments are finite in extent.
  // INVARIANT: If `transitions` is not empty, its initial transition is not to `Optional.empty()`.
  //   The first transition should always begin a defined segment; time prior to it is considered `empty()`.
  // INVARIANT: No two adjacent transitions have the same associated `value`.
  //   This is less important for correctness, and more a concern of efficiency.
  // TODO: Use a linked list of contiguous chunks to avoid quadratic asymptotic reallocation costs
  //   and large single allocation restrictions.
  private final List<Transition<V>> transitions;

  private IntervalMap(final List<Transition<V>> transitions) {
    this.transitions = Objects.requireNonNull(transitions);
  }

  public static <V> Builder<V> builder() {
    return new Builder<>();
  }

  /** Filter the contents of this map by a given window. */
  public IntervalMap<V> select(final Window window) {
    enum Unit { UNIT }

    return this.map2(
        IntervalMap.<Unit>builder().add(window, Unit.UNIT).finish(),
        BinaryTransformation.byCases(
            a -> Optional.empty(),
            b -> Optional.empty(),
            (a, b) -> Optional.of(a)));
  }

  /** Mask the contents of this map whenever a given map is defined. */
  public IntervalMap<V> mask(final IntervalMap<V> mask) {
    return this.map2(
        mask,
        BinaryTransformation.byCases(
            a -> Optional.of(a),
            b -> Optional.of(b),
            (a, b) -> Optional.of(b)));
  }

  /** Pair the values of this map with those of another. */
  public <V2> IntervalMap<Pair<V, V2>> zip(final IntervalMap<V2> other) {
    return this.map2(
        other,
        BinaryTransformation.byCases(
            a -> Optional.empty(),
            b -> Optional.empty(),
            (a, b) -> Optional.of(Pair.of(a, b))));
  }

  /** Get the smallest window containing all defined points in the map. */
  public Window hull() {
    if (this.transitions.isEmpty()) return Window.EMPTY;

    // SAFETY: By invariant, when `transitions` is non-empty,
    return this.transitions.get(0).upTo(this.transitions.get(this.transitions.size() - 1));
  }

  public <R> IntervalMap<R> map(final UnaryTransformation<V, R> transform) {
    final var builder = IntervalMap.<R>builder();

    for (final var segment : this) {
      final var value = transform.apply(segment.value());
      if (value.isPresent()) builder.add(segment.interval(), value.get());
    }

    return builder.finish();
  }

  public <V2, R> IntervalMap<R> map2(final IntervalMap<V2> other, final BinaryTransformation<V, V2, R> transform) {
    final var alg = new Windows.WindowAlgebra();
    final var builder = IntervalMap.<R>builder();

    final var left = this.iterator();
    final var right = other.iterator();

    var leftSegment = Optional.<Segment<V>>empty();
    var rightSegment = Optional.<Segment<V2>>empty();

    while (leftSegment.isPresent() || rightSegment.isPresent() || left.hasNext() || right.hasNext()) {
      if (leftSegment.isEmpty() && left.hasNext()) leftSegment = Optional.of(left.next());
      if (rightSegment.isEmpty() && right.hasNext()) rightSegment = Optional.of(right.next());

      final var leftInterval = leftSegment.map($ -> $.interval()).orElse(Window.EMPTY);
      final var rightInterval = rightSegment.map($ -> $.interval()).orElse(Window.EMPTY);

      // Extract the prefix and overlap between these intervals.
      // At most one prefix will be non-empty (they can't each start before the other),
      // but pretending otherwise makes the code simpler.
      final var leftPrefix = alg.intersect(leftInterval, alg.lowerBoundsOf(rightInterval));
      final var rightPrefix = alg.intersect(rightInterval, alg.lowerBoundsOf(leftInterval));
      final var overlap = alg.intersect(leftInterval, rightInterval);
      // At most one interval will have anything left over, but we need to analyze it against the next
      // interval on the opposing timeline.
      final var leftSuffix = alg.intersect(leftInterval, alg.upperBoundsOf(alg.unify(leftPrefix, overlap)));
      final var rightSuffix = alg.intersect(rightInterval, alg.upperBoundsOf(alg.unify(rightPrefix, overlap)));

      // Compute a new value on each interval.
      if (!leftPrefix.isEmpty()) {
        // SAFETY: leftPrefix can only be non-empty if leftSegment is non-empty.
        final var leftValue = transform.left(leftSegment.get().value());
        if (leftValue.isPresent()) builder.add(leftPrefix, leftValue.get());
      }
      if (!rightPrefix.isEmpty()) {
        // SAFETY: rightPrefix can only be non-empty if rightSegment is non-empty.
        final var rightValue = transform.right(rightSegment.get().value());
        if (rightValue.isPresent()) builder.add(rightPrefix, rightValue.get());
      }
      if (!overlap.isEmpty()) {
        // SAFETY: overlap can only be non-empty if both leftSegment and rightSegment are non-empty.
        final var overlapValue = transform.combine(leftSegment.get().value(), rightSegment.get().value());
        if (overlapValue.isPresent()) builder.add(overlap, overlapValue.get());
      }

      // Trim our current segment to the remaining suffixes.
      if (!leftSuffix.isEmpty()) {
        // SAFETY: leftSuffix can only be non-empty is leftSegment is non-empty.
        leftSegment = Optional.of(new Segment<>(leftSuffix, leftSegment.get().value()));
      } else {
        leftSegment = Optional.empty();
      }
      if (!rightSuffix.isEmpty()) {
        // SAFETY: rightSuffix can only be non-empty is rightSegment is non-empty.
        rightSegment = Optional.of(new Segment<>(rightSuffix, rightSegment.get().value()));
      } else {
        rightSegment = Optional.empty();
      }
    }

    return builder.finish();
  }

  @Override
  public Iterator<Segment<V>> iterator() {
    if (this.transitions.isEmpty()) return Collections.emptyIterator();

    final var iter = this.transitions.iterator();

    return new Iterator<>() {
      Transition<V> prev = iter.next();
      Optional<Segment<V>> next = Optional.empty();

      @Override
      public boolean hasNext() {
        resume();
        return this.next.isPresent();
      }

      @Override
      public Segment<V> next() {
        resume();
        final var result = this.next.orElseThrow(NoSuchElementException::new);
        this.next = Optional.empty();
        return result;
      }

      private void resume() {
        while (this.next.isEmpty() && iter.hasNext()) {
          final var next = iter.next();

          if (this.prev.value.isPresent()) {
            this.next = Optional.of(new Segment<>(this.prev.upTo(next), this.prev.value.get()));
          }

          this.prev = next;
        }
      }
    };
  }

  public static final class Builder<V> {
    // TODO: Use a linked list of contiguous chunks to avoid quadratic asymptotic reallocation costs
    //   and large single allocation restrictions.
    private final List<Transition<V>> transitions;

    private Segment<V> accumulator = null;
    private boolean finished = false;

    private Builder(final List<Transition<V>> transitions) {
      this.transitions = transitions;
    }

    public Builder() {
      this(new ArrayList<>());
    }

    public Builder<V> add(final Window interval, final V value) {
      if (this.finished) throw new IllegalStateException();
      if (interval.isEmpty()) return this;

      final var alg = new Windows.WindowAlgebra();

      if (this.accumulator == null) {
        this.accumulator = new Segment<>(interval, value);
      } else if (alg.meets(this.accumulator.interval(), interval)) {
        if (value.equals(this.accumulator.value())) {
          this.accumulator = new Segment<>(alg.unify(this.accumulator.interval(), interval), this.accumulator.value());
        } else {
          this.transitions.add(new Transition<>(
              this.accumulator.interval().start,
              this.accumulator.interval().startInclusivity,
              Optional.of(this.accumulator.value())));
          this.accumulator = new Segment<>(interval, value);
        }
      } else if (alg.endsBefore(this.accumulator.interval(), interval)) {
        this.transitions.add(new Transition<>(
            this.accumulator.interval().start,
            this.accumulator.interval().startInclusivity,
            Optional.of(this.accumulator.value())));
        this.transitions.add(new Transition<>(
            this.accumulator.interval().end,
            this.accumulator.interval().endInclusivity.opposite(),
            Optional.empty()));
        this.accumulator = new Segment<>(interval, value);
      } else {
        throw new IllegalArgumentException("Intervals must be strictly increasing and non-overlapping");
      }

      return this;
    }

    public IntervalMap<V> finish() {
      if (this.finished) throw new IllegalStateException();

      if (this.accumulator != null) {
        this.transitions.add(new Transition<>(
            this.accumulator.interval().start,
            this.accumulator.interval().startInclusivity,
            Optional.of(this.accumulator.value())));
        this.transitions.add(new Transition<>(
            this.accumulator.interval().end,
            this.accumulator.interval().endInclusivity.opposite(),
            Optional.empty()));
        this.accumulator = null;
      }

      this.finished = true;
      return new IntervalMap<>(this.transitions);
    }
  }
}

Segment.java

public record Segment<V>(Window interval, V value) {}

UnaryTransformation.java

/** A base-preserving map between pointed sets. */
@FunctionalInterface
public interface UnaryTransformation<A, B> {
  Optional<B> apply(A value);
}