Integer Base Converter

// -----------------------------------------------------------------------
// <copyright file="IntegerBaseConverter.cs" company="ProXoft L.L.C.">
// </copyright>
// Author: Adam A. Zgagacz
// Web: http://www.proxoft.com
// -----------------------------------------------------------------------
namespace ProXoft.WinForms
{
    using System;
    using System.Collections.Generic;
    using System.Text;
    using System.Numerics;

    /// <summary>
    /// <para>
    /// Static class containing helper methods to convert numbers from and to different 
    /// positional numeral systems. It also provides methods to compare two numbers written 
    /// in the same numeral systems.<br></br>
    /// Class methods accept integer values greater than two as the numeral system base (radix).
    /// </para>
    /// Class has predefined default digit set used to represent numbers, but most method accept parameter where user can 
    /// provide own set of digits.<br></br>
    /// Default digit set is defined by string <i>"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/"</i>. Using default digit set
    /// numbers encoded with small bases (for example base-2 (binary), base-8 (octal), base-10 (decimal) or base-16 (hexadecimal)) look exactly as
    /// you would expect because default digit set starts with character '0' followed with '1' etc. 
    /// This represents 'natural' digit order we conventionally 
    /// write numbers.<br></br>
    /// However, since user can supply in most method calls own string representing digits used for encoding, numbers might look quite unfamiliar.
    /// Let's look at the following example:
    ///<code>
    /// //The following line converts value 12345 to radix-10 string representation using 0,1,2,3,4,5,6,7,8,9 digits
    /// string Radix10Number = Convert(12345, 10, "0123456789");   
    /// Radix10Number contains string "12345".
    /// //However the following line of code produces result "BCD78" which represents the same number but is using different digits.
    /// string Radix10Number = Convert(12345, 10, "ABCD789012");   
    /// </code>
    /// </summary>
    public static class IntegerBaseConverter
    {
        const string m_DefaultDigitSet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
        /// <summary>
        /// Read-only property showing default character set representing digits used to write the number
        /// in numeral system. 
        /// <para>Characters are ordered in ascending order:
        /// for example 1 is greater than 0 and a is greater B.</para>
        /// To write number in Base-n numeral system only first n characters form the string are used.
        /// For example: octal numbers (base-8) are written using only 0,1,2,3,4,5,6,7 characters (digits).
        /// while base 64 numbers can use any of the following digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,+,/"
        /// </summary>
        public static  string DefaultDigitsSet
        {
            get { return IntegerBaseConverter.m_DefaultDigitSet; }
        } 
     
        /// <summary>
        /// Converts <c>BigInteger</c> to the string representing 
        /// this number written in radix-x numeral system (x is provided as the <c>radix</c> method parameter)
        /// </summary>
        /// <param name="value">Number to be written in <c>radix</c> numeral system.</param>
        /// <param name="radix">Numeral system base (radix).</param>
        /// <param name="digits">Character set representing ascending sequence of digits used
        /// in destination numeral system.</param> 
        /// <returns>String representing number written in <c>radix</c> base numeral system
        /// (where <c>radix</c> is a number between 2 and length of <c>digits</c> string.)
        /// </returns>
        public static string Convert(BigInteger value, int radix, string digits=m_DefaultDigitSet)
        {
            if (value == null)
                value = new BigInteger(0);

            if ((radix > digits.Length) || (radix < 2))
                throw new ArgumentOutOfRangeException("radix", radix, string.Format("Radix has to be within range <2, {0}>;", digits.Length));

            StringBuilder sb = new StringBuilder();
            do
            {
                BigInteger remainder;
                value = BigInteger.DivRem(value, radix, out remainder);

                sb.Insert(0, digits[(int)remainder]);
            } while (value > 0);

            return sb.ToString();
        }


         /// <summary>
        /// Verifies if <c>Number</c> is a valid number, by checking all characters used to represent number against set of valid characters (digits).
        /// </summary>
        /// <param name="number">String representing base encoded number.</param>
        /// <param name="digits">String containing all valid characters (digits), that can be used to represent a number.</param>
        /// <returns><c>true</c> if <c>Number</c> contains only valid characters (digits). Otherwise method returns <c>false</c>.</returns>
        public static bool IsValidNumber(string number, string digits=m_DefaultDigitSet)
        {
            foreach (char ch in number)
            {
                if (digits.IndexOf(ch) < 0)
                    return false;
            }
            return true;
        }
        
        /// <summary>
        /// Check if parameter <c>digits</c> can be used for case insensitive parsing. In order to be valid 
        /// for case insensitive parsing, all characters in the string have to be unique regardless of their case.
        /// </summary>
        /// <param name="digits">Contains sequence of digits to check.</param>
        /// <returns><b>true</b> if <c>digits</c> does not contain duplicate characters, otherwise returns <b>false</b>.</returns>
        public static bool CanUseCaseInsensitiveParsingMode(string digits)
        {
            //Return true if number of unique uppercased digits in set is equal size of digits string
            return new HashSet<char>(digits.ToUpper()).Count == digits.Length;
        }

        /// <summary>
        /// Check if parameter <c>digits</c> is a valid digit set string. In order to be valid 
        /// digit set all characters in the string have to be unique.
        /// </summary>
        /// <param name="digits">Contains sequence of digits to check.</param>
        /// <returns><b>true</b> if <c>digits</c> does not contain duplicate characters, otherwise returns <b>false</b>.</returns>
        public static bool IsValidDigitSet(string digits)
        {
            HashSet<char> hashedCharacters = new HashSet<char>();

            //Try to insert all characters into HashSet. Return false after first duplicate character is detected.
            foreach (char c in digits)
                if (!hashedCharacters.Add(c)) return false;

            return true;
        }

        /// <summary>
        /// Converts string representation of a number (written as <c>radix</c> base string) to its BigInteger equivalent.
        /// </summary>
        /// <param name="value">A string containing a number to convert.</param>
        /// <param name="radix">Numeral base used to write <c>value</c>.</param>
        /// <param name="digits">String containing ordered set of valid digits (characters) for <c>radix</c> </param>
        /// <param name="result">When this method returns, contains BigInteger value equivalent to then number contained in <c>value</c>, if the conversion
        /// succeeded, or zero if the conversion failed. The conversion fails if <c>value</c> parameter is <b>null</b> or is not in correct 
        /// format.</param>
        /// <param name="CaseSensitiveParsing">Flag indicating if parsing is case sensitive. Default value is <b>true</b>.
        /// Setting it to false might be convenient in some applications. For example if we are dealing for example with
        /// radix-16 numbers, and numbers are entered by the user as typed text, user can assume strings contained 
        /// lower cased characters are equivalent to uppercased versions. For example both string "AFC3" and "afc4"
        /// should be consumed by Parse method and both should return valid number.<br></br>
        /// <i>Note:</i>
        /// Setting <c>CaseSensitiveParsing</c>=<b>false</b> should be considered as the hint. It will be used only if
        /// <c>digits</c> can be used for case insensitive parsing (see <c>CanUseCaseInsensitiveParsingMode</c> property)
        /// </param>
        /// <returns>
        /// Return value is 
        /// <b>true</b> if <c>value</c> was converted successfully; otherwise <b>false</b>.</returns>
        public static bool TryParse(string value, int radix, out BigInteger result, string digits = m_DefaultDigitSet, bool CaseSensitiveParsing = true)
        {
            try
            {
                result = Parse(value, radix, digits, CaseSensitiveParsing);
                return true;
            }
            catch
            {
                result = BigInteger.Zero;
                return false;
            }
       }

        /// <summary>
        /// Converts string representation of a number (written as <c>radix</c> base string) to its BigInteger equivalent.
        /// </summary>
        /// <param name="value">A string containing a number to convert.</param>
        /// <param name="radix">Numeral base used to write <c>value</c>.</param>
        /// <param name="digits">String containing ordered set of valid digits (characters) for <c>radix</c> </param>
        /// <param name="CaseSensitiveParsing">Flag indicating if parsing is case sensitive. Default value is <b>true</b>.
        /// Setting it to false might be convenient in some applications. For example if we are dealing for example with
        /// radix-16 numbers, and numbers are entered by the user as typed text, user can assume strings contained 
        /// lower cased characters are equivalent to uppercased versions. For example both string "AFC3" and "afc4"
        /// should be consumed by Parse method and both should return valid number.<br></br>
        /// <i>Note:</i>
        /// Setting <c>CaseSensitiveParsing</c>=<b>false</b> should be considered as the hint. It will be used only if
        /// <c>digits</c> can be used for case insensitive parsing (see <c>CanUseCaseInsensitiveParsingMode</c> property)
        /// </param>
        /// <exception cref="ArgumentOutOfRangeException">Radix is less than 2 or more than number of available digits
        /// (length of <c>digits</c> string).</exception>
        /// <exception cref="ArgumentOutOfRangeException"><c>value</c> contains invalid characters (not present in <c>digits</c> string).</exception>
        /// <returns><c>BigInteger</c> value equivalent to to the number contained in <c>value</c>parameter.</returns>
        public static BigInteger Parse(string value, int radix,  string digits=m_DefaultDigitSet, bool CaseSensitiveParsing=true)
        {

            if (string.IsNullOrEmpty(value))
                value = digits[0].ToString();
 
            if ((radix > digits.Length) || (radix < 2))
                throw new ArgumentOutOfRangeException("radix", radix, string.Format("Radix has to be within range <2, {0}>;", digits.Length));
            
            digits = digits.Substring(0, radix);

            if (!IsValidDigitSet(digits))
                throw new ArgumentException("Invalid digit set; digit set cannot contain duplicate characters.", "digits");

            if (!CaseSensitiveParsing && CanUseCaseInsensitiveParsingMode(digits))
            {
                value = value.ToUpper();
                digits = digits.ToUpper();
            }
            
            BigInteger uBase = 1;
            char[] ValueArray = value.ToCharArray();
            BigInteger RetValue = 0;
            for (int i = value.Length - 1; i >= 0; i--)
            {
                int CharIdx = digits.IndexOf(value[i]);
                if ((CharIdx >= radix) || (CharIdx < 0))
                    throw new ArgumentOutOfRangeException("Value", digits[CharIdx], "Invalid character in the input string.");

                RetValue += CharIdx * uBase;
                uBase *= radix;
            }
            return  RetValue;
        }
 
        /// <summary>
        /// Compares two numbers represented as strings encoded using the same radix value.
         /// </summary>
        /// <param name="numberA">The first number to compare</param>
        /// <param name="numberB">The second number to compare</param>
        /// <param name="Digits">String containing sequence of characters 
        /// used as digits in encoded numbers. Digits are ordered in ascending order
        /// starting from character representing zero</param>
        /// <returns>
        /// if numberA is less than numberB returns negative number; <br></br>
        /// if numberA == numberB returns zero;<br></br>
        /// if numberA is greater than numberB returns positive number.
        /// </returns>
        public static int Compare(string numberA, string numberB, string Digits=m_DefaultDigitSet)
        {
            //pad the shortest string wit equivalent of zeros
            int LengthDiff = numberA.Length - numberB.Length;
            if (LengthDiff > 0)
                numberB = new string(Digits[0], LengthDiff) + numberB;
            else if (LengthDiff < 0)
                numberA = new string(Digits[0], -LengthDiff) + numberA;

            //now strings have equal length so we can start comparing one character at the time
            for (int i = 0; i < numberA.Length; i++)
            {
                int charCompare = Compare(numberA[i], numberB[i], Digits);
                if (charCompare != 0)
                    return charCompare;
            }
            return 0;
        }


        /// <summary>
        /// Compares two digits (characters). Order of digits is determined by order of characters in <c>digits</c> parameter.
        /// </summary>
        /// <param name="digitA">The first digit to compare.</param>
        /// <param name="digitB">The second digit to compare.</param>
        /// <param name="digits">Ordered set of characters representing valid digits.</param>
        /// <returns>
        /// if digitA is less than digitB returns negative number;<br></br>
        /// if digitA == digitB returns zero;<br></br>
        /// if digitA is greater than digitB returns positive number.
        /// </returns>
        /// <exception cref="ArgumentOutOfRangeException">Invalid character</exception>
        public static int Compare(char digitA, char digitB, string digits= m_DefaultDigitSet)
        {
            //find index of charAInvalid character
            int idxA = digits.IndexOf(digitA);
            if (idxA < 0) throw new ArgumentOutOfRangeException("digitA", digitA, "Invalid character.");
            int idxB = digits.IndexOf(digitB);
            if (idxB < 0) throw new ArgumentOutOfRangeException("digitB", digitB, "Invalid character.");

            return (idxA - idxB);
        }

        /// <summary>
        /// Converts BigInteger to the string representing 
        /// this number written in radix-x numeral system (x is provided as the <c>radix</c> method parameter). If string length
        /// is less that maximum string length for given <c>radix</c> and <c>type</c> combination it is left-padded with
        /// characters representing zero digit up to maximum allowed length."/>
        /// </summary>
        /// <param name="value">Number to be written in different numeral system.</param>
        /// <param name="radix">Numeral system base.</param>
        /// <param name="type">Allowed values are: <b>System.Byte</b>, <b>System.UInt16</b>, <b>System.UInt32</b> <b>System.UInt64</b>or <b>System.BigInteger</b></param>
        /// <param name="digits">Character set representing ascending sequence of digits used
        /// in destination numeral system.</param>
        /// <returns>String representing number written in <c>radix</c> base numeral system
        /// (where 'Base is a number between 2 and length of <c>digits</c> string.)
        /// </returns>
        /// <returns></returns>
        /// <exception cref="ArgumentException"><c>value</c> is too big for given <c>type</c>.</exception>
        public static string GetPaddedValue(BigInteger value, int radix, Type type, string digits= m_DefaultDigitSet)
        {
            return GetPaddedValue(value, radix, MaxValue(type), digits);
        }

        public static string  GetPaddedValue(byte[] value,  int radix, BigInteger maxValue, string digits = m_DefaultDigitSet)
        {
            //Convert value to big integer /assuming value is stored in array less than 8
            //Bug Fix: Oct 12, 2013: longVal and Multiplier were Int64 this caused overflow
            UInt64 longVal = 0;
            UInt64 multipler = 1;
            for (int i= value.Length-1; i>=0; i--)
            {
                longVal += value[i]* multipler;
                multipler=multipler <<8;
            }
             return GetPaddedValue(longVal, radix,maxValue, digits);
        }

        /// <summary>
        /// Converts BigInteger to the string representing 
        /// this number written in radix-x numeral system (x is provided as the <c>radix</c> method parameter). If string length
        /// is less that maximum string length for given <c>radix</c> and <c>type</c> combination it is left-padded with
        /// characters representing zero digit up to maximum allowed length."/>
        /// </summary>
        /// <param name="value">Number to be written in different numeral system.</param>
        /// <param name="radix">Numeral system base.</param>
        /// <param name="type">Allowed values are: <b>System.Byte</b>, <b>System.UInt16</b>, <b>System.UInt32</b> <b>System.UInt64</b>or <b>System.BigInteger</b></param>
        /// <param name="digits">Character set representing ascending sequence of digits used
        /// in destination numeral system.</param>
        /// <returns>String representing number written in <c>radix</c> base numeral system
        /// (where 'Base is a number between 2 and length of <c>digits</c> string.)
        /// </returns>
        /// <returns></returns>
        /// <exception cref="ArgumentException"><c>value</c> is too big for given <c>type</c>.</exception>
        public static string GetPaddedValue(BigInteger value, int radix, BigInteger maxValue, string digits = m_DefaultDigitSet)
        {
            //Find string representation of the number encoded with base radix
            string RetValue = Convert(value, radix, digits);
            //Find maximum value allowed for given 'type'
            string Maximum = Convert(maxValue, radix, digits);

            //If encoded value is too big for given 'type' throw an exception.
            if (IntegerBaseConverter.Compare(RetValue, Maximum) > 0)
                throw new ArgumentException(string.Format("Value {0} is too big for {1}.", value, maxValue), "Value");

            //Find how many zero digits have to added in front
            int MaxSize = Maximum.Length;
            int DiffSize = MaxSize - RetValue.Length;

            //If needed, insert appropriate number of zero digits.
            if (DiffSize > 0)
                RetValue = new string(digits[0], DiffSize) + RetValue;
            else if (DiffSize < 0)
                throw new Exception("Unexpected error: Error getting padded value.");  //This should never happen
            return RetValue;
        }
 
    /// <summary>
    /// Returns string representation of maximum value of the number of type <c>type</c>  encoded with base <c>radix</c>.
    /// </summary>
        /// <param name="type">Allowed values are: <b>System.Byte</b>, <b>System.UInt16</b>, <b>System.UInt32</b> or <b>System.BigInteger</b></param>
        /// <param name="radix">Numeral system base (radix).</param>
        /// <param name="digits">Character set representing ascending sequence of digits used
        /// in destination numeral system.</param>
        /// <returns>Returns string representation of maximum value of the number of type <c>type</c>  encoded with base <c>radix</c>.</returns>
        public static string MaxValue(Type type, int radix, string digits= m_DefaultDigitSet)
        {
            return Convert(MaxValue(type), radix, digits);
        }

        /// <summary>
        /// Returns <c>BigInteger</c> value representing maximum value allowed for <b>System.Type</b> provided as method parameter.
        /// </summary>
        /// <param name="type"><b>System.Type</b> object. Only following Types are allowed:<br></br>
        /// <b>System.Byte</b>, <b>System.UInt16</b>, <b>System.UInt32</b>, <b>System.UInt64</b> or <b>Syste.Numerics.BigInteger.</b>
        /// </param>
        /// <exception cref="ArgumentException">Invalid Type. Only System.Byte, System.UInt16, System.UInt64, Syste.Numerics.BigInteger are allowed</exception>
        /// <returns>Maximum value for <c>type</c> provided as parameter.</returns>
        /// <remarks>Since <c>BigInteger</c> does not have maximum value defined, theoretically does not have value limit.
        /// For purpose of this class artificial maximum value of BigInteger was set for 1 googol (1 followed with 100 zeros)</remarks>
        public static BigInteger MaxValue(Type type)
        {
            if (type == typeof(Byte))
                return Byte.MaxValue;
            else if (type == typeof(UInt16))
                return UInt16.MaxValue;
            else if (type == typeof(UInt32))
                return UInt32.MaxValue;
            else if (type == typeof(UInt64))
                return UInt64.MaxValue;
            else if (type == typeof(BigInteger))
                 return BigInteger.Parse("1" + new string('0', 100));
            else
                throw new ArgumentException("Invalid argument.", "type");
        }
    }

    #region SandCastle help utility requires existence of this empty class
    /* The following empty class exists only in order to provide SandCastle help utility
     * extract namespace summary.   
     */

    /// <summary>
    /// Collection of WinForms components and controls.
    /// </summary>
    [System.Runtime.CompilerServices.CompilerGenerated]
    class NamespaceDoc
    {

    }
    #endregion

}