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 Detail

      • 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)
     throws IntervalConflictException
        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)
    throws NoSuchElementException
        Get the start of an interval.
        Parameters:
        label - the label
        Returns:
        low end, inclusive, of the interval associated with label
        Throws:
        NoSuchElementException - if label is not in this set

      • end

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