/*=======================================================================================
	Copyright (c) 2001, Joel de Guzman
	Isis Technologies. All rights reserved.

	Static Sets (stateless sets).
	
	Static sets are parameterized sets that can conceptually hold 
	up to 256 boolean keys. Yet, like magic does not hold any data 
	at all, nil, zilch! The data is encoded completely in its type.
	
	Static Sets are constructed from basic primitives:
	
		Key<v>				key;	Declares a set with a single element v
		Range<start, end>	range;	Declares a set with elements from start to end

	Both keys and ranges are in fact static sets and the 
	usual set operations apply to these:
	
		1) Set negation:	 	~a		Set of all keys not in a
		2) Set union:		 	a | b	Set of keys in a or b
		3) Set intersection: 	a & b	Set of keys in a and b
		4) Set difference:	 	a - b	Set of keys in a but not b
		5) Set xor:			 	a ^ b	Set of keys in a or b but not both
	
	Static sets may be tested for set membership through 
	its IsMember member function:
	
		a_set.IsMember('x');	//	Tests if 'x' is a member of a_set 
		(a | b).IsMember('x');	//	Tests if 'x' is a member of sets a | b
	
	Examples:
	
		Range<'a','z'>	atoz;	//	Set of all lower case characters
		Key<'x'>		x;		//	Set with single element 'x'
		(atoz - x);				//	Yields a set of all lower case characters except 'x'
=======================================================================================*/
#ifndef __Spirit_StaticSet__
#define __Spirit_StaticSet__
#include <Spirit_Basics.h>

/////////////////////////////////////////////////////////////////////////////////////////
namespace Spirit {

/////////////////////////////////////////////////////////////////////////////////////////
//
//	StaticSet class and specializations
//
/////////////////////////////////////////////////////////////////////////////////////////
template <
	uint32 v0_, uint32 v1_, uint32 v2_, uint32 v3_,
	uint32 v4_, uint32 v5_, uint32 v6_, uint32 v7_
>
struct StaticSet {

	enum {
	
		v0 = v0_,	v1 = v1_,	v2 = v2_,	v3 = v3_,
		v4 = v4_,	v5 = v5_,	v6 = v6_,	v7 = v7_
	};

	bool
	IsMember(char ch) const
	{
		//	A reasonably good compiler will optimize this code.
		uint	mask = 1 << (ch & 31);
		switch (ch / 32) {
		
			case 0:		return v0 & mask;
			case 1:		return v1 & mask;
			case 2:		return v2 & mask;
			case 3:		return v3 & mask;
			case 4:		return v4 & mask;
			case 5:		return v5 & mask;
			case 6:		return v6 & mask;
			case 7:		return v7 & mask;
			default:	return false;
		}
	}
};

//////////////////////////////////
template <>
struct StaticSet<0, 0, 0, 0, 0, 0, 0, 0> {

	bool
	IsMember(char ch) const
	{ return false; } 
};

//////////////////////////////////
template <>
struct StaticSet<
	max_uint32, max_uint32, max_uint32, max_uint32, 
	max_uint32, max_uint32, max_uint32, max_uint32> {

	bool
	IsMember(char ch) const
	{ return true; } 
};

/////////////////////////////////////////////////////////////////////////////////////////
//
//	Key class
//
/////////////////////////////////////////////////////////////////////////////////////////
namespace Impl {

	template <char ch, char msb = ch / 32>	struct Key2Set {};

	template <char ch> struct Key2Set<ch, 0>	{ typedef StaticSet<1 << (ch & 31), 0, 0, 0, 0, 0, 0, 0> T; };
	template <char ch> struct Key2Set<ch, 1>	{ typedef StaticSet<0, 1 << (ch & 31), 0, 0, 0, 0, 0, 0> T; };
	template <char ch> struct Key2Set<ch, 2> 	{ typedef StaticSet<0, 0, 1 << (ch & 31), 0, 0, 0, 0, 0> T; };
	template <char ch> struct Key2Set<ch, 3> 	{ typedef StaticSet<0, 0, 0, 1 << (ch & 31), 0, 0, 0, 0> T; };
	template <char ch> struct Key2Set<ch, 4> 	{ typedef StaticSet<0, 0, 0, 0, 1 << (ch & 31), 0, 0, 0> T; };
	template <char ch> struct Key2Set<ch, 5> 	{ typedef StaticSet<0, 0, 0, 0, 0, 1 << (ch & 31), 0, 0> T; };
	template <char ch> struct Key2Set<ch, 6> 	{ typedef StaticSet<0, 0, 0, 0, 0, 0, 1 << (ch & 31), 0> T; };
	template <char ch> struct Key2Set<ch, 7> 	{ typedef StaticSet<0, 0, 0, 0, 0, 0, 0, 1 << (ch & 31)> T; };
}

//////////////////////////////////
template <char ch_>
struct Key : public Impl::Key2Set<ch_>::T {

	static char const	ch = ch_;

	bool	IsMember(char ch__) const 
	{ return ch__ == ch; }
};

/////////////////////////////////////////////////////////////////////////////////////////
//
//	Range class
//
/////////////////////////////////////////////////////////////////////////////////////////
namespace Impl {

	//////////////////////////////////
	template <char start, char end, bool forward = start < end>
	struct RangeBase {};
	
	//////////////////////////////////
	template <char start, char end>
	struct RangeBase<start, end, true> {

		enum {
		
			full = max_uint32,
			lmask = full << (start & 31),
			rmask = full >> (31 - (end & 31)),
			lindex = start / 32,
			rindex = end / 32,

			v0l = lindex == 0 ? lmask : lindex > 0 ? 0 : full,
			v1l = lindex == 1 ? lmask : lindex > 1 ? 0 : full,
			v2l = lindex == 2 ? lmask : lindex > 2 ? 0 : full,
			v3l = lindex == 3 ? lmask : lindex > 3 ? 0 : full,
			v4l = lindex == 4 ? lmask : lindex > 4 ? 0 : full,
			v5l = lindex == 5 ? lmask : lindex > 5 ? 0 : full,
			v6l = lindex == 6 ? lmask : lindex > 6 ? 0 : full,
			v7l = lindex == 7 ? lmask : full,

			v0r = rindex == 0 ? rmask : full,
			v1r = rindex == 1 ? rmask : rindex < 1 ? 0 : full,
			v2r = rindex == 2 ? rmask : rindex < 2 ? 0 : full,
			v3r = rindex == 3 ? rmask : rindex < 3 ? 0 : full,
			v4r = rindex == 4 ? rmask : rindex < 4 ? 0 : full,
			v5r = rindex == 5 ? rmask : rindex < 5 ? 0 : full,
			v6r = rindex == 6 ? rmask : rindex < 6 ? 0 : full,
			v7r = rindex == 7 ? rmask : rindex < 7 ? 0 : full,
		};
		
		typedef StaticSet<v0l & v0r, v1l & v1r, v2l & v2r, v3l & v3r, 
					v4l & v4r, v5l & v5r, v6l & v6r, v7l & v7r>	T;
		
		bool	IsMember(char ch) const 
		{ return ch >= start && ch <= end; }
	};

	//////////////////////////////////
	template <char start, char end>
	struct RangeBase<start, end, false> 
		: public RangeBase<end, start, true> {};
}

//////////////////////////////////
template <char start, char end>
struct Range : 
	public Impl::RangeBase<start, end>, 
	public Impl::RangeBase<start, end>::T {

	using Impl::RangeBase<start, end>::IsMember; 
};

/////////////////////////////////////////////////////////////////////////////////////////
//
//	StaticSet operations
//
/////////////////////////////////////////////////////////////////////////////////////////
//
//	Set Negation:	~a
//
//////////////////////////////////
template <
	uint32 v0, uint32 v1, uint32 v2, uint32 v3,
	uint32 v4, uint32 v5, uint32 v6, uint32 v7>
inline StaticSet<~v0, ~v1, ~v2, ~v3, ~v4, ~v5, ~v6, ~v7>
operator ~ (StaticSet<v0, v1, v2, v3, v4, v5, v6, v7>)
{
	return StaticSet<~v0, ~v1, ~v2, ~v3, ~v4, ~v5, ~v6, ~v7>();
}

//////////////////////////////////
//
//	Set Union:	a | b	
//
//////////////////////////////////
template <
	uint32 v0A, uint32 v1A, uint32 v2A, uint32 v3A,
	uint32 v4A, uint32 v5A, uint32 v6A, uint32 v7A,
	uint32 v0B, uint32 v1B, uint32 v2B, uint32 v3B,
	uint32 v4B, uint32 v5B, uint32 v6B, uint32 v7B>
inline StaticSet<
	v0A | v0B, v1A | v1B, v2A | v2B, v3A | v3B, 
	v4A | v4B, v5A | v5B, v6A | v6B, v7A | v7B>
operator | (StaticSet<v0A, v1A, v2A, v3A, v4A, v5A, v6A, v7A>,
			StaticSet<v0B, v1B, v2B, v3B, v4B, v5B, v6B, v7B>)
{
	return StaticSet<
			v0A | v0B, v1A | v1B, v2A | v2B, v3A | v3B, 
			v4A | v4B, v5A | v5B, v6A | v6B, v7A | v7B>();
}

//////////////////////////////////
//
//	Set Difference:	a - b
//
//////////////////////////////////
template <
	uint32 v0A, uint32 v1A, uint32 v2A, uint32 v3A,
	uint32 v4A, uint32 v5A, uint32 v6A, uint32 v7A,
	uint32 v0B, uint32 v1B, uint32 v2B, uint32 v3B,
	uint32 v4B, uint32 v5B, uint32 v6B, uint32 v7B>
inline StaticSet<
	v0A & ~v0B, v1A & ~v1B, v2A & ~v2B, v3A & ~v3B, 
	v4A & ~v4B, v5A & ~v5B, v6A & ~v6B, v7A & ~v7B>
operator - (StaticSet<v0A, v1A, v2A, v3A, v4A, v5A, v6A, v7A>,
			StaticSet<v0B, v1B, v2B, v3B, v4B, v5B, v6B, v7B>)
{
	return StaticSet<
			v0A & ~v0B, v1A & ~v1B, v2A & ~v2B, v3A & ~v3B, 
			v4A & ~v4B, v5A & ~v5B, v6A & ~v6B, v7A & ~v7B>();
}

//////////////////////////////////
//
//	Set Intersection:	a & b
//
//////////////////////////////////
template <
	uint32 v0A, uint32 v1A, uint32 v2A, uint32 v3A,
	uint32 v4A, uint32 v5A, uint32 v6A, uint32 v7A,
	uint32 v0B, uint32 v1B, uint32 v2B, uint32 v3B,
	uint32 v4B, uint32 v5B, uint32 v6B, uint32 v7B>
inline StaticSet<
	v0A & v0B, v1A & v1B, v2A & v2B, v3A & v3B, 
	v4A & v4B, v5A & v5B, v6A & v6B, v7A & v7B>
operator & (StaticSet<v0A, v1A, v2A, v3A, v4A, v5A, v6A, v7A>,
			StaticSet<v0B, v1B, v2B, v3B, v4B, v5B, v6B, v7B>)
{
	return StaticSet<
			v0A & v0B, v1A & v1B, v2A & v2B, v3A & v3B, 
			v4A & v4B, v5A & v5B, v6A & v6B, v7A & v7B>();
}

//////////////////////////////////
//
//	Set Xor:	a ^ b
//
//////////////////////////////////
template <
	uint32 v0A, uint32 v1A, uint32 v2A, uint32 v3A,
	uint32 v4A, uint32 v5A, uint32 v6A, uint32 v7A,
	uint32 v0B, uint32 v1B, uint32 v2B, uint32 v3B,
	uint32 v4B, uint32 v5B, uint32 v6B, uint32 v7B>
inline StaticSet<
	v0A ^ v0B, v1A ^ v1B, v2A ^ v2B, v3A ^ v3B, 
	v4A ^ v4B, v5A ^ v5B, v6A ^ v6B, v7A ^ v7B>
operator ^ (StaticSet<v0A, v1A, v2A, v3A, v4A, v5A, v6A, v7A>,
			StaticSet<v0B, v1B, v2B, v3B, v4B, v5B, v6B, v7B>)
{
	return StaticSet<
			v0A ^ v0B, v1A ^ v1B, v2A ^ v2B, v3A ^ v3B, 
			v4A ^ v4B, v5A ^ v5B, v6A ^ v6B, v7A ^ v7B>();
}

/////////////////////////////////////////////////////////////////////////////////////////
}	//	namespace Spirit

#endif