//
// Copyright (c) 2002 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 or makes no representations about the suitability of this software for any purpose.
// It is provided "as is" without express or implied warranty.
//
// "typeint" implementation
//
// Described in CUJ online experts column, February 2003
// 
#ifndef TYPEINT_H
#define TYPEINT_H

#include "utils.h"
#include <iostream>
#include <limits>

//
// Number of bits
//
template <typename T>
struct Len {
	enum { r = Len<typename Deref<T>::R>::r + 1 };
};

template <>
struct Len<char> {
	enum { r = 0 };
};

//
//	Addition
//
// Technique:  use a compile time switch
template <typename A, typename B>
struct Add;

template <int n, typename A, typename B>
struct AddImpl;

template <typename A, typename B>
struct AddImpl<3,A,B> { // 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 Deref<A>::R DA;
    typedef typename Deref<B>::R DB;
    typedef typename Add<DA,DB>::R Temp;
    typedef
    	typename Select<
    		IsConst<A>::r&&IsConst<B>::r, // if both bits are 1
    		typename Add<Temp,char *const>::R *, // add one to Temp, lower bit is 0
    		typename Select<
    			IsConst<A>::r||IsConst<B>::r, // else if one bit is 1
    			Temp *const, // lower bit is one
    			Temp * // else it's 0
    		>::R
    	>::R R;
};

template <typename A, typename B>
struct AddImpl<2,A,B> {
    typedef A R; // A+0=A
};

template <typename A, typename B>
struct AddImpl<1,A,B> {
    typedef B R; // 0+B=B
};

template <typename A, typename B>
struct AddImpl<0,A,B> {
    typedef char R; // 0+0=0
};

template <typename A, typename B>
struct Add {
	enum { switchval = IsPtr<A>::r*2 + IsPtr<B>::r };
	typedef typename AddImpl<switchval,A,B>::R R;
};

//
//	Subtract 1
//
template <typename T>
struct Sub1;

template <typename T>
struct Sub1<T *const> {
	typedef T *R;
};

template <typename T>
struct Sub1<T *> {
	typedef typename Sub1<T>::R *const R;
};

template <>
struct Sub1<char *const> {
	typedef char R;
};

//
//	Left shift
//

template <typename T, int n>
struct LShift {
	typedef typename LShift<T,n-1>::R *R;
};

template <typename T>
struct LShift<T,0> {
	typedef T R;
};

// need to avoid shifting zeros
template <int n>
struct LShift<char,n> {
	typedef char R;
};

template <>
struct LShift<char,0> {
	typedef char R;
};

//
//	Right shift
//

template <typename T, int n>
struct RShift {
	// Note: Deref has no effect if not a ref, so OK if n>#refs
	typedef typename Deref<typename RShift<T,n-1>::R>::R R;
};

template <typename T>
struct RShift<T,0> {
	typedef T R;
};


//
//	Multiplication
//
// As noted in the article, this multiplication algorithm is simple, but
// has quadratic complexity.  An improved version, along with a more general
// subtraction algorithm, will be presented in the April, 2003 CUJ.
template <typename A, typename B>
struct Mul; // no definition of primary

template <typename A>
struct Mul<A,char> // A * 0 == 0
{ typedef char R; };

template <typename A, typename B>
struct Mul<A,B *> // 0 digit, just shift: A*B0 == (A*B)<<1
{ typedef typename Mul<A,B>::R *R; };

template <typename A, typename B>
struct Mul<A,B *const> { // 1 digit, shift and add: A*B1 == ((A*B)<<1)+A
	typedef typename Mul<A,B>::R *Tmp;
	typedef typename Add<Tmp,A>::R R;
};

template <typename A>
struct Mul<A,char *const> // for high-order bit, to avoid a char * typeint
{ typedef A R; };

//
//	Bitwise Or
//
// Technique:  use exhaustive specialization instead of switch.
template <typename A, typename B>
struct Or
	{ typedef char R; };

template <typename A, typename B>
struct Or<A *,B *>
	{ typedef typename Or<A,B>::R *R; };

template <typename A, typename B>
struct Or<A *const,B *>
	{ typedef typename Or<A,B>::R *const R; };

template <typename A, typename B>
struct Or<A *,B *const>
	{ typedef typename Or<A,B>::R *const R; };

template <typename A, typename B>
struct Or<A *const,B *const>
	{ typedef typename Or<A,B>::R *const R; };

template <typename A, typename B>
struct Or<A,B *>
	{ typedef B *R; };

template <typename A, typename B>
struct Or<A,B *const>
	{ typedef B *const R; };

template <typename A, typename B>
struct Or<A *,B>
	{ typedef A *R; };

template <typename A, typename B>
struct Or<A *const,B>
	{ typedef A *const R; };

//
//	Bitwise And
//
// Technique:  use exhaustive specialization instead of switch.
template <typename A, typename B>
struct And // at least one of A or B is 0
	{ typedef char R; };

template <typename A, typename B>
struct And<A *,B *>
	{ typedef typename And<A,B>::R *R; };

template <typename A, typename B>
struct And<A *const,B *>
	{ typedef typename And<A,B>::R *R; };

template <typename A, typename B>
struct And<A *,B *const>
	{ typedef typename And<A,B>::R *R; };

template <typename A, typename B>
struct And<A *const,B *const>
	{ typedef typename And<A,B>::R *const R; };

//
//	Bitwise Xor
//
// Technique:  use exhaustive specialization instead of switch.
template <typename A, typename B>
struct Xor
	{ typedef char R; };

template <typename A, typename B>
struct Xor<A *,B *>
	{ typedef typename Xor<A,B>::R *R; };

template <typename A, typename B>
struct Xor<A *const,B *>
	{ typedef typename Xor<A,B>::R *const R; };

template <typename A, typename B>
struct Xor<A *,B *const>
	{ typedef typename Xor<A,B>::R *const R; };

template <typename A, typename B>
struct Xor<A *const,B *const>
	{ typedef typename Xor<A,B>::R *R; };

template <typename A, typename B>
struct Xor<A,B *>
	{ typedef B *R; };

template <typename A, typename B>
struct Xor<A,B *const>
	{ typedef B *const R; };

template <typename A, typename B>
struct Xor<A *,B>
	{ typedef A *R; };

template <typename A, typename B>
struct Xor<A *const,B>
	{ typedef A *const R; };
	
//
//	Bitwise not (~)
//
//	The semantics of this bitwise not are a little unconventional,
//	since inversion doesn't make a lot of sense in a variable length
//	integer such as a typeint.  For example, applying Not to a typeint
//	of a given length always results in a shorter typeint.  (Since this
//	typeint representation has no leading zeros.)  Therefore inverting a
//	typint twice will not restore the original value.  Repeated application
//	of Not will produce a zero (char) result.  (This might be useful as a means
//	of counting runs of ones and zeros in the binary analog of a particular typeint.)

//	Note: for those who care about such things, the above is what's
//	known as (or should be known as) a rhophalic comment.
template <typename A>
struct Not
	{ typedef char R; };

template <typename A>
struct Not<A *>
	{ typedef typename Not<A>::R *const R; };

template <typename A>
struct Not<A *const> {
	typedef typename Not<A>::R Temp;
	typedef typename Select<IsPtr<Temp>::r,
		Temp *,
		char
	>::R R;
};

//
//	Comparing typeints.
//

// Technique:  Using the primary template to catch meaningless expansions,
// to avoid having to go indirect with implementation of a compile time if.
template <typename A, typename B>
struct Comp {
	enum {
		// These results mean nothing, because Comp compares only
		// equal-length typeints, and the specializations already
		// handle all legal possibilities.
		// This will be instantiated, but the results will never be used.
		ls = 0xDEAD,
		eq = 0xBEEF
	};
};

template <>
struct Comp<char,char> {
	enum {
		ls = false,
		eq = true
	};
};

template <typename A, typename B>
struct Comp<A *,B *> {
	enum {
		ls = Comp<A,B>::ls,
		eq = Comp<A,B>::eq
	};
};

template <typename A, typename B>
struct Comp<A *, B *const> {
	enum {
		ls = Comp<A,B>::ls || Comp<A,B>::eq,
		eq = false
	};
};

template <typename A, typename B>
struct Comp<A *const, B *> {
	enum {
		ls = Comp<A,B>::ls,
		eq = false
	};
};

template <typename A, typename B>
struct Comp<A *const, B *const> {
	enum {
		ls = Comp<A,B>::ls,
		eq = Comp<A,B>::eq
	};
};

template <typename A, typename B>
struct Less {
	enum { r = (Len<A>::r < Len<B>::r) || ((Len<A>::r == Len<B>::r) && Comp<A,B>::ls) };
};

template <typename A, typename B>
struct Equal {
	enum { r = Len<A>::r == Len<B>::r && Comp<A,B>::eq };
};

template <typename A, typename B>
struct Greater {
	enum { r = Less<B,A>::r };
};

template <typename A, typename B>
struct GreaterEqual {
	enum { r = !Less<A,B>::r };
};

template <typename A, typename B>
struct LessEqual {
	enum { r = !Greater<A,B>::r };
};

template <typename A, typename B>
struct NotEqual {
	enum { r = !Equal<A,B>::r };
};

//
//	Translating type-integers that represent small integers to integers
//
typedef unsigned long Int;
const Int IntLen = std::numeric_limits<Int>::digits;

template <typename T>
struct Value {
	enum { r = 0 };
};

template <typename T>
struct Value<T *> {
	enum { r = Value<T>::r*2 };
};

template <typename T>
struct Value<T * const> {
	enum { r = Value<T>::r*2 + 1 };
};

//
//	Translating small integers to type-integers
//
template <Int n>
struct TypeInt {
	typedef typename Select<n&1,typename TypeInt<n>>1>::R *const, typename TypeInt<n>>1>::R *>::R R;
};

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

//
//	A version for pasting together integers into large typeints
//
template <Int n8, Int n7, Int n6, Int n5, Int n4, Int n3, Int n2, Int n1>
struct TypeIntN {
	typedef typename TypeInt<n8>::R N8;
	typedef typename TypeInt<n7>::R N7;
	typedef typename TypeInt<n6>::R N6;
	typedef typename TypeInt<n5>::R N5;
	typedef typename TypeInt<n4>::R N4;
	typedef typename TypeInt<n3>::R N3;
	typedef typename TypeInt<n2>::R N2;
	typedef typename TypeInt<n1>::R N1;
	typedef typename Add<typename LShift<N8,IntLen>::R, N7>::R N87;
	typedef typename Add<typename LShift<N87,IntLen>::R, N6>::R N876;
	typedef typename Add<typename LShift<N876,IntLen>::R, N5>::R N8765;
	typedef typename Add<typename LShift<N8765,IntLen>::R, N4>::R N87654;
	typedef typename Add<typename LShift<N87654,IntLen>::R, N3>::R N876543;
	typedef typename Add<typename LShift<N876543,IntLen>::R, N2>::R N8765432;
	typedef typename Add<typename LShift<N8765432,IntLen>::R, N1>::R N87654321;
	typedef N87654321 R;
};

template <Int n1>
struct TypeInt1 {
	typedef typename TypeIntN<0,0,0,0,0,0,0,n1>::R R;
};

template <Int n2, Int n1>
struct TypeInt2 {
	typedef typename TypeIntN<0,0,0,0,0,0,n2,n1>::R R;
};

template <Int n3, Int n2, Int n1>
struct TypeInt3 {
	typedef typename TypeIntN<0,0,0,0,0,n3,n2,n1>::R R;
};

template <Int n4, Int n3, Int n2, Int n1>
struct TypeInt4 {
	typedef typename TypeIntN<0,0,0,0,n4,n3,n2,n1>::R R;
};

template <Int n5, Int n4, Int n3, Int n2, Int n1>
struct TypeInt5 {
	typedef typename TypeIntN<0,0,0,n5,n4,n3,n2,n1>::R R;
};

template <Int n6, Int n5, Int n4, Int n3, Int n2, Int n1>
struct TypeInt6 {
	typedef typename TypeIntN<0,0,n6,n5,n4,n3,n2,n1>::R R;
};

template <Int n7, Int n6, Int n5, Int n4, Int n3, Int n2, Int n1>
struct TypeInt7 {
	typedef typename TypeIntN<0,n7,n6,n5,n4,n3,n2,n1>::R R;
};

template <Int n8, Int n7, Int n6, Int n5, Int n4, Int n3, Int n2, Int n1>
struct TypeInt8 {
	typedef typename TypeIntN<n8,n7,n6,n5,n4,n3,n2,n1>::R R;
};

//
//	Printing big typeints
//
// Just a handy utility for debugging, and is not more generally useful.
// Prints a binary representation, but always prints a leading zero.
template <typename T>
struct PrintTypeint;

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

template <typename T>
struct PrintTypeint<T *> {
	static void print() {
		PrintTypeint<T>::print();
		std::cout << '0';
	}
};

template <typename T>
struct PrintTypeint<T *const> {
	static void print() {
		PrintTypeint<T>::print();
		std::cout << '1';
	}
};

#endif