com.limegroup.gnutella.util
Class IntSet

java.lang.Object
  extended bycom.limegroup.gnutella.util.IntSet

public class IntSet
extends java.lang.Object

A set of integers. Optimized to have an extremely compact representation when the set is "dense", i.e., has many sequential elements. For example {1, 2} and {1, 2, ..., 1000} require the same amount of space. All retrieval operations run in O(log n) time, where n is the size of the set. Insertion operations may be slower.

All methods have the same specification as the Set class, except that values are restricted to int' for the reason described above. For this reason, methods are not specified below. Like Set, this class is not synchronized.


Nested Class Summary
 class IntSet.IntSetIterator
          Yields a sequence of int's (not Object's) in order, without removal support.
 
Field Summary
 java.util.ArrayList list
          Our current implementation consists of a list of disjoint intervals, sorted by starting location.
 
Constructor Summary
IntSet()
           
IntSet(int expectedSize)
           
 
Method Summary
 boolean add(int x)
           
 boolean addAll(IntSet s)
           
 boolean contains(int x)
           
 IntSet.IntSetIterator iterator()
          Returns the values of this in order from lowest to highest, as int.
 boolean remove(int x)
           
protected  void repOk()
          Checks rep invariant.
 boolean retainAll(IntSet s)
           
 int size()
           
 java.lang.String toString()
           
 void trim()
          Ensures that this consumes the minimum amount of memory.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

list

public java.util.ArrayList list
Our current implementation consists of a list of disjoint intervals, sorted by starting location. As an example, the set {1, 3, 4, 5, 7} is represented by [1, 3-5, 7] Adding 2 turns the representation into [1-5, 7] Note that [1-2 ,3-5, 7] is not allowed by the invariant below. Continuing with the example, removing 3 turns the rep into [1-2, 4-5, 7] We use a sorted List instead of a TreeSet because it has a more compact memory footprint, amd memory is at a premium here. It also makes implementation much easier. Unfortunately it means that insertion and some set operations are more expensive because memory must be allocated and copied. INVARIANT: for all i
Constructor Detail

IntSet

public IntSet()

IntSet

public IntSet(int expectedSize)
Method Detail

repOk

protected void repOk()
Checks rep invariant.


size

public int size()

contains

public boolean contains(int x)

add

public boolean add(int x)

remove

public boolean remove(int x)

addAll

public boolean addAll(IntSet s)

retainAll

public boolean retainAll(IntSet s)

trim

public void trim()
Ensures that this consumes the minimum amount of memory. This method should typically be called after the last call to add(..). Insertions can still be done after the call, but they might be slower. Because this method only affects the performance of this, there is no modifies clause listed.


iterator

public IntSet.IntSetIterator iterator()
Returns the values of this in order from lowest to highest, as int.


toString

public java.lang.String toString()