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 and Description
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.
boolean	remove(L label) Remove a labeled interval from this set, if present.
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)

remove

boolean remove(L label)

Remove a labeled interval from this set, if present.

Parameters:

label - label to remove

Returns:

true if this set contained label, 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