MPQC 2.3.1

- Main Page
- Related Pages
- Classes
- Files

- File List

bitarray.h
1 //
2 // bitarray.h
3 //
4 // Modifications are
5 // Copyright (C) 1996 Limit Point Systems, Inc.
6 //
7 // Author: Edward Seidl <seidl@janed.com>
8 // Maintainer: LPS
9 //
10 // This file is part of the SC Toolkit.
11 //
12 // The SC Toolkit is free software; you can redistribute it and/or modify
13 // it under the terms of the GNU Library General Public License as published by
14 // the Free Software Foundation; either version 2, or (at your option)
15 // any later version.
16 //
17 // The SC Toolkit is distributed in the hope that it will be useful,
18 // but WITHOUT ANY WARRANTY; without even the implied warranty of
19 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 // GNU Library General Public License for more details.
21 //
22 // You should have received a copy of the GNU Library General Public License
23 // along with the SC Toolkit; see the file COPYING.LIB. If not, write to
24 // the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
25 //
26 // The U.S. Government is granted a limited license as per AL 91-7.
27 //
28
29 /* bitarray.h -- definition of the BitArray Class
30 *
31 * THIS SOFTWARE FITS THE DESCRIPTION IN THE U.S. COPYRIGHT ACT OF A
32 * "UNITED STATES GOVERNMENT WORK". IT WAS WRITTEN AS A PART OF THE
33 * AUTHOR'S OFFICIAL DUTIES AS A GOVERNMENT EMPLOYEE. THIS MEANS IT
34 * CANNOT BE COPYRIGHTED. THIS SOFTWARE IS FREELY AVAILABLE TO THE
35 * PUBLIC FOR USE WITHOUT A COPYRIGHT NOTICE, AND THERE ARE NO
36 * RESTRICTIONS ON ITS USE, NOW OR SUBSEQUENTLY.
37 *
38 * Author:
39 * E. T. Seidl
40 * Bldg. 12A, Rm. 2033
41 * Computer Systems Laboratory
42 * Division of Computer Research and Technology
43 * National Institutes of Health
44 * Bethesda, Maryland 20892
45 * Internet: seidl@alw.nih.gov
46 * July, 1993
47 */
48
49 #ifndef _util_container_bitarray_h
50 #define _util_container_bitarray_h
51
52 #include <string.h>
53 #include <stdlib.h>
54
55 #include <util/misc/formio.h>
56
57 namespace sc {
58
59 //
60 // class BitArrayLTri is used as the lower triangle of a boolean matrix.
61 // rather than storing an int or a char, just use one bit for each, so
62 // instead of n(n+1)/2 bytes of storage you have n(n+1)/16 bytes. A
63 // further savings of n bits could be obtained by setting the diagonal to
64 // always true or always false depending on the application, but this would
65 // probably be more expensive computationally than it's worth.
66 //
67
68 class BitArrayLTri {
69 private:
70 unsigned char *a;
71 int n;
72 int nm;
73 int na;
74
75 static int
76 ij_offset(int i, int j)
77 {
78 return (i>j) ? (((i*(i+1)) >> 1) + j) : (((j*(j+1)) >> 1) + i);
79 }
80
81 public:
82 BitArrayLTri(int =0, int =0);
83 ~BitArrayLTri();
84
85 void set(unsigned int i) { a[(i>>3)] |= (1 << (i&7)); }
86 void set(unsigned int i, unsigned int j) { set(ij_offset(i,j)); }
87
88 int is_set(unsigned int i, unsigned int j) const
89 { int ij = ij_offset(i,j); return (a[(ij>>3)] & (1 << (ij&7))); }
90 int is_set(unsigned int i) const
91 { return (a[(i>>3)] & (1 << (i&7))); }
92
93 int operator()(unsigned int i, unsigned int j) const
94 { int ij = ij_offset(i,j); return (a[(ij>>3)] & (1 << (ij&7))); }
95 int operator()(unsigned int i) const
96 { return (a[(i>>3)] & (1 << (i&7))); }
97 int operator[](unsigned int i) const
98 { return (a[(i>>3)] & (1 << (i&7))); }
99
100 int dim() const { return na; }
101 int nrow() const { return nm; }
102 int ncol() const { return nm; }
103
104 int degree(unsigned int i) const {
105 int nedge=0;
106 for (int j=0; j < nm; j++) if ((*this)(i,j)) nedge++;
107 return nedge;
108 }
109 };
110
111 }
112
113 #endif
114
115 // Local Variables:
116 // mode: c++
117 // c-file-style: "ETS"
118 // End: