{-
	Copyright (C) 2011 Dr. Alistair Ward

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]	Facilitates representation of 'Integral' values in alternative 'Integral' bases.
-}

module Factory.Math.Radix(
-- * Constants
--	decodes,
--	digits,
--	encodes,
-- * Functions
	digitSum,
	digitalRoot,
	fromBase,
	toBase
) where

import			Data.Array.IArray((!))
import qualified	Data.Array.IArray
import qualified	Data.Char
import qualified	Data.List
import qualified	Data.Maybe

-- | Characters used to represent the digits of numbers in @(-36 <= base <= 36)@.
digits :: String
digits	= ['0' .. '9'] ++ ['a' .. 'z']

-- | Constant random-access lookup for 'digits'.
encodes :: (Data.Array.IArray.Ix index, Integral index) => Data.Array.IArray.Array index Char
encodes	= Data.Array.IArray.listArray (0, pred $ Data.List.genericLength digits) digits

-- | Constant reverse-lookup for 'digits'.
decodes :: Integral i => [(Char, i)]
decodes	= zip digits [0 ..]

{- |
	* Convert the specified integral decimal quantity, to an alternative base, and represent the result as a 'String'.

	* Both negative decimals and negative bases are permissible.

	* The conversion to 'Char' can only succeed where printable and intelligible characters exist to represent all digits in the chosen base;
	which in practice means @(-36 <= base <= 36)@.
-}
toBase :: (
	Data.Array.IArray.Ix	decimal,
	Integral		base,
	Integral		decimal,
	Show			base,
	Show			decimal
 ) => base -> decimal -> String
toBase 10 decimal	= show decimal	-- Base unchanged.
toBase _ 0		= "0"		-- Zero has the same representation in any base.
toBase base decimal
	| abs base < 2					= error $ "Factory.Math.Radix.toBase:\tan arbitrary integer can't be represented in base " ++ show base
	| abs base > Data.List.genericLength digits	= error $ "Factory.Math.Radix.toBase:\tunable to clearly represent the complete set of digits in base " ++ show base
	| base > 0 && decimal < 0			= '-' : map toDigit (fromDecimal (negate decimal) [])
	| otherwise					= toDigit `map` fromDecimal decimal []
	where
		fromDecimal 0		= id
		fromDecimal n
			| remainder < 0	= fromDecimal (succ quotient) . ((remainder - fromIntegral base) :)	-- This can only occur when base is negative; cf. 'divMod'.
			| otherwise	= fromDecimal quotient . (remainder :)
			where
				(quotient, remainder)	= n `quotRem` fromIntegral base

		toDigit :: (Data.Array.IArray.Ix i, Integral i, Show i) => i -> Char
		toDigit n
			| n >&< encodes	= encodes ! n
			| otherwise	= error $ "Factory.Math.Radix.toBase.toDigit:\tno suitable character-representation for integer " ++ show n
			where
				(>&<) :: (Data.Array.IArray.Ix i, Integral i) => i -> Data.Array.IArray.Array i Char -> Bool
				index >&< array	= ($ index) `all` [(>= lower), (<= upper)]	where
					(lower, upper)	= Data.Array.IArray.bounds array

{- |
	* Convert the 'String'-representation of a number in the specified base, to a decimal integer.

	* Both negative numbers and negative bases are permissible.
-}
fromBase :: (
	Integral	base,
	Integral	decimal,
	Read		decimal,
	Show		base
 ) => base -> String -> decimal
fromBase 10 s	= read s	-- Base unchanged.
fromBase _ "0"	= 0		-- Zero has the same representation in any base.
fromBase base s
	| abs base < 2					= error $ "Factory.Math.Radix.fromBase:\tan arbitrary integer can't be represented in base " ++ show base
	| abs base > Data.List.genericLength digits	= error $ "Factory.Math.Radix.fromBase:\tunable to clearly represent the complete set of digits in base " ++ show base
	| base > 0 && head s == '-'			= negate . fromBase base $ tail s	-- Recurse.
	| otherwise					= Data.List.foldl' (\l -> ((l * fromIntegral base) +) . fromDigit) 0 s	where
		fromDigit :: Integral i => Char -> i
		fromDigit c	= case c `lookup` decodes of
			Just i
				| i >= abs (fromIntegral base)	-> error $ "Factory.Math.Radix.fromBase.fromDigit:\tillegal char " ++ show c ++ ", for base " ++ show base
				| otherwise			-> i
			_					-> error $ "Factory.Math.Radix.fromBase.fromDigit:\tunrecognised char " ++ show c

{- |
	* <http://mathworld.wolfram.com/DigitSum.html>.

	* <http://en.wikipedia.org/wiki/Digit_sum>.
-}
digitSum :: (
	Data.Array.IArray.Ix	decimal,
	Integral		base,
	Integral		decimal,
	Show			base,
	Show			decimal
 ) => base -> decimal -> decimal
digitSum 10	= fromIntegral . foldr ((+) . Data.Char.digitToInt) 0 . show
digitSum base	= sum . Data.Maybe.mapMaybe (`lookup` decodes) . toBase base

-- | <http://en.wikipedia.org/wiki/Digital_root>.
digitalRoot :: (
	Data.Array.IArray.Ix	decimal,
	Integral		decimal,
	Show			decimal
 ) => decimal -> decimal
digitalRoot	= until (<= 9) (digitSum (10 :: Int))