/usr/include/sc/util/container/bitarray.h is in libsc-dev 2.3.1-16.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | //
// 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:
|