Package net.algart.arrays

Interface BitArray

All Superinterfaces:
Array, PArray, PFixedArray
All Known Subinterfaces:
MutableBitArray, UpdatableBitArray
All Known Implementing Classes:
AbstractBitArray, AbstractUpdatableBitArray
public interface BitArray extends PFixedArray

AlgART array of boolean values, read-only access.

Author:
Daniel Alievsky

  • Method Details

    • type

      Class<? extends BitArray> type()
      Description copied from interface: Array
      Returns the canonical AlgART type of this array: the class of one of 9 basic interfaces, describing all kinds of AlgART arrays for 8 primitive and any non-primitive element types. More precisely, returns:

      There is a guarantee that this method works very quickly (usually it just returns a constant value).

      Specified by:
      type in interface Array
      Specified by:
      type in interface PArray
      Returns:
      canonical AlgART type of this array.

    • updatableType

      Class<? extends UpdatableBitArray> updatableType()
      Description copied from interface: Array
      Returns the canonical updatable AlgART type of arrays with the same element types: the class of one of 9 basic interfaces, describing all kinds of updatable AlgART arrays for 8 primitive and any non-primitive element types. More precisely, returns:

      There is a guarantee that this method works very quickly (usually it just returns a constant value).

      Specified by:
      updatableType in interface Array
      Specified by:
      updatableType in interface PArray
      Returns:
      canonical AlgART type of an updatable array of the same kind.

    • mutableType

      Class<? extends MutableBitArray> mutableType()
      Description copied from interface: Array
      Returns the canonical resizable AlgART type of arrays with the same element types: the class of one of 9 basic interfaces, describing all kinds of resizable AlgART arrays for 8 primitive and any non-primitive element types. More precisely, returns:

      There is a guarantee that this method works very quickly (usually it just returns a constant value).

      Specified by:
      mutableType in interface Array
      Specified by:
      mutableType in interface PArray
      Returns:
      canonical AlgART type of a resizable array of the same kind.

    • getBit

      boolean getBit(long index)
      Returns the element #index.
      Parameters:
      index - index of element to get.
      Returns:
      the element at the specified position in this array.
      Throws:
      IndexOutOfBoundsException - if index is out of range 0..length()-1.

    • indexOf

      long indexOf(long lowIndex, long highIndex, boolean value)
      Returns the minimal index k, so that lowIndex<=k<min(highIndex,thisArray.length()) and getBit(k)==value, or -1 if there is no such array element.

      In particular, if lowIndex>=thisArray.length()} or lowIndex>=highIndex, this method returns -1, and if lowIndex<0, the result is the same as if lowIndex==0.

      You may specify lowIndex=0 and highIndex=Long.MAX_VALUE to search through all array elements.

      Parameters:
      lowIndex - the low index in the array for search (inclusive).
      highIndex - the high index in the array for search (exclusive).
      value - the value to be found.
      Returns:
      the index of the first occurrence of this value in this array in range lowIndex<=index<highIndex, or -1 if this value does not occur in this range.

    • lastIndexOf

      long lastIndexOf(long lowIndex, long highIndex, boolean value)
      Returns the maximal index k, so that highIndex>k>=max(lowIndex,0) and getBit(k)==value, or -1 if there is no such array element.

      In particular, if highIndex<=0 or highIndex<=lowIndex, this method returns -1, and if highIndex>=thisArray.length(), the result is the same as if highIndex==thisArray.length().

      You may specify lowIndex=0 and highIndex=Long.MAX_VALUE to search through all array elements.

      Parameters:
      lowIndex - the low index in the array for search (inclusive).
      highIndex - the high index in the array for search (exclusive).
      value - the value to be found.
      Returns:
      the index of the last occurrence of this value in this array in range lowIndex<=index<highIndex, or -1 if this value does not occur in this range.

    • buffer

      DataBitBuffer buffer(DataBuffer.AccessMode mode, long capacity)
      Description copied from interface: Array
      Returns a data buffer allowing block access to this array with the specified access mode and buffer capacity.

      If this array does not implement UpdatableArray interface (so, it is probably immutable or trusted immutable), the mode argument must be DataBuffer.AccessMode.READ.

      The capacity argument must be in range 0..237-1 for bit arrays or 0..231-1 for all other element types.

      If the capacity argument is greater than this array Array.length(), it is truncated to this length.

      Specified by:
      buffer in interface Array
      Parameters:
      mode - the access mode for new buffer.
      capacity - the capacity of the buffer.
      Returns:
      new data buffer for accessing this array.
      See Also:

    • buffer

      DataBitBuffer buffer(DataBuffer.AccessMode mode)
      Description copied from interface: Array
      Equivalent to buffer(mode, someCapacity), where mode is the argument of this method and someCapacity is chosen automatically to provide good performance in typical situations. Usually, the capacity is chosen to get a buffer occupying several kilobytes, that can fit in an internal cache of most processors.

      In any case, you can be sure that the chosen capacity will not be greater than Integer.MAX_VALUE-64.

      Specified by:
      buffer in interface Array
      Parameters:
      mode - the access mode for new buffer.
      Returns:
      new data buffer for accessing this array.

    • buffer

      DataBitBuffer buffer(long capacity)
      Description copied from interface: Array
      Equivalent to buffer(suitableMode, capacity), where capacity is the argument of this method and suitableMode is chosen automatically. Namely, suitableMode is:
      Specified by:
      buffer in interface Array
      Parameters:
      capacity - the capacity of the buffer.
      Returns:
      new data buffer for accessing this array.

    • buffer

      DataBitBuffer buffer()
      Description copied from interface: Array
      Equivalent to buffer(suitableMode, someCapacity), where both suitableMode and someCapacity arguments are chosen automatically. The algorithm of choosing these arguments is the same as for Array.buffer(net.algart.arrays.DataBuffer.AccessMode) and Array.buffer(long) methods.

      In any case, you can be sure that the chosen capacity will not be greater than Integer.MAX_VALUE-64.

      Specified by:
      buffer in interface Array
      Returns:
      new data buffer for accessing this array.

    • asImmutable

      BitArray asImmutable()
      Description copied from interface: Array
      Returns an immutable view of this array. If this array is already immutable (i.e. Array.isImmutable() is true), returns a reference to this object.

      A array is considered to be immutable, if there are no ways to modify its content or state with help of this instance. In particular, immutable arrays never implement UpdatableArray or DirectAccessible interfaces. Moreover, any third-party implementation of Array interface must return an instance of a class, which has no methods or fields allowing to change this instance.

      Query operations on the returned array "read through" to this array. The returned view is also unresizable (see UpdatableArray.asUnresizable()).

      The returned view (when it is not a reference to this object) contains the same elements as this array, but independent length, start offset, capacity, copy-on-next-write and possible other information about array characteristics besides its elements, as for Array.shallowClone() method. If modifications of this array characteristics lead to reallocation of the internal storage, then the returned array ceases to be a view of this array. The only possible reasons for reallocation are the following: calling MutableArray.length(long), MutableArray.ensureCapacity(long) or MutableArray.trim() methods for this array, or any modification of this or returned array in a case when this array is copy-on-next-write.

      By default, the array factories (memory models) create mutable arrays, but they can be converted to immutable by this method.

      Note: Array.isNew() method, called for the result of this method, always returns false — because it does not implement UpdatableArray.

      Also note: Array.isNewReadOnlyView() method, called for the result of this method, always returns the same value as Array.isNewReadOnlyView() for this object. Really,

      Specified by:
      asImmutable in interface Array
      Specified by:
      asImmutable in interface PArray
      Specified by:
      asImmutable in interface PFixedArray
      Returns:
      an immutable view of this array (or a reference to this array if it is already immutable).
      See Also:

    • asTrustedImmutable

      BitArray asTrustedImmutable()
      Description copied from interface: Array
      Returns a trusted immutable view of this array. If this array is already trusted immutable, returns a reference to this object.

      A array is considered to be "trusted" immutable, if it potentially can change its elements, but the Java code working with this array promises that it will not change them. The returned instance never implements UpdatableArray, but may implement DirectAccessible, that allow quick access to its elements. As for usual immutable view, query operations on the returned array "read through" to this array.

      The only standard way allowing to change elements of returned array is using DirectAccessible.javaArray() method, in a case when the array is backed by an accessible array. But the Java code, processing the trusted immutable array, must use this method only for quick reading elements and not try to change them. If, despite the promise, the elements of the trusted immutable array will be changed, the UnallowedMutationError may be thrown by the call of Array.checkUnallowedMutation() method.

      In some implementations — for example, if DirectAccessible interface is not supported by this array — this method may return the same result as Array.asImmutable().

      The returned view is always unresizable.

      The returned view (when it is not a reference to this object) contains the same elements as this array, but independent length, start offset, capacity, copy-on-next-write and possible other information about array characteristics besides its elements, as for Array.shallowClone() method. If modifications of this array characteristics lead to reallocation of the internal storage, then the returned array ceases to be a view of this array. The only possible reasons for reallocation are the following: calling MutableArray.length(long), MutableArray.ensureCapacity(long) or MutableArray.trim() methods for this array, or any modification of this or returned array in a case when this array is copy-on-next-write.

      Trusted immutable view is a compromise between absolute safety, provided by usual immutable view, and maximal efficiency, achieved while using the original non-protected array. Please see the package description to learn more about possible usage of this method.

      Specified by:
      asTrustedImmutable in interface Array
      Specified by:
      asTrustedImmutable in interface PArray
      Specified by:
      asTrustedImmutable in interface PFixedArray
      Returns:
      a trusted immutable view of this array (or a reference to this array if it is already trusted immutable).
      See Also:

    • mutableClone

      MutableBitArray mutableClone(MemoryModel memoryModel)
      Description copied from interface: Array
      Returns a mutable resizable copy of this array. This method is equivalent to the following code: 
       memoryModel.newArray(thisArray).copy(thisArray);

      Please note: this method is a good choice for cloning little arrays (thousands, maybe millions elements). If you clone large arrays by this method, the user, in particular, has no ways to view the progress of copying or to interrupt copying. To clone large arrays, we recommend the following code: 

       MutableArray clone = memoryModel.newArray(thisArray);
 Arrays.copy(someContext, clone, a);
      Specified by:
      mutableClone in interface Array
      Specified by:
      mutableClone in interface PArray
      Specified by:
      mutableClone in interface PFixedArray
      Parameters:
      memoryModel - the memory model, used for allocation a new copy of this array.
      Returns:
      a mutable copy of this array.
      See Also:

    • updatableClone

      UpdatableBitArray updatableClone(MemoryModel memoryModel)
      Description copied from interface: Array
      Returns an unresizable updatable copy of this array. This method is equivalent to the following code: 
       memoryModel.newUnresizableArray(thisArray).copy(thisArray);

      Please note: this method is a good choice for cloning little arrays (thousands, maybe millions elements). If you clone large arrays by this method, the user, in particular, has no ways to view the progress of copying or to interrupt copying. To clone large arrays, we recommend the following code: 

       UpdatableArray clone = memoryModel.newUnresizableArray(thisArray);
 Arrays.copy(someContext, clone, a);
      Specified by:
      updatableClone in interface Array
      Specified by:
      updatableClone in interface PArray
      Specified by:
      updatableClone in interface PFixedArray
      Parameters:
      memoryModel - the memory model, used for allocation a new copy of this array.
      Returns:
      an updatable copy of this array.
      See Also:

    • ja

      boolean[] ja()
      Description copied from interface: Array
      Returns the underlying Java array ja, if this AlgART array is its wrapper (see Arrays.isJavaArrayWrapper(Array)); otherwise returns Arrays.toJavaArray(thisObject) in other case.

      In other words, this method returns a Java-array, absolutely identical to this AlgART array — having identical length and elements, — and does this as quickly as possible (unlike Arrays.toJavaArray(Array), which always copies the data).

      This method is equivalent to the following operators:

           thisObject instanceof DirectAccessible da &&
                 da.hasJavaArray() &&
                 da.javaArrayOffset() == 0 &&
                 java.lang.reflect.Array.getLength(da.javaArray()) == thisObject.length() ?
                 da.javaArray() :
                 Arrays.toJavaArray(this);

      but works little faster if the first case, "da.javaArray()", is selected (this is a wrapper).

      There are overridden versions of this method in subinterfaces for specific element types: ja(), CharArray.ja()}, ByteArray.ja()}, ShortArray.ja()}, IntArray.ja()}, LongArray.ja()}, FloatArray.ja()}, DoubleArray.ja()}, ObjectArray.ja()}.

      Be careful: this method is potentially unsafe! The main purpose of this method is to quickly access array data for reading. But it also allows you to modify this data, and the result of such modification is unpredictable: this may change the original AlgART array, but may also not change. Typically you should not attempt to modify the Java array returned by this method; this helps to avoid difficult bugs.

      Note that usually you should prefer methods of DirectAccessible interface instead of this method, because that interface allows to quickly process sub-arrays with non-zero start offsets and mutable arrays, for which the length of underlying Java array (capacity) is usually greater than the actual AlgART array length. But if you are sure that your array is created by SimpleMemoryModel and is not a sub-array, this method provides the simplest way to receive an identical Java array maximally quickly.

      Specified by:
      ja in interface Array
      Returns:
      Java array, equivalent to this AlgART array.
      See Also:

    • matrix

      default Matrix<? extends BitArray> matrix(long... dim)
      Description copied from interface: Array
      Equivalent to matrix(thisArray, dim).
      Specified by:
      matrix in interface Array
      Specified by:
      matrix in interface PArray
      Specified by:
      matrix in interface PFixedArray
      Parameters:
      dim - the matrix dimensions.
      Returns:
      new matrix backed by array with the given dimensions.

    • getInt

      int getInt(long index)
      Equivalent to getBit() ? 1 : 0.

      Note that this method is already declared in PFixedArray. It is redeclared here only for documentation and code search purposes.

      Specified by:
      getInt in interface PFixedArray
      Parameters:
      index - index of element to get.
      Returns:
      the element at the specified position in this array.
      Throws:
      IndexOutOfBoundsException - if index out of range 0..length()-1.
      See Also:

    • getBits

      void getBits(long arrayPos, long[] destArray, long destArrayOffset, long count)
      Copies count bits of this array, starting from arrayPos index, into the specified packed bit array, starting from destArrayOffset index.

      This method is equivalent to the following loop:

       for (long k = 0; k < count; k++)
     PackedBitArrays.setBit(destArray, destArrayOffset + k, thisArray.getBit(arrayPos + k);

      Note: if IndexOutOfBoundsException occurs due to attempt to write data outside the passed Java array, the target Java array can be partially filled. In other words, this method can be non-atomic regarding this failure. All other possible exceptions are checked in the very beginning of this method before any other actions (the standard way for checking exceptions).

      Parameters:
      arrayPos - starting position in this AlgART array.
      destArray - the target packed bit array.
      destArrayOffset - starting position in the target packed bit array.
      count - the number of bits to be copied.
      Throws:
      NullPointerException - if destArray argument is null.
      IndexOutOfBoundsException - if copying would cause access of data outside this array or target Java array.
      See Also:

    • nextQuickPosition

      long nextQuickPosition(long position)
      Returns the minimal pos >= max(position,0), for which the calls getBits(pos, destArray, 0, someCount) and (for updatable array) setBits(pos, srcArray, 0, someCount) work essentially faster than for most of other ("slow") positions, or -1 if there is no such position, in particular, if position>=length().

      These calls perform copying bits to / from a bit array (with zero offset), where the bits are packed into usual Java long[] array. For many implementations of this interface, in particular, for AlgART bit arrays created by all simple, buffer and large memory models, it means copying bits between internal packed representation and Java long[]array. If the bit index "position" corresponds to a beginning of some packed portion of such representation (usually long value), in other words, if the position is aligned, then the copying may be performed quickly: it is just copying a sequence of long values. In other case, the copying requires bit shift of long values. This method returns the nearest aligned position, starting from the passed index, for such AlgART bit arrays.

      In common case, when you call getBits(pos, destArray, arrayOffset, someCount) and (for updatable array) setBits(pos, srcArray, arrayOffset, someCount) with any (non-zero) arrayOffset, you may suppose that these calls are quick, for most implementations, when pos=qp+arrayOffset±64*j, where qp!=-1 is the result of this method for the given position and j=0,1,2,... is any integer.

      This method may return -1 in some cases: it means that there are no preferred indexes in the bit array, at least, after the passed index position. (For example, -1 is usually returned for any position argument in "lazy" arrays, created by Arrays.asFuncArray and similar methods.) In other case, the returned value is usually in a range position..position+63.

      Important note: if this method returns -1 for the argument position=0, it means that getBits method never (or almost never) work faster than getData for any positions in this bit array. Moreover, if nextQuickPosition(0)==-1, then getBits, as well as the standard data buffer, probably works slower than getData. In this situation, it's good idea to choose the algorithm branch based on getData and processing boolean[] arrays.

      For arrays, created by Arrays.nBitCopies(long, boolean) method, this method just returns max(position,0) (or -1 if position>=length()): all positions are good enough in such arrays.

      For negative position argument this method returns the same result as for position=0.

      Parameters:
      position - some index inside this bit array.
      Returns:
      the minimal "quick" (usually "aligned") position starting from this index.
      See Also:

    • as

      static UpdatableBitArray as(long[] packedBitArray, long length)
      Equivalent to SimpleMemoryModel.asUpdatableBitArray(packedBitArray, length).
      Parameters:
      packedBitArray - the source long[]> array.
      length - the length of the returned bit array.
      Returns:
      an unresizable AlgART bit array backed by the specified Java array.
      Throws:
      NullPointerException - if array argument is null.
      IllegalArgumentException - if length<0 or if the passed array is too short to store length bits (i.e. if array.length < (length+63)/64).