org.limewire.collection
Class SparseIntSet

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<java.lang.Integer>
          org.limewire.collection.SparseIntSet

All Implemented Interfaces:

java.lang.Iterable<java.lang.Integer>, java.util.Collection<java.lang.Integer>, java.util.Set<java.lang.Integer>

public class SparseIntSet
extends java.util.AbstractSet<java.lang.Integer>

Represents a set of distinct integers. Like Set, SparseIntSet is not synchronized.

The integers in this set are sorted in ascending order. It would be nice for it to implement the SortedSet interface eventually.

Optimized to have compact representation when the set is "sparse". (For "dense" sets you should use IntSet.) Integers are stored as primitives, so you're guaranteed 4*N bytes of memory used after calling the compact() method.

All retrieval and insertion operations run in O(log n) time, where n is the size of the set.

This class is not thread-safe.

Constructor Summary

SparseIntSet()
Creates an empty set with capacity = 8.

SparseIntSet(java.util.Collection<? extends java.lang.Integer> c)
Creates a set containing all the elements of the provided collection.

SparseIntSet(int initialCapacity)
Creates an empty set with the provided initial capacity.

Method Summary

boolean	add(java.lang.Integer i)
boolean	addAll(java.util.Collection<? extends java.lang.Integer> c)
void	compact() Compacts this set to occupy 4*size() bytes of memory.
boolean	contains(java.lang.Object o)
int	getActualMemoryUsed()
java.util.Iterator<java.lang.Integer>	iterator()
int	nextSetBit(int fromIndex)
boolean	remove(java.lang.Object o)
boolean	retainAll(java.util.Collection<?> o)
int	size()

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

clear, containsAll, isEmpty, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

clear, containsAll, isEmpty, toArray, toArray

Constructor Detail

SparseIntSet

public SparseIntSet()

Creates an empty set with capacity = 8. (similar to ArrayList)

SparseIntSet

public SparseIntSet(int initialCapacity)

Creates an empty set with the provided initial capacity.

Parameters:

initialCapacity - the initial capacity desired.

SparseIntSet

public SparseIntSet(java.util.Collection<? extends java.lang.Integer> c)

Creates a set containing all the elements of the provided collection.

Method Detail

compact

public void compact()

Compacts this set to occupy 4*size() bytes of memory.

getActualMemoryUsed

public int getActualMemoryUsed()

Returns:

the actual memory used, in bytes.

nextSetBit

public int nextSetBit(int fromIndex)

Returns:

the next element that is larger than the provided element

add

public boolean add(java.lang.Integer i)

Specified by:

add in interface java.util.Collection<java.lang.Integer>

Specified by:

add in interface java.util.Set<java.lang.Integer>

Overrides:

add in class java.util.AbstractCollection<java.lang.Integer>

addAll

public boolean addAll(java.util.Collection<? extends java.lang.Integer> c)

Specified by:

addAll in interface java.util.Collection<java.lang.Integer>

Specified by:

addAll in interface java.util.Set<java.lang.Integer>

Overrides:

addAll in class java.util.AbstractCollection<java.lang.Integer>

remove

public boolean remove(java.lang.Object o)

Specified by:

remove in interface java.util.Collection<java.lang.Integer>

Specified by:

remove in interface java.util.Set<java.lang.Integer>

Overrides:

remove in class java.util.AbstractCollection<java.lang.Integer>

contains

public boolean contains(java.lang.Object o)

Specified by:

contains in interface java.util.Collection<java.lang.Integer>

Specified by:

contains in interface java.util.Set<java.lang.Integer>

Overrides:

contains in class java.util.AbstractCollection<java.lang.Integer>

iterator

public java.util.Iterator<java.lang.Integer> iterator()

Specified by:

iterator in interface java.lang.Iterable<java.lang.Integer>

Specified by:

iterator in interface java.util.Collection<java.lang.Integer>

Specified by:

iterator in interface java.util.Set<java.lang.Integer>

Specified by:

iterator in class java.util.AbstractCollection<java.lang.Integer>

size

public int size()

Specified by:

size in interface java.util.Collection<java.lang.Integer>

Specified by:

size in interface java.util.Set<java.lang.Integer>

Specified by:

size in class java.util.AbstractCollection<java.lang.Integer>

retainAll

public boolean retainAll(java.util.Collection<?> o)

Specified by:

retainAll in interface java.util.Collection<java.lang.Integer>

Specified by:

retainAll in interface java.util.Set<java.lang.Integer>

Overrides:

retainAll in class java.util.AbstractCollection<java.lang.Integer>