drwnBitArray.h

/*****************************************************************************
** DARWIN: A FRAMEWORK FOR MACHINE LEARNING RESEARCH AND DEVELOPMENT
** Distributed under the terms of the BSD license (see the LICENSE file)
** Copyright (c) 2007-2015, Stephen Gould
** All rights reserved.
**
******************************************************************************
** FILENAME:    drwnBitArray.h
** AUTHOR(S):   Stephen Gould <stephen.gould@anu.edu.au>
**              Paul Baumstarck <pbaumstarck@stanford.edu>
** DESCRIPTION:
**  Implements a packed array of bits.
**
*****************************************************************************/

#pragma once

#include <stdlib.h>
#include <iostream>
#include <cstring>

using namespace std;

#define DRWN_INT_BIT_SIZE (8*sizeof(int))
#define DRWN_BIT_GET(x,b) ( ( (x)[(b)/DRWN_INT_BIT_SIZE] & (1<<((b)%DRWN_INT_BIT_SIZE)) ) != 0 )
#define DRWN_BIT_SET(x,b) ( (x)[(b)/DRWN_INT_BIT_SIZE] |= (1<<((b)%DRWN_INT_BIT_SIZE)) )
#define DRWN_BIT_CLEAR(x,b) ( (x)[(b)/DRWN_INT_BIT_SIZE] &= (unsigned int)(-1) - (1<<((b)%DRWN_INT_BIT_SIZE)) )
#define DRWN_BIT_FLIP(x,b) ( (x)[(b)/DRWN_INT_BIT_SIZE] ^= (1<<((b)%DRWN_INT_BIT_SIZE)) )
#define DRWN_BITMAP_SIZE(x) int( ((x+DRWN_INT_BIT_SIZE-1)/DRWN_INT_BIT_SIZE) )

class drwnBitArray {
 protected:
    static const int NUMSETLOOKUP[256]; 
    int _sz;                            
    int _map_sz;                        
    int *_map;                          
    int _mask;                          

 public:
    drwnBitArray();
    drwnBitArray(int sz);
    drwnBitArray(const drwnBitArray &m);
    virtual ~drwnBitArray();

    inline bool empty() const { return (_sz == 0); }
    inline int size() const { return _sz; }
    int count() const;

    inline bool get(int i) const { return DRWN_BIT_GET(_map, i); }
    inline void set(int i) { DRWN_BIT_SET(_map, i); }
    inline void clear(int i) { DRWN_BIT_CLEAR(_map, i); }
    inline void flip(int i) { DRWN_BIT_FLIP(_map, i); }

    drwnBitArray& ones();
    drwnBitArray& zeros();
    drwnBitArray& negate();
    drwnBitArray& bitwiseand(const drwnBitArray& c);
    drwnBitArray& bitwiseor(const drwnBitArray& c);
    drwnBitArray& bitwisenand(const drwnBitArray& c);
    drwnBitArray& bitwisenor(const drwnBitArray& c);
    drwnBitArray& bitwisexor(const drwnBitArray& c);

    drwnBitArray& operator=(const drwnBitArray &c);
    bool operator==(const drwnBitArray& c) const;
    bool operator!=(const drwnBitArray& c) const;
    bool operator<=(const drwnBitArray& c) const;
    inline bool operator[](int i) const { return DRWN_BIT_GET(_map, i); }

    void print(ostream &os = cout, int stride = -1) const;
};