org.archive.util
Class AbstractLongFPSet

java.lang.Object
  org.archive.util.AbstractLongFPSet

All Implemented Interfaces:

java.io.Serializable, LongFPSet

Direct Known Subclasses:

MemLongFPSet

public abstract class AbstractLongFPSet
extends java.lang.Object
implements LongFPSet, java.io.Serializable

Shell of functionality for a Set of primitive long fingerprints, held in an array of possibly-empty slots. The implementation of that holding array is delegated to subclasses.

Capacity is always a power of 2.

Fingerprints are already assumed to be well-distributed, so the hashed position for a value is just its high-order bits.

Version:

$Date: 2005-05-06 02:49:04 +0000 (Fri, 06 May 2005) $, $Revision: 3437 $

Author:

gojomo

See Also:

Serialized Form

Field Summary

protected int	capacityPowerOfTwo the capacity of this set, specified as the exponent of a power of 2
protected long	count The current number of elements in the set
protected static byte	EMPTY A constant used to indicate that a slot in the set storage is empty.
protected float	loadFactor The load factor, as a fraction.

Constructor Summary

AbstractLongFPSet()
To support serialization TODO: verify needed?

AbstractLongFPSet(int capacityPowerOfTwo, float loadFactor)
Create a new AbstractLongFPSet with a given capacity and load Factor

Method Summary

boolean	add(long val) Add the given value to this set
protected abstract void	clearAt(long index)
boolean	contains(long val) Does this set contain the given value?
long	count() Return the number of entries in this set.
protected abstract long	getAt(long i) Get the stored value at the given slot.
protected abstract int	getSlotState(long i) Check the state of a slot in the storage.
protected abstract void	makeSpace() Make additional space to keep the load under the target loadFactor level.
boolean	quickContains(long fp) Low-cost, non-definitive (except when true) contains test.
protected abstract void	relocate(long value, long fromIndex, long toIndex)
boolean	remove(long l) Remove a fingerprint from the set, if it is there
protected void	removeAt(long index) Remove the value at the given index, relocating its successors as necessary.
protected abstract void	setAt(long i, long l) Set the stored value at the given slot.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

EMPTY

protected static byte EMPTY

A constant used to indicate that a slot in the set storage is empty. A zero or positive value means slot is filled

capacityPowerOfTwo

protected int capacityPowerOfTwo

the capacity of this set, specified as the exponent of a power of 2

loadFactor

protected float loadFactor

The load factor, as a fraction. This gives the amount of free space to keep in the Set.

count

protected long count

The current number of elements in the set

Constructor Detail

AbstractLongFPSet

public AbstractLongFPSet()

To support serialization TODO: verify needed?

AbstractLongFPSet

public AbstractLongFPSet(int capacityPowerOfTwo,
                         float loadFactor)

Create a new AbstractLongFPSet with a given capacity and load Factor

Parameters:

capacityPowerOfTwo - The capacity as the exponent of a power of 2. e.g if the capacity is 4 this means 2^^4 entries

loadFactor - The load factor as a fraction. This gives the amount of free space to keep in the Set.

Method Detail

contains

public boolean contains(long val)

Does this set contain the given value?

Specified by:

contains in interface LongFPSet

Parameters:

val - the fingerprint to check for

Returns:

true if the fingerprint is in the set

See Also:

LongFPSet.contains(long)

getSlotState

protected abstract int getSlotState(long i)

Check the state of a slot in the storage.

Parameters:

i - the index of the slot to check

Returns:

-1 if slot is filled; nonegative if full.

count

public long count()

Return the number of entries in this set.

Specified by:

count in interface LongFPSet

Returns:

the number of elements in the Set

See Also:

LongFPSet.count()

add

public boolean add(long val)

Add the given value to this set

Specified by:

add in interface LongFPSet

Parameters:

val - the fingerprint to add

Returns:

true if set has changed with this addition

See Also:

LongFPSet.add(long)

makeSpace

protected abstract void makeSpace()

Make additional space to keep the load under the target loadFactor level. Subclasses may grow or discard entries to satisfy.

setAt

protected abstract void setAt(long i,
                              long l)

Set the stored value at the given slot.

Parameters:

i - the slot index

l - the value to set

getAt

protected abstract long getAt(long i)

Get the stored value at the given slot.

Parameters:

i - the slot index

Returns:

The stored value at the given slot.

remove

public boolean remove(long l)

Description copied from interface: LongFPSet

Remove a fingerprint from the set, if it is there

Specified by:

remove in interface LongFPSet

Parameters:

l - the fingerprint to remove

Returns:

true if we removed the fingerprint

removeAt

protected void removeAt(long index)

Remove the value at the given index, relocating its successors as necessary.

Parameters:

index -

clearAt

protected abstract void clearAt(long index)

relocate

protected abstract void relocate(long value,
                                 long fromIndex,
                                 long toIndex)

quickContains

public boolean quickContains(long fp)

Low-cost, non-definitive (except when true) contains test. Default answer of false is acceptable.

Specified by:

quickContains in interface LongFPSet

Parameters:

fp - the fingerprint to check for

Returns:

true if contains the fingerprint

See Also:

LongFPSet.quickContains(long)