Class LongArrayBitVector
- java.lang.Object
-
- java.util.AbstractCollection<java.lang.Boolean>
-
- it.unimi.dsi.fastutil.booleans.AbstractBooleanCollection
-
- it.unimi.dsi.fastutil.booleans.AbstractBooleanBigList
-
- it.unimi.dsi.bits.AbstractBitVector
-
- it.unimi.dsi.bits.LongArrayBitVector
-
- All Implemented Interfaces:
BitVector
,it.unimi.dsi.fastutil.BigList<java.lang.Boolean>
,it.unimi.dsi.fastutil.booleans.BooleanBigList
,it.unimi.dsi.fastutil.booleans.BooleanCollection
,it.unimi.dsi.fastutil.booleans.BooleanIterable
,it.unimi.dsi.fastutil.booleans.BooleanStack
,it.unimi.dsi.fastutil.Size64
,it.unimi.dsi.fastutil.Stack<java.lang.Boolean>
,java.io.Serializable
,java.lang.Cloneable
,java.lang.Comparable<it.unimi.dsi.fastutil.BigList<? extends java.lang.Boolean>>
,java.lang.Iterable<java.lang.Boolean>
,java.util.Collection<java.lang.Boolean>
,java.util.RandomAccess
public class LongArrayBitVector extends AbstractBitVector implements java.lang.Cloneable, java.io.Serializable
A bit vector implementation based on arrays of longs.The main goal of this class is to be fast and flexible. It implements a lightweight, fast, open, optimized, reuse-oriented version of bit vectors. Instances of this class represent a bit vector using an array of longs that is enlarged as needed when new entries are created (using
LongArrays.grow(long[], int, int)
), but is never made smaller (even on aclear()
). Usetrim()
for that purpose.Besides usual methods for setting and getting bits, this class provides views that make it possible to access comfortably the bit vector in different ways: for instance,
asLongBigList(int)
provide access as a list of longs, whereasAbstractBitVector.asLongSet()
provides access in setwise form.When enlarging the underlying array (e.g., for
append(long, int)
operations or add operations on the big list view), or when invokingensureCapacity(long)
, this class callsLongArrays.grow(long[], int, int)
, which could enlarge the array more than expected. On the contrary,length(long)
(and the corresponding method in the big list view) sizes the underlying array in an exact manner.Bit numbering follows the right-to-left convention: bit k (counted from the right) of word w is bit 64w + k of the overall bit vector.
If
CHECKS
is true at compile time, boundary checks for all bit operations will be compiled in. For maximum speed, you may want to recompile this class withCHECKS
set to false.CHECKS
is public, so you can check from your code whether you're being provided a version with checks or not. In any case, many checks happen when you enable assertions.Warning: A few optional methods have still to be implemented (e.g., adding an element at an arbitrary position using the list view).
Warning: In some cases, you might want to cache locally the result of
bits()
to speed up computations on immutable bit vectors (this is what happens, for instance, in static ranking structures). This class, however, does its own serialization of the bit vector: as a result, all cached references to the result ofbits()
must be marked as transient and rebuilt at deserialization time, or you will end up saving the bits twice.- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected static class
LongArrayBitVector.LongBigListView
A list-of-integers view of a bit vector.-
Nested classes/interfaces inherited from class it.unimi.dsi.bits.AbstractBitVector
AbstractBitVector.LongSetView, AbstractBitVector.SubBitVector
-
-
Field Summary
Fields Modifier and Type Field Description static long
ALL_ONES
protected long[]
bits
The backing array of this vector.static int
BITS_PER_WORD
Deprecated.Please useLong.SIZE
.static boolean
CHECKS
Whether this class has been compiled with index checks or not.static int
LAST_BIT
static long
LAST_BIT_MASK
protected long
length
The number of bits in this vector.static int
LOG2_BITS_PER_WORD
static int
WORD_MASK
Deprecated.Please use ~-Long.SIZE
.
-
Constructor Summary
Constructors Modifier Constructor Description protected
LongArrayBitVector(long capacity)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
add(long index, boolean value)
BitVector
and(BitVector v)
Performs a logical and between this bit vector and another one, leaving the result in this vector.LongArrayBitVector
append(long value, int width)
Appends the less significant bits of a long integer to this bit vector.it.unimi.dsi.fastutil.longs.LongBigList
asLongBigList(int width)
Returns a view of this bit vector as a list of nonnegative integers of specified width.static int
bit(long index)
Returns the inside-word index of the bit that would hold the bit of specified index.long[]
bits()
Returns the bits in this bit vector as an array of longs, not to be modified.static long
bits(int word)
Returns the number of bits in the given number of words.void
clear()
Sets the size of this bit vector to 0.void
clear(long index)
Clears a bit in this bit vector (optional operation).LongArrayBitVector
clone()
Returns a cloned copy of this bit vector.LongArrayBitVector
copy()
Returns a copy of this bit vector.LongArrayBitVector
copy(long from, long to)
Returns a copy of a part of this bit vector.static LongArrayBitVector
copy(BitVector bv)
Returns a copy of the given bit vector.long
count()
Counts the number of bits set to true in this bit vector.LongArrayBitVector
ensureCapacity(long numBits)
Ensures that this bit vector can hold the specified number of bits.boolean
equals(LongArrayBitVector v)
boolean
equals(LongArrayBitVector v, long start, long end)
boolean
equals(java.lang.Object o)
LongArrayBitVector
fast()
Returns this bit vector.void
fill(boolean value)
Sets all bits this bit vector to the given boolean value (optional operation).void
fill(long from, long to, boolean value)
Fills a range of bits in this bit vector (optional operation).void
flip()
Flips all bits in this bit vector (optional operation).void
flip(long from, long to)
Flips a range of bits in this bit vector (optional operation).boolean
getBoolean(long index)
static LongArrayBitVector
getInstance()
Creates a new empty bit vector.static LongArrayBitVector
getInstance(long capacity)
Creates a new empty bit vector of given capacity.long
getLong(long from, long to)
Returns the specified bit range as a long.int
hashCode()
Returns a hash code for this bit vector.long
length()
Returns the number of bits in this bit vector.LongArrayBitVector
length(long newLength)
Sets the number of bits in this bit vector.long
longestCommonPrefixLength(BitVector v)
Returns the length of the greatest common prefix between this and the specified bit vector.long
longestCommonPrefixLength(LongArrayBitVector v)
static long
mask(long index)
Returns a mask having a 1 exactly at the bitbit(index)
.long
nextOne(long index)
Returns the position of the first bit set at of after the given position.long
nextZero(long index)
Returns the position of the first bit unset after the given position.static LongArrayBitVector
of(int... bit)
Creates a new bit vector with given bits.static LongArrayBitVector
ofLength(long length)
Creates a new empty bit vector of given length.BitVector
or(BitVector v)
Performs a logical or between this bit vector and another one, leaving the result in this bit vector.long
previousOne(long index)
Returns the position of the first bit set strictly before the given position.long
previousZero(long index)
Returns the position of the first bit unset before or at the given position.boolean
removeBoolean(long index)
LongArrayBitVector
replace(BitVector bv)
Replaces the content of this bit vector with another bit vector.LongArrayBitVector
replace(LongArrayBitVector bv)
static boolean
round(long index)
Returns true if the argument is a multiple ofLong.SIZE
.static boolean
sameWord(long index0, long index1)
Returns true if the two bit indices point at the same word.void
set(long index)
Sets a bit in this bit vector (optional operation).boolean
set(long index, boolean value)
boolean
trim()
Reduces as must as possible the size of the backing array.static int
word(long index)
Returns the index of the word that holds a bit of specified index.static int
words(long size)
Returns the number of words that are necessary to hold the given number of bits.static LongArrayBitVector
wrap(long[] array)
Wraps the given array of longs in a bit vector.static LongArrayBitVector
wrap(long[] array, long size)
Wraps the given array of longs in a bit vector for the given number of bits.BitVector
xor(BitVector v)
Performs a logical xor between this bit vector and another one, leaving the result in this vector.-
Methods inherited from class it.unimi.dsi.bits.AbstractBitVector
add, add, add, add, append, asLongSet, clear, compareTo, compareTo, ensureIndex, ensureRestrictedIndex, equals, fill, fill, firstOne, firstZero, flip, flip, getBoolean, getInt, isPrefix, isProperPrefix, lastOne, lastZero, removeBoolean, set, set, set, size, size, size64, subVector, subVector, toString
-
Methods inherited from class it.unimi.dsi.fastutil.booleans.AbstractBooleanBigList
add, addAll, addAll, addAll, addAll, addElements, addElements, contains, forEach, get, getElements, indexOf, indexOf, iterator, lastIndexOf, lastIndexOf, listIterator, listIterator, peek, peekBoolean, pop, popBoolean, push, push, rem, remove, removeElements, set, setElements, subList, top, topBoolean
-
Methods inherited from class it.unimi.dsi.fastutil.booleans.AbstractBooleanCollection
add, contains, containsAll, containsAll, remove, removeAll, removeAll, retainAll, retainAll, toArray, toBooleanArray, toBooleanArray
-
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface it.unimi.dsi.fastutil.booleans.BooleanBigList
add, addAll, addAll, addAll, addAll, addAll, addElements, addElements, get, getElements, getElements, indexOf, indexOf, iterator, lastIndexOf, lastIndexOf, listIterator, listIterator, remove, removeElements, set, setElements, setElements, setElements, spliterator, subList
-
Methods inherited from interface it.unimi.dsi.fastutil.booleans.BooleanCollection
add, addAll, contains, contains, containsAll, rem, remove, removeAll, removeIf, removeIf, retainAll, toArray, toBooleanArray, toBooleanArray
-
-
-
-
Field Detail
-
LOG2_BITS_PER_WORD
public static final int LOG2_BITS_PER_WORD
-
BITS_PER_WORD
@Deprecated public static final int BITS_PER_WORD
Deprecated.Please useLong.SIZE
.- See Also:
- Constant Field Values
-
WORD_MASK
@Deprecated public static final int WORD_MASK
Deprecated.Please use ~-Long.SIZE
.- See Also:
- Constant Field Values
-
LAST_BIT
public static final int LAST_BIT
- See Also:
- Constant Field Values
-
ALL_ONES
public static final long ALL_ONES
- See Also:
- Constant Field Values
-
LAST_BIT_MASK
public static final long LAST_BIT_MASK
- See Also:
- Constant Field Values
-
CHECKS
public static final boolean CHECKS
Whether this class has been compiled with index checks or not.- See Also:
- Constant Field Values
-
length
protected long length
The number of bits in this vector.
-
bits
protected transient long[] bits
The backing array of this vector. Bit 0 of the first element contains bit 0 of the bit vector, bit 0 of the second element contains bitLong.SIZE
of the bit vector and so on.
-
-
Method Detail
-
words
public static final int words(long size)
Returns the number of words that are necessary to hold the given number of bits.- Parameters:
size
- a number of bits.- Returns:
- the number of words that are necessary to hold the given number of bits.
-
word
public static final int word(long index)
Returns the index of the word that holds a bit of specified index.- Parameters:
index
- the index of a bit, or -1.- Returns:
- the index of the word that holds the bit of given index, or -1 if
index
is -1.
-
sameWord
public static final boolean sameWord(long index0, long index1)
Returns true if the two bit indices point at the same word.- Parameters:
index0
- the index of a bit, or -1.index1
- the index of a bit, or -1.- Returns:
- true if the two indices point at the same word.
-
bits
public static final long bits(int word)
Returns the number of bits in the given number of words.- Parameters:
word
- a word position.- Returns:
Long.SIZE
*word
.
-
round
public static final boolean round(long index)
Returns true if the argument is a multiple ofLong.SIZE
.- Parameters:
index
- the index of a bit, or -1.- Returns:
- true if
index
is a multiple ofLong.SIZE
.
-
bit
public static final int bit(long index)
Returns the inside-word index of the bit that would hold the bit of specified index.Note that bit 0 is positioned in word 0, index 0, bit 1 in word 0, index 1, …, bit
BITS_PER_WORD
in word 0, index 0, bitLong.SIZE
+ 1 in word 1, index 1, and so on.- Parameters:
index
- the index of a bit.- Returns:
- the inside-word index of the bit that would hold the bit of specified index.
-
mask
public static final long mask(long index)
Returns a mask having a 1 exactly at the bitbit(index)
.- Parameters:
index
- the index of a bit- Returns:
- a mask having a 1 exactly at the bit
bit(index)
.
-
getInstance
public static LongArrayBitVector getInstance(long capacity)
Creates a new empty bit vector of given capacity. The resulting vector will be able to containcapacity
bits without reallocations of the backing array.Note that this constructor creates an empty bit vector. If you want a cleared bit vector of a specified size, please use the
ofLength(long)
factory method.- Parameters:
capacity
- the capacity (in bits) of the new bit vector.- Returns:
- a new bit vector of given capacity.
-
getInstance
public static LongArrayBitVector getInstance()
Creates a new empty bit vector. No allocation is actually performed.- Returns:
- a new bit vector with no capacity.
-
ofLength
public static LongArrayBitVector ofLength(long length)
Creates a new empty bit vector of given length.- Parameters:
length
- the size (in bits) of the new bit vector.
-
of
public static LongArrayBitVector of(int... bit)
Creates a new bit vector with given bits.- Parameters:
bit
- a list of bits that will be set in the newly created bit vector.
-
bits
public long[] bits()
Description copied from interface:BitVector
Returns the bits in this bit vector as an array of longs, not to be modified.- Specified by:
bits
in interfaceBitVector
- Overrides:
bits
in classAbstractBitVector
- Returns:
- an array of longs whose first
BitVector.length()
bits contain the bits of this bit vector. The array cannot be modified.
-
length
public long length()
Description copied from interface:BitVector
Returns the number of bits in this bit vector.If the number of bits in this bit vector is smaller than or equal to
Integer.MAX_VALUE
, this method is semantically equivalent toList.size()
. In any case, this method is semantically equivalent toSize64.size64()
, but it is prefererred.
-
ensureCapacity
public LongArrayBitVector ensureCapacity(long numBits)
Ensures that this bit vector can hold the specified number of bits.This method uses
LongArrays.grow(long[], int, int)
to ensure that there is enough space for the given number of bits. As a consequence, the actual length of the long array allocated might be larger than expected.- Parameters:
numBits
- the number of bits that this vector must be able to contain.- Returns:
- this bit vector.
-
length
public LongArrayBitVector length(long newLength)
Description copied from interface:BitVector
Sets the number of bits in this bit vector.It is expected that this method will try to allocate exactly the necessary space.
If the argument fits an integer, this method has the same side effects of
BooleanList.size(int)
. In any case, this method has the same side effects ofBigList.size(long)
, but it is preferred, as it has the advantage of returning this bit vector, thus making it possible to chain methods.- Specified by:
length
in interfaceBitVector
- Overrides:
length
in classAbstractBitVector
- Parameters:
newLength
- the new length in bits for this bit vector.- Returns:
- this bit vector.
-
fill
public void fill(boolean value)
Description copied from interface:BitVector
Sets all bits this bit vector to the given boolean value (optional operation).- Specified by:
fill
in interfaceBitVector
- Overrides:
fill
in classAbstractBitVector
- Parameters:
value
- the value (true or false).
-
fill
public void fill(long from, long to, boolean value)
Description copied from interface:BitVector
Fills a range of bits in this bit vector (optional operation).- Specified by:
fill
in interfaceBitVector
- Overrides:
fill
in classAbstractBitVector
- Parameters:
from
- the first index (inclusive).to
- the last index (not inclusive).value
- the value (true or false).
-
flip
public void flip()
Description copied from interface:BitVector
Flips all bits in this bit vector (optional operation).- Specified by:
flip
in interfaceBitVector
- Overrides:
flip
in classAbstractBitVector
-
flip
public void flip(long from, long to)
Description copied from interface:BitVector
Flips a range of bits in this bit vector (optional operation).- Specified by:
flip
in interfaceBitVector
- Overrides:
flip
in classAbstractBitVector
- Parameters:
from
- the first index (inclusive).to
- the last index (not inclusive).
-
trim
public boolean trim()
Reduces as must as possible the size of the backing array.- Returns:
- true if some trimming was actually necessary.
-
clear
public void clear()
Sets the size of this bit vector to 0.Note that this method does not try to reallocate that backing array. If you want to force that behaviour, call
trim()
afterwards.- Specified by:
clear
in interfacejava.util.Collection<java.lang.Boolean>
- Overrides:
clear
in classAbstractBitVector
-
copy
public LongArrayBitVector copy(long from, long to)
Description copied from interface:BitVector
Returns a copy of a part of this bit vector.- Specified by:
copy
in interfaceBitVector
- Overrides:
copy
in classAbstractBitVector
- Parameters:
from
- the starting bit, inclusive.to
- the ending bit, not inclusive.- Returns:
- a copy of the part of this bit vector going from bit
from
(inclusive) to bitto
(not inclusive)
-
copy
public LongArrayBitVector copy()
Description copied from interface:BitVector
Returns a copy of this bit vector.- Specified by:
copy
in interfaceBitVector
- Overrides:
copy
in classAbstractBitVector
- Returns:
- a copy of this bit vector.
-
fast
public LongArrayBitVector fast()
Returns this bit vector.- Specified by:
fast
in interfaceBitVector
- Overrides:
fast
in classAbstractBitVector
- Returns:
- this bit vector.
-
copy
public static LongArrayBitVector copy(BitVector bv)
Returns a copy of the given bit vector.This method uses
BitVector.getLong(long, long)
onLong.SIZE
boundaries to copy at high speed.- Parameters:
bv
- a bit vector.- Returns:
- an instance of this class containing a copy of the given vector.
-
getBoolean
public boolean getBoolean(long index)
- Specified by:
getBoolean
in interfaceit.unimi.dsi.fastutil.booleans.BooleanBigList
-
set
public boolean set(long index, boolean value)
- Specified by:
set
in interfaceit.unimi.dsi.fastutil.booleans.BooleanBigList
- Overrides:
set
in classAbstractBitVector
-
set
public void set(long index)
Description copied from interface:BitVector
Sets a bit in this bit vector (optional operation).- Specified by:
set
in interfaceBitVector
- Overrides:
set
in classAbstractBitVector
- Parameters:
index
- the index of a bit.
-
clear
public void clear(long index)
Description copied from interface:BitVector
Clears a bit in this bit vector (optional operation).- Specified by:
clear
in interfaceBitVector
- Overrides:
clear
in classAbstractBitVector
- Parameters:
index
- the index of a bit.
-
add
public void add(long index, boolean value)
- Specified by:
add
in interfaceit.unimi.dsi.fastutil.booleans.BooleanBigList
- Overrides:
add
in classAbstractBitVector
-
removeBoolean
public boolean removeBoolean(long index)
- Specified by:
removeBoolean
in interfaceit.unimi.dsi.fastutil.booleans.BooleanBigList
- Overrides:
removeBoolean
in classAbstractBitVector
-
append
public LongArrayBitVector append(long value, int width)
Description copied from interface:BitVector
Appends the less significant bits of a long integer to this bit vector.- Specified by:
append
in interfaceBitVector
- Overrides:
append
in classAbstractBitVector
- Parameters:
value
- a value to be appendedwidth
- the number of less significant bits to be added to this bit vector.- Returns:
- this bit vector.
-
getLong
public long getLong(long from, long to)
Description copied from interface:BitVector
Returns the specified bit range as a long.Note that bit 0 of the returned long will be bit
from
of this bit vector.Implementations are invited to provide high-speed implementations for the case in which
from
is a multiple ofLong.SIZE
andto
isfrom
+Long.SIZE
(or less, in case the vector length is exceeded). This behaviour make it possible to implement high-speed hashing, copies, etc.- Specified by:
getLong
in interfaceBitVector
- Overrides:
getLong
in classAbstractBitVector
- Parameters:
from
- the starting bit (inclusive).to
- the ending bit (exclusive).- Returns:
- the long value contained in the specified bits.
-
count
public long count()
Description copied from interface:BitVector
Counts the number of bits set to true in this bit vector.- Specified by:
count
in interfaceBitVector
- Overrides:
count
in classAbstractBitVector
- Returns:
- the number of bits set to true in this bit vector.
-
nextOne
public long nextOne(long index)
Description copied from interface:BitVector
Returns the position of the first bit set at of after the given position.- Specified by:
nextOne
in interfaceBitVector
- Overrides:
nextOne
in classAbstractBitVector
- Parameters:
index
- a bit position.- Returns:
- the position of the first bit set at or after position
index
, or -1 if no such bit exists.
-
previousOne
public long previousOne(long index)
Description copied from interface:BitVector
Returns the position of the first bit set strictly before the given position.- Specified by:
previousOne
in interfaceBitVector
- Overrides:
previousOne
in classAbstractBitVector
- Parameters:
index
- a bit position.- Returns:
- the position of the first bit set strictly before position
index
, or -1 if no such bit exists.
-
nextZero
public long nextZero(long index)
Description copied from interface:BitVector
Returns the position of the first bit unset after the given position.- Specified by:
nextZero
in interfaceBitVector
- Overrides:
nextZero
in classAbstractBitVector
- Parameters:
index
- a bit position.- Returns:
- the first bit unset after position
index
(inclusive), or -1 if no such bit exists.
-
previousZero
public long previousZero(long index)
Description copied from interface:BitVector
Returns the position of the first bit unset before or at the given position.- Specified by:
previousZero
in interfaceBitVector
- Overrides:
previousZero
in classAbstractBitVector
- Parameters:
index
- a bit position.- Returns:
- the first bit unset before or at the given position, or -1 if no such bit exists.
-
longestCommonPrefixLength
public long longestCommonPrefixLength(BitVector v)
Description copied from interface:BitVector
Returns the length of the greatest common prefix between this and the specified bit vector.- Specified by:
longestCommonPrefixLength
in interfaceBitVector
- Overrides:
longestCommonPrefixLength
in classAbstractBitVector
- Parameters:
v
- a bit vector.- Returns:
- the length of the greatest common prefix.
-
longestCommonPrefixLength
public long longestCommonPrefixLength(LongArrayBitVector v)
-
and
public BitVector and(BitVector v)
Description copied from interface:BitVector
Performs a logical and between this bit vector and another one, leaving the result in this vector.- Specified by:
and
in interfaceBitVector
- Overrides:
and
in classAbstractBitVector
- Parameters:
v
- a bit vector.- Returns:
- this bit vector.
-
or
public BitVector or(BitVector v)
Description copied from interface:BitVector
Performs a logical or between this bit vector and another one, leaving the result in this bit vector.- Specified by:
or
in interfaceBitVector
- Overrides:
or
in classAbstractBitVector
- Parameters:
v
- a bit vector.- Returns:
- this bit vector.
-
xor
public BitVector xor(BitVector v)
Description copied from interface:BitVector
Performs a logical xor between this bit vector and another one, leaving the result in this vector.- Specified by:
xor
in interfaceBitVector
- Overrides:
xor
in classAbstractBitVector
- Parameters:
v
- a bit vector.- Returns:
- this bit vector.
-
wrap
public static LongArrayBitVector wrap(long[] array, long size)
Wraps the given array of longs in a bit vector for the given number of bits.Note that all bits in
array
beyond that of indexsize
must be unset, or an exception will be thrown.- Parameters:
array
- an array of longs.size
- the number of bits of the newly created bit vector.- Returns:
- a bit vector of size
size
usingarray
as backing array.
-
wrap
public static LongArrayBitVector wrap(long[] array)
Wraps the given array of longs in a bit vector.- Parameters:
array
- an array of longs.- Returns:
- a bit vector of size
array.length * Long.SIZE
usingarray
as backing array.
-
clone
public LongArrayBitVector clone() throws java.lang.CloneNotSupportedException
Returns a cloned copy of this bit vector.This method is functionally equivalent to
copy()
, except thatcopy()
trims the backing array.- Overrides:
clone
in classjava.lang.Object
- Returns:
- a copy of this bit vector.
- Throws:
java.lang.CloneNotSupportedException
-
replace
public LongArrayBitVector replace(LongArrayBitVector bv)
-
replace
public LongArrayBitVector replace(BitVector bv)
Description copied from class:AbstractBitVector
Replaces the content of this bit vector with another bit vector.- Specified by:
replace
in interfaceBitVector
- Overrides:
replace
in classAbstractBitVector
- Parameters:
bv
- a bit vector.- Returns:
- this bit vector.
-
hashCode
public int hashCode()
Description copied from interface:BitVector
Returns a hash code for this bit vector.Hash codes for bit vectors are defined as follows:
final long length = length(); long fullLength = length & -Long.SIZE; long h = 0x9e3779b97f4a7c13L ^ length; for(long i = 0; i < fullLength; i += Long.SIZE) h ^= (h << 5) + getLong(i, i + Long.SIZE) + (h >>> 2); if (length != fullLength) h ^= (h << 5) + getLong(fullLength, length) + (h >>> 2); (int)((h >>> 32) ^ h);
The last value is the hash code of the bit vector. This hashing is based on shift-add-xor hashing (M.V. Ramakrishna and Justin Zobel, “Performance in practice of string hashing functions”, Proc. of the Fifth International Conference on Database Systems for Advanced Applications, 1997, pages 215−223).
The returned value is not a high-quality hash such as Jenkins's, but it can be computed very quickly; in any case, 32 bits are too few for a high-quality hash to be used in large-scale applications.
Important: all bit vector implementations are required to return the value defined here. The simplest way to obtain this result is to subclass
AbstractBitVector
.- Specified by:
hashCode
in interfaceBitVector
- Specified by:
hashCode
in interfacejava.util.Collection<java.lang.Boolean>
- Overrides:
hashCode
in classAbstractBitVector
- Returns:
- a hash code for this bit vector.
-
equals
public boolean equals(java.lang.Object o)
- Specified by:
equals
in interfacejava.util.Collection<java.lang.Boolean>
- Overrides:
equals
in classAbstractBitVector
-
equals
public boolean equals(LongArrayBitVector v)
-
equals
public boolean equals(LongArrayBitVector v, long start, long end)
-
asLongBigList
public it.unimi.dsi.fastutil.longs.LongBigList asLongBigList(int width)
Description copied from interface:BitVector
Returns a view of this bit vector as a list of nonnegative integers of specified width.More formally,
getLong(p)
will return the nonnegative integer defined by the bits starting atp * width
(bit 0, inclusive) and ending at(p + 1) * width
(bitwidth
− 1, exclusive).- Specified by:
asLongBigList
in interfaceBitVector
- Overrides:
asLongBigList
in classAbstractBitVector
- Parameters:
width
- a bit width.- Returns:
- a view of this bit vector as a list of nonnegative integers of specified width.
-
-