package jsat.utils;
import java.io.Serializable;
import java.util.*;
import static jsat.utils.ClosedHashingUtil.*;
import static jsat.utils.IntDoubleMap.h;
/**
* A utility class for efficiently storing a set of integers. The implementation
* is based on Algorithm D (Open addressing with double hashing) from Knuth's
* TAOCP page 528.
*
* @author Edward Raff
*/
public class IntSet extends AbstractSet implements Serializable
{
private static final long serialVersionUID = -2175363824037596497L;
private static final int DEFAULT_CAPACITY = 8;
private float loadFactor;
private int used = 0;
/**
* Number of indices marked "free". It is possible for used= 0 and free =
* 0, if everything was deleted. When nothig is free, we need to re-insert
* and clear the index to avoid corner case infinite loop that was not
* accounted for in original algo description
*/
private int free = 0;
private byte[] status;
private int[] keys;
/**
* Creates a new empty integer set
*/
public IntSet()
{
this(DEFAULT_CAPACITY);
}
/**
* Creates an empty integer set pre-allocated to store a specific number of
* items
*
* @param capacity the number of items to store
*/
public IntSet(int capacity)
{
this(capacity, 0.75f);
}
/**
* Creates an empty integer set pre-allocated to store a specific number of
* items
*
* @param capacity the number of items to store
* @param loadFactor the maximum ratio of used to un-used storage
*/
public IntSet(int capacity, float loadFactor)
{
this.loadFactor = loadFactor;
int size = getNextPow2TwinPrime((int) Math.max(capacity / loadFactor, 4));
status = new byte[size];
keys = new int[size];
used = 0;
free = size;
}
/**
* Creates a new set of integers from the given set
* @param set the set of integers to create a copy of
*/
public IntSet(Set set)
{
this(set.size());
for(Integer integer : set)
this.add(integer);
}
/**
* Creates a set of integers from the given collection
* @param collection a collection of integers to create a set from
*/
public IntSet(Collection collection)
{
this();
for(Integer integer : collection)
this.add(integer);
}
/**
* Creates a set of integers from the given list of integers.
* @param ints a list of integers to create a set from
* @return a set of integers of all the unique integers in the given list
*/
public static IntSet from(int... ints)
{
return new IntSet(IntList.view(ints, ints.length));
}
/**
* Gets the index of the given key. Based on that {@link #status} variable,
* the index is either the location to insert OR the location of the key.
*
* This method returns 2 integer table in the long. The lower 32 bits are
* the index that either contains the key, or is the first empty index.
*
* The upper 32 bits is the index of the first position marked as
* {@link #DELETED} either {@link Integer#MIN_VALUE} if no position was
* marked as DELETED while searching.
*
* @param key they key to search for
* @param inserting {@code true} if a value is being inserted into the index, false otherwise
* @return the mixed long containing the index of the first DELETED position
* and the position that the key is in or the first EMPTY position found
*/
private long getIndex(int key, boolean inserting)
{
long extraInfo = EXTRA_INDEX_INFO;
//D1
final int hash = h(key) & INT_MASK;
int i = hash % keys.length;
//D2
int satus_i = status[i];
if((keys[i] == key && satus_i != DELETED) || satus_i == EMPTY)
return extraInfo | i;
if(extraInfo == EXTRA_INDEX_INFO && satus_i == DELETED)
extraInfo = ((long)i) << 32;
//D3
final int c = 1 + (hash % (keys.length -2));
while(true)//this loop will terminate
{
//D4
i -= c;
if(i < 0)
i += keys.length;
//D5
satus_i = status[i];
if( (keys[i] == key && satus_i != DELETED) || satus_i == EMPTY || (satus_i == DELETED && inserting))
return extraInfo | i;
if(extraInfo == EXTRA_INDEX_INFO && satus_i == DELETED)
extraInfo = ((long)i) << 32;
}
}
private void enlargeIfNeeded()
{
if(used < keys.length*loadFactor && free > 0)
return;
//enlarge
final byte[] oldSatus = status;
final int[] oldKeys = keys;
int newSize;
if(used > keys.length*loadFactor)
newSize = getNextPow2TwinPrime(status.length*3/2);//it will actually end up doubling in size since we have twin primes spaced that was
else//Don't expand, but free = 0, so re-hash to avoild infinite chaning
{
newSize = oldSatus.length;
}
status = new byte[newSize];
keys = new int[newSize];
used = 0;
free = newSize;
for(int oldIndex = 0; oldIndex < oldSatus.length; oldIndex++)
if(oldSatus[oldIndex] == OCCUPIED)
add(oldKeys[oldIndex]);
}
@Override
public void clear()
{
used = 0;
Arrays.fill(status, EMPTY);
}
@Override
public boolean add(Integer e)
{
if(e == null)
return false;
return add(e.intValue());
}
/**
*
* @param e element to be added to this set
* @return true if this set did not already contain the specified element
*/
public boolean add(int e)
{
final int key = e;
long pair_index = getIndex(key, true);
int deletedIndex = (int) (pair_index >>> 32);
int valOrFreeIndex = (int) (pair_index & INT_MASK);
byte origStatus = status[valOrFreeIndex];
if(origStatus == OCCUPIED)//easy case
{
return false;//we already had this item in the set!
}
//else, not present
int i = valOrFreeIndex;
if(deletedIndex >= 0)//use occupied spot instead
{
i = deletedIndex;
origStatus = status[i];
}
status[i] = OCCUPIED;
keys[i] = key;
used++;
if(origStatus == EMPTY)
free--;
enlargeIfNeeded();
return true;//item was not in the set previously
}
public boolean contains(int o)
{
int index = (int) (getIndex(o, false) & INT_MASK);
return status[index] == OCCUPIED;//would be FREE if we didn't have the key
}
@Override
public boolean remove(Object key)
{
if(key instanceof Integer)
return remove(((Integer)key).intValue());
return false;
}
/**
*
* @param key the value from the set to remove
* @return true if this set contained the specified element
*/
public boolean remove(int key)
{
long pair_index = getIndex(key, false);
int valOrFreeIndex = (int) (pair_index & INT_MASK);
if(status[valOrFreeIndex] == EMPTY)//ret index is always EMPTY or OCCUPIED
return false;
//else
status[valOrFreeIndex] = DELETED;
used--;
return true;
}
@Override
public boolean contains(Object o)
{
if(o != null && o instanceof Integer)
return contains(((Integer)o).intValue());
else
return false;
}
@Override
public Iterator iterator()
{
final IntSet parentRef = this;
//find the first starting inded
int START = 0;
while (START < status.length && status[START] != OCCUPIED)
START++;
if (START == status.length)
return Collections.emptyIterator();
final int startPos = START;
return new Iterator()
{
int pos = startPos;
int prevPos = -1;
@Override
public boolean hasNext()
{
return pos < status.length;
}
@Override
public Integer next()
{
//final int make so that object remains good after we call next again
final int oldPos = prevPos = pos++;
//find next
while (pos < status.length && status[pos] != OCCUPIED)
pos++;
//and return new object
return keys[oldPos];
}
@Override
public void remove()
{
//its ok to just call remove b/c nothing is re-ordered when we remove an element, we just set the status to DELETED
parentRef.remove(keys[prevPos]);
}
};
}
@Override
public int size()
{
return used;
}
}
Ads help maintain this website.