summaryrefslogtreecommitdiffstats
path: root/gnu/lib/libg++/include/BitSet.h
diff options
context:
space:
mode:
authorphk <phk@FreeBSD.org>1994-08-08 05:52:55 +0000
committerphk <phk@FreeBSD.org>1994-08-08 05:52:55 +0000
commitc8beafaf61a7e1bf16aaef28f9112c7705f4f1f1 (patch)
tree45b379846d17cbe73053d37a6dc47dae07cdc33d /gnu/lib/libg++/include/BitSet.h
parent4c5e434fdaef40513ed9bc2059aa202f7e1b9929 (diff)
downloadFreeBSD-src-c8beafaf61a7e1bf16aaef28f9112c7705f4f1f1.zip
FreeBSD-src-c8beafaf61a7e1bf16aaef28f9112c7705f4f1f1.tar.gz
I belive this should be makeable under 2.0. There may be outstanding
issues in these areas: .h's installed .hP's installed -lcurses interaction files needed in ~/legal for copyleft reasons.
Diffstat (limited to 'gnu/lib/libg++/include/BitSet.h')
-rw-r--r--gnu/lib/libg++/include/BitSet.h374
1 files changed, 374 insertions, 0 deletions
diff --git a/gnu/lib/libg++/include/BitSet.h b/gnu/lib/libg++/include/BitSet.h
new file mode 100644
index 0000000..ca1d96f
--- /dev/null
+++ b/gnu/lib/libg++/include/BitSet.h
@@ -0,0 +1,374 @@
+// This may look like C code, but it is really -*- C++ -*-
+/*
+Copyright (C) 1988 Free Software Foundation
+ written by Doug Lea (dl@rocky.oswego.edu)
+
+This file is part of the GNU C++ Library. This library 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 of the License, or (at your
+option) any later version. This library 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 this library; if not, write to the Free Software
+Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
+*/
+
+#ifndef _BitSet_h
+#ifdef __GNUG__
+#pragma interface
+#endif
+
+#define _BitSet_h 1
+
+#include <iostream.h>
+#include <limits.h>
+
+#define BITSETBITS (sizeof(short) * CHAR_BIT)
+
+struct BitSetRep
+{
+ unsigned short len; // number of shorts in s
+ unsigned short sz; // allocated slots
+ unsigned short virt; // virtual 0 or 1
+ unsigned short s[1]; // bits start here
+};
+
+extern BitSetRep* BitSetalloc(BitSetRep*, const unsigned short*,
+ int, int, int);
+extern BitSetRep* BitSetcopy(BitSetRep*, const BitSetRep*);
+extern BitSetRep* BitSetresize(BitSetRep*, int);
+extern BitSetRep* BitSetop(const BitSetRep*, const BitSetRep*,
+ BitSetRep*, char);
+extern BitSetRep* BitSetcmpl(const BitSetRep*, BitSetRep*);
+
+
+extern BitSetRep _nilBitSetRep;
+
+class BitSet;
+
+class BitSetBit
+{
+protected:
+ BitSet* src;
+ unsigned long pos;
+
+ public:
+ BitSetBit(BitSet* v, int p);
+ BitSetBit(const BitSetBit& b);
+ ~BitSetBit();
+ operator int() const;
+ int operator = (int b);
+ int operator = (const BitSetBit& b);
+};
+
+class BitSet
+{
+protected:
+ BitSetRep* rep;
+
+
+public:
+
+// constructors
+ BitSet();
+ BitSet(const BitSet&);
+
+ ~BitSet();
+
+ BitSet& operator = (const BitSet& y);
+
+// equality & subset tests
+
+ friend int operator == (const BitSet& x, const BitSet& y);
+ friend int operator != (const BitSet& x, const BitSet& y);
+ friend int operator < (const BitSet& x, const BitSet& y);
+ friend int operator <= (const BitSet& x, const BitSet& y);
+ friend int operator > (const BitSet& x, const BitSet& y);
+ friend int operator >= (const BitSet& x, const BitSet& y);
+
+
+// operations on self
+
+ BitSet& operator |= (const BitSet& y);
+ BitSet& operator &= (const BitSet& y);
+ BitSet& operator -= (const BitSet& y);
+ BitSet& operator ^= (const BitSet& y);
+
+ void complement();
+
+// individual bit manipulation
+
+ void set(int pos);
+ void set(int from, int to);
+ void set(); // set all
+
+ void clear(int pos);
+ void clear(int from, int to);
+ void clear(); // clear all
+
+ void invert(int pos);
+ void invert(int from, int to);
+
+ int test(int pos) const;
+ int test(int from, int to) const;
+
+ BitSetBit operator [] (int i);
+
+// iterators
+
+ int first(int b = 1) const;
+ int last(int b = 1) const;
+
+ int next(int pos, int b = 1) const;
+ int prev(int pos, int b = 1) const;
+ int previous(int pos, int b = 1) const /* Obsolete synonym */
+ { return prev(pos, b); }
+
+// status
+
+ int empty() const;
+ int virtual_bit() const;
+ int count(int b = 1) const;
+
+// convertors & IO
+
+ friend BitSet atoBitSet(const char* s,
+ char f='0', char t='1', char star='*');
+ // BitSettoa is deprecated; do not use in new programs.
+ friend const char* BitSettoa(const BitSet& x,
+ char f='0', char t='1', char star='*');
+
+ friend BitSet shorttoBitSet(unsigned short w);
+ friend BitSet longtoBitSet(unsigned long w);
+
+ friend ostream& operator << (ostream& s, const BitSet& x);
+ void printon(ostream& s,
+ char f='0', char t='1', char star='*') const;
+
+// procedural versions of operators
+
+ friend void and(const BitSet& x, const BitSet& y, BitSet& r);
+ friend void or(const BitSet& x, const BitSet& y, BitSet& r);
+ friend void xor(const BitSet& x, const BitSet& y, BitSet& r);
+ friend void diff(const BitSet& x, const BitSet& y, BitSet& r);
+ friend void complement(const BitSet& x, BitSet& r);
+
+// misc
+
+ void error(const char* msg) const;
+ int OK() const;
+};
+
+
+typedef BitSet BitSetTmp;
+
+
+ BitSet operator | (const BitSet& x, const BitSet& y);
+ BitSet operator & (const BitSet& x, const BitSet& y);
+ BitSet operator - (const BitSet& x, const BitSet& y);
+ BitSet operator ^ (const BitSet& x, const BitSet& y);
+
+ BitSet operator ~ (const BitSet& x);
+
+// These are inlined regardless of optimization
+
+inline int BitSet_index(int l)
+{
+ return (unsigned)(l) / BITSETBITS;
+}
+
+inline int BitSet_pos(int l)
+{
+ return l & (BITSETBITS - 1);
+}
+
+
+inline BitSet::BitSet() : rep(&_nilBitSetRep) {}
+
+inline BitSet::BitSet(const BitSet& x) :rep(BitSetcopy(0, x.rep)) {}
+
+inline BitSet::~BitSet() { if (rep != &_nilBitSetRep) delete rep; }
+
+inline BitSet& BitSet::operator = (const BitSet& y)
+{
+ rep = BitSetcopy(rep, y.rep);
+ return *this;
+}
+
+inline int operator != (const BitSet& x, const BitSet& y) { return !(x == y); }
+
+inline int operator > (const BitSet& x, const BitSet& y) { return y < x; }
+
+inline int operator >= (const BitSet& x, const BitSet& y) { return y <= x; }
+
+inline void and(const BitSet& x, const BitSet& y, BitSet& r)
+{
+ r.rep = BitSetop(x.rep, y.rep, r.rep, '&');
+}
+
+inline void or(const BitSet& x, const BitSet& y, BitSet& r)
+{
+ r.rep = BitSetop(x.rep, y.rep, r.rep, '|');
+}
+
+inline void xor(const BitSet& x, const BitSet& y, BitSet& r)
+{
+ r.rep = BitSetop(x.rep, y.rep, r.rep, '^');
+}
+
+inline void diff(const BitSet& x, const BitSet& y, BitSet& r)
+{
+ r.rep = BitSetop(x.rep, y.rep, r.rep, '-');
+}
+
+inline void complement(const BitSet& x, BitSet& r)
+{
+ r.rep = BitSetcmpl(x.rep, r.rep);
+}
+
+#if defined(__GNUG__) && !defined(_G_NO_NRV)
+
+inline BitSet operator & (const BitSet& x, const BitSet& y) return r
+{
+ and(x, y, r);
+}
+
+inline BitSet operator | (const BitSet& x, const BitSet& y) return r
+{
+ or(x, y, r);
+}
+
+inline BitSet operator ^ (const BitSet& x, const BitSet& y) return r
+{
+ xor(x, y, r);
+}
+
+inline BitSet operator - (const BitSet& x, const BitSet& y) return r
+{
+ diff(x, y, r);
+}
+
+inline BitSet operator ~ (const BitSet& x) return r
+{
+ ::complement(x, r);
+}
+
+#else /* NO_NRV */
+
+inline BitSet operator & (const BitSet& x, const BitSet& y)
+{
+ BitSet r; and(x, y, r); return r;
+}
+
+inline BitSet operator | (const BitSet& x, const BitSet& y)
+{
+ BitSet r; or(x, y, r); return r;
+}
+
+inline BitSet operator ^ (const BitSet& x, const BitSet& y)
+{
+ BitSet r; xor(x, y, r); return r;
+}
+
+inline BitSet operator - (const BitSet& x, const BitSet& y)
+{
+ BitSet r; diff(x, y, r); return r;
+}
+
+inline BitSet operator ~ (const BitSet& x)
+{
+ BitSet r; ::complement(x, r); return r;
+}
+
+#endif
+
+inline BitSet& BitSet::operator &= (const BitSet& y)
+{
+ and(*this, y, *this);
+ return *this;
+}
+
+inline BitSet& BitSet::operator |= (const BitSet& y)
+{
+ or(*this, y, *this);
+ return *this;
+}
+
+inline BitSet& BitSet::operator ^= (const BitSet& y)
+{
+ xor(*this, y, *this);
+ return *this;
+}
+
+inline BitSet& BitSet::operator -= (const BitSet& y)
+{
+ diff(*this, y, *this);
+ return *this;
+}
+
+
+inline void BitSet::complement()
+{
+ ::complement(*this, *this);
+}
+
+inline int BitSet::virtual_bit() const
+{
+ return rep->virt;
+}
+
+inline int BitSet::first(int b) const
+{
+ return next(-1, b);
+}
+
+inline int BitSet::test(int p) const
+{
+ if (p < 0) error("Illegal bit index");
+ int index = BitSet_index(p);
+ return (index >= rep->len)? rep->virt :
+ ((rep->s[index] & (1 << BitSet_pos(p))) != 0);
+}
+
+
+inline void BitSet::set()
+{
+ rep = BitSetalloc(rep, 0, 0, 1, 0);
+}
+
+inline BitSetBit::BitSetBit(const BitSetBit& b) :src(b.src), pos(b.pos) {}
+
+inline BitSetBit::BitSetBit(BitSet* v, int p)
+{
+ src = v; pos = p;
+}
+
+inline BitSetBit::~BitSetBit() {}
+
+inline BitSetBit::operator int() const
+{
+ return src->test(pos);
+}
+
+inline int BitSetBit::operator = (int b)
+{
+ if (b) src->set(pos); else src->clear(pos); return b;
+}
+
+inline int BitSetBit::operator = (const BitSetBit& b)
+{
+ int i = (int)b;
+ *this = i;
+ return i;
+}
+
+inline BitSetBit BitSet::operator [] (int i)
+{
+ if (i < 0) error("illegal bit index");
+ return BitSetBit(this, i);
+}
+
+#endif
OpenPOWER on IntegriCloud