org.limewire.collection
Class SparseIntSet

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

All Implemented Interfaces:

Iterable<Integer>, Collection<Integer>, Set<Integer>

public class SparseIntSet
extends AbstractSet<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(Collection<? extends 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(Integer i)
boolean	addAll(Collection<? extends Integer> c)
void	compact() Compacts this set to occupy 4*size() bytes of memory.
boolean	contains(Object o)
int	getActualMemoryUsed()
Iterator<Integer>	iterator()
int	nextSetBit(int fromIndex)
boolean	remove(Object o)
boolean	retainAll(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(Collection<? extends 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(Integer i)

Specified by:

add in interface Collection<Integer>

Specified by:

add in interface Set<Integer>

Overrides:

add in class AbstractCollection<Integer>

addAll

public boolean addAll(Collection<? extends Integer> c)

Specified by:

addAll in interface Collection<Integer>

Specified by:

addAll in interface Set<Integer>

Overrides:

addAll in class AbstractCollection<Integer>

remove

public boolean remove(Object o)

Specified by:

remove in interface Collection<Integer>

Specified by:

remove in interface Set<Integer>

Overrides:

remove in class AbstractCollection<Integer>

contains

public boolean contains(Object o)

Specified by:

contains in interface Collection<Integer>

Specified by:

contains in interface Set<Integer>

Overrides:

contains in class AbstractCollection<Integer>

iterator

public Iterator<Integer> iterator()

Specified by:

iterator in interface Iterable<Integer>

Specified by:

iterator in interface Collection<Integer>

Specified by:

iterator in interface Set<Integer>

Specified by:

iterator in class AbstractCollection<Integer>

size

public int size()

Specified by:

size in interface Collection<Integer>

Specified by:

size in interface Set<Integer>

Specified by:

size in class AbstractCollection<Integer>

retainAll

public boolean retainAll(Collection<?> o)

Specified by:

retainAll in interface Collection<Integer>

Specified by:

retainAll in interface Set<Integer>

Overrides:

retainAll in class AbstractCollection<Integer>