Package net.algart.arrays

Class PackedBitBuffers

java.lang.Object

net.algart.arrays.PackedBitBuffers

public class PackedBitBuffers
extends Object

Operations with bit arrays packed into java.nio.LongBuffer.

AlgART bits arrays, created by BufferMemoryModel and LargeMemoryModel, are based on operations provided by this class.

The maximal length of bit arrays supported by this class is 2³⁷-64. All indexes and lengths passed to methods of this class should not exceed this value. In other case, the results are unspecified. ("Unspecified" means that any elements of the passed buffers can be read or changed, or that IndexOutOfBoundsException can be thrown.)

In all methods of this class, it's supposed that the bit #k in a packed LongBuffer b is the bit #(k%64) in the long element b.get(k/64). In other words, the bit #k (false or true value) can be extracted by the following operator:

 (b.get(k >>> 6) & (1L << (k & 63))) != 0L
 

and can be set or cleared by the following operators:

 if (newValue) // we need to set bit #k to 1
     b.put(k >>> 6, b.get(k >>> 6) | 1L << (k & 63));
 else          // we need to clear bit #k to 0
     b.put(k >>> 6, b.get(k >>> 6) & ~(1L << (k & 63)));
 

You may use getBit(LongBuffer, long) and setBit(LongBuffer, long, boolean), implementing the equivalent code.

If any method of this class modifies some portion of an element of a packed LongBuffer, i.e. modifies less than all 64 its bits, then all accesses to this long element are performed inside a single synchronized block, using the following instruction:

 synchronized (getLock(buffer)) {
     // accessing to some element #k via buffer.get(k) and buffer.put(k, ...)
 }
 

unless otherwise specified in the method comments. (See an example in comments to setBit(java.nio.LongBuffer, long, boolean) method.) If all 64 bits of the element are written, or if the bits are read only, then no synchronization is performed. Such behavior allows to simultaneously work with non-overlapping fragments of a packed bit array from several threads (different fragments for different threads), as if it would be a usual Java array. Synchronization by getLock(buffer) (instead of buffer instance) allows to use in different threads different instances of LongBuffer, created by LongBuffer.wrap method for the sampe Java long[] array.

This class cannot be instantiated.

Author:

Daniel Alievsky

See Also:

• PackedBitArrays

Method Summary

Modifier and Type	Method	Description
static void	andBits(long[] dest, long destPos, LongBuffer src, long srcPos, long count)	Replaces count bits, packed in dest array, starting from the bit #destPos, with the logical AND of them and corresponding count bits, packed in src buffer, starting from the bit #srcPos.
static void	andNotBits(long[] dest, long destPos, LongBuffer src, long srcPos, long count)	Replaces count bits, packed in dest array, starting from the bit #destPos, with the logical AND of them and inverted corresponding count bits, packed in src buffer, starting from the bit #srcPos.
static long	cardinality(LongBuffer src, long fromIndex, long toIndex)	Returns the number of high bits (1) in the given fragment of the given packed bit buffer.
static void	copyBits(LongBuffer dest, long destPos, LongBuffer src, long srcPos, long count)	Copies count bits, packed into src buffer, starting from the bit #srcPos, to packed dest buffer, starting from the bit #destPos.
static void	copyBits(LongBuffer dest, long destPos, LongBuffer src, long srcPos, long count, boolean reverseOrder)	Copies count bits, packed into src buffer, starting from the bit #srcPos, to packed dest buffer, starting from the bit #destPos, in normal or reverse order depending on reverseOrder argument.
static void	fillBits(LongBuffer dest, long destPos, long count, boolean value)	Fills count bits in the packed dest buffer, starting from the bit #destPos, by the specified value.
static boolean	getBit(LongBuffer src, long index)	Returns the bit #index in the packed src bit buffer.
static Object	getLock(LongBuffer buffer)	Returns buffer.hasArray()?buffer.array():buffer.
static long	indexOfBit(LongBuffer src, long lowIndex, long highIndex, boolean value)	Returns the minimal index k, so that lowIndex<=k<highIndex and the bit #k in the packed src bit buffer is equal to value, or -1 if there is no such bits.
static long	lastIndexOfBit(LongBuffer src, long lowIndex, long highIndex, boolean value)	Returns the maximal index k, so that highIndex>k>=lowIndex and the bit #k in the packed src bit buffer is equal to value, or -1 if there is no such bits.
static void	notBits(long[] dest, long destPos, LongBuffer src, long srcPos, long count)	Replaces count bits, packed in dest array, starting from the bit #destPos, with the logical NOT of corresponding count bits, packed in src buffer, starting from the bit #srcPos.
static void	orBits(long[] dest, long destPos, LongBuffer src, long srcPos, long count)	Replaces count bits, packed in dest array, starting from the bit #destPos, with the logical OR of them and corresponding count bits, packed in src buffer, starting from the bit #srcPos.
static void	orNotBits(long[] dest, long destPos, LongBuffer src, long srcPos, long count)	Replaces count bits, packed in dest array, starting from the bit #destPos, with the logical OR of them and inverted corresponding count bits, packed in src buffer, starting from the bit #srcPos.
static void	packBits(LongBuffer dest, long destPos, boolean[] src, int srcPos, int count)	Copies count bits from src array, starting from the element #srcPos, to packed dest buffer, starting from the bit #destPos.
static void	setBit(LongBuffer dest, long index, boolean value)	Sets the bit #index in the packed dest bit buffer.
static void	setBitNoSync(LongBuffer dest, long index, boolean value)	Sets the bit #index in the packed dest bit buffer without synchronization.
static void	swapBits(LongBuffer first, long firstPos, LongBuffer second, long secondPos, long count)	Swaps count bits, packed into first buffer, starting from the bit #firstPos, with count bits, packed into second buffer, starting from the bit #secondPos.
static void	unpackBits(boolean[] dest, int destPos, LongBuffer src, long srcPos, int count)	Copies count bits, packed into src buffer, starting from the bit #srcPos, to dest array, starting from the element #destPos.
static void	xorBits(long[] dest, long destPos, LongBuffer src, long srcPos, long count)	Replaces count bits, packed in dest array, starting from the bit #destPos, with the logical XOR of them and corresponding count bits, packed in src buffer, starting from the bit #srcPos.

Methods inherited from class java.lang.Object

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

Method Details

getLock

public static Object getLock(LongBuffer buffer)

Returns buffer.hasArray()?buffer.array():buffer. This object is used by all methods of this class for synchronization, when any portion (not all 64 bits) of some long element is modified. Synchronization by buffer.array() (instead of buffer instance) allows to use in different threads different instances of LongBuffer, created by LongBuffer.wrap method for the sampe Java long[] array.

Parameters:

buffer - the buffer.

Returns:

this buffer if it is not backed by a Java array, the underlying Java array if it is backed by it.

getBit

public static boolean getBit(LongBuffer src,
 long index)

Returns the bit #index in the packed src bit buffer. Equivalent to the following expression:

 (src.get((int)(index >>> 6)) & (1L << (index & 63))) != 0L;
 

Parameters:

src - the source buffer (bits are packed into long values).

index - index of the returned bit.

Returns:

the bit at the specified index.

Throws:

IndexOutOfBoundsException - if this method cause access of data outside buffer limits.

NullPointerException - if src is null.

setBit

public static void setBit(LongBuffer dest,
 long index,
 boolean value)

Sets the bit #index in the packed dest bit buffer. Equivalent to the following operators:

 synchronized (PackedBitBuffers.getLock(dest)) {
     if (value)
         dest.put((int)(index >>> 6),
             dest.get((int)(index >>> 6)) | 1L << (index & 63));
     else
         dest.put((int)(index >>> 6),
             dest.get((int)(index >>> 6)) & ~(1L << (index & 63)));
 }
 

Parameters:

dest - the destination buffer (bits are packed into long values).

index - index of the written bit.

value - new bit value.

Throws:

IndexOutOfBoundsException - if this method cause access of data outside array bounds.

NullPointerException - if dest is null.

setBitNoSync

public static void setBitNoSync(LongBuffer dest,
 long index,
 boolean value)

Sets the bit #index in the packed dest bit buffer without synchronization. May be used instead of setBit(LongBuffer, long, boolean), if you are not planning to call this method from different threads for the same dest array. Equivalent to the following operators:

     if (value)
         dest.put((int)(index >>> 6),
             dest.get((int)(index >>> 6)) | 1L << (index & 63));
     else
         dest.put((int)(index >>> 6),
             dest.get((int)(index >>> 6)) & ~(1L << (index & 63)));
 }
 

Parameters:

dest - the destination buffer (bits are packed into long values).

index - index of the written bit.

value - new bit value.

Throws:

IndexOutOfBoundsException - if this method cause access of data outside array bounds.

NullPointerException - if dest is null.

copyBits

public static void copyBits(LongBuffer dest,
 long destPos,
 LongBuffer src,
 long srcPos,
 long count)

Copies count bits, packed into src buffer, starting from the bit #srcPos, to packed dest buffer, starting from the bit #destPos.

This method works correctly even if src == dest and the copied areas overlap, i.e. if Math.abs(destPos - srcPos) < count. More precisely, in this case the copying is performed as if the bits at positions srcPos..srcPos+count-1 in src were first unpacked to a temporary boolean[] array with count elements and then the contents of the temporary array were packed into positions destPos..destPos+count-1 of dest.

Parameters:

dest - the destination LongBuffer (bits are packed into long values).

destPos - position of the first bit written in the destination buffer.

src - the source LongBuffer (bits are packed into long values).

srcPos - position of the first bit read in the source buffer.

count - the number of bits to be copied (must be >=0).

Throws:

IndexOutOfBoundsException - if copying would cause access of data outside buffer limits.

NullPointerException - if either src or dest is null.

copyBits

public static void copyBits(LongBuffer dest,
 long destPos,
 LongBuffer src,
 long srcPos,
 long count,
 boolean reverseOrder)

Copies count bits, packed into src buffer, starting from the bit #srcPos, to packed dest buffer, starting from the bit #destPos, in normal or reverse order depending on reverseOrder argument.

If reverseOrder flag is false, this method copies bits in normal order: bit #srcPos of src to bit #destPos of dest, then bit #srcPos+1 of src to bit #destPos+1 of dest, then bit #srcPos+2 of src to bit #destPos+2 of dest, ..., then bit #srcPos+count-1 of src to bit #destPos+count-1 of dest. If reverseOrder flag is true, this method copies bits in reverse order: bit #srcPos+count-1 of src to bit #destPos+count-1 of dest, then bit #srcPos+count-2 of src to bit #destPos+count-2 of dest, ..., then bit #srcPos of src to bit #destPos of dest. Usually, copying in reverse order is slower, but it is necessary if src and dest are the same buffer or views or the same data (for example, buffers mapped to the same file), the copied areas overlap and destination position is greater than source position. If src==dest, you may use copyBits(LongBuffer, long, LongBuffer, long, long) method that chooses the suitable order automatically.

Parameters:

dest - the destination LongBuffer (bits are packed into long values).

destPos - position of the first bit written in the destination buffer.

src - the source LongBuffer (bits are packed into long values).

srcPos - position of the first bit read in the source buffer.

count - the number of bits to be copied (must be >=0).

reverseOrder - if true, the bits will be copied in the reverse order.

Throws:

IndexOutOfBoundsException - if copying would cause access of data outside buffer limits.

NullPointerException - if either src or dest is null.

See Also:

• copyBits(LongBuffer, long, LongBuffer, long, long)

swapBits

public static void swapBits(LongBuffer first,
 long firstPos,
 LongBuffer second,
 long secondPos,
 long count)

Swaps count bits, packed into first buffer, starting from the bit #firstPos, with count bits, packed into second buffer, starting from the bit #secondPos.

Some bits may be swapped incorrectly if the swapped areas overlap, i.e. if first==second and Math.abs(firstIndex - secondIndex) < count, or if first and second are views of the same data (for example, buffers mapped to the same file) and the corresponding areas of this data overlap.

Parameters:

first - the first LongBuffer (bits are packed into long values).

firstPos - starting index of bit to exchange in the first LongBuffer.

second - the second LongBuffer (bits are packed into long values).

secondPos - starting index of bit to exchange in the second LongBuffer.

count - the number of bits to be exchanged (must be >=0).

Throws:

IndexOutOfBoundsException - if copying would cause access of data outside buffer limits.

NullPointerException - if either src or dest is null.

packBits

public static void packBits(LongBuffer dest,
 long destPos,
 boolean[] src,
 int srcPos,
 int count)

Copies count bits from src array, starting from the element #srcPos, to packed dest buffer, starting from the bit #destPos.

Parameters:

dest - the destination LongBuffer (bits are packed into long values).

destPos - position of the first bit written in the destination buffer.

src - the source array (unpacked boolean values).

srcPos - position of the first bit read in the source array.

count - the number of bits to be packed (must be >=0).

Throws:

IndexOutOfBoundsException - if copying would cause access of data outside array bounds or buffer limit.

NullPointerException - if either src or dest is null.

unpackBits

public static void unpackBits(boolean[] dest,
 int destPos,
 LongBuffer src,
 long srcPos,
 int count)

Copies count bits, packed into src buffer, starting from the bit #srcPos, to dest array, starting from the element #destPos.

Parameters:

dest - the destination array (unpacked boolean values).

destPos - position of the first bit written in the destination array.

src - the source LongBuffer (bits are packed into long values).

srcPos - position of the first bit read in the source buffer.

count - the number of bits to be unpacked (must be >=0).

Throws:

IndexOutOfBoundsException - if copying would cause access of data outside array bounds or buffer limit.

NullPointerException - if either src or dest is null.

fillBits

public static void fillBits(LongBuffer dest,
 long destPos,
 long count,
 boolean value)

Fills count bits in the packed dest buffer, starting from the bit #destPos, by the specified value. Be careful: the second int argument in this method is the number of filled element, but not the end filled index as in java.util.Arrays.fill methods.

Parameters:

dest - the destination LongBuffer (bits are packed into long values).

destPos - position of the first bit written in the destination buffer.

count - the number of bits to be filled (must be >=0).

value - new value of all filled bits (false means the bit 0, true means the bit 1).

Throws:

IndexOutOfBoundsException - if filling would cause access of data outside buffer limit.

NullPointerException - if dest is null.

notBits

public static void notBits(long[] dest,
 long destPos,
 LongBuffer src,
 long srcPos,
 long count)

Replaces count bits, packed in dest array, starting from the bit #destPos, with the logical NOT of corresponding count bits, packed in src buffer, starting from the bit #srcPos. The packed long[] Java array stores bits as described in PackedBitArrays class.

Parameters:

dest - the destination array (bits are packed in long values).

destPos - position of the first bit written in the destination array.

src - the source LongBuffer (bits are packed into long values).

srcPos - position of the first bit read in the source buffer.

count - the number of bits to be replaced (must be >=0).

Throws:

IndexOutOfBoundsException - if accessing bits would cause access of data outside array bounds.

NullPointerException - if either src or dest is null.

andBits

public static void andBits(long[] dest,
 long destPos,
 LongBuffer src,
 long srcPos,
 long count)

Replaces count bits, packed in dest array, starting from the bit #destPos, with the logical AND of them and corresponding count bits, packed in src buffer, starting from the bit #srcPos. The packed long[] Java array stores bits as described in PackedBitArrays class.

Parameters:

dest - the destination array (bits are packed in long values).

destPos - position of the first bit written in the destination array.

src - the source LongBuffer (bits are packed into long values).

srcPos - position of the first bit read in the source buffer.

count - the number of bits to be replaced (must be >=0).

Throws:

IndexOutOfBoundsException - if accessing bits would cause access of data outside array bounds.

NullPointerException - if either src or dest is null.

orBits

public static void orBits(long[] dest,
 long destPos,
 LongBuffer src,
 long srcPos,
 long count)

Replaces count bits, packed in dest array, starting from the bit #destPos, with the logical OR of them and corresponding count bits, packed in src buffer, starting from the bit #srcPos. The packed long[] Java array stores bits as described in PackedBitArrays class.

Parameters:

dest - the destination array (bits are packed in long values).

destPos - position of the first bit written in the destination array.

src - the source LongBuffer (bits are packed into long values).

srcPos - position of the first bit read in the source buffer.

count - the number of bits to be replaced (must be >=0).

Throws:

IndexOutOfBoundsException - if accessing bits would cause access of data outside array bounds.

NullPointerException - if either src or dest is null.

xorBits

public static void xorBits(long[] dest,
 long destPos,
 LongBuffer src,
 long srcPos,
 long count)

Replaces count bits, packed in dest array, starting from the bit #destPos, with the logical XOR of them and corresponding count bits, packed in src buffer, starting from the bit #srcPos. The packed long[] Java array stores bits as described in PackedBitArrays class.

Parameters:

dest - the destination array (bits are packed in long values).

destPos - position of the first bit written in the destination array.

src - the source LongBuffer (bits are packed into long values).

srcPos - position of the first bit read in the source buffer.

count - the number of bits to be replaced (must be >=0).

Throws:

IndexOutOfBoundsException - if accessing bits would cause access of data outside array bounds.

NullPointerException - if either src or dest is null.

andNotBits

public static void andNotBits(long[] dest,
 long destPos,
 LongBuffer src,
 long srcPos,
 long count)

Replaces count bits, packed in dest array, starting from the bit #destPos, with the logical AND of them and inverted corresponding count bits, packed in src buffer, starting from the bit #srcPos. The packed long[] Java array stores bits as described in PackedBitArrays class.

Parameters:

dest - the destination array (bits are packed in long values).

destPos - position of the first bit written in the destination array.

src - the source LongBuffer (bits are packed into long values).

srcPos - position of the first bit read in the source buffer.

count - the number of bits to be replaced (must be >=0).

Throws:

IndexOutOfBoundsException - if accessing bits would cause access of data outside array bounds.

NullPointerException - if either src or dest is null.

orNotBits

public static void orNotBits(long[] dest,
 long destPos,
 LongBuffer src,
 long srcPos,
 long count)

Replaces count bits, packed in dest array, starting from the bit #destPos, with the logical OR of them and inverted corresponding count bits, packed in src buffer, starting from the bit #srcPos. The packed long[] Java array stores bits as described in PackedBitArrays class.

Parameters:

dest - the destination array (bits are packed in long values).

destPos - position of the first bit written in the destination array.

src - the source LongBuffer (bits are packed into long values).

srcPos - position of the first bit read in the source buffer.

count - the number of bits to be replaced (must be >=0).

Throws:

IndexOutOfBoundsException - if accessing bits would cause access of data outside array bounds.

NullPointerException - if either src or dest is null.

indexOfBit

public static long indexOfBit(LongBuffer src,
 long lowIndex,
 long highIndex,
 boolean value)

Returns the minimal index k, so that lowIndex<=k<highIndex and the bit #k in the packed src bit buffer is equal to value, or -1 if there is no such bits.

If lowIndex>=highIndex, this method returns -1.

Parameters:

src - the searched packed bit buffer.

lowIndex - the low index for search (inclusive).

highIndex - the high index for search (exclusive).

value - the value of bit to be found.

Returns:

the index of the first occurrence of this bit in range lowIndex..highIndex-1, or -1 if this bit does not occur or if lowIndex>=highIndex.

Throws:

NullPointerException - if buffer is null.

IndexOutOfBoundsException - if lowIndex is negative or if highIndex is greater than src.limit()*64.

See Also:

• lastIndexOfBit(LongBuffer, long, long, boolean)

lastIndexOfBit

public static long lastIndexOfBit(LongBuffer src,
 long lowIndex,
 long highIndex,
 boolean value)

Returns the maximal index k, so that highIndex>k>=lowIndex and the bit #k in the packed src bit buffer is equal to value, or -1 if there is no such bits.

If highIndex<=lowIndex, this method returns -1.

Note that lowIndex and highIndex arguments have the same sense as in indexOfBit(LongBuffer, long, long, boolean) method: they describes the search index range lowIndex<=k<highIndex.

Parameters:

src - the searched packed bit buffer.

lowIndex - the low index in the array for search (inclusive); pass 0 to search all remaining elements.

highIndex - the high index in the array for search (exclusive).

value - the value of bit to be found.

Returns:

the index of the last occurrence of this bit in range lowIndex..highIndex-1, or -1 if this bit does not occur or if lowIndex>=highIndex.

Throws:

NullPointerException - if src is null.

IndexOutOfBoundsException - if lowIndex is negative or if highIndex is greater than src.length*64.

cardinality

public static long cardinality(LongBuffer src,
 long fromIndex,
 long toIndex)

Returns the number of high bits (1) in the given fragment of the given packed bit buffer.

Parameters:

src - the source packed bit buffer.

fromIndex - the initial checked bit index in src, inclusive.

toIndex - the end checked bit index in src, exclusive.

Returns:

the number of high bits (1) in the given fragment of the given packed bit buffer.

Throws:

NullPointerException - if the src argument is null.

IndexOutOfBoundsException - if fromIndex or toIndex are negative, if toIndex is greater than src.limit() * 64, or if fromIndex is greater than startIndex