BitSet.h

Go to the documentation of this file.

/*
 * 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 {

    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:

        BitSet();

        BitSet(int bitCount);

        BitSet(const BitSet& set);

        BitSet& operator= (const BitSet& set);

        virtual ~BitSet();

        bool operator==(const BitSet& other) const {
            return this->equals(other);
        }

        bool operator!=(const BitSet& other) const {
            return !this->equals(other);
        }

    public:

        void AND(const BitSet& set);

        void OR(const BitSet& set);

        void andNot(const BitSet& set);

        int cardinality();

        void clear();

        void clear(int index);

        void clear(int fromIndex, int toIndex);

        bool equals(const BitSet& set) const;

        void flip(int index);

        void flip(int fromIndex, int toIndex);

        bool get(int index) const;

        BitSet get(int fromIndex, int toIndex) const;

        bool intersects(const BitSet& set) const;

        bool isEmpty() const;

        int length() const;

        int nextClearBit(int index) const;

        int nextSetBit(int index) const;

        void set(int index);

        void set(int index, bool value);

        void set(int fromIndex, int toIndex);

        void set(int fromIndex, int toIndex, bool value);

        int size() const;

        std::string toString() const;

        void XOR(const BitSet& set);

    private:

        void ensureCapacity(int length);

        int getActualArrayLength() const;

    };

}}

#endif /* _DECAF_UTIL_BITSET_H_ */