/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef _DECAF_UTIL_BITSET_H_
#define _DECAF_UTIL_BITSET_H_

#include <decaf/util/Config.h>

#include <string>

namespace decaf {
namespace util {

    /**
     * This class implements a vector of bits that grows as needed. Each component of
     * the bit set has a boolean value. The bits of a BitSet are indexed by nonnegative
     * integers. Individual indexed bits can be examined, set, or cleared. One BitSet
     * may be used to modify the contents of another BitSet through logical AND, logical
     * inclusive OR, and logical exclusive OR operations.
     *
     * By default, all bits in the set initially have the value false.
     *
     * Every bit set has a current size, which is the number of bits of space currently
     * in use by the bit set. Note that the size is related to the implementation of a
     * bit set, so it may change with implementation. The length of a bit set relates to
     * logical length of a bit set and is defined independently of implementation.
     *
     * A BitSet is not safe for multi-threaded use without external synchronization.
     *
     * @since 1.0
     */
    class DECAF_API BitSet {
    private:

        // The actual array of 64 bit bits elements
        unsigned long long* bits;
        int bitsSize;

        // Optimization, when the array is all zero there's no need to traverse
        bool needClear;

        // Lazily maintained actual array length and state.
        mutable int actualArrayLength;
        mutable bool isLengthActual;

    private:

        BitSet(unsigned long long* bits, int bitsSize, bool needClear, int actualArrayLength, bool isLengthActual);

    public:

        /**
         * Creates a new BitSet whose bits are all false.
         */
        BitSet();

        /**
         * Creates a bit set whose initial size is large enough to explicitly represent bits
         * with indices in the range 0 through bitCount-1. All bits are initially false.  If the
         * bitCount is not a multiple of 64 then the count is rounded to the next closest
         * multiple of 64.
         *
         * @param bitCount
         *      The number of bits this BitSet should hold.
         *
         * @throws NegativeArraySizeException if bitCount is negative.
         */
        BitSet(int bitCount);

        /**
         * Copy Constructor
         */
        BitSet(const BitSet& set);

        /**
         * Assignment
         */
        BitSet& operator= (const BitSet& set);

        virtual ~BitSet();

        /**
         * Boolean comparison operator ==
         *
         * @param other
         *      The other BitSet to compare to this one.
         */
        bool operator==(const BitSet& other) const {
            return this->equals(other);
        }

        /**
         * Boolean comparison operator !=
         *
         * @param other
         *      The other BitSet to compare to this one.
         */
        bool operator!=(const BitSet& other) const {
            return !this->equals(other);
        }

    public:

        /**
         * Performs a logical AND of this target bit set with the argument bit set. This bit
         * set is modified so that each bit in it has the value true if and only if it both
         * initially had the value true and the corresponding bit in the bit set argument
         * also had the value true.
         *
         * @param set
         *      The BitSet to perform this action against.
         */
        void AND(const BitSet& set);

        /**
         * Performs a logical OR of this bit set with the bit set argument. This bit set is
         * modified so that a bit in it has the value true if and only if it either already had
         * the value true or the corresponding bit in the bit set argument has the value true.
         *
         * @param set
         *      The BitSet to perform this action against.
         */
        void OR(const BitSet& set);

        /**
         * Clears all of the bits in this BitSet whose corresponding bit is set in the specified BitSet.
         *
         * @param set
         *      The BitSet to perform this action against.
         */
        void andNot(const BitSet& set);

        /**
         * Returns the number of bits set to true in this BitSet.
         *
         * @return the number of bits set to true in this BitSet.
         */
        int cardinality();

        /**
         * Sets all of the bits in this BitSet to false.
         */
        void clear();

        /**
         * Sets the bit specified by the index to false.
         *
         * @param index
         *      The index of the bit whose value is to be set to false
         *
         * @throws IndexOutOfBoundsException if the index value is negative.
         */
        void clear(int index);

        /**
         * Sets the bits from the specified fromIndex (inclusive) to the specified toIndex
         * (exclusive) to false.
         *
         * @param fromIndex
         *      The index (inclusive) to start setting bits to false.
         * @param toIndex
         *      The index (exclusive) to stop setting bits to false.
         *
         * @throws IndexOutOfBoundsException if fromIndex is negative, or toIndex is negative, or
         *                                   fromIndex is larger than toIndex.
         */
        void clear(int fromIndex, int toIndex);

        /**
         * Compares this object against the specified object. The result is true if and only if
         * is a Bitset object that has exactly the same set of bits set to true as this bit set.
         * That is, for every nonnegative int index k,
         *
         *   set.get(k) == this->get(k)
         *
         * must be true. The current sizes of the two bit sets are not compared.
         *
         * @return true if the sets are the same, false otherwise.
         */
        bool equals(const BitSet& set) const;

        /**
         * Sets the bit at the specified index to the complement of its current value.
         *
         * @param index
         *      The index of the bit whose value is to be set to its compliment.
         *
         * @throws IndexOutOfBoundsException if the index value is negative.
         */
        void flip(int index);

        /**
         * Sets each bit from the specified fromIndex (inclusive) to the specified toIndex
         * (exclusive) to the complement of its current value.
         *
         * @param fromIndex
         *      The index (inclusive) to start setting bits to its compliment.
         * @param toIndex
         *      The index (exclusive) to stop setting bits to its compliment.
         *
         * @throws IndexOutOfBoundsException if fromIndex is negative, or toIndex is negative, or
         *                                   fromIndex is larger than toIndex.
         */
        void flip(int fromIndex, int toIndex);

        /**
         * Returns the value of the bit with the specified index. The value is true if the bit
         * with the given index is currently set in this BitSet; otherwise, the result is false.
         *
         * @param index
         *      The index of the bit in question.
         *
         * @return the value of the bit with the specified index.
         *
         * @throws IndexOutOfBoundsException if the index value is negative.
         */
        bool get(int index) const;

        /**
         * Returns a new BitSet composed of bits from this BitSet from fromIndex (inclusive) to
         * toIndex (exclusive).
         *
         * @param fromIndex
         *      The index (inclusive) to start at.
         * @param toIndex
         *      The index (exclusive) to stop at.
         *
         * @return a new BitSet containing the specified values.
         *
         * @throws IndexOutOfBoundsException if fromIndex is negative, or toIndex is negative, or
         *                                   fromIndex is larger than toIndex.
         */
        BitSet get(int fromIndex, int toIndex) const;

        /**
         * Returns true if the specified BitSet has any bits set to true that are also set to
         * true in this BitSet.
         *
         * @param set
         *      BitSet to intersect with.
         *
         * @return boolean indicating whether this BitSet intersects the specified BitSet.
         */
        bool intersects(const BitSet& set) const;

        /**
         * Returns true if this BitSet contains no bits that are set to true.
         *
         * @return true if the set is empty, false otherwise.
         */
        bool isEmpty() const;

        /**
         * Returns the "logical size" of this BitSet: the index of the highest set bit in the
         * BitSet plus one. Returns zero if the BitSet contains no set bits.
         *
         * @return the logical size of the BitSet.
         */
        int length() const;

        /**
         * Returns the index of the first bit that is set to false that occurs on or after the
         * specified starting index.
         *
         * @param index
         *      The index to start the search from (inclusive).
         *
         * @return the index of the next clear bit.
         *
         * @throws IndexOutOfBoundsException if the index value is negative.
         */
        int nextClearBit(int index) const;

        /**
         * Returns the index of the first bit that is set to true that occurs on or after the
         * specified starting index.
         *
         * @param index
         *      The index to start the search from (inclusive).
         *
         * @return the index of the next set bit.
         *
         * @throws IndexOutOfBoundsException if the index value is negative.
         */
        int nextSetBit(int index) const;

        /**
         * Sets the bit at the specified index to true.
         *
         * @param index
         *      The index to set to true.
         *
         * @throws IndexOutOfBoundsException if the index value is negative.
         */
        void set(int index);

        /**
         * Sets the bit at the specified index to the specified value.
         *
         * @param index
         *      The index to set.
         * @param value
         *      The value to assign to the given bit.
         *
         * @throws IndexOutOfBoundsException if the index value is negative.
         */
        void set(int index, bool value);

        /**
         * Sets the bits from the specified fromIndex (inclusive) to the specified toIndex
         * (exclusive) to true.
         *
         * @param fromIndex
         *      The index (inclusive) to start at.
         * @param toIndex
         *      The index (exclusive) to stop at.
         *
         * @throws IndexOutOfBoundsException if fromIndex is negative, or toIndex is negative, or
         *                                   fromIndex is larger than toIndex.
         */
        void set(int fromIndex, int toIndex);

        /**
         * Sets the bits from the specified fromIndex (inclusive) to the specified toIndex
         * (exclusive) to the value given.
         *
         * @param fromIndex
         *      The index (inclusive) to start at.
         * @param toIndex
         *      The index (exclusive) to stop at.
         * @param value
         *      The boolean value to assign to the target bits.
         *
         * @throws IndexOutOfBoundsException if fromIndex is negative, or toIndex is negative, or
         *                                   fromIndex is larger than toIndex.
         */
        void set(int fromIndex, int toIndex, bool value);

        /**
         * Returns the number of bits of space actually in use by this BitSet to represent bit
         * values. The maximum element in the set is the size - 1st element.
         *
         * @return the number of bits currently in this bit set.
         */
        int size() const;

        /**
         * Returns a string representation of this bit set. For every index for which this BitSet
         * contains a bit in the set state, the decimal representation of that index is included
         * in the result. Such indices are listed in order from lowest to highest, separated by
         * ", " (a comma and a space) and surrounded by braces, resulting in the usual mathematical
         * notation for a set of integers.
         *
         * @return string representation of the BitSet.
         */
        std::string toString() const;

        /**
         * Performs a logical XOR of this bit set with the bit set argument. This bit set is modified
         * so that a bit in it has the value true if and only if one of the following statements holds:
         *
         *   * The bit initially has the value true, and the corresponding bit in the argument has
         *     the value false.
         *   * The bit initially has the value false, and the corresponding bit in the argument has
         *     the value true.
         *
         * @param set
         *      The BitSet to use.
         */
        void XOR(const BitSet& set);

    private:

        /**
         * Increase the size of the internal array to accommodate length bits.
         * The new array max index will be a multiple of 64.
         *
         * @param length
         *      the index the new array needs to be able to access.
         */
        void ensureCapacity(int length);

        /**
         * Gets the actual length of the BitSet bit array which is maintained in a
         * sometimes lazy fashion to avoid excessive array traversals.  The actual
         * length is the number of non-zero array elements in the physical array
         * used to back this BitSet.
         *
         * @return the actual array length.
         */
        int getActualArrayLength() const;

    };

}}

#endif /* _DECAF_UTIL_BITSET_H_ */