The List Trifecta, Part 1

//
// Fixed-point math structures produced with the help of T4 (FixedPoint.tt)
// NOTE: THIS CODE HAS NOT BEEN WELL-TESTED AND DOES NOT YET HAVE A TEST SUITE.
// 
<#@ template language="C#" #>
<#@ output extension="cs" #>
<#@ assembly name="System.Core" #>
<#@ import namespace="System.Linq" #>
<#@ import namespace="System.Runtime.InteropServices" #>

namespace Loyc.Math
{
	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;
	using System.Diagnostics;

<#	foreach (FPTraits T in _types) { #>
	/// <summary>Fixed-point type based on <#=T.Int#> with <#=T.Frac#> fractional bits</summary>
	public partial struct <#=T#> : IComparable<<#=T#>>, IEquatable<<#=T#>>, IConvertible
	{
		public const int Frac = <#=T.Frac#>;
		public const <#=T.Int#> Unit = 1 << Frac;
		public static <#=T#> Prescaled(<#=T.Int#> n) { <#=T#> r = new <#=T#>(); r.N = n; return r; }
		public static readonly <#=T#> Zero = new <#=T#>();
		public static readonly <#=T#> One = new <#=T#>(1);
		public static readonly <#=T#> Epsilon = Prescaled(1);
		public static readonly <#=T#> MaxValue = Prescaled(<#=T.Int#>.MaxValue);
		public static readonly <#=T#> MinValue = Prescaled(<#=T.Int#>.MinValue);
		public const <#=T.Int#> MaxInt = <#=T.Int#>.MaxValue >> Frac;
		public const <#=T.Int#> MinInt = <#=T.Int#>.MinValue >> Frac;
		public const double MaxDouble = <#=T.Int#>.MaxValue / (double)(1 << Frac);
		public const double MinDouble = <#=T.Int#>.MinValue / (double)(1 << Frac);
		public const <#=T.Int#> Mask = (1 << Frac) - 1;

<#		if (T.WholeBits < 31) { #>
		public static explicit operator <#=T#>(int value) { return new <#=T#>(value); }
<#			if (T.WholeBits >= 15) { #>
		public static implicit operator <#=T#>(short value) { return new <#=T#>(value); }
<#			} else if (T.WholeBits >= 7) { #>
		public static implicit operator <#=T#>(sbyte value) { return new <#=T#>(value); }
<#			} #>
<#		} else { #>
		public static implicit operator <#=T#>(int value) { return new <#=T#>(value); }
<#		} #>
		
<#		if (T.WholeBits < 32) { #>
		public static explicit operator <#=T#>(uint value) { return new <#=T#>(value); }
<#			if (T.WholeBits >= 15) { #>
		// C# complains about ambiguity if we have two implicit conversion operators
		//public static implicit operator <#=T#>(ushort value) { return new <#=T#>(value); }
<#			} else if (T.WholeBits >= 7) { #>
		//public static implicit operator <#=T#>(byte value) { return new <#=T#>(value); }
<#			} #>
<#		} else { #>
		public static implicit operator <#=T#>(uint value) { return new <#=T#>(value); }
<#		} #>

		public static explicit operator <#=T#>(long value) { return new <#=T#>(value); }
		public static explicit operator <#=T#>(ulong value) { return new <#=T#>(value); }
		public static explicit operator <#=T#>(float value) { return new <#=T#>(value); }
		public static explicit operator <#=T#>(double value) { return new <#=T#>(value); }
		public static explicit operator int(<#=T#> value) { return (int)(value.N >> Frac); }
		public static explicit operator long(<#=T#> value) { return (long)(value.N >> Frac); }
		public static explicit operator uint(<#=T#> value) { return (uint)(value.N >> Frac); }
		public static explicit operator ulong(<#=T#> value) { return (ulong)(value.N >> Frac); }
		public static explicit operator float(<#=T#> value) { return (float)value.N * (1.0f / (1 << Frac)); }
		public static explicit operator double(<#=T#> value) { return (double)value.N * (1.0 / (1 << Frac)); }
		
<#		foreach (FPTraits T2 in _types) { if (T2 == T) continue; #>
		public static explicit operator <#=T2#>(<#=T#> value)
		{
<#			int fracDif = T.Frac - T2.Frac; #>
<#			int loss = T.WholeBits - T2.WholeBits; #>
<#			if (loss > 0) { #>
			if (value.N > <#=T.Int#>.MaxValue >> <#=loss#>)
				return <#=T2#>.MaxValue;
			if (value.N < <#=T.Int#>.MinValue >> <#=loss#>)
				return <#=T2#>.MinValue;
<#			} #>
			return <#=T2#>.Prescaled(<#= 
				string.Format(T2.IsLong && fracDif<0 ? "(({0})" : "({0})(", T2.Int)
				#>value.N<#=
				fracDif>0 ? " >> " + fracDif.ToString() : fracDif<0 ? " << " + (-fracDif).ToString() : "" #>));
		}
<#		} #>

		public <#=T.Int#> N;

		private static void Overflow()
		{
 			throw new OverflowException();
		}
<#		if (int.MinValue < T.MinInt || int.MaxValue > T.MaxInt) { #>
		public static <#=T#> CheckedCast(int num)
		{
			if (num < MinInt<# if (int.MaxValue > T.MaxInt) { #> || num > MaxInt<# } #>)
				Overflow();
			return Prescaled((<#=T.Int#>)num << Frac);
		}
<#		} #>
<#		if (uint.MaxValue > T.MaxInt) { #>
		public static <#=T#> CheckedCast(uint num)
		{
			if (num > MaxInt)
				Overflow();
			return Prescaled((<#=T.Int#>)num << Frac);
		}
<#		} #>
		public static <#=T#> CheckedCast(long num)
		{
			if (num < MinInt || num > MaxInt)
				Overflow();
			return Prescaled((<#=T.Int#>)num << Frac);
		}
		public static <#=T#> CheckedCast(ulong num)
		{
			if (num > MaxInt)
				Overflow();
			return Prescaled((<#=T.Int#>)num << Frac);
		}
		public static <#=T#> CheckedCast(double num)
		{
			if (!(num >= MinDouble && num <= MaxDouble))
				Overflow();
			return FastCast(num);
		}
		public static <#=T#> FastCast(int num)
		{
			return Prescaled((<#=T.Int#>)num << Frac);
		}
		public static <#=T#> FastCast(uint num)
		{
			return Prescaled((<#=T.Int#>)num << Frac);
		}
		public static <#=T#> FastCast(long num)
		{
			return Prescaled((<#=T.Int#>)num << Frac);
		}
		public static <#=T#> FastCast(double num)
		{
			return Prescaled((int)Math.Round(MathEx.ShiftLeft(num, Frac)));
		}

		public <#=T#>(int num)
		{
			N = (<#=T.Int#>)num << Frac;
<#			if (T.WholeBits < 31) { #>
			if (num < MinInt)
				N = <#=T.Int#>.MinValue;
			if (num > MaxInt)
				N = <#=T.Int#>.MaxValue;
<#			} #>
		}
		public <#=T#>(uint num)
		{
			N = (<#=T.Int#>)num << Frac;
<#			if (T.WholeBits < 32) { #>
			if (num > (uint)MaxInt)
				N = <#=T.Int#>.MaxValue;
<#			} #>
		}
		public <#=T#>(long num)
		{
			N = (<#=T.Int#>)num << Frac;
			if (num < MinInt)
				N = <#=T.Int#>.MinValue;
			if (num > MaxInt)
				N = <#=T.Int#>.MaxValue;
		}
		public <#=T#>(ulong num)
		{
			N = (<#=T.Int#>)num << Frac;
			if (num > MaxInt)
				N = <#=T.Int#>.MaxValue;
		}
		public <#=T#>(double num)
		{
			N = (<#=T.Int#>)Math.Round(MathEx.ShiftLeft(num, Frac));
			if (num <= MinDouble)
				N = <#=T.Int#>.MinValue;
			if (num >= MaxDouble)
				N = <#=T.Int#>.MaxValue;
		}

		public static <#=T#> operator +(<#=T#> a, <#=T.Int#> b) { a.N += b << Frac; return a; }
		public static <#=T#> operator -(<#=T#> a, <#=T.Int#> b) { a.N -= b << Frac; return a; }
		public static <#=T#> operator *(<#=T#> a, <#=T.Int#> b) { a.N *= b; return a; }
		public static <#=T#> operator /(<#=T#> a, <#=T.Int#> b) { a.N /= b; return a; }
		public static <#=T#> operator %(<#=T#> a, <#=T.Int#> b) { a.N %= b << Frac; return a; }
		public static <#=T#> operator +(<#=T#> a, <#=T#> b) { a.N += b.N; return a; }
		public static <#=T#> operator -(<#=T#> a, <#=T#> b) { a.N -= b.N; return a; }
		public static <#=T#> operator -(<#=T#> a) { a.N = -a.N; return a; }

<#		if (T.IsLong) { #>
		public static <#=T#> operator *(<#=T#> a, <#=T#> b)
		{
			return Prescaled(MathEx.MulShift(a.N, b.N, Frac));
			// Flaw: unreliable if Frac < 32
			//var afrac = a.N & Mask;
			//var bfrac = b.N & Mask;
			//var whole = (<#=T#>)((<#=T.Int#>)a * (<#=T.Int#>)b);
			//whole.N += afrac * bfrac >> Frac;
			//return whole;
		}
		public static <#=T#> operator /(<#=T#> a, <#=T#> b)
		{
			long whole = a.N / b.N;
			long remainder = a.N % b.N;
			remainder = (remainder << Frac) / b.N;
			Debug.Assert(remainder < (1 << Frac));
			a.N = (whole << Frac) + remainder;
			return a;
			// TODO: test negative numbers: 7 / -2.5, -7 / 2.5, -7 / -2.5
		}
<#		} else { #>
		public static <#=T#> operator *(<#=T#> a, <#=T#> b) { return Prescaled((int)((long)a.N * (long)b.N >> Frac)); }
		public static <#=T#> operator /(<#=T#> a, <#=T#> b) { return Prescaled((int)((long)(a.N << Frac) / b.N)); }
<#		} #>
		public static <#=T#> operator %(<#=T#> a, <#=T#> b) { a.N %= b.N; return a; }
		public static <#=T#> operator <<(<#=T#> a, int b) { a.N <<= b; return a; }
		public static <#=T#> operator >>(<#=T#> a, int b) { a.N >>= b; return a; }
		public static bool operator ==(<#=T#> a, <#=T#> b) { return a.N == b.N; }
		public static bool operator !=(<#=T#> a, <#=T#> b) { return a.N != b.N; }
		public static bool operator >=(<#=T#> a, <#=T#> b) { return a.N >= b.N; }
		public static bool operator <=(<#=T#> a, <#=T#> b) { return a.N <= b.N; }
		public static bool operator >(<#=T#> a, <#=T#> b) { return a.N > b.N; }
		public static bool operator <(<#=T#> a, <#=T#> b) { return a.N < b.N; }
		
		public static bool operator ==(<#=T#> a, <#=T.Int#> b) { return a.N == b << Frac; }
		public static bool operator !=(<#=T#> a, <#=T.Int#> b) { return a.N != b << Frac; }
		public static bool operator >=(<#=T#> a, <#=T.Int#> b) { return a.N >= b << Frac; }
		public static bool operator <=(<#=T#> a, <#=T.Int#> b) { return a.N <= b << Frac; }
		public static bool operator >(<#=T#> a, <#=T.Int#> b) { return a.N > b << Frac; }
		public static bool operator <(<#=T#> a, <#=T.Int#> b) { return a.N < b << Frac; }

		public static <#=T#> operator &(<#=T#> a, <#=T#> b) { a.N &= b.N; return a; }
		public static <#=T#> operator |(<#=T#> a, <#=T#> b) { a.N |= b.N; return a; }
		public static <#=T#> operator ^(<#=T#> a, <#=T#> b) { a.N ^= b.N; return a; }
		public static <#=T#> operator ~(<#=T#> a) { a.N = ~a.N; return a; }
		
		public static <#=T#> operator ++(<#=T#> a) { a.N += Unit; return a; }
		public static <#=T#> operator --(<#=T#> a) { a.N -= Unit; return a; }
		
		public <#=T#> Abs() { return Prescaled(N >= 0 ? N : -N); }
		public int CountOnes() { return MathEx.CountOnes(N); }
		public int Log2Floor()
		{
			int r = MathEx.Log2Floor(N);
			if (r >= 0) r -= Frac;
			return r;
		}
		public <#=T#> Sqrt()
		{
			if ((<#=T.UInt#>)N <= (<#=T.UInt#>)MaxInt)
				return Prescaled((<#=T.Int#>)MathEx.Sqrt((<#=T.UInt#>)N << Frac));
			else
				// Compute lower-precision answer (this path is also taken if N is negative)
				return Prescaled(MathEx.Sqrt(<#= (T.Frac & 1) == 0 ? "N" : "N << 1" #>) << Frac/2);
		}
		public <#=T#> MulDiv(<#=T#> mul, <#=T#> div)
		{
			return Prescaled(MathEx.MulDiv(N, mul.N, div.N));
		}
		public <#=T#> MulShift(<#=T#> mul, int shift)
		{
			return Prescaled(MathEx.MulShift(N, mul.N, shift + Frac));
		}

		public override bool Equals(object obj)
		{
			return obj is <#=T#> && ((<#=T#>)obj).N == N;
		}
		public override int GetHashCode()
		{
			return N.GetHashCode();
		}
		public override string ToString()
		{
			return ((double)this).ToString("0.<#= new string('#', (1ul<<T.Frac).ToString().Length) #>");
		}

		public int CompareTo(<#=T#> other)
		{
			return N.CompareTo(other.N);
		}
		public bool Equals(<#=T#> other)
		{
			return N == other.N;
		}

		#region IConvertible

		TypeCode IConvertible.GetTypeCode()
		{
			return TypeCode.Object;
		}
		public bool ToBoolean(IFormatProvider provider)
		{
			return N != 0;
		}
		public sbyte ToSByte(IFormatProvider provider)
		{
			return checked((sbyte)(N >> Frac));
		}
		public short ToInt16(IFormatProvider provider)
		{
			return checked((short)(N >> Frac));
		}
		public int ToInt32(IFormatProvider provider)
		{
			return checked((int)(N >> Frac));
		}
		public long ToInt64(IFormatProvider provider)
		{
			return checked((long)(N >> Frac));
		}
		public byte ToByte(IFormatProvider provider)
		{
			return checked((byte)(N >> Frac));
		}
		public ushort ToUInt16(IFormatProvider provider)
		{
			return checked((ushort)(N >> Frac));
		}
		public uint ToUInt32(IFormatProvider provider)
		{
			return checked((uint)(N >> Frac));
		}
		public ulong ToUInt64(IFormatProvider provider)
		{
			return checked((ulong)(N >> Frac));
		}
		public char ToChar(IFormatProvider provider)
		{
			return checked((char)(N >> Frac));
		}
		public double ToDouble(IFormatProvider provider)
		{
			return (double)this;
		}
		DateTime IConvertible.ToDateTime(IFormatProvider provider)
		{
			throw new InvalidCastException();
		}
		public decimal ToDecimal(IFormatProvider provider)
		{
			return (decimal)(double)this;
		}
		public float ToSingle(IFormatProvider provider)
		{
			return (float)this;
		}
		string IConvertible.ToString(IFormatProvider provider)
		{
			return ToString();
		}
		object IConvertible.ToType(Type conversionType, IFormatProvider provider)
		{
			return Convert.ChangeType((double)this, conversionType, provider);
		}

		#endregion
	}

<#	} // end foreach (var T in _types) #>
}

<#+
	class FPTraits {
		public FPTraits(Type intType, int fracBits, string name)
		{
			IntType = intType;
			Int = intType.Name;
			Frac = fracBits;
			Name = name;
			//IsSigned = intType == typeof(sbyte) || intType == typeof(short) || intType == typeof(int) || intType == typeof(long);
			WholeBits = Marshal.SizeOf(intType) * 8 - 1 - Frac;//(IsSigned ? 1 : 0);
			IsLong = intType == typeof(long) || intType == typeof(ulong);
			UInt = IsLong ? "ulong" : "uint";
			MaxInt = (long)(Convert.ToUInt64(intType.GetField("MaxValue").GetRawConstantValue()) / (1u << Frac));
			MinInt = (long)(Convert.ToInt64(intType.GetField("MinValue").GetRawConstantValue()) / (1 << Frac));
		}
		public long MaxInt, MinInt;
		public string Name;
		public string Int;
		public string UInt;
		public Type IntType;
		public bool IsLong;
		public int Frac;
		public int WholeBits;
		public override string ToString() { return Name; }
	}
	FPTraits[] _types = new FPTraits[]
	{
		new FPTraits(typeof(int), 8, "FPI8"), 
		new FPTraits(typeof(int), 16, "FPI16"),
		new FPTraits(typeof(int), 23, "FPI23"),
		new FPTraits(typeof(long), 16, "FPL16"), 
		new FPTraits(typeof(long), 32, "FPL32"),
	};
#>