# bitarray.h

    00001 //
    00002 // bitarray.h
    00003 //
    00004 // Modifications are
    00005 // Copyright (C) 1996 Limit Point Systems, Inc.
    00006 //
    00007 // Author: Edward Seidl <seidl@janed.com>
    00008 // Maintainer: LPS
    00009 //
    00010 // This file is part of the SC Toolkit.
    00011 //
    00012 // The SC Toolkit is free software; you can redistribute it and/or modify
    00013 // it under the terms of the GNU Library General Public License as published by
    00014 // the Free Software Foundation; either version 2, or (at your option)
    00015 // any later version.
    00016 //
    00017 // The SC Toolkit is distributed in the hope that it will be useful,
    00018 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00019 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00020 // GNU Library General Public License for more details.
    00021 //
    00022 // You should have received a copy of the GNU Library General Public License
    00023 // along with the SC Toolkit; see the file COPYING.LIB.  If not, write to
    00024 // the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
    00025 //
    00026 // The U.S. Government is granted a limited license as per AL 91-7.
    00027 //
    00028
    00029 /* bitarray.h -- definition of the BitArray Class
    00030  *
    00031  *      THIS SOFTWARE FITS THE DESCRIPTION IN THE U.S. COPYRIGHT ACT OF A
    00032  *      "UNITED STATES GOVERNMENT WORK".  IT WAS WRITTEN AS A PART OF THE
    00033  *      AUTHOR'S OFFICIAL DUTIES AS A GOVERNMENT EMPLOYEE.  THIS MEANS IT
    00034  *      CANNOT BE COPYRIGHTED.  THIS SOFTWARE IS FREELY AVAILABLE TO THE
    00035  *      PUBLIC FOR USE WITHOUT A COPYRIGHT NOTICE, AND THERE ARE NO
    00036  *      RESTRICTIONS ON ITS USE, NOW OR SUBSEQUENTLY.
    00037  *
    00038  *  Author:
    00039  *      E. T. Seidl
    00040  *      Bldg. 12A, Rm. 2033
    00041  *      Computer Systems Laboratory
    00042  *      Division of Computer Research and Technology
    00043  *      National Institutes of Health
    00044  *      Bethesda, Maryland 20892
    00045  *      Internet: seidl@alw.nih.gov
    00046  *      July, 1993
    00047  */
    00048
    00049 #ifndef _util_container_bitarray_h
    00050 #define _util_container_bitarray_h
    00051
    00052 #include <string.h>
    00053 #include <stdlib.h>
    00054
    00055 #include <util/misc/formio.h>
    00056
    00057 namespace sc {
    00058
    00059 //
    00060 // class BitArrayLTri is used as the lower triangle of a boolean matrix.
    00061 // rather than storing an int or a char, just use one bit for each, so
    00062 // instead of n(n+1)/2 bytes of storage you have n(n+1)/16 bytes.  A
    00063 // further savings of n bits could be obtained by setting the diagonal to
    00064 // always true or always false depending on the application, but this would
    00065 // probably be more expensive computationally than it's worth.
    00066 //
    00067
    00068 class BitArrayLTri {
    00069   private:
    00070     unsigned char *a;
    00071     int n;
    00072     int nm;
    00073     int na;
    00074
    00075     static int
    00076     ij_offset(int i, int j)
    00077         {
    00078           return (i>j) ? (((i*(i+1)) >> 1) + j) : (((j*(j+1)) >> 1) + i);
    00079         }
    00080
    00081   public:
    00082     BitArrayLTri(int =0, int =0);
    00083     ~BitArrayLTri();
    00084
    00085     void set(unsigned int i) { a[(i>>3)] |= (1 << (i&7)); }
    00086     void set(unsigned int i, unsigned int j) { set(ij_offset(i,j)); }
    00087
    00088     int is_set(unsigned int i, unsigned int j) const
    00089       { int ij = ij_offset(i,j); return (a[(ij>>3)] & (1 << (ij&7))); }
    00090     int is_set(unsigned int i) const
    00091       { return (a[(i>>3)] & (1 << (i&7))); }
    00092
    00093     int operator()(unsigned int i, unsigned int j) const
    00094       { int ij = ij_offset(i,j); return (a[(ij>>3)] & (1 << (ij&7))); }
    00095     int operator()(unsigned int i) const
    00096       { return (a[(i>>3)] & (1 << (i&7))); }
    00097     int operator[](unsigned int i) const
    00098       { return (a[(i>>3)] & (1 << (i&7))); }
    00099
    00100     int dim() const { return na; }
    00101     int nrow() const { return nm; }
    00102     int ncol() const { return nm; }
    00103
    00104     int degree(unsigned int i) const {
    00105       int nedge=0;
    00106       for (int j=0; j < nm; j++) if ((*this)(i,j)) nedge++;
    00107       return nedge;
    00108     }
    00109 };
    00110
    00111 }
    00112
    00113 #endif
    00114
    00115 // Local Variables:
    00116 // mode: c++
    00117 // c-file-style: "ETS"
    00118 // End: