Package interval

Interface IntervalSet<L>

Type Parameters:
L - type of labels in this set, must be immutable
public interface IntervalSet<L>
A mutable set of labeled intervals, where each unique label is associated with a non-overlapping half-open interval [start,end). Labels are of immutable type L and must implement the Object contract: they are compared for equality using Object.equals(java.lang.Object).

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).

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

  • Method Summary

    Modifier and Type Method Description
    boolean clear()
    Remove all intervals from this set.
    static <L> IntervalSet<L> empty()
    Create an empty interval set.
    long end​(L label)
    Get the end of an interval.
    void insert​(long start, long end, L label)
    Add a labeled interval (if not present) to this set, if it does not conflict with existing intervals.
    Set<L> labels()
    Get the labels in this set.
    long start​(L label)
    Get the start of an interval.

  • Method Details

    • empty

      static <L> IntervalSet<L> empty()
      Create an empty interval set.
      Type Parameters:
      L - type of labels in the set, must be immutable
      Returns:
      a new empty interval set

    • insert

      void insert​(long start, long end, L label)
      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) },

      • insert("A"=[0,10)) has no effect
      • insert("B"=[10,20)) throws IntervalConflictException
      • insert("C"=[20,30)) throws IntervalConflictException
      • insert("D"=[30,40)) adds "D"=[30,40)
      Parameters:
      start - low end of the interval, inclusive
      end - high end of the interval, exclusive, must be greater than start
      label - label to add
      Throws:
      IntervalConflictException - 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)

    • clear

      boolean clear()
      Remove all intervals from this set.
      Returns:
      true if this set was non-empty, and false otherwise

    • labels

      Set<L> labels()
      Get the labels in this set.
      Returns:
      the labels in this set

    • start

      long start​(L label)
      Get the start of an interval.
      Parameters:
      label - the label
      Returns:
      low end, inclusive, of the interval associated with label in this set
      Throws:
      NoSuchElementException - if label is not in this set

    • end

      long end​(L label)
      Get the end of an interval.
      Parameters:
      label - the label
      Returns:
      high end, exclusive, of the interval associated with label in this set
      Throws:
      NoSuchElementException - if label is not in this set