package jsat.utils;
import java.io.Serializable;
import java.util.AbstractSet;
import java.util.Iterator;
/**
* A set for integers that is of a fixed initial size, and can only accept
* integers in the range [0, size). Insertions, removals, and checks are all
* constant time with a fast iterator.
* Null values are not supported
*
* @author Edward Raff
*/
public class IntSetFixedSize extends AbstractSet implements Serializable
{
private static final long serialVersionUID = 7743166074116253587L;
private static final int STOP = -1;
private int nnz = 0;
private int first = -1;
private boolean[] has;
//Use as a linked list
private int[] prev;
private int[] next;
/**
* Creates a new fixed size int set
* @param size the size of the int set
*/
public IntSetFixedSize(int size)
{
has = new boolean[size];
prev = new int[size];
next = new int[size];
first = STOP;
}
@Override
public boolean add(Integer e)
{
return add(e.intValue());
}
/**
* Adds a new integer into the set
* @param e the value to add into the set
* @return {@code true} if the operation modified the set, {@code false}
* otherwise.
*/
public boolean add(int e)
{
if(e < 0 || e >= has.length)
throw new IllegalArgumentException("Input must be in range [0, " + has.length + ") not " + e);
else if(contains(e) )
return false;
else
{
if (nnz == 0)
{
first = e;
next[e] = prev[e] = STOP;
}
else
{
prev[first] = e;
next[e] = first;
prev[e] = STOP;
first = e;
}
nnz++;
return has[e] = true;
}
}
@Override
public boolean remove(Object o)
{
if(o instanceof Integer)
return remove_int((Integer)o);
return super.remove(o);
}
/**
* Removes the specified integer from the set
* @param val the value to remove
* @return {@code true} if the set was modified by this operation,
* {@code false} if it was not.
*/
public boolean remove(int val)
{
return remove_int(val);
}
@Override
public boolean contains(Object o)
{
if(o instanceof Integer)
{
int val = (Integer)o;
return contains(val);
}
else
return false;
}
/**
* Checks if the given value is contained in this set
* @param val the value to check for
* @return {@code true} if the value is in the set, {@code false} otherwise.
*/
public boolean contains(int val)
{
if(val < 0 || val >= has.length)
return false;
return has[val];
}
private boolean remove_int(int index)
{
if (contains(index))
{
if (first == index)
first = next[index];
else
next[prev[index]] = next[index];
if (next[index] != STOP)
prev[next[index]] = prev[index];
next[index] = STOP;
has[index] = false;
nnz--;
return true;
}
else
return false;
}
@Override
public Iterator iterator()
{
final Iterator iterator = new Iterator()
{
int prev = STOP;
int runner = first;
@Override
public boolean hasNext()
{
return runner != STOP;
}
@Override
public Integer next()
{
prev = runner;
runner = next[runner];
return prev;
}
@Override
public void remove()
{
remove_int(prev);
}
};
return iterator;
}
@Override
public int size()
{
return nnz;
}
}
Ads help maintain this website.