Package io.deephaven.engine.rowset.impl.rsp.container

Class ContainerUtil

java.lang.Object
io.deephaven.engine.rowset.impl.rsp.container.ContainerUtil
public final class ContainerUtil extends Object
Various useful methods for roaring bitmaps.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static interface 
    ContainerUtil.TargetComparator
     

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final boolean
    USE_HYBRID_BINSEARCH
    optimization flag: whether to use hybrid binary search: hybrid formats combine a binary search with a sequential search

  • Method Summary

    Modifier and Type
    Method
    Description
    static int
    advanceUntil(short[] array, int pos, int length, short min)
    Find the smallest integer larger than pos such that array[pos]>= min.
    protected static int
    branchyUnsignedBinarySearch(short[] array, int begin, int end, short k)
     
    static int
    cardinalityInBitmapRange(long[] bitmap, int start, int end)
    Hamming weight of the bitset in the range start, start+1,..., end-1
    static int
    cardinalityInBitmapWordRange(long[] bitmap, int start, int end)
    Deprecated.
    static int
    compareUnsigned(short a, short b)
    Compares the two specified short values, treating them as unsigned values between 0 and 2^16 - 1 inclusive.
    static void
    fillArrayAND(short[] container, long[] bitmap1, long[] bitmap2)
    Compute the bitwise AND between two long arrays and write the set bits in the container.
    static void
    fillArrayANDNOT(short[] container, long[] bitmap1, long[] bitmap2)
    Compute the bitwise ANDNOT between two long arrays and write the set bits in the container.
    static void
    fillArrayXOR(short[] container, long[] bitmap1, long[] bitmap2)
    Compute the bitwise XOR between two long arrays and write the set bits in the container.
    static void
    flipBitmapRange(long[] bitmap, int start, int end)
    flip bits at start, start+1,..., end-1
    static int
    flipBitmapRangeAndCardinalityChange(long[] bitmap, int start, int end)
    Deprecated.
    protected static int
    hybridUnsignedBinarySearch(short[] array, int begin, int end, short k)
     
    static int
    iterateUntil(short[] array, int pos, int length, int min)
    Find the smallest integer larger than pos such that array[pos]>= min.
    protected static short
    lowbits(int x)
     
    protected static short
    lowbits(long x)
     
    static void
    partialRadixSort(int[] data)
    Sorts the data by the 16 bit prefix.
    static int
    rangeSearch(int begin, int end, ContainerUtil.TargetComparator comp)
    Look for the biggest value of i that satisfies begin <= i < end and comp.directionFrom(i) >= 0.
    static void
    resetBitmapRange(long[] bitmap, int start, int end)
    clear bits at start, start+1,..., end-1
    static int
    resetBitmapRangeAndCardinalityChange(long[] bitmap, int start, int end)
    Deprecated.
    static int
    search(short[] array, int begin, int end, ContainerUtil.TargetComparator comp)
    Search for the largest value in array such that comp.directionFrom(value) > 0, or any value such that comp.directionFrom(value) == 0, and return its index.
    static int
    select(long w, int j)
    Given a word w, return the position of the jth true bit.
    static void
    setBitmapRange(long[] bitmap, int start, int end)
    set bits at start, start+1,..., end-1
    static int
    setBitmapRangeAndCardinalityChange(long[] bitmap, int start, int end)
    Deprecated.
    protected static int
    toIntUnsigned(short x)
     
    static int
    unsignedBinarySearch(short[] array, int begin, int end, short k)
    Look for value k in array in the range [begin,end).
    static int
    unsignedDifference(short[] set1, int length1, short[] set2, int length2, short[] buffer)
    Compute the difference between two sorted lists and write the result to the provided output array
    static int
    unsignedDifference(ShortIterator set1, ShortIterator set2, short[] buffer)
    Compute the difference between two sorted lists and write the result to the provided output array
    static int
    unsignedExclusiveUnion2by2(short[] set1, int length1, short[] set2, int length2, short[] buffer)
    Compute the exclusive union of two sorted lists and write the result to the provided output array
    static int
    unsignedIntersect2by2(short[] set1, int length1, short[] set2, int length2, short[] buffer)
    Intersect two sorted lists and write the result to the provided output array
    static boolean
    unsignedIntersects(short[] set1, int length1, short[] set2, int length2)
    Checks if two arrays intersect
    protected static int
    unsignedLocalIntersect2by2(short[] set1, int length1, short[] set2, int length2, short[] buffer)
     
    static int
    unsignedLocalIntersect2by2Cardinality(short[] set1, int length1, short[] set2, int length2)
    Compute the cardinality of the intersection
    protected static int
    unsignedOneSidedGallopingIntersect2by2(short[] smallSet, int smallLength, short[] largeSet, int largeLength, short[] buffer)
     
    static int
    unsignedUnion2by2(short[] set1, int offset1, int length1, short[] set2, int offset2, int length2, short[] buffer)
    Unite two sorted lists and write the result to the provided output array

    Methods inherited from class java.lang.Object

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

  • Field Details

    • USE_HYBRID_BINSEARCH

      public static final boolean USE_HYBRID_BINSEARCH
      optimization flag: whether to use hybrid binary search: hybrid formats combine a binary search with a sequential search
      See Also:

  • Method Details

    • advanceUntil

      public static int advanceUntil(short[] array, int pos, int length, short min)
      Find the smallest integer larger than pos such that array[pos]>= min. If none can be found, return length. Based on code by O. Kaser.
      Parameters:
      array - array to search within
      pos - starting position of the search
      length - length of the array to search
      min - minimum value
      Returns:
      x greater than pos such that array[pos] is at least as large as min, pos is is equal to length if it is not possible.

    • iterateUntil

      public static int iterateUntil(short[] array, int pos, int length, int min)
      Find the smallest integer larger than pos such that array[pos]>= min. If none can be found, return length.
      Parameters:
      array - array to search within
      pos - starting position of the search
      length - length of the array to search
      min - minimum value
      Returns:
      x greater than pos such that array[pos] is at least as large as min, pos is is equal to length if it is not possible.

    • branchyUnsignedBinarySearch

      protected static int branchyUnsignedBinarySearch(short[] array, int begin, int end, short k)

    • search

      public static int search(short[] array, int begin, int end, ContainerUtil.TargetComparator comp)
      Search for the largest value in array such that comp.directionFrom(value) > 0, or any value such that comp.directionFrom(value) == 0, and return its index. If there is no such a value return -1.
      Parameters:
      array - Array with values sorted in increasing order.
      begin - Start position in the array for the search.
      end - One past the last position in the array for the search.
      comp - A comparator.
      Returns:
      -1 if comp.directionFrom(array[begin]) < 0, otherwise the biggest position pos in [begin, end - 1] such that comp.directionFrom(array[pos]) > 0 or, if there is a one or more positions pos for which comp.directionFrom(array[pos]) == 0, return any of them.

    • rangeSearch

      public static int rangeSearch(int begin, int end, ContainerUtil.TargetComparator comp)
      Look for the biggest value of i that satisfies begin <= i < end and comp.directionFrom(i) >= 0.
      Parameters:
      begin - The beginning of the range (inclusive)
      end - The end of the range (exclusive)
      comp - a TargetComparator.
      Returns:
      the last position i inside the provided range that satisfies comp.directionFrom(i) >= 0, or -1 if none does.

    • compareUnsigned

      public static int compareUnsigned(short a, short b)
      Compares the two specified short values, treating them as unsigned values between 0 and 2^16 - 1 inclusive.
      Parameters:
      a - the first unsigned short to compare
      b - the second unsigned short to compare
      Returns:
      a negative value if a is less than b; a positive value if a is greater than b; or zero if they are equal

    • fillArrayAND

      public static void fillArrayAND(short[] container, long[] bitmap1, long[] bitmap2)
      Compute the bitwise AND between two long arrays and write the set bits in the container.
      Parameters:
      container - where we write
      bitmap1 - first bitmap
      bitmap2 - second bitmap

    • fillArrayANDNOT

      public static void fillArrayANDNOT(short[] container, long[] bitmap1, long[] bitmap2)
      Compute the bitwise ANDNOT between two long arrays and write the set bits in the container.
      Parameters:
      container - where we write
      bitmap1 - first bitmap
      bitmap2 - second bitmap

    • fillArrayXOR

      public static void fillArrayXOR(short[] container, long[] bitmap1, long[] bitmap2)
      Compute the bitwise XOR between two long arrays and write the set bits in the container.
      Parameters:
      container - where we write
      bitmap1 - first bitmap
      bitmap2 - second bitmap

    • flipBitmapRange

      public static void flipBitmapRange(long[] bitmap, int start, int end)
      flip bits at start, start+1,..., end-1
      Parameters:
      bitmap - array of words to be modified
      start - first index to be modified (inclusive)
      end - last index to be modified (exclusive)

    • cardinalityInBitmapWordRange

      @Deprecated public static int cardinalityInBitmapWordRange(long[] bitmap, int start, int end)
      Deprecated.
      Hamming weight of the 64-bit words involved in the range start, start+1,..., end-1, that is, it will compute the cardinality of the bitset from index (floor(start/64) to floor((end-1)/64)) inclusively.
      Parameters:
      bitmap - array of words representing a bitset
      start - first index (inclusive)
      end - last index (exclusive)
      Returns:
      the hamming weight of the corresponding words

    • cardinalityInBitmapRange

      public static int cardinalityInBitmapRange(long[] bitmap, int start, int end)
      Hamming weight of the bitset in the range start, start+1,..., end-1
      Parameters:
      bitmap - array of words representing a bitset
      start - first index (inclusive)
      end - last index (exclusive)
      Returns:
      the hamming weight of the corresponding range

    • hybridUnsignedBinarySearch

      protected static int hybridUnsignedBinarySearch(short[] array, int begin, int end, short k)

    • lowbits

      protected static short lowbits(int x)

    • lowbits

      protected static short lowbits(long x)

    • resetBitmapRange

      public static void resetBitmapRange(long[] bitmap, int start, int end)
      clear bits at start, start+1,..., end-1
      Parameters:
      bitmap - array of words to be modified
      start - first index to be modified (inclusive)
      end - last index to be modified (exclusive)

    • select

      public static int select(long w, int j)
      Given a word w, return the position of the jth true bit.
      Parameters:
      w - word
      j - index
      Returns:
      position of jth true bit in w

    • setBitmapRange

      public static void setBitmapRange(long[] bitmap, int start, int end)
      set bits at start, start+1,..., end-1
      Parameters:
      bitmap - array of words to be modified
      start - first index to be modified (inclusive)
      end - last index to be modified (exclusive)

    • setBitmapRangeAndCardinalityChange

      @Deprecated public static int setBitmapRangeAndCardinalityChange(long[] bitmap, int start, int end)
      Deprecated.
      set bits at start, start+1,..., end-1 and report the cardinality change
      Parameters:
      bitmap - array of words to be modified
      start - first index to be modified (inclusive)
      end - last index to be modified (exclusive)
      Returns:
      cardinality change

    • flipBitmapRangeAndCardinalityChange

      @Deprecated public static int flipBitmapRangeAndCardinalityChange(long[] bitmap, int start, int end)
      Deprecated.
      flip bits at start, start+1,..., end-1 and report the cardinality change
      Parameters:
      bitmap - array of words to be modified
      start - first index to be modified (inclusive)
      end - last index to be modified (exclusive)
      Returns:
      cardinality change

    • resetBitmapRangeAndCardinalityChange

      @Deprecated public static int resetBitmapRangeAndCardinalityChange(long[] bitmap, int start, int end)
      Deprecated.
      reset bits at start, start+1,..., end-1 and report the cardinality change
      Parameters:
      bitmap - array of words to be modified
      start - first index to be modified (inclusive)
      end - last index to be modified (exclusive)
      Returns:
      cardinality change

    • toIntUnsigned

      protected static int toIntUnsigned(short x)

    • unsignedBinarySearch

      public static int unsignedBinarySearch(short[] array, int begin, int end, short k)
      Look for value k in array in the range [begin,end). If the value is found, return its index. If not, return -(i+1) where i is the index where the value would be inserted. The array is assumed to contain sorted values where shorts are interpreted as unsigned integers.
      Parameters:
      array - array where we search
      begin - first index (inclusive)
      end - last index (exclusive)
      k - value we search for
      Returns:
      count

    • unsignedDifference

      public static int unsignedDifference(short[] set1, int length1, short[] set2, int length2, short[] buffer)
      Compute the difference between two sorted lists and write the result to the provided output array
      Parameters:
      set1 - first array
      length1 - length of first array
      set2 - second array
      length2 - length of second array
      buffer - output array
      Returns:
      cardinality of the difference

    • unsignedDifference

      public static int unsignedDifference(ShortIterator set1, ShortIterator set2, short[] buffer)
      Compute the difference between two sorted lists and write the result to the provided output array
      Parameters:
      set1 - first array
      set2 - second array
      buffer - output array
      Returns:
      cardinality of the difference

    • unsignedExclusiveUnion2by2

      public static int unsignedExclusiveUnion2by2(short[] set1, int length1, short[] set2, int length2, short[] buffer)
      Compute the exclusive union of two sorted lists and write the result to the provided output array
      Parameters:
      set1 - first array
      length1 - length of first array
      set2 - second array
      length2 - length of second array
      buffer - output array
      Returns:
      cardinality of the exclusive union

    • unsignedIntersect2by2

      public static int unsignedIntersect2by2(short[] set1, int length1, short[] set2, int length2, short[] buffer)
      Intersect two sorted lists and write the result to the provided output array
      Parameters:
      set1 - first array
      length1 - length of first array
      set2 - second array
      length2 - length of second array
      buffer - output array
      Returns:
      cardinality of the intersection

    • unsignedIntersects

      public static boolean unsignedIntersects(short[] set1, int length1, short[] set2, int length2)
      Checks if two arrays intersect
      Parameters:
      set1 - first array
      length1 - length of first array
      set2 - second array
      length2 - length of second array
      Returns:
      true if they intersect

    • unsignedLocalIntersect2by2

      protected static int unsignedLocalIntersect2by2(short[] set1, int length1, short[] set2, int length2, short[] buffer)

    • unsignedLocalIntersect2by2Cardinality

      public static int unsignedLocalIntersect2by2Cardinality(short[] set1, int length1, short[] set2, int length2)
      Compute the cardinality of the intersection
      Parameters:
      set1 - first set
      length1 - how many values to consider in the first set
      set2 - second set
      length2 - how many values to consider in the second set
      Returns:
      cardinality of the intersection

    • unsignedOneSidedGallopingIntersect2by2

      protected static int unsignedOneSidedGallopingIntersect2by2(short[] smallSet, int smallLength, short[] largeSet, int largeLength, short[] buffer)

    • unsignedUnion2by2

      public static int unsignedUnion2by2(short[] set1, int offset1, int length1, short[] set2, int offset2, int length2, short[] buffer)
      Unite two sorted lists and write the result to the provided output array
      Parameters:
      set1 - first array
      offset1 - offset of first array
      length1 - length of first array
      set2 - second array
      offset2 - offset of second array
      length2 - length of second array
      buffer - output array
      Returns:
      cardinality of the union

    • partialRadixSort

      public static void partialRadixSort(int[] data)
      Sorts the data by the 16 bit prefix.
      Parameters:
      data - - the data