Package interval

Class MultiIntervalSet<L>

java.lang.Object
interval.MultiIntervalSet<L>
Type Parameters:
L - type of labels in this set, must be immutable
public class MultiIntervalSet<L>
extends Object
A mutable set of labeled intervals, where each label is associated with one or more non-overlapping half-open intervals [start, end). Neither intervals with the same label nor with different labels may overlap. 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 a multi-interval set where the labels are Strings "A" and "B". We could add "A"=[10,20) to that set to obtain { "A"=[[0,10),[10,20)], "B"=[[20,30)] }.

PS2 instructions: this is a required ADT class. You may not change the specifications or add new public methods. You must use IntervalSet in your rep, but otherwise the implementation of this class is up to you.

  • Constructor Details

    • MultiIntervalSet

      public MultiIntervalSet()
      Create an empty multi-interval set.

    • MultiIntervalSet

      public MultiIntervalSet​(IntervalSet<L> initial)
      Create a new multi-interval set containing the given labeled intervals.
      Parameters:
      initial - initial contents of the new multi-interval set

  • Method Details

    • insert

      public 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, overlapping intervals, or
      • they have different labels with overlapping intervals.

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

      • insert("A"=[0,10)) has no effect
      • insert("B"=[10,20)) adds "B"=[[10,20)]
      • insert("C"=[20,30)) throws IntervalConflictException
      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 is associated with an interval other than [start,end) that overlaps [start,end), or if an interval in this set with a different label overlaps [start,end)

    • clear

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

    • labels

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

    • intervals

      public IntervalSet<Integer> intervals​(L label)
      Get all the intervals in this set associated with a given label. The returned set has Integer labels that act as indices: label 0 is associated with the lowest interval, 1 the next, and so on, for all the intervals in this set that have the provided label.

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

      • intervals("A") returns { 0=[0,10), 1=[20,30) }
      Parameters:
      label - the label
      Returns:
      a new interval set that associates integer indices with the in-order intervals of label in this set
      Throws:
      NoSuchElementException - if label is not in this set

    • toString

      public String toString()
      Overrides:
      toString in class Object