edu.northwestern.at.utils.intcollections
Class IntRangeList

java.lang.Object
  edu.northwestern.at.utils.intcollections.IntRangeList

All Implemented Interfaces:

java.io.Externalizable, java.io.Serializable, java.lang.Cloneable

public class IntRangeList
extends java.lang.Object
implements java.io.Externalizable, java.lang.Cloneable

A set of non-negative integers.

The set is maintained as a list of integer ranges in increasing order with no overlap and with automatic coalescing of adjacent ranges.

Inspired by the traditional Usenet "newsrc" format.

See Also:

Serialized Form

Field Summary

(package private) static long

serialVersionUID Serial version UID.

Constructor Summary

IntRangeList()
Constructs a new empty list.

IntRangeList(int x)
Constructs a new list with an initial single element.

IntRangeList(int first, int last)
Constructs a new list with an initial range.

IntRangeList(IntRange range)
Constructs a new list from an IntRange object.

IntRangeList(java.lang.String str)
Constructs a new list from a string representation.

Method Summary

void	add(int x) Adds an integer to the list.
void	add(int first, int last) Adds a range of integers to the list.
void	add(IntRange range) Adds an integer range to the list.
IntRangeList	centerInterval(int x, int delta) Gets a centered interval from the list.
void	clear() Clears the list.
java.lang.Object	clone() Returns a copy of the list.
IntRangeList	complement(int max) Returns a new list which is the complement of the list.
boolean	contains(int x) Returns true if the list contains an integer.
boolean	contains(int first, int last) Returns true if the list contains a range of integers.
boolean	contains(IntRangeList other) Returns true if the list contains another list.
IntRangeList	difference(IntRangeList other) Returns a new list which is this list minus another list.
boolean	equals(java.lang.Object other) Compares this list to another list.
int	first() Gets the first integer in the list.
int	get(int i) Gets the i'th integer in the list.
int	indexOf(int x) Gets the index of a list element.
IntRangeList	intersect(IntRangeList other) Returns a new list which is the intersection of this list with another list.
IntIterator	intIterator() Returns an IntIterator for the list.
boolean	isEmpty() Returns true if the list is empty.
(package private) boolean	isValid() Checks to see if the list is valid.
int	last() Gets the last integer in the list.
IntRangeList	leftInterval(int x, int delta) Gets a left interval from the list.
java.util.Iterator	rangeIterator() Returns a range iterator for the list.
void	readExternal(java.io.ObjectInput in) Reads the list on deserialization.
void	remove(int x) Removes an integer from the list.
void	remove(int first, int last) Removes a range of integers from the list.
void	remove(IntRange range) Removes an integer range from the list.
IntRangeList	rightInterval(int x, int delta) Gets a right interval from the list.
void	set(int first, int last) Sets the list to a range.
int	size() Returns the size of the list.
java.lang.String	toString() Returns a string representation of the list.
IntRangeList	union(IntRangeList other) Returns a new list which is the union of this list and another list.
void	writeExternal(java.io.ObjectOutput out) Writes the list on serialization.

Methods inherited from class java.lang.Object

finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

serialVersionUID

static final long serialVersionUID

Serial version UID.

See Also:

Constant Field Values

Constructor Detail

IntRangeList

public IntRangeList()

Constructs a new empty list.

IntRangeList

public IntRangeList(int x)

Constructs a new list with an initial single element.

Parameters:

x - The initial single element.

IntRangeList

public IntRangeList(int first,
                    int last)

Constructs a new list with an initial range.

Parameters:

first - The first integer in the range.

last - The last integer in the range + 1.

IntRangeList

public IntRangeList(IntRange range)

Constructs a new list from an IntRange object.

Parameters:

range - The IntRange object.

IntRangeList

public IntRangeList(java.lang.String str)

Constructs a new list from a string representation.

See toString() for a description of string representations of integer range lists.

Parameters:

str - The string.

Throws:

java.lang.IllegalArgumentException - If syntax error in string.

Method Detail

intIterator

public IntIterator intIterator()

Returns an IntIterator for the list.

The iterator returns the integer list elements in increasing order. The "remove" method is not supported.

Returns:

An IntIterator for the list.

rangeIterator

public java.util.Iterator rangeIterator()

Returns a range iterator for the list.

The IntRange objects returned by the iterator are cloned. If they are modifed the list is unaffected. They are returned in increasing order. The "remove" method is not supported.

Returns:

A range iterator for the list.

size

public int size()

Returns the size of the list.

The value returned is the number of integers in the list, not the number of ranges.

Returns:

The size of the list.

isEmpty

public boolean isEmpty()

Returns true if the list is empty.

Returns:

True if list is empty.

get

public int get(int i)

Gets the i'th integer in the list.

Parameters:

i - The index in the list of the integer to return.

Returns:

The i'th integer in the list (starting at 0), or -1 if i is negative or greater than or equal to the size of the list.

indexOf

public int indexOf(int x)

Gets the index of a list element.

Parameters:

x - The list element.

Returns:

The index of the element in the list, or -1 if the list does not contain the element.

first

public int first()

Gets the first integer in the list.

Returns:

The first element, or -1 if the list is empty.

last

public int last()

Gets the last integer in the list.

Returns:

The last element, or -1 if the list is empty.

clear

public void clear()

Clears the list.

set

public void set(int first,
                int last)

Sets the list to a range.

Parameters:

first - The first integer in the range.

last - The last integer in the range + 1.

add

public void add(int x)

Adds an integer to the list.

Parameters:

x - The integer

add

public void add(int first,
                int last)

Adds a range of integers to the list.

Parameters:

first - The first integer in the range.

last - The last integer in the range + 1.

add

public void add(IntRange range)

Adds an integer range to the list.

Parameters:

range - The integer range.

remove

public void remove(int x)

Removes an integer from the list.

Parameters:

x - The integer

remove

public void remove(int first,
                   int last)

Removes a range of integers from the list.

Parameters:

first - The first integer in the range.

last - The last integer in the range + 1.

remove

public void remove(IntRange range)

Removes an integer range from the list.

Parameters:

range - The integer range.

contains

public boolean contains(int x)

Returns true if the list contains an integer.

Parameters:

x - The integer.

Returns:

True if the list contains x.

contains

public boolean contains(int first,
                        int last)

Returns true if the list contains a range of integers.

Parameters:

first - The first integer in the range.

last - The last integer in the range + 1.

Returns:

True if the list contains the range.

contains

public boolean contains(IntRangeList other)

Returns true if the list contains another list.

Parameters:

other - The other list.

Returns:

True if this list contains the other list.

rightInterval

public IntRangeList rightInterval(int x,
                                  int delta)

Gets a right interval from the list.

The interval returned is another IntRangeList which is a sublist of this list. The sublist contains the specified left endpoint of the interval x plus the delta-1 elements following the left endpoint. If there aren't that many elements following the endpoint, as many as possible are included.

Parameters:

x - The left endpoint of the interval.

delta - The number of elements after the endpoint + 1.

Returns:

The interval, or null if the list does not contain x.

leftInterval

public IntRangeList leftInterval(int x,
                                 int delta)

Gets a left interval from the list.

The interval returned is another IntRangeList which is a sublist of this list. The sublist contains the delta elements preceding the specified right endpoint x, but does not include x. If there aren't that many elements preceding the endpoint, as many as possible are included.

Parameters:

x - The right endpoint of the interval.

delta - The number of elements before the endpoint.

Returns:

The interval.

centerInterval

public IntRangeList centerInterval(int x,
                                   int delta)

Gets a centered interval from the list.

The interval returned is another IntRangeList which is a sublist of this list. The sublist contains the delta elements preceding the midpoint, the midpoint, and the delta-1 elements following the midpoint. If there aren't that many elements preceding and/or following the midpoint, as many as possible are included.

Parameters:

x - The midpoint of the interval.

delta - The range before and after the midpoint.

Returns:

The interval, or null if the list does not contain x.

complement

public IntRangeList complement(int max)

Returns a new list which is the complement of the list.

Parameters:

max - Maximum value + 1 for complemented list.

Returns:

The complement of the list.

union

public IntRangeList union(IntRangeList other)

Returns a new list which is the union of this list and another list.

Parameters:

other - The other list.

Returns:

The union of this list and the other list.

intersect

public IntRangeList intersect(IntRangeList other)

Returns a new list which is the intersection of this list with another list.

Parameters:

other - The other list.

Returns:

This list intersected with the other list.

difference

public IntRangeList difference(IntRangeList other)

Returns a new list which is this list minus another list.

Parameters:

other - The other list.

Returns:

This list minus the other list.

toString

public java.lang.String toString()

Returns a string representation of the list.

The string representation is "xxx,xxx,xxx,...,xxx" where each "xxx" is one integer "a" or is a range of integers "a-b".

Note that the end of each range is inclusive in the string representation, while it is exclusive in the API. For example, a call to "add(10,20)" adds the integers 10 to but not including 20 to the list. When represented as a string the notation is "10-19" meaning "10 through 19 inclusive."

Overrides:

toString in class java.lang.Object

Returns:

The string representation of the list.

clone

public java.lang.Object clone()

Returns a copy of the list.

Overrides:

clone in class java.lang.Object

Returns:

The copy.

equals

public boolean equals(java.lang.Object other)

Compares this list to another list.

Overrides:

equals in class java.lang.Object

Parameters:

other - The other list.

Returns:

True if the lists are equal.

writeExternal

public void writeExternal(java.io.ObjectOutput out)
                   throws java.io.IOException

Writes the list on serialization.

Specified by:

writeExternal in interface java.io.Externalizable

Parameters:

out - Object output stream.

Throws:

java.io.IOException

readExternal

public void readExternal(java.io.ObjectInput in)
                  throws java.io.IOException,
                         java.lang.ClassNotFoundException

Reads the list on deserialization.

Specified by:

readExternal in interface java.io.Externalizable

Parameters:

in - Object input stream.

Throws:

java.io.IOException

java.lang.ClassNotFoundException

isValid

boolean isValid()

Checks to see if the list is valid.

For debugging.

Returns:

True if list is valid.