# -*- Mode: Python -*-

# Exercise 2.3 from EOPLv3, taken to extremes.

# one  == 1
# diff == (<tree>, <tree>)
# <tree> := one | diff

#  0 == (1,1)
# -1 == ((1,1),1)
# +1 == 0 - (-1) == ((1,1),((1,1),1))

def successor (t):
    return (t, ((1, 1), 1))

def predecessor (t):
    return (t, 1)

def is_zero (t):
    # TBD
    pass

def to_number (t):
    if t == 1:
        return 1
    else:
        return to_number (t[0]) - to_number (t[1])

# generate a non-canonical random number
def gen_random():
    import random
    t = 1
    # to generate a positive number, pick a direction favoring +1
    # 0=-1  1=+1 2=+1
    n = 100
    while n:
        direction = random.randrange (0, 3)
        if direction is 0:
            t = predecessor (t)
        else:
            t = successor (t)
        n -= 1
    return t

# generate a randomly formed non-canonical number
# (this is more truly random than the above, which does +1/-1 only)
def gen_random ():
    import random
    d = random.randrange (0, 120)
    if d == 0:
        return 1
    elif d % 2 == 0:
        return (gen_random (), 1)
    elif d % 2 == 1:
        return (1, gen_random())

def canon_n (n):
    if n == 0:
        return ZERO
    elif n > 0:
        r = ZERO
        while n:
            r = canon_successor (r)
            n -= 1
        return r
    else:
        r = ZERO
        while n < 0:
            r = canon_predecessor (r)
            n += 1
        return r

# here is the canonical form:
#  positive numbers are of the form (<n-1>, -1)
#  negative numbers are of the form (<n+1>, 1)

# (<n-1>, -1)
# -1  = (zero,1)
# zero: (1,1)
# one: 1
# two: (1, -1)
# three: (two, -1)
# four: (three, -1)

# -1 = (zero, 1)
# -two = (-1, 1)
# -three = (-two, 1)
# -four = (-three, 1)

ZERO = (1,1)
NEG1 = (ZERO,1)
POS1 = 1

def canon_positive (t):
    return t == POS1 or t[1] == NEG1

def canon_negative (t):
    return t != POS1 and t[1] == POS1

def canon_successor (t):
    if t == ZERO:
        return POS1
    elif t == NEG1:
        return ZERO
    elif t == POS1 or canon_positive (t):
        return (t, NEG1)
    else:
        #assert (t[1] == POS1)
        return t[0]

def canon_predecessor (t):
    if t == ZERO:
        return NEG1
    elif t == POS1:
        return ZERO
    elif t == NEG1 or canon_negative (t):
        return (t, POS1)
    else:
        #assert (t[1] == NEG1)
        return t[0]

PLUS = canon_successor
MINUS = canon_predecessor

import sys
W = sys.stderr.write

def canon (t):
    if t == ZERO:
        return t
    elif t == NEG1:
        return t
    elif t == POS1:
        return t
    else:
        a, b = oa, ob = t
        a = canon (a)
        #assert (is_canon (a))
        b = canon (b)
        #assert (is_canon (b))
        while 1:
            #an = to_number (a)
            #bn = to_number (b)
            #print an, bn
            if b == NEG1:
                #W ('<')
                # is this well-formed?
                if a == ZERO:
                    return POS1
                elif a == NEG1:
                    return ZERO
                elif canon_negative (a):
                    # no: (-5, -1)
                    # fix: (-3, 1)
                    a = canon_successor (canon_successor (a))
                    b = POS1
                else:
                    return (a, b)
            elif b == POS1:
                #W ('>')
                # well-formed?
                if a == ZERO:
                    # (0,1) == ((1,1),1) == NEG1
                    return NEG1
                elif a == NEG1:
                    # (-1,1) == -2
                    return canon_predecessor (NEG1)
                elif a == POS1:
                    return ZERO
                elif canon_positive (a):
                    a = canon_predecessor (canon_predecessor (a))
                    b = NEG1
                else:
                    return (a, b)
            else:
                # non-canonical, fix it.
                # (-,+) => becomes more negative - decrement <b> to 1
                # (+,-) => becomes more positive - increment <b> to -1
                # (+,+) => ???
                # (-,-) => ???
                # whatever <b> is, it needs to be taken up or down toward 1 or -1
                if canon_negative (b):
                    # (5, -2)   == 7  : (6, -1)
                    # (-5, -2)  == 3  : (-4, -1)
                    # b = b + 1
                    b = canon_successor (b)
                    # a = a + 1
                    a = canon_successor (a)
                    #W ("+")
                elif canon_positive (b):
                    # (5, 2)   == 3  : (4, 1)
                    # (-5, 2)  == -7  : (-6, 1)
                    # b = b - 1
                    b = canon_predecessor (b)
                    # a = a + 1
                    a = canon_predecessor (a)
                    #W ("-")
                else:
                    raise ValueError ("impossible?")


def is_canon (t):
    # XXX only meant for debugging
    if t == 1:
        return True
    elif t == (1, 1):
        return True
    elif t[1] == 1:
        # negative number
        if to_number (t[0]) > 1:
            return False
        else:
            return is_canon (t[0])
    elif t[1] == NEG1:
        # positive number
        if to_number (t[0]) < 1:
            return False
        else:
            return is_canon (t[0])
    else:
        return False

if __name__ == '__main__':
    #bad_zero = (((((((1, 1), 1), ((1, 1), 1)), 1), 1), ((1, 1), 1)), ((1, 1), 1))
    #bad_neg2 = (((((1, 1), 1), ((1, 1), 1)), 1), 1)
    #bad_three = (1,(((1,1),1),1))
    #canon (bad_three)
    for i in range (300):
        n = gen_random()
        val = to_number (n)
        W ('[%d]' % (val,))
        n2 = canon_n (val)
        n3 = canon (n)
        assert (to_number (n2) == val)
        assert (to_number (n3) == val)
        assert (n3 == n2)