Interface IntervalSet<Label>

A mutable set of labeled intervals, where each unique label is associated with a non-overlapping half-open interval [start,end).

For example, { "A"=[0,10), "B"=[20,30) } is an interval set where the labels are strings "A" and "B". We could add "C"=[10,20) to such a set, but not "D"=[25,35) since that interval overlaps with "B"=[20,30).

Labels are of arbitrary type Label and are compared for equality using ===. They may not be null, undefined, or NaN*.
* Note: this spec was corrected

PS2 instructions: this is a required ADT interface. You may not change the specifications or add new methods.

interface IntervalSet<Label> {
    add(start: bigint, end: bigint, label: Label): void;
    interval(label: Label): undefined | Interval;
    labels(): Set<Label>;
}

Type Parameters

  • Label

    type of labels in this set, compared for equality using ===

Implemented by

Methods

add interval labels

Methods

add

  • add(start: bigint, end: bigint, label: Label): void

  • Add a labeled interval (if not present) to this set, if it does not conflict with existing intervals.

    Labeled intervals conflict if:

    • they have the same label with different intervals; or
    • they have different labels with overlapping intervals.

    For example, if this set is { "A"=[0,10), "B"=[20,30) },

    • add("A"=[0,10)) has no effect
    • add("B"=[10,20)) throws IntervalConflictError
    • add("C"=[20,30)) throws IntervalConflictError
    • add("D"=[30,40)) adds "D"=[30,40)

    Parameters

    • start: bigint

      low end of the interval, inclusive

    • end: bigint

      high end of the interval, exclusive, must be greater than start

    • label: Label

      label to add

    Returns void

    Throws

    an IntervalConflictError if label is already in this set and its interval is not [start,end), or if an interval in this set with a different label overlaps [start,end)

interval

  • interval(label: Label): undefined | Interval

  • Get the interval associated with a label in this set, if any.

    Parameters

    Returns undefined | Interval

    the interval associated with label in this set, or undefined if none

labels

  • labels(): Set<Label>

  • Get the labels in this set.

    Returns Set<Label>

    the labels in this set

Settings

Member Visibility

On This Page

Methods