# Copyright 2004, Nathaniel Smith <njs@pobox.com>.
# 
# You must be this |-------------------------------| geeky to use this module.
# (Line not drawn to scale.)
# 
# Released under the terms of the GNU GPL v2, or, at your discretion, any
# later version.  (cf. http://www.gnu.org/philosophy/why-not-lgpl.html)

from sets import ImmutableSet

class Number(ImmutableSet):

    if __debug__:
        def __new__(class_, iterable=None):
            l = list(iterable or [])
            for e in l:
                assert isinstance(e, Number)
            return ImmutableSet.__new__(class_, l)

    def successor(self):

        return Number(self.union(ImmutableSet([self])))

    def predecessor(self):

        return max(self)


    def __add__(self, other):

        if other == Zero:
            return self
        else:
            return (self + other.predecessor()).successor()

    def __sub__(self, other):

        if other == Zero:
            return self
        else:
            return (self - other.predecessor()).predecessor()

    def __mul__(self, other):

        if other == Zero:
            return Zero
        else:
            return (self * other.predecessor()) + self


    def __floordiv__(self, other):

        if self < other:
            return Zero
        else:
            return ((self - other) // other).successor()

    def __mod__(self, other):

        if self < other:
            return self
        else:
            return (self - other) % other

    def __divmod__(self, other):

        return (self // other, self % other)


    def __pow__(self, other):

        if other == Zero:
            return Zero.successor()
        elif other % Zero.successor().successor():
            return self * (self ** (other.predecessor()))
        else:
            return (self * self) ** (other // Zero.successor().successor())
            

    def __lshift__(self, other):

        if other == Zero:
            return self
        else:
            return (self * Zero.successor().successor()) << other.predecessor()

    def __rshift__(self, other):

        if other == Zero:
            return self
        else:
            return (self // Zero.successor().successor()) << other.predecessor()


    def __and__(self, other):

        One = Zero.successor()
        Two = One.successor()
        if other == Zero:
            return Zero
        elif self % Two and other % Two:
            return ((self >> One & other >> One) << One).successor()
        else:
            return (self >> One & other >> One) << One

    def __or__(self, other):

        One = Zero.successor()
        Two = One.successor()
        if other == Zero:
            return self
        elif self % Two or other % Two:
            return ((self >> One | other >> One) << One).successor()
        else:
            return (self >> One | other >> One) << One

    def __xor__(self, other):

        One = Zero.successor()
        Two = One.successor()
        if other == Zero:
            return self
        elif self % Two and not other % Two:
            return ((self >> One ^ other >> One) << One).successor()
        elif not self % Two and other % Two:
            return ((self >> One ^ other >> One) << One).successor()
        else:
            return (self >> One ^ other >> One) << One


    def __nonzero__(self):

        return self != Zero


    def __str__(self):

        if self <= _FormattingStuff.Nine:
            return _FormattingStuff.digits[self]
        else:
            return str(self // _FormattingStuff.Ten) \
                   + _FormattingStuff.digits[self % _FormattingStuff.Ten]

    def __hex__(self):

        if self <= _FormattingStuff.Fifteen:
            return "0x" + _FormattingStuff.digits[self]
        else:
            return "0x" + hex(self // _FormattingStuff.Sixteen)[2:] \
                   + _FormattingStuff.digits[self % _FormattingStuff.Sixteen]

    def __oct__(self):

        if self <= _FormattingStuff.Seven:
            return "0" + _FormattingStuff.digits[self]
        else:
            return "0" + oct(self // _FormattingStuff.Eight)[1:] \
                   + _FormattingStuff.digits[self % _FormattingStuff.Eight]

    def from_string(string, base=None):

        if base is None:
            base = _FormattingStuff.Ten
        if base > _FormattingStuff.Sixteen:
            raise ValueError, "Base must be 16 or less"
        if not string:
            return Zero
        else:
            return Number.from_string(string[:-1], base) * base \
                   + _FormattingStuff.numbers[string[-1]]
    from_string = staticmethod(from_string)


    # Backwards compatibility:
    def from_int(n_int):
        n = Zero
        # Use xrange for efficiency.
        for i in xrange(n_int):
            n = n.successor()
        return n
    from_int = staticmethod(from_int)
    
    def to_int(self):
        return len(self)


Zero = Number()


class _FormattingStuff:
    """Collection of constants needed for formatting.  If we could make array
    indexing work this wouldn't be necessary..."""

    One = Zero.successor()
    Two = One.successor()
    Three = Two.successor()
    Four = Three.successor()
    Five = Four.successor()
    Six = Five.successor()
    Seven = Six.successor()
    Eight = Seven.successor()
    Nine = Eight.successor()
    Ten = Nine.successor()
    Eleven = Ten.successor()
    Twelve = Eleven.successor()
    Thirteen = Twelve.successor()
    Fourteen = Thirteen.successor()
    Fifteen = Fourteen.successor()
    Sixteen = Fifteen.successor()
    digits = { Zero: "0",
               One: "1",
               Two: "2",
               Three: "3",
               Four: "4",
               Five: "5",
               Six: "6",
               Seven: "7",
               Eight: "8",
               Nine: "9",
               Ten: "a",
               Eleven: "b",
               Twelve: "c",
               Thirteen: "d",
               Fourteen: "e",
               Fifteen: "f",
               }
    numbers = dict(zip(digits.values(), digits.keys()))


if __name__ == "__main__":

    print "2 + 2 =", \
          Number.from_int(2) + Number.from_int(2)
    print "3 - 1 =", \
          Number.from_int(3) - Number.from_int(1)
    print "2 * 3 =", \
          Number.from_int(2) * Number.from_int(3)
    print "12 / 4 =", \
          Number.from_int(12) // Number.from_int(4)
    print "10 % 3 =", \
          Number.from_int(10) % Number.from_int(3)
    print "2 ** 7 =", \
          Number.from_int(2) ** Number.from_int(7)
    print "5 & 3 =", \
          Number.from_int(5) & Number.from_int(3)
    print "5 | 3 =", \
          Number.from_int(5) | Number.from_int(3)
    print "5 ^ 3 =", \
          Number.from_int(5) ^ Number.from_int(3)

    print "str(20) =", str(Number.from_int(20))
    print "oct(20) =", oct(Number.from_int(20))
    print "hex(20) =", hex(Number.from_int(20))

    print 'from_string("20") = ', Number.from_string("20")
    print 'from_string("20", 16) = ', Number.from_string("20",
                                                         Number.from_int(16))