# baseConvert.py  V.3.6, September 6 2005, by leonardo maffi.

from collections import deque

digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ+="



_nibbles = {"0":"0000", "1":"0001", "2":"0010", "3":"0011",
            "4":"0100", "5":"0101", "6":"0110", "7":"0111",
            "8":"1000", "9":"1001", "A":"1010", "B":"1011",
            "C":"1100", "D":"1101", "E":"1110", "F":"1111",
            "-":"-"}

def toBase2(number):
    "toBase2(number): given an int/long, converts it to a string containing the number in base 2."
    # Faster version possibile, improved from a suggestion by Dennis Lee Bieber.
    if number == 0:
        return "0"
    result = [_nibbles[nibble] for nibble in "%X"%number]
    result[number<0] = result[number<0].lstrip("0")
    return "".join(result)


def toBase(n, base):
    """toBase(n, base):
     Input:
       n: int or long to be converted
       base: int or long in [2,10]
     Output:
       n converted in the given base, as an int or long."""
    if not isinstance(n, (int, long)):
        raise TypeError, "in toBase, n ins't an int or long."
    if not isinstance(base, (int, long)):
        raise TypeError, "in toBase, base ins't an int or long."
    assert 11 > base > 1, "toBase error: base must be <11 and >1."
    if n == 0 or base == 10:
        return n
    else:
        d = [ str(i) for i in xrange(base) ]
        n2 = abs(n)
        result = deque()
        _app = result.appendleft # faster local variable
        _divmod = divmod
        while n2:
            n2, digit = _divmod(n2, base)
            _app( d[digit] )
        if n<0:
            return -int("".join(result))
        else:
            return int("".join(result))


def baseConvert(n, inBase=10, outBase=16, inDigits=digits, outDigits=digits):
    """baseConvert(n, inBase=10, outBase=16, inDigits=digits, outDigits=digits)
    convert a number between any two bases, using arbitrary digit representation.
    Input:
      n = integer, long, or ordered sequence (basestring, list, tuple, etc.)
      inBase = number (default = 10)
      outBase = number (default = 16)
      inDigits = basestring, list or tuple of input digits.
      outDigits = basestring, list or tuple of output digits (digits must be strings).
        Default inDigits and outDigits (64 symbols) =
          "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ+="
        inDigits must be all different basestrings.
        outDigits must be basestrings.
    Output:
      basestring of the converted number.

    There are some particular cases, like:
      baseConvert("-1", inBase=2, outBase=2, inDigits="1-", outDigits="01") => '-0'
      in this situation the "-" of n is intended as a negative sign, and not as a digit.
    Spaces can become digits too:
      baseConvert("-.-.. ..-", inBase=3, outBase=10, inDigits=" .-") ==> '-3983'
    Another example:
      baseConvert("_._.. .._ .__.. _.", inBase=3, outBase=256, inDigits=" ._",
        outDigits=map(chr, xrange(256)) ) ==> '-3983'
    """
    def nTo10(n):
        "Convert n into a int/log from inBase to a positive in base 10"
        tyn = type(n)
        if tyn in int_long and inDigits is digits:
            if inBase == 10:
                if n >= 0:
                    return n, False
                else:
                    return -n, True
            elif inBase < 10:
                if n >= 0:
                    return int(str(n), inBase), False
                else:
                    return int(str(-n), inBase), True

        if tyn in int_long:
            n = str(n)
        elif not n:
            raise "Error in baseConvert: n is empty."
        if n[0] == '-':
            n = n[1:]
            negative = True
        elif n[0] == '+':
            n = n[1:]
            negative = False
        else:
            negative = False
        if not n:
            raise "Error in baseConvert: n is just a +/- sign."
        if not set(n).issubset(inDigitsDict):
            raise "Error in baseConvert: input n contains characters not in inDigits[:inBase]."

        # Conversion:
        n2 = 0
        for digit in n:
           n2 = n2*inBase + inDigitsDict[digit]
        return n2, negative


    def n2toOutBase(n2, negative):
        "Convert n2 from base 10 to base outBase. n2 is a positive int or long. Output is a string."
        if n2 == 0:
            return outDigits[0]
        if outDigits is digits:
            if outBase == 10:
                if negative:
                    return str(-n2)
                else:
                    return str(n2)
            elif outBase == 8:
                if negative:
                    return "-" + "%o" % n2
                else:
                    return "%o" % n2
            elif outBase == 16:
                if negative:
                    return "-" + "%x" % n2
                else:
                    return "%x" % n2
        result = deque()
        _divmod = divmod # faster local variables
        result_appendleft = result.appendleft
        while n2:
            n2, digit = _divmod(n2, outBase)
            result_appendleft( outDigits[digit] )
        if negative:
            result.appendleft("-")
        result = "".join(result)
        return result


    result = None
    int_long = (int, long)
    if not isinstance(inBase, int_long) or inBase<2 or inBase>len(inDigits):
        raise TypeError, "in baseConvert: inBase is wrong: " + str(inBase)
    if not isinstance(outBase, int_long) or outBase<2 or outBase>len(outDigits):
        raise TypeError, "in baseConvert: outBase is wrong: " + str(outBase)
    if isinstance(n, float):
        raise TypeError, "in baseConvert: input n is a float."
    if not inDigits:
        raise "Error in baseConvert: inDigits is empty."
    if not outDigits:
        raise "Error in baseConvert: outDigits is empty."
    if len(inDigits) != len(set(inDigits)):
        raise "Error in baseConvert: inDigits must be all different."
    if inDigits is not digits:
        for d in inDigits:
            if not isinstance(d, basestring):
                raise "Error in baseConvert: inDigits contains a non-basestring."
    if outDigits is not digits:
        for d in outDigits:
            if not isinstance(d, basestring):
                raise "Error in baseConvert: outDigits contains a non-basestring."
    inDigitsDict = dict( (d,i) for i,d in enumerate(inDigits[:inBase]) )
    n2, negative = nTo10(n)
    return n2toOutBase(n2, negative)


try: # Import Psyco if available.
    import psyco
except ImportError:
    pass
else:
    # psyco.bind(baseConvert) # useless for now
    psyco.bind(toBase)
    psyco.bind(toBase2)

__all__ = ["toBase2", "toBase", "baseConvert"]


if __name__ == '__main__':
    n = 1000000
    print "From:", n
    print "Converted 10==>16:", baseConvert(n, 10, 16)

    import time
    n = 13**15759
    t1 = time.clock()
    ncc = baseConvert(baseConvert(n, 10, 16), 16, 10)
    t2 = time.clock()
    print round(t2-t1, 3), "s"
    assert "From == Converted (b=16)?", ncc == str(n)

    ncc = baseConvert(baseConvert(n, 10, 63), 63, 10)
    assert "From == Converted (b=21)?", ncc == str(n)

    print
    print baseConvert(15255, 10, 10)
    digits = "abcdefghijklmnopqrstuvwxyz"
    print baseConvert(15255, 10, 10, outDigits=digits)
    print

    bases = [2, 8, 10, 16, 64]
    numbers = [-100, "-12", 0, 2L, 8, 16, "25", 77]
    for b in bases:
        for n in numbers:
            c = baseConvert(n, 10, b)
            print c
            assert baseConvert(c, b, 10) == str(n)
        print
    n = "_._.. .._ .__.. _."
    all256 = map(chr, xrange(256))
    assert baseConvert(n, inBase=3, outBase=256, inDigits=" ._", outDigits=all256) == '\x14\x11[\xe9'
    thousand = map(str, range(1000))
    n = ["723", "151", "478", "441"]
    print n
    print baseConvert(n, inBase=1000, outBase=2, inDigits=thousand)

    print
    for i in xrange(-20, 21):
        print toBase2(i)

    print "All baseconvert asserts passed."
    print
    raw_input("Press enter to finish.")