Class EWAHCompressedBitmap

    • Field Detail

      • usetrailingzeros

        public static final boolean usetrailingzeros
        optimization option
        See Also:
        Constant Field Values
      • adjustContainerSizeWhenAggregating

        public static final boolean adjustContainerSizeWhenAggregating
        whether we adjust after some aggregation by adding in zeroes
        See Also:
        Constant Field Values
      • wordinbits

        public static final int wordinbits
        The Constant wordinbits represents the number of bits in a long.
        See Also:
        Constant Field Values
    • Constructor Detail

      • EWAHCompressedBitmap

        public EWAHCompressedBitmap()
        Creates an empty bitmap (no bit set to true).
      • EWAHCompressedBitmap

        public EWAHCompressedBitmap​(int buffersize)
        Sets explicitly the buffer size (in 64-bit words). The initial memory usage will be "buffersize * 64". For large poorly compressible bitmaps, using large values may improve performance.
        Parameters:
        buffersize - number of 64-bit words reserved when the object is created)
    • Method Detail

      • add

        public void add​(long newdata)
        Adding words directly to the bitmap (for expert use). This is normally how you add data to the array. So you add bits in streams of 8*8 bits. Example: if you add 321, you are have added (in binary notation) 0b101000001, so you have effectively called set(0), set(6), set(8) in sequence.
        Specified by:
        add in interface BitmapStorage
        Parameters:
        newdata - the word
      • add

        public void add​(long newdata,
                        int bitsthatmatter)
        Adding words directly to the bitmap (for expert use).
        Parameters:
        newdata - the word
        bitsthatmatter - the number of significant bits (by default it should be 64)
      • addStreamOfLiteralWords

        public void addStreamOfLiteralWords​(long[] data,
                                            int start,
                                            int number)
        if you have several literal words to copy over, this might be faster.
        Specified by:
        addStreamOfLiteralWords in interface BitmapStorage
        Parameters:
        data - the literal words
        start - the starting point in the array
        number - the number of literal words to add
      • addStreamOfEmptyWords

        public void addStreamOfEmptyWords​(boolean v,
                                          long number)
        For experts: You want to add many zeroes or ones? This is the method you use.
        Specified by:
        addStreamOfEmptyWords in interface BitmapStorage
        Parameters:
        v - the boolean value
        number - the number
      • addStreamOfNegatedLiteralWords

        public void addStreamOfNegatedLiteralWords​(long[] data,
                                                   int start,
                                                   int number)
        Same as addStreamOfLiteralWords, but the words are negated.
        Specified by:
        addStreamOfNegatedLiteralWords in interface BitmapStorage
        Parameters:
        data - the literal words
        start - the starting point in the array
        number - the number of literal words to add
      • and

        public EWAHCompressedBitmap and​(EWAHCompressedBitmap a)
        Returns a new compressed bitmap containing the bitwise AND values of the current bitmap with some other bitmap. The running time is proportional to the sum of the compressed sizes (as reported by sizeInBytes()). If you are not planning on adding to the resulting bitmap, you may call the trim() method to reduce memory usage.
        Specified by:
        and in interface LogicalElement<EWAHCompressedBitmap>
        Parameters:
        a - the other bitmap
        Returns:
        the EWAH compressed bitmap
        Since:
        0.4.3
      • andToContainer

        public void andToContainer​(EWAHCompressedBitmap a,
                                   BitmapStorage container)
        Computes new compressed bitmap containing the bitwise AND values of the current bitmap with some other bitmap. The running time is proportional to the sum of the compressed sizes (as reported by sizeInBytes()).
        Parameters:
        a - the other bitmap
        container - where we store the result
        Since:
        0.4.0
      • andCardinality

        public int andCardinality​(EWAHCompressedBitmap a)
        Returns the cardinality of the result of a bitwise AND of the values of the current bitmap with some other bitmap. Avoids needing to allocate an intermediate bitmap to hold the result of the OR.
        Parameters:
        a - the other bitmap
        Returns:
        the cardinality
        Since:
        0.4.0
      • andNot

        public EWAHCompressedBitmap andNot​(EWAHCompressedBitmap a)
        Returns a new compressed bitmap containing the bitwise AND NOT values of the current bitmap with some other bitmap. The running time is proportional to the sum of the compressed sizes (as reported by sizeInBytes()). If you are not planning on adding to the resulting bitmap, you may call the trim() method to reduce memory usage.
        Specified by:
        andNot in interface LogicalElement<EWAHCompressedBitmap>
        Parameters:
        a - the other bitmap
        Returns:
        the EWAH compressed bitmap
      • andNotToContainer

        public void andNotToContainer​(EWAHCompressedBitmap a,
                                      BitmapStorage container)
        Returns a new compressed bitmap containing the bitwise AND NOT values of the current bitmap with some other bitmap. This method is expected to be faster than doing A.and(B.clone().not()). The running time is proportional to the sum of the compressed sizes (as reported by sizeInBytes()).
        Parameters:
        a - the other bitmap
        container - where to store the result
        Since:
        0.4.0
      • andNotCardinality

        public int andNotCardinality​(EWAHCompressedBitmap a)
        Returns the cardinality of the result of a bitwise AND NOT of the values of the current bitmap with some other bitmap. Avoids needing to allocate an intermediate bitmap to hold the result of the OR.
        Parameters:
        a - the other bitmap
        Returns:
        the cardinality
        Since:
        0.4.0
      • cardinality

        public int cardinality()
        reports the number of bits set to true. Running time is proportional to compressed size (as reported by sizeInBytes).
        Returns:
        the number of bits set to true
      • clear

        public void clear()
        Clear any set bits and set size in bits back to 0
      • clone

        public EWAHCompressedBitmap clone()
                                   throws java.lang.CloneNotSupportedException
        Overrides:
        clone in class java.lang.Object
        Throws:
        java.lang.CloneNotSupportedException
      • deserialize

        public void deserialize​(java.io.DataInput in)
                         throws java.io.IOException
        Deserialize.
        Parameters:
        in - the DataInput stream
        Throws:
        java.io.IOException - Signals that an I/O exception has occurred.
      • equals

        public boolean equals​(java.lang.Object o)
        Check to see whether the two compressed bitmaps contain the same set bits.
        Overrides:
        equals in class java.lang.Object
        See Also:
        Object.equals(java.lang.Object)
      • getEWAHIterator

        public EWAHIterator getEWAHIterator()
        Gets an EWAHIterator over the data. This is a customized iterator which iterates over run length word. For experts only.
        Returns:
        the EWAHIterator
      • getIteratingRLW

        public IteratingRLW getIteratingRLW()
        Returns:
        the IteratingRLW iterator corresponding to this bitmap
      • getPositions

        public java.util.List<java.lang.Integer> getPositions()
        get the locations of the true values as one vector. (may use more memory than iterator())
        Returns:
        the positions
      • hashCode

        public int hashCode()
        Returns a customized hash code (based on Karp-Rabin). Naturally, if the bitmaps are equal, they will hash to the same value.
        Overrides:
        hashCode in class java.lang.Object
      • intersects

        public boolean intersects​(EWAHCompressedBitmap a)
        Return true if the two EWAHCompressedBitmap have both at least one true bit in the same position. Equivalently, you could call "and" and check whether there is a set bit, but intersects will run faster if you don't need the result of the "and" operation.
        Parameters:
        a - the other bitmap
        Returns:
        whether they intersect
        Since:
        0.3.2
      • intIterator

        public IntIterator intIterator()
        Iterator over the set bits (this is what most people will want to use to browse the content if they want an iterator). The location of the set bits is returned, in increasing order.
        Returns:
        the int iterator
      • iterator

        public java.util.Iterator<java.lang.Integer> iterator()
        iterate over the positions of the true values. This is similar to intIterator(), but it uses Java generics.
        Specified by:
        iterator in interface java.lang.Iterable<java.lang.Integer>
        Returns:
        the iterator
      • not

        public void not()
        Negate (bitwise) the current bitmap. To get a negated copy, do EWAHCompressedBitmap x= ((EWAHCompressedBitmap) mybitmap.clone()); x.not(); The running time is proportional to the compressed size (as reported by sizeInBytes()).
        Specified by:
        not in interface LogicalElement<EWAHCompressedBitmap>
      • or

        public EWAHCompressedBitmap or​(EWAHCompressedBitmap a)
        Returns a new compressed bitmap containing the bitwise OR values of the current bitmap with some other bitmap. The running time is proportional to the sum of the compressed sizes (as reported by sizeInBytes()). If you are not planning on adding to the resulting bitmap, you may call the trim() method to reduce memory usage.
        Specified by:
        or in interface LogicalElement<EWAHCompressedBitmap>
        Parameters:
        a - the other bitmap
        Returns:
        the EWAH compressed bitmap
      • orToContainer

        public void orToContainer​(EWAHCompressedBitmap a,
                                  BitmapStorage container)
        Computes the bitwise or between the current bitmap and the bitmap "a". Stores the result in the container.
        Parameters:
        a - the other bitmap
        container - where we store the result
        Since:
        0.4.0
      • orCardinality

        public int orCardinality​(EWAHCompressedBitmap a)
        Returns the cardinality of the result of a bitwise OR of the values of the current bitmap with some other bitmap. Avoids needing to allocate an intermediate bitmap to hold the result of the OR.
        Parameters:
        a - the other bitmap
        Returns:
        the cardinality
        Since:
        0.4.0
      • readExternal

        public void readExternal​(java.io.ObjectInput in)
                          throws java.io.IOException
        Specified by:
        readExternal in interface java.io.Externalizable
        Throws:
        java.io.IOException
      • serialize

        public void serialize​(java.io.DataOutput out)
                       throws java.io.IOException
        Serialize.
        Parameters:
        out - the DataOutput stream
        Throws:
        java.io.IOException - Signals that an I/O exception has occurred.
      • serializedSizeInBytes

        public int serializedSizeInBytes()
        Report the size required to serialize this bitmap
        Returns:
        the size in bytes
      • get

        public boolean get​(int i)
        Query the value of a single bit. Relying on this method when speed is needed is discouraged. The complexity is linear with the size of the bitmap. (This implementation is based on zhenjl's Go version of JavaEWAH.)
        Parameters:
        i - the bit we are interested in
        Returns:
        whether the bit is set to true
      • set

        public boolean set​(int i)
        Set the bit at position i to true, the bits must be set in (strictly) increasing order. For example, set(15) and then set(7) will fail. You must do set(7) and then set(15).
        Parameters:
        i - the index
        Returns:
        true if the value was set (always true when i greater or equal to sizeInBits()).
        Throws:
        java.lang.IndexOutOfBoundsException - if i is negative or greater than Integer.MAX_VALUE - 64
      • setSizeInBits

        public void setSizeInBits​(int size)
        Set the size in bits. This does not change the compressed bitmap.
        Specified by:
        setSizeInBits in interface BitmapStorage
        Parameters:
        size - number of bits
        Since:
        0.4.0
      • setSizeInBits

        public boolean setSizeInBits​(int size,
                                     boolean defaultvalue)
        Change the reported size in bits of the *uncompressed* bitmap represented by this compressed bitmap. It may change the underlying compressed bitmap. It is not possible to reduce the sizeInBits, but it can be extended. The new bits are set to false or true depending on the value of defaultvalue.
        Parameters:
        size - the size in bits
        defaultvalue - the default boolean value
        Returns:
        true if the update was possible
      • sizeInBits

        public int sizeInBits()
        Returns the size in bits of the *uncompressed* bitmap represented by this compressed bitmap. Initially, the sizeInBits is zero. It is extended automatically when you set bits to true.
        Specified by:
        sizeInBits in interface LogicalElement<EWAHCompressedBitmap>
        Returns:
        the size in bits
      • sizeInBytes

        public int sizeInBytes()
        Report the *compressed* size of the bitmap (equivalent to memory usage, after accounting for some overhead).
        Specified by:
        sizeInBytes in interface LogicalElement<EWAHCompressedBitmap>
        Returns:
        the size in bytes
      • toArray

        public int[] toArray()
        Populate an array of (sorted integers) corresponding to the location of the set bits.
        Returns:
        the array containing the location of the set bits
      • toDebugString

        public java.lang.String toDebugString()
        A more detailed string describing the bitmap (useful for debugging).
        Returns:
        the string
      • toString

        public java.lang.String toString()
        A string describing the bitmap.
        Overrides:
        toString in class java.lang.Object
        Returns:
        the string
      • swap

        public void swap​(EWAHCompressedBitmap other)
        swap the content of the bitmap with another.
        Parameters:
        other - bitmap to swap with
      • trim

        public void trim()
        Reduce the internal buffer to its minimal allowable size (given by this.actualsizeinwords). This can free memory.
      • writeExternal

        public void writeExternal​(java.io.ObjectOutput out)
                           throws java.io.IOException
        Specified by:
        writeExternal in interface java.io.Externalizable
        Throws:
        java.io.IOException
      • xor

        public EWAHCompressedBitmap xor​(EWAHCompressedBitmap a)
        Returns a new compressed bitmap containing the bitwise XOR values of the current bitmap with some other bitmap. The running time is proportional to the sum of the compressed sizes (as reported by sizeInBytes()). If you are not planning on adding to the resulting bitmap, you may call the trim() method to reduce memory usage.
        Specified by:
        xor in interface LogicalElement<EWAHCompressedBitmap>
        Parameters:
        a - the other bitmap
        Returns:
        the EWAH compressed bitmap
      • xorToContainer

        public void xorToContainer​(EWAHCompressedBitmap a,
                                   BitmapStorage container)
        Computes a new compressed bitmap containing the bitwise XOR values of the current bitmap with some other bitmap. The running time is proportional to the sum of the compressed sizes (as reported by sizeInBytes()).
        Parameters:
        a - the other bitmap
        container - where we store the result
        Since:
        0.4.0
      • xorCardinality

        public int xorCardinality​(EWAHCompressedBitmap a)
        Returns the cardinality of the result of a bitwise XOR of the values of the current bitmap with some other bitmap. Avoids needing to allocate an intermediate bitmap to hold the result of the OR.
        Parameters:
        a - the other bitmap
        Returns:
        the cardinality
        Since:
        0.4.0
      • andWithContainer

        public static void andWithContainer​(BitmapStorage container,
                                            EWAHCompressedBitmap... bitmaps)
        For internal use. Computes the bitwise and of the provided bitmaps and stores the result in the container.
        Parameters:
        container - where the result is stored
        bitmaps - bitmaps to AND
        Since:
        0.4.3
      • and

        public static EWAHCompressedBitmap and​(EWAHCompressedBitmap... bitmaps)
        Returns a new compressed bitmap containing the bitwise AND values of the provided bitmaps. It may or may not be faster than doing the aggregation two-by-two (A.and(B).and(C)). If only one bitmap is provided, it is returned as is. If you are not planning on adding to the resulting bitmap, you may call the trim() method to reduce memory usage.
        Parameters:
        bitmaps - bitmaps to AND together
        Returns:
        result of the AND
        Since:
        0.4.3
      • andCardinality

        public static int andCardinality​(EWAHCompressedBitmap... bitmaps)
        Returns the cardinality of the result of a bitwise AND of the values of the provided bitmaps. Avoids needing to allocate an intermediate bitmap to hold the result of the AND.
        Parameters:
        bitmaps - bitmaps to AND
        Returns:
        the cardinality
        Since:
        0.4.3
      • bitmapOf

        public static EWAHCompressedBitmap bitmapOf​(int... setbits)
        Return a bitmap with the bit set to true at the given positions. The positions should be given in sorted order. (This is a convenience method.)
        Parameters:
        setbits - list of set bit positions
        Returns:
        the bitmap
        Since:
        0.4.5
      • orWithContainer

        public static void orWithContainer​(BitmapStorage container,
                                           EWAHCompressedBitmap... bitmaps)
        Uses an adaptive technique to compute the logical OR. Mostly for internal use.
        Parameters:
        container - where the aggregate is written.
        bitmaps - to be aggregated
      • xorWithContainer

        public static void xorWithContainer​(BitmapStorage container,
                                            EWAHCompressedBitmap... bitmaps)
        Uses an adaptive technique to compute the logical XOR. Mostly for internal use.
        Parameters:
        container - where the aggregate is written.
        bitmaps - to be aggregated
      • or

        public static EWAHCompressedBitmap or​(EWAHCompressedBitmap... bitmaps)
        Returns a new compressed bitmap containing the bitwise OR values of the provided bitmaps. This is typically faster than doing the aggregation two-by-two (A.or(B).or(C).or(D)). If only one bitmap is provided, it is returned as is. If you are not planning on adding to the resulting bitmap, you may call the trim() method to reduce memory usage.
        Parameters:
        bitmaps - bitmaps to OR together
        Returns:
        result of the OR
        Since:
        0.4.0
      • xor

        public static EWAHCompressedBitmap xor​(EWAHCompressedBitmap... bitmaps)
        Returns a new compressed bitmap containing the bitwise XOR values of the provided bitmaps. This is typically faster than doing the aggregation two-by-two (A.xor(B).xor(C).xor(D)). If only one bitmap is provided, it is returned as is. If you are not planning on adding to the resulting bitmap, you may call the trim() method to reduce memory usage.
        Parameters:
        bitmaps - bitmaps to XOR together
        Returns:
        result of the XOR
      • orCardinality

        public static int orCardinality​(EWAHCompressedBitmap... bitmaps)
        Returns the cardinality of the result of a bitwise OR of the values of the provided bitmaps. Avoids needing to allocate an intermediate bitmap to hold the result of the OR.
        Parameters:
        bitmaps - bitmaps to OR
        Returns:
        the cardinality
        Since:
        0.4.0