bitset.h

Go to the documentation of this file.

#ifndef BITSET_H
#define BITSET_H

#include <stdint.h>

namespace frechet { namespace data {

class BitSet {
private:
    int _size;
    int numWords;
    uint64_t* bits;

public:
    BitSet();
    BitSet(int asize);
    BitSet(const BitSet& that);
    //BitSet(BitSet&& that);
    ~BitSet();
    BitSet& operator= (const BitSet& that);
    //BitSet& operator= (BitSet&& that);
    BitSet& swap (BitSet& that);

    int size() const;
    int count() const;
    void clear();

    bool contains(int offset) const;
    void add(int offset);
    void remove(int offset);

    bool operator[] (int offset) const  { return contains(offset); }
    BitSet& operator+= (int offset)     { add(offset); return *this; }
    BitSet& operator-= (int offset)     { remove(offset); return *this; }

    void add_lf(int offset);
    void remove_lf(int offset);


    class iterator {
    public:
        iterator();
        iterator(const iterator& that);

        iterator& operator= (const iterator& that);

        bool operator== (const iterator& that) const;

        bool    valid() const;
        int     operator* () const;

        iterator&    operator++ (/*pre-increment*/);
        iterator     operator++ (int/*post-increment*/);

        iterator&    operator-- (/*pre-decrement*/);
        iterator     operator-- (int/*post-decrement*/);

        iterator&    operator+= (int n);
        iterator     operator+ (int n) const;

        iterator&    operator-= (int n);
        iterator     operator- (int n);

        int          operator- (const iterator& that);

    private:
        friend class BitSet;
        const BitSet* parent;
        int _offset;
        iterator(const BitSet* aparent,int start);
    };
    iterator    begin() const;
    iterator    end() const     { return iterator(this,_size); }

    iterator    first() const   { return begin(); }
    iterator    last() const    {
        iterator it = end();
        if (it._offset > 0) --it;
        return it;
    }

private:
    void copyBits(const BitSet& that);
    void stealBits(BitSet&& that);

    int next(int index) const;
    int prev(int off) const;

    static int numberOfTrailingZeros(uint64_t word);
    static int numberOfLeadingZeros(uint64_t word);
    static int bitCount(uint64_t word);
    static int64_t compare_and_swap(volatile int64_t* value, int64_t old_value, int64_t update_value);
};

} } // namespace

#endif // BITSET_H