// Semantics Consulting's Tyr Library
// http://www.semantics.org
//
// 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.

// "typeint" implementation
//
// Described in Typeints. C/C++ Users Journal Experts Forum, 21, 2 (February 2003)

#ifndef TYPEINT_H
#define TYPEINT_H

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

namespace Tyr {

//
// 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;
};


//
//	Simple and Slow Multiplication
//
// As noted in the article, this multiplication algorithm is simple, but
// has quadratic complexity.
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; };

//
// Subtract
//
// Note:  This is unsigned subtraction with the assumption
// that A >= B!!!
template <typename A, typename B>
struct Sub;

template <typename A, typename B>
struct Sub<A *const,B *const> {
	typedef typename Sub<A,B>::R *R; // A1-B1 == (A-B)0
};

template <typename A, typename B>
struct Sub<A *const,B *> {
	typedef typename Sub<A,B>::R *const R; // A1-B0 == (A-B)1
};

template <typename A, typename B>
struct Sub<A *,B *> {
	typedef typename Sub<A,B>::R *R; // A0-B0 == (A-B)0
};

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

template <>
struct Sub<char,char> {
	typedef char R; // 0-0 == 0
};

// Borrow scans back to find a 1 bit, zeros it,
// and sets all the preceding 0 bits to 1.
template <typename T>
struct Borrow;

template <typename T>
struct Borrow<T *const> {
	// make sure there's no leading 0
	typedef typename Select<IsPtr<T>::r,T *,T>::R R;
};

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

template <typename A, typename B>
struct Sub<A *,B *const> {
	// Need to borrow.
	typedef typename Borrow<A>::R T1;
	typedef typename Sub<T1,B>::R *const R;
};

//
//	Scouts that are used to look ahead for runs
//	of like bits.
//
template <typename T>
struct Count0s
	{ enum { r = 0 }; };

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

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

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

//
//	An optimized multiplication algorithm.
//	The complexity is still quadratic, but the actual
//	compile time is typically much better than that of
//	the unoptimized algorithm.
//
template <typename A, typename B>
struct Mulopt;

template <int zeros, int ones, typename A, typename B>
struct M4;

template <int n, typename A, typename B>
struct M4<0,n,A,B> { // B has run of 1s
	typedef typename RShift<B,n>::R T1;
	typedef typename Mulopt<A,T1>::R T2;
	typedef typename LShift<T2,n>::R T3;
	typedef typename LShift<A,n>::R Ax2n;
	typedef typename Sub<Ax2n,A>::R Ax2n_1;
	typedef typename Add<T3,Ax2n_1>::R R;
};

template <int n, typename A, typename B>
struct M4<n,0,A,B> { // B has run of 0s
	typedef typename RShift<B,n>::R T1;
	typedef typename Mulopt<A,T1>::R T2;
	typedef typename LShift<T2,n>::R R;
};

template <typename A, typename B>
struct M4<0,0,A,B> { // nothing left of B
	// specialization of Mulopt assures us no zero args
	// so we can return 1 here
	typedef char * const R;
};

// M3 counts runs of 0s and 1s and goes to the appropriate place.
template <typename A, typename B>
struct M3 {
	enum {
		ones = Count1s<B>::r,
		zeros = Count0s<B>::r
	};
	typedef typename M4<zeros,ones,A,B>::R R;
};

// M2 switches the args, if necessary, so the longer arg is second arg.
template <bool, typename A, typename B>
struct M2 {
	typedef typename M3<A,B>::R R;
};

template <typename A, typename B>
struct M2<false,A,B> {
	typedef typename M3<B,A>::R R;
};

template <typename A, typename B>
struct Mulopt {
	// the second arg should be the larger of the two
	enum { alen = Len<A>::r, blen = Len<B>::r };
	typedef typename M2<(alen<=blen),A,B>::R R;
};

// three specializations for zero args
template <typename A>
struct Mulopt<A,char> {
	typedef char R;
};

template <typename B>
struct Mulopt<char,B> {
	typedef char R;
};

template <>
struct Mulopt<char,char> {
	typedef char 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';
	}
};

} // namespace Tyr

#endif