#ifndef __ISET_INCLUDED__
#define __ISET_INCLUDED__

#ifndef __ARRAY_INCLUDED__
#include "array.h"
#endif

#ifndef __TWO_INCLUDED__
#include "two.h"
#endif

class ISet {	// dense set of small integers, implemented using a bit array
public:
	ISet() {
	}
	~ISet() {
	}
	void reset() {
		rgw.reset();
	}
	BOOL __fastcall contains(unsigned i) const {
		return (i < size()) && (word(i) & bitmask(i));
	}
	BOOL __fastcall add(unsigned i) {
		if (!ensureRoomFor(i))
			return FALSE;
		word(i) |= bitmask(i);
		return TRUE;
	}
	unsigned __fastcall size() const {
		return rgw.size() << lgBPW;
	}
	BOOL __fastcall remove(unsigned i) {
		if (i < size())
			word(i) &= ~bitmask(i);
		return TRUE;
	}
	unsigned cardinality() const {
		unsigned n = 0;
		for (unsigned i = 0; i < rgw.size(); i++)
			n += bitcount(rgw[i]);
		return n;
	}
	friend BOOL intersect(const ISet& s1, const ISet& s2, ISet& iset) {
		iset.reset();
		if (iset.rgw.setSize(min(s1.rgw.size(), s2.rgw.size()))) {
			for (unsigned i = 0; i < iset.rgw.size(); i++)
				iset.rgw[i] = s1.rgw[i] & s2.rgw[i];
			return TRUE;
		} else {
			return FALSE;
		}
	}
	BOOL save(Buffer* pbuf) {
		return rgw.save(pbuf);
	}
	BOOL reload(PB* ppb) {
		return rgw.reload(ppb);
	}
	void swap(ISet& is) {
		rgw.swap(is.rgw);
	}
	CB cbSave() const {
		return rgw.cbSave();
	}
private:
	enum { BPW = 32, lgBPW = 5 };
	Array<ulong> rgw;

	ISet(const ISet&);
	unsigned __fastcall index(unsigned i) const {
		return i >> lgBPW;
	}
	unsigned __fastcall words(unsigned i) const {
		return index(i) + 1;
	}
	unsigned __fastcall bit(unsigned i) const {
		return i & (BPW-1);
	}
	ulong& __fastcall word(unsigned i) {
		return rgw[index(i)];
	}
	const ulong& __fastcall word(unsigned i) const {
		return rgw[index(i)];
	}
	ulong bitmask(unsigned i) const {
		return 1 << bit(i);
	}
  	BOOL ensureRoomFor(unsigned i) {
		unsigned long zero = 0;
		while (words(i) > (unsigned)rgw.size())
			if (!rgw.append(zero))
				return FALSE;
		return TRUE;
	}
};

#endif // !__ISET_INCLUDED__