bitvector64.h

Go to the documentation of this file.

// $Id$
//      Author: John Wu <John.Wu at ACM.org>
//              Lawrence Berkeley National Laboratory
//      Copyright 2000-2011 the Regents of the University of California
#ifndef BITVECTOR64_H
#define BITVECTOR64_H



#include "array_t.h"    // alternative to std::vector

#include <stdio.h>      // sprintf
#include <limits.h>     // INT_MAX
#include <iomanip>      // setw()


class ibis::bitvector64 {
public:
    typedef uint64_t word_t;

    // constructors of bitvector64 class
    bitvector64() : nbits(0), nset(0), active(), m_vec() {};
    ~bitvector64() {clear();};
    bitvector64(const bitvector64& bv) : nbits(bv.nbits), nset(bv.nset),
        active(bv.active), m_vec(bv.m_vec) {};
    bitvector64(const array_t<word_t>& arr);
    bitvector64(const char* file); 
    inline bitvector64& operator=(const bitvector64& bv); 
    inline bitvector64& copy(const bitvector64& bv);      
    inline bitvector64& swap(bitvector64& bv);
    // use bv to replace part of the existing value, match the ith bit with
    // the first of bv, return reference to self
    //bitvector64& copy(const word_t i, const bitvector64& bv);
    void setBit(const word_t i, int val);
    void erase(word_t i, word_t j);

    void set(int val, word_t n);
    void clear() {nbits = 0; nset = 0; active.reset(); m_vec.clear();}

    bitvector64& operator+=(const bitvector64& bv); 
    inline bitvector64& operator+=(int b);      
    void appendWord(word_t w);                  

    inline void appendFill(int val, word_t n);

    int operator==(const bitvector64& rhs) const;

    void flip();
    void operator&=(const bitvector64& rhs);
    bitvector64* operator&(const bitvector64&) const;
    void operator|=(const bitvector64& rhs);
    bitvector64* operator|(const bitvector64&) const;
    void operator^=(const bitvector64& rhs);
    bitvector64* operator^(const bitvector64&) const;
    void operator-=(const bitvector64& rhs);
    bitvector64* operator-(const bitvector64&) const;

    // I/O functions.
    void read(const char *fn);
    void write(const char *fn) const;
    void write(FILE* fptr) const;
    void write(array_t<word_t>& arr) const;

    void compress();    
    void decompress();  

    word_t compressible() const;

    word_t cnt() const {
        if (nset==0) do_cnt(); return (nset+cnt_ones(active.val));
    };

    word_t size() const throw() {return (nbits+active.nbits);};
    inline word_t numFillWords() const;
    word_t bytes() const throw() {
        return (m_vec.size()*sizeof(word_t) + sizeof(bitvector64));
    };
    word_t getSerialSize() const throw() {
        return (m_vec.size() + 1 + (active.nbits>0));
    };
    static unsigned bitsPerLiteral() {return MAXBITS;}
    inline static double randomSize(word_t nb, word_t nc);
    inline static double markovSize(word_t nb, word_t nc, double f);
    static double clusteringFactor(word_t nb, word_t nc, word_t nw);

    void adjustSize(word_t nv, word_t nt);
    std::ostream& print(std::ostream &) const; 

    class iterator;
    inline iterator end();
    inline iterator begin();

    class const_iterator;
    inline const_iterator end() const;
    inline const_iterator begin() const;

    class indexSet;
    inline indexSet firstIndexSet() const;

    // give accesses to some friends
    friend class indexSet;
    friend class iterator;
    friend class const_iterator;

protected:
    bool isCompressed() const {return (m_vec.size()*MAXBITS < nbits);}
    inline bool all0s() const;
    inline bool all1s() const;

private:
    // static members, i.e., constants to be used internally
    static const unsigned MAXBITS;
    static const unsigned SECONDBIT;
    static const word_t FILLBIT;
    static const word_t HEADER0;
    static const word_t HEADER1;
    static const word_t ALLONES;
    static const word_t MAXCNT;

    struct active_word {
        word_t val;     // the value
        word_t nbits;   // total number of bits

        active_word() : val(0), nbits(0) {};
        void reset() {val = 0; nbits = 0;};
        int is_full() const {return (nbits >= MAXBITS);};
        void append(int b) { // append a single bit
            val <<= 1; nbits ++; val += b;
        };
    }; // struct active_word

    struct run {
        int isFill;
        int fillBit;
        word_t nWords;
        array_t<word_t>::const_iterator it;
        run() : isFill(0), fillBit(0), nWords(0), it(0) {};
        void decode() { 
            fillBit = (*it > HEADER1);
            if (*it > ALLONES) {
                nWords = (*it & MAXCNT);
                isFill = 1;
            }
            else {
                nWords = 1;
                isFill = 0;
            }
        };
        void operator--() {
            if (nWords > 1) {--nWords;}
            else {++ it; nWords = 0;}
        };
        void operator-=(word_t len) {
            while (len > 0) {
                if (nWords == 0) decode();
                if (isFill) {
                    if (nWords > len) {nWords -= len; len = 0;}
                    else if (nWords == len) {nWords = 0; len = 0; ++ it;}
                    else {len -= nWords; ++ it; nWords = 0;}
                }
                else {-- len; ++ it; nWords = 0;}
            }
        };
    };
    friend struct run;
    friend struct active_word;

    // member variables of bitvector64 class
    word_t nbits;       
    mutable word_t nset;
    active_word active; 
    array_t<word_t> m_vec;      

    // private functions of bitvector64 class
    // The following three functions all performs or operation, _c2 and _c1
    // generate compressed solutions, but _c0, _d1, and _d2 generate
    // uncompressed solutions.
    // or_c2 assumes there are compressed word in both operands
    // or_c1 *this may contain compressed word, but not rhs
    // or_c0 assumes both operands are not compressed
    // or_d1 *this contains no compressed word and is overwritten with the
    //       result
    // or_d2 both *this and rhs are compressed, but res will not be compressed
    void or_c2(const bitvector64& rhs, bitvector64& res) const;
    void or_c1(const bitvector64& rhs, bitvector64& res) const;
    void or_c0(const bitvector64& rhs);
    void or_d1(const bitvector64& rhs);
    void or_d2(const bitvector64& rhs, bitvector64& res) const;
    void and_c2(const bitvector64& rhs, bitvector64& res) const;
    void and_c1(const bitvector64& rhs, bitvector64& res) const;
    void and_c0(const bitvector64& rhs);
    void and_d1(const bitvector64& rhs);
    void and_d2(const bitvector64& rhs, bitvector64& res) const;
    void xor_c2(const bitvector64& rhs, bitvector64& res) const;
    void xor_c1(const bitvector64& rhs, bitvector64& res) const;
    void xor_c0(const bitvector64& rhs);
    void xor_d1(const bitvector64& rhs);
    void xor_d2(const bitvector64& rhs, bitvector64& res) const;
    void minus_c2(const bitvector64& rhs, bitvector64& res) const;
    void minus_c1(const bitvector64& rhs, bitvector64& res) const;
    void minus_c1x(const bitvector64& rhs, bitvector64& res) const;
    void minus_c0(const bitvector64& rhs);
    void minus_d1(const bitvector64& rhs);
    void minus_d2(const bitvector64& rhs, bitvector64& res) const;
    inline void copy_runs(run& it, word_t& nw); // copy nw words
    inline void copy_runsn(run& it, word_t& nw); // copy nw words and negate
    inline void copy_fill(array_t<word_t>::iterator& jt, run& it);
    inline void copy_runs(array_t<word_t>::iterator& jt, run& it,
                          word_t& nw);
    inline void copy_runsn(array_t<word_t>::iterator& jt, run& it,
                           word_t& nw);
    void decompress(array_t<word_t>& tmp) const;
    void copy_comp(array_t<word_t>& tmp) const;
    inline void append_active();
    inline void append_counter(int val, word_t cnt);
    inline unsigned cnt_ones(word_t) const; // number of 1s in a literal word
    inline word_t cnt_bits(word_t) const; // number of bits in a word
    word_t do_cnt() const; // count the number of bits and number of ones
}; // end class bitvector64

class ibis::bitvector64::indexSet {
public:
    // let the compiler define most of the canonical functions

    // allow bitvector64::firstIndexSet() to access private variables of this
    // class
    friend indexSet ibis::bitvector64::firstIndexSet() const;

    //int operator!=(const indexSet& rhs) const {return (it != rhs.it);};
    bool isRange() const {return (nind>=ibis::bitvector64::MAXBITS);}
    const word_t* indices() const {return ind;};
    word_t nIndices() const {return nind;}
    indexSet& operator++();

private:
    array_t<word_t>::const_iterator it;
    array_t<word_t>::const_iterator end;
    const active_word* active; // points back to the active word
    word_t nind; // number of indices
    word_t ind[64];
}; // class ibis::bitvector64::indexSet

class ibis::bitvector64::const_iterator {
public:
    inline bool operator*() const;
    inline int operator!=(const const_iterator& rhs) const throw ();
    inline int operator==(const const_iterator& rhs) const throw ();

    inline const_iterator& operator++();
    inline const_iterator& operator--();
    const_iterator& operator+=(int64_t incr);

private:
    ibis::bitvector64::word_t   compressed;
    ibis::bitvector64::word_t   ind;
    ibis::bitvector64::word_t   nbits;
    ibis::bitvector64::word_t   literalvalue;
    int                         fillbit;
    const active_word*          active;
    array_t<word_t>::const_iterator end;
    array_t<word_t>::const_iterator begin;
    array_t<word_t>::const_iterator it;

    void decodeWord();

    // give three functions of bitvector64 access to private variables
    friend void ibis::bitvector64::erase(word_t i, word_t j);
    friend const_iterator ibis::bitvector64::begin() const;
    friend const_iterator ibis::bitvector64::end() const;
    friend class ibis::bitvector64::iterator;
}; // end class ibis::bitvector64::const_iterator

class ibis::bitvector64::iterator {
public:
    inline bool operator*() const; // still can not modify this
    inline int operator!=(const const_iterator& rhs) const throw ();
    inline int operator==(const const_iterator& rhs) const throw ();
    inline int operator!=(const iterator& rhs) const throw ();
    inline int operator==(const iterator& rhs) const throw ();

    inline iterator& operator++();
    inline iterator& operator--();
    iterator& operator+=(int64_t incr);
    iterator& operator=(int val);

private:
    ibis::bitvector64::word_t   compressed;
    ibis::bitvector64::word_t   ind;
    ibis::bitvector64::word_t   nbits;
    ibis::bitvector64::word_t   literalvalue;
    int                         fillbit;
    ibis::bitvector64*          bitv;
    active_word*                active;
    array_t<word_t>*            vec;
    array_t<word_t>::iterator   it;

    void decodeWord();

    friend iterator ibis::bitvector64::begin();
    friend iterator ibis::bitvector64::end();
}; // end class ibis::bitvector64::iterator

inline bool ibis::bitvector64::all0s() const {
    if (m_vec.empty()) {
        return true;
    }
    else if (m_vec.size() == 1) {
        return (m_vec[0] == 0 || (m_vec[0] >= HEADER0 && m_vec[0] < HEADER1));
    }
    else {
        return false;
    }
} // ibis::bitvector64::all0s

inline bool ibis::bitvector64::all1s() const {
    if (m_vec.size() == 1) {
        return (m_vec[0] == ALLONES || (m_vec[0] > HEADER1));
    }
    else {
        return false;
    }
} // ibis::bitvector64::all1s()

inline ibis::bitvector64::word_t
ibis::bitvector64::cnt_bits(ibis::bitvector64::word_t val) const {
    return  ((val>ALLONES) ? ((val&MAXCNT)*MAXBITS) : MAXBITS);
}

inline unsigned 
ibis::bitvector64::cnt_ones(ibis::bitvector64::word_t val) const {
    // number of 1 bits in a value between 0 and 255
    static const unsigned table[256] = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
    //assert(8 == sizeof(word_t));
    return table[val&0xFF] + table[(val>>8)&0xFF] +
        table[(val>>16)&0xFF] + table[(val>>24)&0xFF] +
        table[(val>>32)&0xFF] + table[(val>>40)&0xFF] +
        table[(val>>48)&0xFF] + table[val>>56];
} // inline unsigned ibis::bitvector64::cnt_ones(word_t) const

inline ibis::bitvector64::word_t
ibis::bitvector64::numFillWords() const {
    word_t cnt=0;
    array_t<word_t>::const_iterator it = m_vec.begin();
    while (it != m_vec.end()) {
        cnt += (*it >> ibis::bitvector64::MAXBITS);
        it++;
    }
    return cnt;
} // ibis::bitvector64::numFillWords

// The assignment operator.  Wanted to use shallow copy for efficiency
// consideration, but SHALLOW copy causes unexpected problem in test
// program bitty.cpp change to deep copy
inline ibis::bitvector64&
ibis::bitvector64::operator=(const ibis::bitvector64& bv) {
    nbits = bv.nbits; nset = bv.nset; active = bv.active;
    m_vec.deepCopy(bv.m_vec);
    return *this;
}

// deep copy
inline ibis::bitvector64& 
ibis::bitvector64::copy(const ibis::bitvector64& bv) {
    nbits = bv.nbits; nset = bv.nset; active = bv.active;
    m_vec.deepCopy(bv.m_vec);
    return *this;
}

inline ibis::bitvector64&
ibis::bitvector64::swap(bitvector64& bv) {
    word_t tmp;
    tmp = bv.nbits; bv.nbits = nbits; nbits = tmp;
    tmp = bv.nset; bv.nset = nset; nset = tmp;
    active_word atmp = bv.active;
    bv.active = active; active = atmp;
    m_vec.swap(bv.m_vec);
    return *this;
}

// append_active assumes that nbits == MAXBITS and refers to MAXBITS instead
// of nbits
inline void ibis::bitvector64::append_active() {
    if (m_vec.empty()) {
        m_vec.push_back(active.val);
    }
    else if (active.val == 0) {// incoming word is zero
        if (m_vec.back() == 0) {
            m_vec.back() = (HEADER0 + 2);
        }
        else if (m_vec.back() >= HEADER0 && m_vec.back() < HEADER1) {
            ++ m_vec.back();
        }
        else {
            m_vec.push_back(active.val);
        }
    }
    else if (active.val == ALLONES) {// incoming word is allones
        if (m_vec.back() == ALLONES) {
            m_vec.back() = (HEADER1 | 2);
        }
        else if (m_vec.back() >= HEADER1) {
            ++m_vec.back();
        }
        else {
            m_vec.push_back(active.val);
        }
    }
    else { // incoming word contains a mixture of bits
        m_vec.push_back(active.val);
    }
    nbits += MAXBITS;
    active.reset();
    nset = 0;
} // void ibis::bitvector64::append_active()

// a private function to append a single counter when the active word is
// empty cnt is assumed to be multiples of MAXBITS (more than MAXBITS)
inline void ibis::bitvector64::append_counter(int val, word_t cnt) {
    word_t head = 2 + val;
    word_t w = (head << SECONDBIT) + cnt;
    nbits += cnt*MAXBITS;
    if (m_vec.empty()) {
        m_vec.push_back(w);
    }
    else if ((m_vec.back()>>SECONDBIT) == head) {
        m_vec.back() += cnt;
    }
    else if ((m_vec.back()==ALLONES) && head==3) {
        m_vec.back() = w + 1;
    }
    else if ((m_vec.back() == 0) && head==2) {
        m_vec.back() = w + 1;
    }
    else {
        m_vec.push_back(w);
    }
} // void append_counter()

// append a single bit
inline ibis::bitvector64& ibis::bitvector64::operator+=(int b) {
    active.append(b);
    if (active.is_full()) append_active();
    return *this;
} // ibis::bitvector64& ibis::bitvector64::operator+=(int b)

// append n bits of val (n may be arbitrary integer, value must be either 0
// or 1)
inline void ibis::bitvector64::appendFill(int val,
                                          ibis::bitvector64::word_t n) {
    if (active.nbits > 0) {
        word_t tmp = (MAXBITS - active.nbits);
        if (tmp > n) tmp = n;
        active.nbits += tmp;
        active.val <<= tmp;
        n -= tmp;
        if (val)
            active.val |= (static_cast<word_t>(1)<<tmp) - 1;
        if (active.nbits >= MAXBITS) append_active();
    }
    if (n >= MAXBITS) {
        word_t cnt = n / MAXBITS;
        if (cnt > 1)
            append_counter(val, cnt);
        else if (val) {
            active.val = ALLONES;
            append_active();
        }
        else {
            active.val = 0;
            append_active();
        }
        n -= cnt * MAXBITS;
    }
    if (n > 0) {
        active.nbits = n;
        active.val = val*((static_cast<word_t>(1)<<n)-1);
    }
} // ibis::bitvector64::appendFill(val, n)

// append nw words starting from 'it' to the current bit vector -- assume
// active is empty
inline void ibis::bitvector64::copy_runs(run& it, word_t& nw) {
#if defined(DEBUG) && DEBUG + 0 > 1
    LOGGER(ibis::gVerbose >= 0)
        << "bitvector64::copy_runs(0x"
        << std::hex << std::setw(8) << std::setfill('0')
        << *(it.it) << ", " << std::dec << nw
        << ") ... it.nWords = " << it.nWords;
#endif
    // deal with the first word -- need to attach it to the last word in m_vec
    if (it.isFill) {
        append_counter(it.fillBit, it.nWords);
        nw -= it.nWords;
    }
    else {
        active.val = *(it.it);
        append_active();
        -- nw;
    }
    ++ it.it; // advance to the next word
    //if (nw == 0) {it.nWords = 0; return;}
    it.decode();
    nset = 0;
    nbits += MAXBITS * nw;
    while (nw >= it.nWords && nw > 0) { // only need to copy the word
        m_vec.push_back(*(it.it));
        nw -= it.nWords;
        ++ it.it; // advance to the next word
        it.decode();
    }
    nbits -= MAXBITS * nw;
} // ibis::bitvector64::copy_runs

// append nw words starting from it to the current bit vector -- assume
// active is empty
inline void ibis::bitvector64::copy_runsn(run& it, word_t& nw) {
#if defined(DEBUG) && DEBUG + 0 > 1
    LOGGER(ibis::gVerbose >= 0)
        << "bitvector64::copy_runsn(0x"
        << std::hex << std::setw(8) << std::setfill('0')
        << *(it.it) << ", " << std::dec << nw
        << ") ... it.nWords = " << it.nWords;
#endif
    // deal with the first word -- need to attach it to the last word in m_vec
    if (it.isFill) {
        append_counter(!it.fillBit, it.nWords);
        nw -= it.nWords;
    }
    else {
        active.val = ALLONES ^ *(it.it);
        append_active();
        -- nw;
    }
    ++ it.it; // advance to the next word
    //if (nw == 0) {it.nWords = 0; return;}
    it.decode();
    nset = 0;
    nbits += MAXBITS * nw;
    while (nw >= it.nWords && nw > 0) { // only need to copy the word
        m_vec.push_back((it.isFill?FILLBIT:ALLONES) ^ *(it.it));
        nw -= it.nWords;
        ++ it.it; // advance to the next word
        it.decode();
    }
    nbits -= MAXBITS * nw;
} // ibis::bitvector64::copy_runsn

// copy the fill in "run it" as literal words
inline void ibis::bitvector64::copy_fill
(array_t<ibis::bitvector64::word_t>::iterator& jt, run& it) {
    const array_t<word_t>::iterator iend = jt + it.nWords;
    if (it.fillBit == 0) {
        switch (it.nWords) {
        case 0: break;
        case 1:
            *jt = 0; ++jt; break;
        case 2:
            *jt = 0; ++jt; *jt = 0; ++jt; break;
        case 3:
            *jt = 0; ++jt; *jt = 0; ++jt; *jt = 0; ++jt; break;
        default:
            while (jt < iend) {
                *jt = 0;
                ++ jt;
            }
            break;
        }
    }
    else {
        switch (it.nWords) {
        case 0: break;
        case 1:
            *jt = ALLONES; ++jt; break;
        case 2:
            *jt = ALLONES; ++jt; *jt = ALLONES; ++jt; break;
        case 3:
            *jt = ALLONES; ++jt; *jt = ALLONES; ++jt; *jt = ALLONES; ++jt;
            break;
        default:
            while (jt < iend) {
                *jt = ALLONES;
                ++ jt;
            }
            break;
        }
    }
    it.nWords = 0;
    ++ it.it;
} // ibis::bitvector64::copy_fill

// copy the next nw words (nw X MAXBITS bits) starting with run it
// to an array_t as uncompressed words
inline void ibis::bitvector64::copy_runs
(array_t<ibis::bitvector64::word_t>::iterator& jt, run& it, word_t& nw) {
    while (nw >= it.nWords && nw > 0) { // only need to copy the word
        if (it.isFill) {
            const array_t<word_t>::iterator iend = jt + it.nWords;
            if (it.fillBit == 0) {
                while (jt < iend) {
                    *jt = 0;
                    ++ jt;
                }
            }
            else {
                while (jt < iend) {
                    *jt = ALLONES;
                    ++ jt;
                }
            }
            nw -= it.nWords;
        }
        else {
            *jt = *(it.it);
            ++ jt;
            -- nw;
        }
        ++ it.it; // advance to the next word
        it.decode();
    }
} // ibis::bitvector64::copy_runs

// copy the complements of the next nw words (nw X MAXBITS bits)
// starting with "run it" as uncompressed words
inline void ibis::bitvector64::copy_runsn
(array_t<ibis::bitvector64::word_t>::iterator& jt, run& it, word_t& nw) {
    while (nw >= it.nWords && nw > 0) { // only need to copy the word
        if (it.isFill) {
            const array_t<word_t>::iterator iend = jt + it.nWords;
            if (it.fillBit == 0) {
                while (jt < iend) {
                    *jt = ALLONES;
                    ++ jt;
                }
            }
            else {
                while (jt < iend) {
                    *jt = 0;
                    ++ jt;
                }
            }
            nw -= it.nWords;
        }
        else {
            *jt = *(it.it) ^ ALLONES;
            ++ jt;
            -- nw;
        }
        ++ it.it; // advance to the next word
        it.decode();
    }
} // ibis::bitvector64::copy_runsn

inline ibis::bitvector64::iterator ibis::bitvector64::begin() {
    iterator it;
    it.it     = m_vec.begin();
    it.vec    = &m_vec;
    it.bitv   = this;
    it.active = &active;
    it.decodeWord();
    return it;
} // ibis::bitvector64::begin()

inline ibis::bitvector64::iterator ibis::bitvector64::end() {
    iterator it;
    it.ind              = 0;
    it.compressed       = 0;
    it.nbits            = 0;
    it.literalvalue     = 0;
    it.fillbit          = 0;
    it.it     = m_vec.end() + 1;
    it.vec    = &m_vec;
    it.bitv   = this;
    it.active = &active;
    return it;
} // ibis::bitvector64::end()

inline ibis::bitvector64::const_iterator ibis::bitvector64::begin() const {
    const_iterator it;
    it.it     = m_vec.begin();
    it.begin  = m_vec.begin();
    it.end    = m_vec.end();
    it.active = &active;
    it.decodeWord();
    return it;
} // ibis::bitvector64::begin()

// dereference -- no error checking
inline bool ibis::bitvector64::iterator::operator*() const {
#if defined(DEBUG) && DEBUG + 0 > 1
    if (vec==0 || it<vec->begin() ||  it>vec->end())
        throw "bitvector64::const_iterator not initialized correctly.";
#endif
    if (compressed != 0)
        return (fillbit != 0);
    else
        return ((word_t)1 & (literalvalue >> (bitvector64::SECONDBIT - ind)));
}

// comparison only based on the iterator
inline int ibis::bitvector64::iterator::operator!=
(const ibis::bitvector64::const_iterator& rhs) const throw () {
    return (it != rhs.it);
}
inline int ibis::bitvector64::iterator::operator==
(const ibis::bitvector64::const_iterator& rhs) const throw () {
    return (it == rhs.it);
}
inline int ibis::bitvector64::iterator::operator!=
(const ibis::bitvector64::iterator& rhs) const throw () {
    return (it != rhs.it);
}
inline int ibis::bitvector64::iterator::operator==
(const ibis::bitvector64::iterator& rhs) const throw () {
    return (it == rhs.it);
}

// increment by one
inline ibis::bitvector64::iterator& ibis::bitvector64::iterator::operator++() {
#if defined(DEBUG) && DEBUG + 0 > 1
    if (vec==0 || it<vec->begin() || it>vec->end())
        throw "bitvector64::iterator not formed correctly.";
#endif
    if (ind+1<nbits) {++ind;}
    else {++ it; decodeWord();}
    return *this;
}

// decrement by one
inline ibis::bitvector64::iterator& ibis::bitvector64::iterator::operator--() {
#if defined(DEBUG) && DEBUG + 0 > 1
    if (vec==0 || it<vec->begin() || it>vec->end()+1)
        throw "bitvector64::iterator not formed correctly.";
#endif
    if (ind) -- ind;
    else {
        if (it <= vec->end()) -- it;
        else if (active->nbits) it = vec->end();
        else it = vec->end() - 1;
        decodeWord();
        if (nbits) ind = nbits - 1;
    }
    return *this;
}

inline ibis::bitvector64::const_iterator ibis::bitvector64::end() const {
    const_iterator it;
    it.ind              = 0;
    it.compressed       = 0;
    it.nbits            = 0;
    it.literalvalue     = 0;
    it.fillbit          = 0;
    it.it    = m_vec.end() + 1;
    it.begin = m_vec.begin();
    it.end   = m_vec.end();
    it.active = &active;
    return it;
} // ibis::bitvector64::end()

// dereference -- no error checking
inline bool ibis::bitvector64::const_iterator::operator*() const {
#if defined(DEBUG) && DEBUG + 0 > 1
    if (it==0 || end==0 || it>end || nbits<=ind)
        throw "bitvector64::const_iterator not initialized correctly.";
#endif
    if (compressed != 0)
        return (fillbit != 0);
    else
        return ((word_t)1 & (literalvalue >> (bitvector64::SECONDBIT - ind)));
}

// comparison only based on the iterator
inline int ibis::bitvector64::const_iterator::operator!=
(const ibis::bitvector64::const_iterator& rhs) const throw (){
    return (it != rhs.it);
}
inline int ibis::bitvector64::const_iterator::operator==
(const ibis::bitvector64::const_iterator& rhs) const throw () {
    return (it == rhs.it);
}

// increment by one
inline ibis::bitvector64::const_iterator&
ibis::bitvector64::const_iterator::operator++() {
#if defined(DEBUG) && DEBUG + 0 > 1
    if (it==0 || end==0 || it>end)
        throw "bitvector64::const_iterator not formed correctly.";
#endif
    if (ind+1<nbits) {++ind;}
    else {++ it; decodeWord();}
    return *this;
}

// decrement by one
inline ibis::bitvector64::const_iterator&
ibis::bitvector64::const_iterator::operator--() {
#if defined(DEBUG) && DEBUG + 0 > 1
    if (it==0 || end==0 || it>end)
        throw "bitvector64::const_iterator not formed correctly.";
#endif
    if (ind) -- ind;
    else {
        if (it <= end) -- it;
        else if (active->nbits) it = end;
        else it = end - 1;
        decodeWord();
        if (nbits) ind = nbits - 1;
    }
    return *this;
}

inline ibis::bitvector64::indexSet ibis::bitvector64::firstIndexSet() const {
    indexSet is;
    if (m_vec.end() > m_vec.begin()) {
        is.it = m_vec.begin() - 1;
        is.end = m_vec.end();
    }
    else {
        is.it = 0;
        is.end = 0;
    }
    is.active = &active;
    is.ind[0] = static_cast<word_t>(-1);
    is.nind = 0;
    ++is;
    return is;
} // end ibis::bitvector64::firstIndexSet;

inline double ibis::bitvector64::randomSize(word_t nb, word_t nc) {
    double sz = 0.0;
    if (nb > 0 && nb >= nc) {
        const double den = static_cast<double>(nc) /
            static_cast<double>(nb);
        const word_t nw = (nb > SECONDBIT ? nb / SECONDBIT - 1 : 0);
        sz = 3.0 + nw - nw *
            (pow(1.0-den, static_cast<int>(2*SECONDBIT)) +
             pow(den, static_cast<int>(2*SECONDBIT)));
    }
    return sz*sizeof(word_t);
} // end ibis::bitvector64::randomSize

inline double
ibis::bitvector64::markovSize(word_t nb, word_t nc, double f) {
    double sz = 0.0;
    if (nb > 0 && nb >= nc) {
        const double den = static_cast<double>(nc) /
            static_cast<double>(nb);
        const word_t nw = (nb > SECONDBIT ? nb / SECONDBIT - 1 : 0);
        if ((den <= 0.5 && f > 1.0) || (den > 0.5 && (1.0-den)*f > den))
            sz = ((1.0-den) * pow(1.0-den/((1.0-den)*f),
                                  static_cast<int>(2*MAXBITS-3)) +
                  den * pow(1.0-1.0/f, static_cast<int>(2*MAXBITS-3)));
        else
            sz = (pow(1.0-den, static_cast<int>(2*SECONDBIT)) +
                  pow(den, static_cast<int>(2*SECONDBIT)));
        sz = 3.0 + nw * (1.0 - sz);
    }
    return sz*sizeof(word_t);
} // end ibis::bitvector64::markovSize

std::ostream& operator<<(std::ostream&, const ibis::bitvector64&);
#endif // __BITVECTOR64_H