bitarray.h

//
// bitarray.h
//
// Modifications are
// Copyright (C) 1996 Limit Point Systems, Inc.
//
// Author: Edward Seidl <seidl@janed.com>
// Maintainer: LPS
//
// This file is part of the SC Toolkit.
//
// The SC Toolkit is free software; you can redistribute it and/or modify
// it under the terms of the GNU Library General Public License as published by
// the Free Software Foundation; either version 2, or (at your option)
// any later version.
//
// The SC Toolkit is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Library General Public License for more details.
//
// You should have received a copy of the GNU Library General Public License
// along with the SC Toolkit; see the file COPYING.LIB.  If not, write to
// the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
//
// The U.S. Government is granted a limited license as per AL 91-7.
//
 
/* bitarray.h -- definition of the BitArray Class
 *
 *      THIS SOFTWARE FITS THE DESCRIPTION IN THE U.S. COPYRIGHT ACT OF A
 *      "UNITED STATES GOVERNMENT WORK".  IT WAS WRITTEN AS A PART OF THE
 *      AUTHOR'S OFFICIAL DUTIES AS A GOVERNMENT EMPLOYEE.  THIS MEANS IT
 *      CANNOT BE COPYRIGHTED.  THIS SOFTWARE IS FREELY AVAILABLE TO THE
 *      PUBLIC FOR USE WITHOUT A COPYRIGHT NOTICE, AND THERE ARE NO
 *      RESTRICTIONS ON ITS USE, NOW OR SUBSEQUENTLY.
 *
 *  Author:
 *      E. T. Seidl
 *      Bldg. 12A, Rm. 2033
 *      Computer Systems Laboratory
 *      Division of Computer Research and Technology
 *      National Institutes of Health
 *      Bethesda, Maryland 20892
 *      Internet: seidl@alw.nih.gov
 *      July, 1993
 */
 
#ifndef _util_container_bitarray_h
#define _util_container_bitarray_h
 
#include <vector>
#include <cstring>
#include <cstdlib>
 
#include <util/misc/formio.h>
 
namespace sc {
 
//
// class BitArrayLTri is used as the lower triangle of a boolean matrix.
// rather than storing an int or a char, just use one bit for each, so
// instead of n(n+1)/2 bytes of storage you have n(n+1)/16 bytes.  A
// further savings of n bits could be obtained by setting the diagonal to
// always true or always false depending on the application, but this would
// probably be more expensive computationally than it's worth.
//
 
class BitArrayLTri {
  private:
    std::vector<unsigned char> a;
    int n;
    int nm;
    int na;
 
    static int
    ij_offset(int i, int j)
        {
          return (i>j) ? (((i*(i+1)) >> 1) + j) : (((j*(j+1)) >> 1) + i);
        }
 
  public:
    BitArrayLTri(int =0, int =0);
    ~BitArrayLTri();
 
    void set(unsigned int i) { a[(i>>3)] |= (1 << (i&7)); }
    void set(unsigned int i, unsigned int j) { set(ij_offset(i,j)); }
 
    int is_set(unsigned int i, unsigned int j) const
      { int ij = ij_offset(i,j); return (a[(ij>>3)] & (1 << (ij&7))); }
    int is_set(unsigned int i) const
      { return (a[(i>>3)] & (1 << (i&7))); }
 
    int operator()(unsigned int i, unsigned int j) const
      { int ij = ij_offset(i,j); return (a[(ij>>3)] & (1 << (ij&7))); }
    int operator()(unsigned int i) const
      { return (a[(i>>3)] & (1 << (i&7))); }
    int operator[](unsigned int i) const
      { return (a[(i>>3)] & (1 << (i&7))); }
 
    int dim() const { return na; }
    int nrow() const { return nm; }
    int ncol() const { return nm; }
 
    int degree(unsigned int i) const {
      int nedge=0;
      for (int j=0; j < nm; j++) if ((*this)(i,j)) nedge++;
      return nedge;
    }
};
 
}
 
#endif
 
// Local Variables:
// mode: c++
// c-file-style: "ETS"
// End: