Enter your search terms GNU-Darwin Web Submit search form

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 <string.h> #include <stdlib.h> #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: 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: