"""
graycode.py -- V.1.0 jan 21 2007, by leonardo maffi

Functions to convert  binary <--> Gray code.
"""
# See:
# http://www.faqs.org/faqs/ai-faq/genetic/part6/section-1.html
# http://yagni.com/graycode/
# http://en.wikipedia.org/wiki/Gray_code


def togreycode(binary):
    """togreycode(binary): given an int number, return its (base 10)
    conversion to Gray code.

    >>> togreycode(-1)
    Traceback (most recent call last):
      ...
    AssertionError: togreycode(binary): binary must be >= 0
    >>> [togreycode(i) for i in range(16)]
    [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
    >>> togreycode(54250959485948)
    46166297191938L
    """
    assert binary >= 0, "togreycode(binary): binary must be >= 0"
    return binary ^ (binary >> 1)


_xor = {("0", "0"): "0",
        ("0", "1"): "1",
        ("1", "0"): "1",
        ("1", "1"): "0"}


def tograystr(binary, xor=_xor):
    """tograystr(binary): given a binary number represented as string, returns
    its string representation as Gray code in base 2. The oppotite of tobinarystr().

    >>> tograystr("")
    Traceback (most recent call last):
      ...
    IndexError: string index out of range
    >>> tograystr("0")
    '0'
    >>> bins = ['000', '001', '010', '011', '100', '101', '110', '111']
    >>> [tograystr(b) for b in bins]
    ['000', '001', '011', '010', '110', '111', '101', '100']
    """
    prec = binary[0]
    result = prec
    for el in binary[1:]:
        result += xor[el, prec]
        prec = el
    return result


def tobinarystr(gray, xor=_xor):
    """tobinarystr(gray): given a string that contains a gray number in base 2, returns
    its string representation as binary code. The oppotite of tograystr().

    >>> tobinarystr("")
    Traceback (most recent call last):
      ...
    IndexError: string index out of range
    >>> tobinarystr("0")
    '0'
    >>> grays = ['000', '001', '011', '010', '110', '111', '101', '100']
    >>> [tobinarystr(g) for g in grays]
    ['000', '001', '010', '011', '100', '101', '110', '111']
    """
    result = gray[0]
    prec = result
    for el in gray[1:]:
        prec = xor[prec, el]
        result += prec
    return result


def graycodes(nbits):
    """
    graycodes(nbits): return the ordered list of all the Gray codes of nbits bits,
    represented as strings of "0", "1".

    >>> graycodes(0)
    ['']
    >>> graycodes(1)
    ['0', '1']
    >>> graycodes(2)
    ['00', '01', '11', '10']
    >>> graycodes(3)
    ['000', '001', '011', '010', '110', '111', '101', '100']
    >>> for code in graycodes(4): print code
    0000
    0001
    0011
    0010
    0110
    0111
    0101
    0100
    1100
    1101
    1111
    1110
    1010
    1011
    1001
    1000
    """
    result = [""]
    for i in xrange(nbits):
        result1 = ["0" + s for s in result]
        result1.extend(["1" + s for s in reversed(result)])
        result = result1
    return result


if __name__ == "__main__":
    import doctest
    doctest.testmod()
    print "Tests finished."