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