//
// Copyright (c) 2003 by Stephen C. Dewhurst
// Permission to use, copy, modify, distribute and sell this software for any purpose is
// hereby granted without fee, provided that the above copyright notice appears in all copies
// and that both that copyright notice and this permission notice appear in supporting documentation.
// The author makes no representations about the suitability of this software for any purpose.
// It is provided "as is" without express or implied warranty.
//
// N-ary typeint implementation
//
// Described in CUJ online experts column, June 2003
// 
#ifndef TYPEINT_NARY_H
#define TYPEINT_NARY_H

#include "utils.h"

//
//	Basic Parameterization
//
//	The value L is the number of bits used to represent each
//	fragment of the extended precision integer.  The larger L is,
//	the faster compile time will be and the larger integers can be.
//
//	L must be chosen carefully to satisfy your compiler.
//	Remember that Annex B suggests an implementation support
//	object sizes of only 256*1024==2**18, so the array bound
//	should in the representation should be <= 2**18/sizeof(pointer)
//	probably == 2**16.  Since stored array bounds are incremented
//	by 1, a safer value would be 2**15 (or 2**1, for that matter).
const int L = 15; // number of bits in representation
#define MASK( n ) ((1<<(n))-1)
#define BOUND( b ) ((b)&MASK(L))
#define END( b, n ) ((b) & (MASK(n)<<(L-(n))))
//#define LSLOST( bits, n ) ((bits)&(((1<<(n))-1)<<(L-(n))))>>(L-(n))
#define LSLOST( b, n ) (END(b,n)>>(L-(n)))

//
//	Left Shift
//
template <typename T, int n, int lostbits>
struct LShiftShort {
	typedef T R;
};

template <typename T, int n, int bound, int lostbits>
struct LShiftShort<T(*)[bound],n,lostbits> {
	enum {
		mylostbits = LSLOST(bound-1,n),
		newb = (BOUND((bound-1)<<n) | lostbits) + 1 // limit result to L bits!
	};
	// If mylostbits is non-zero, and this is the last modifier (prev bound==0),
	// then we have to add a new last modifier with the lost bits (otherwise we'd
	// lose the high-order digit).
	typedef typename LShiftShort<T,n,mylostbits>::R Temp;
	typedef Temp (*RR)[newb];
	typedef typename Select<
				(mylostbits && (IsAry<typename Deref<T>::R>::bound==0)),
				RR (*)[mylostbits+1],
				RR
			>::R R;
};

template <typename T, int n>
struct LShift {
	typedef typename LShiftShort<T,n%L,0>::R Temp;
	typedef typename AddPtrAryN<Temp,n/L>::R R;
};

//
//	Right Shift
//
template <typename T, int n>
struct RShiftShort {
	typedef T R;
};

template <typename T, int n, int bound>
struct RShiftShort<T[bound],n> {
	enum {
		pb = IsAry<T>::bound, // previous bound
		fixedpb = pb ? pb-1 : 0, // if prev not array, bound==0, else remove 1 added to avoid 0 bound
		lostbits = fixedpb & ((1<<n)-1), // bits from prev bound lost in shift
		newb = (((bound-1)>>n) | (lostbits<<(L-n))) + 1 // add 1 to fix up
	};
	typedef typename RShiftShort<T,n>::R Temp;
	// if the previous bound is 0, then this is lowest level array mod.
	// if bound is 0, then trim the useless modifier (it's a leading zero, essentially).
	typedef typename Select<
				newb==1 && pb==0,
				Temp,
				Temp(*)[newb]
			>::R R;
};

template <typename T, int n>
struct RShift {
	typedef typename DePtrAryN<T,n/L>::R Temp;
	typedef typename RShiftShort<Temp,n%L>::R R;
};

//
//	Bitwise Or
//
template <typename T1, typename T2>
struct Or;

template <>
struct Or<char,char> {
	typedef char R;
};

template <typename T1, int b1>
struct Or<T1(*)[b1],char> {
	typedef T1 (*R)[b1];
};

template <typename T2, int b2>
struct Or<char, T2(*)[b2]> {
	typedef T2 (*R)[b2];
};

template <typename T1, int b1, typename T2, int b2>
struct Or<T1(*)[b1],T2(*)[b2]> {
	typedef typename Or<T1,T2>::R Temp;
	enum { newbound = ((b1-1) | (b2-1)) + 1 };
	typedef Temp (*R)[newbound];
};

//
//	Bitwise And
//
template <typename T1, typename T2>
struct And;

template <>
struct And<char,char> {
	typedef char R;
};

template <typename T1, int b1, typename T2, int b2>
struct And<T1(*)[b1],T2(*)[b2]> {
	typedef typename And<T1,T2>::R Temp;
	enum { newbound = ((b1-1) & (b2-1)) + 1 };
	// if this is the high-order digit, and it's zero, clip it.
	typedef typename Select<
				(newbound==1) && IsSame<Temp,char>::r,
				char,
				Temp (*) [newbound]
			>::R R;
};

template <typename T1, int b1>
struct And<T1(*)[b1],char> {
	typedef char R;
};

template <typename T2, int b2>
struct And<char, T2(*)[b2]> {
	typedef char R;
};

//
//	Bitwise Xor
//
template <typename T1, typename T2>
struct Xor;

template <>
struct Xor<char,char> {
	typedef char R;
};

template <typename T1, int b1, typename T2, int b2>
struct Xor<T1(*)[b1],T2(*)[b2]> {
	typedef typename Xor<T1,T2>::R Temp;
	enum { newbound = ((b1-1) ^ (b2-1)) + 1 };
	typedef Temp (*R)[newbound];
};

template <typename T1, int b1>
struct Xor<T1(*)[b1],char> {
	typedef T1 (*R)[b1];
};

template <typename T2, int b2>
struct Xor<char, T2(*)[b2]> {
	typedef T2 (*R)[b2];
};

//
//	Addition
//
template <typename T1, typename T2>
struct Add;

template <typename T1, int b1, typename T2, int b2>
struct Add<T1(*)[b1],T2(*)[b2]> { // neither A nor B is 0
	// Approach:  find the sum of more significant bits
	// then modify to take into account least significant bit pos
    typedef typename Add<T1,T2>::R Temp;
    typedef
    	typename Select<
    		((b1-1+b2-1)>BOUND(b1-1+b2-1)), // if there's overflow
    		typename Add<Temp,char(*)[2]>::R, // add one to Temp
    		Temp // otherwise not
    	>::R (*R)[BOUND(b1-1+b2-1)+1];
};

template <typename T1, int b1>
struct Add<T1 (*)[b1],char> {
    typedef T1 (*R)[b1]; // A+0=A
};

template <typename T2, int b2>
struct Add<char,T2 (*)[b2]> {
    typedef T2 (*R)[b2]; // 0+B=B
};

template <>
struct Add<char,char> {
    typedef char R; // 0+0=0
};

//
//	Comparison
//
template <typename T1, typename T2>
struct Comp {
	enum {
		ls = false,
		eql = true,
		gtr = false
	};
};

template <typename T1, int b1, typename T2, int b2>
struct Comp<T1(*)[b1],T2(*)[b2]> {
	enum {
		pls = Comp<T1,T2>::ls,
		peql = Comp<T1,T2>::eql,
		pgtr = Comp<T1,T2>::gtr,
		ls = pls || (peql && b1<b2),
		eql = peql && b1==b2,
		gtr = pgtr || (peql && b1>b2)
	};
};

template <typename T1, int b1, typename T2>
struct Comp<T1(*)[b1],T2> {
	// T1 longer than T2, T1 is greater
	enum {
		ls = false,
		eql = false,
		gtr = true
	};
		
};

template <typename T1, typename T2, int b2>
struct Comp<T1, T2(*)[b2]> {
	// T2 longer than T1, T1 is less
	enum {
		ls = true,
		eql = false,
		gtr = false
	};
};

template <typename T1, typename T2>
struct Less
	{ enum { r = Comp<T1,T2>::ls }; };

template <typename T1, typename T2>
struct LessEqual {
	typedef Comp<T1,T2> C;
	enum { r = C::ls || C::eql };
};

template <typename T1, typename T2>
struct Equal
	{ enum { r = Comp<T1,T2>::eql }; };

template <typename T1, typename T2>
struct NotEqual
	{ enum { r = !Comp<T1,T2>::eql }; };

template <typename T1, typename T2>
struct GreaterEqual {
	typedef Comp<T1,T2> C;
	enum { r = C::gtr || C::eql };
};

template <typename T1, typename T2>
struct Greater
	{ enum { r = Comp<T1,T2>::gtr }; };

//
//	Converting small integers to and from types.
//
template <typename T>
struct Value {
    enum { r = 0 };
};

template <typename T, int bound>
struct Value<T (*) [bound]> {
    enum { r = (Value<T>::r << L) + bound-1 };
};


template <int n>
struct TypeInt {
	typedef typename TypeInt<(n>>L)>::R (*R) [(n&MASK(L))+1]; // add 1 to avoid zero bound
};

template <>
struct TypeInt<0> {
	typedef char R;
};

//
//	Printing big typeints
//
// Just a handy utility for debugging, and is not more generally useful.
// Prints a binary representation.

template <typename T>
struct PrintTypeint;

template <>
struct PrintTypeint<char> {
	static void print() {
		std::cout << "==>";
	}
};

template <typename T, int bound>
struct PrintTypeint<T (*) [bound]> {
	static void print();
};

//#define METROWERKS

template <typename T, int bound>
void PrintTypeint<T(*)[bound]>::print() {
		PrintTypeint<T>::print();
		for( int i = L-1; i >= 0; --i ) {
#ifdef METROWERKS
			// can't seem to reference bound without core dump!?!
			std::cout << 'x';
#else
			const char c = (((bound-1)&(1<<i)) ? '1' : '0');
			std::cout << c;
#endif
		}
		std::cout << '|';
	}

#endif