diff options
author | phk <phk@FreeBSD.org> | 1994-08-08 05:52:55 +0000 |
---|---|---|
committer | phk <phk@FreeBSD.org> | 1994-08-08 05:52:55 +0000 |
commit | c8beafaf61a7e1bf16aaef28f9112c7705f4f1f1 (patch) | |
tree | 45b379846d17cbe73053d37a6dc47dae07cdc33d /gnu/lib/libg++/include/BitSet.h | |
parent | 4c5e434fdaef40513ed9bc2059aa202f7e1b9929 (diff) | |
download | FreeBSD-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.h | 374 |
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 |