MPQC  3.0.0-alpha
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 <vector>
53 #include <cstring>
54 #include <cstdlib>
55 
56 #include <util/misc/formio.h>
57 
58 namespace sc {
59 
60 //
61 // class BitArrayLTri is used as the lower triangle of a boolean matrix.
62 // rather than storing an int or a char, just use one bit for each, so
63 // instead of n(n+1)/2 bytes of storage you have n(n+1)/16 bytes. A
64 // further savings of n bits could be obtained by setting the diagonal to
65 // always true or always false depending on the application, but this would
66 // probably be more expensive computationally than it's worth.
67 //
68 
69 class BitArrayLTri {
70  private:
71  std::vector<unsigned char> a;
72  int n;
73  int nm;
74  int na;
75 
76  static int
77  ij_offset(int i, int j)
78  {
79  return (i>j) ? (((i*(i+1)) >> 1) + j) : (((j*(j+1)) >> 1) + i);
80  }
81 
82  public:
83  BitArrayLTri(int =0, int =0);
84  ~BitArrayLTri();
85 
86  void set(unsigned int i) { a[(i>>3)] |= (1 << (i&7)); }
87  void set(unsigned int i, unsigned int j) { set(ij_offset(i,j)); }
88 
89  int is_set(unsigned int i, unsigned int j) const
90  { int ij = ij_offset(i,j); return (a[(ij>>3)] & (1 << (ij&7))); }
91  int is_set(unsigned int i) const
92  { return (a[(i>>3)] & (1 << (i&7))); }
93 
94  int operator()(unsigned int i, unsigned int j) const
95  { int ij = ij_offset(i,j); return (a[(ij>>3)] & (1 << (ij&7))); }
96  int operator()(unsigned int i) const
97  { return (a[(i>>3)] & (1 << (i&7))); }
98  int operator[](unsigned int i) const
99  { return (a[(i>>3)] & (1 << (i&7))); }
100 
101  int dim() const { return na; }
102  int nrow() const { return nm; }
103  int ncol() const { return nm; }
104 
105  int degree(unsigned int i) const {
106  int nedge=0;
107  for (int j=0; j < nm; j++) if ((*this)(i,j)) nedge++;
108  return nedge;
109  }
110 };
111 
112 }
113 
114 #endif
115 
116 // Local Variables:
117 // mode: c++
118 // c-file-style: "ETS"
119 // End:
sc::BitArrayLTri
Definition: bitarray.h:69
sc
Contains all MPQC code up to version 3.
Definition: mpqcin.h:14

Generated at Sun Jan 26 2020 23:24:01 for MPQC 3.0.0-alpha using the documentation package Doxygen 1.8.16.