org.sourceforge.jxutil
Class IntRangesSet

java.lang.Object
  |
  +--org.sourceforge.jxutil.IntRangesSet

All Implemented Interfaces:

Cloneable, Collection, Set, SortedSet

public final class IntRangesSet

extends Object

implements SortedSet, Cloneable

A sorted set to store integers. This set is specialized on storing integer values which can be grouped into ranges. E.g. the set {1,2,3,4,5,11,12,13,30} is stored as {1,5,11,13,30,30}. The more ranges are in the set, the better the storage characteristics get, compared to an int[]. This set is always better as an corresponding TreeSet with Integer values.

Author:

Keve Müller

Field Summary

private boolean	debug
private static int	DEFAULTDELTA
private int	delta The delta to grow the set with.
(package private) int	length The highest index that stores information+1
(package private) int[]	set The integers stored in groups of start,end values.
(package private) long	size The cached number of elements in the set.

Constructor Summary

IntRangesSet()
Construct an empty IntRangesSet.

IntRangesSet(int initialsize, int delta)
Construct an empty IntRangesSet with given initial storage size and delta.

Method Summary

boolean	add(int x) Add an int to the set.
boolean	add(int[] ia)
boolean	add(Object obj) Add an Integer to the set.
boolean	addAll(Collection coll) Add all Integers in given collection.
boolean	addRange(int from, int to)
void	clear() Clear all elements of this set.
Object	clone() Return a clone of this set.
Comparator	comparator() Return null.
IntRangesSet	complement() Return the complement of the set on the complete range of int.
IntRangesSet	complement(int min, int max) Return the complement of the set given the universe.
boolean	contains(int x) Check if the set contains given int.
boolean	contains(Object obj) Check whether the set contains given Integer.
boolean	containsAll(Collection coll) Check whether the set contains given Integers.
boolean	equals(Object obj) Check whether the set equals the given object.
Object	first() Return the first element.
SortedSet	headSet(Object toElement) Return a view...
boolean	isEmpty() Test for emptyness.
Iterator	iterator() Return an iterator over the elements.
Object	last() Return the last element.
long	lsize() Return the full size of the set.
void	pack() Pack the array to contain only as much space as neccessary.
boolean	remove(int x) Remove given int from the set.
boolean	remove(Object obj) Remove given Integer from set.
boolean	removeAll(Collection coll) Remove given Integers from set.
boolean	retainAll(Collection coll) Retain given Integers.
private int	search(int x) Find the index for a value.
int	size() Return the number of elements in the set.
SortedSet	subSet(Object fromElement, Object toElement) Return a view.
SortedSet	tailSet(Object fromElement) Return a view.
Object[]	toArray() Return an array with the elements.
Object[]	toArray(Object[] ia) Copy the elements into an array.
int[]	toIntArray() Copy the sets elements into an int[].
String	toString() Format the set to a string.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Set

hashCode

Field Detail

debug

private boolean debug

DEFAULTDELTA

private static final int DEFAULTDELTA

See Also:

Constant Field Values

delta

private final int delta

The delta to grow the set with.

length

int length

The highest index that stores information+1

set

int[] set

The integers stored in groups of start,end values.

size

long size

The cached number of elements in the set.

Constructor Detail

IntRangesSet

public IntRangesSet()

Construct an empty IntRangesSet.

IntRangesSet

public IntRangesSet(int initialsize,
                    int delta)

Construct an empty IntRangesSet with given initial storage size and delta.

Method Detail

add

public final boolean add(int x)

Add an int to the set.

add

public final boolean add(int[] ia)

add

public final boolean add(Object obj)
                  throws NullPointerException,
                         ClassCastException

Add an Integer to the set.

Specified by:

add in interface Set

Throws:

NullPointerException - - if the specified element is null

ClassCastException - - if the class of the specified element is not Integer

addAll

public final boolean addAll(Collection coll)
                     throws ClassCastException

Add all Integers in given collection. TODO: Optimize for coll==IntSet

Specified by:

addAll in interface Set

Throws:

ClassCastException - - if the class of some element of the specified collection is not Integer, in this case no element is added.

addRange

public final boolean addRange(int from,
                              int to)

clear

public final void clear()

Clear all elements of this set.

Specified by:

clear in interface Set

clone

public final Object clone()

Return a clone of this set. The returned set is always packed.

Overrides:

clone in class Object

comparator

public final Comparator comparator()

Return null.

Specified by:

comparator in interface SortedSet

complement

public final IntRangesSet complement()

Return the complement of the set on the complete range of int. The complement is calculated over [Integer.MIN_VALUE, Integer.MAX_VALUE].

Returns:

An IntRangesSet that contains all integers except those contained in this set.

complement

public final IntRangesSet complement(int min,
                                     int max)

Return the complement of the set given the universe. The complement is calculated over [min, max].

Parameters:

min - The start of the range.

max - The end of the range.

Returns:

An IntRangesSet that contains all integers in the given range except those contained in this set.

contains

public final boolean contains(int x)

Check if the set contains given int.

contains

public final boolean contains(Object obj)
                       throws ClassCastException

Check whether the set contains given Integer.

Specified by:

contains in interface Set

Throws:

ClassCastException - - if the class of the specified element is not Integer

containsAll

public final boolean containsAll(Collection coll)

Check whether the set contains given Integers. TODO: Optimize for coll==IntSet

Specified by:

containsAll in interface Set

equals

public final boolean equals(Object obj)

Check whether the set equals the given object.

Specified by:

equals in interface Set

Overrides:

equals in class Object

first

public final Object first()

Return the first element.

Specified by:

first in interface SortedSet

headSet

public final SortedSet headSet(Object toElement)
                        throws ClassCastException

Return a view... TODO: Implement

Specified by:

headSet in interface SortedSet

Throws:

ClassCastException - - if the class of the specified element is not Integer

isEmpty

public final boolean isEmpty()

Test for emptyness.

Specified by:

isEmpty in interface Set

iterator

public final Iterator iterator()

Return an iterator over the elements. TODO: Implement ConcurrentModificationException. Implement remove

Specified by:

iterator in interface Set

last

public final Object last()

Return the last element.

Specified by:

last in interface SortedSet

lsize

public final long lsize()

Return the full size of the set.

pack

public final void pack()

Pack the array to contain only as much space as neccessary.

remove

public final boolean remove(int x)

Remove given int from the set.

remove

public final boolean remove(Object obj)

Remove given Integer from set.

Specified by:

remove in interface Set

removeAll

public final boolean removeAll(Collection coll)

Remove given Integers from set. TODO: Optimize for coll==IntSet

Specified by:

removeAll in interface Set

retainAll

public final boolean retainAll(Collection coll)

Retain given Integers. TODO: Better implementation Optimize for coll==IntSet

Specified by:

retainAll in interface Set

search

private final int search(int x)

Find the index for a value. Uses a fast binary search on the set's ranges.

size

public final int size()

Return the number of elements in the set.

Specified by:

size in interface Set

subSet

public final SortedSet subSet(Object fromElement,
                              Object toElement)
                       throws ClassCastException

Return a view. TODO: Implement

Specified by:

subSet in interface SortedSet

Throws:

ClassCastException - - if the class of the specified elements is not Integer

tailSet

public final SortedSet tailSet(Object fromElement)
                        throws ClassCastException

Return a view. TODO: Implement

Specified by:

tailSet in interface SortedSet

Throws:

ClassCastException - - if the class of the specified element is not Integer

toArray

public final Object[] toArray()

Return an array with the elements.

Specified by:

toArray in interface Set

toArray

public final Object[] toArray(Object[] ia)

Copy the elements into an array.

Specified by:

toArray in interface Set

toIntArray

public final int[] toIntArray()

Copy the sets elements into an int[].

toString

public final String toString()

Format the set to a string.

Overrides:

toString in class Object