'''Polynomial

A Package which does simple polynomial arithmetic and evaluations.
Supports PleasePardonMyDearAuntSally.  :)'''

import string, types

FunctionalTypes = [ types.BuiltinMethodType, types.BuiltinFunctionType, types.FunctionType, types.LambdaType, types.MethodType, types.UnboundMethodType ]

class Operator:
    Positive	= lambda x: +x
    Negate        = lambda x: -x
    Not		= lambda x: ~x
    Add		= lambda x, y: x + y
    Subtract      = lambda x, y: x - y
    Multiply	= lambda x, y: x * y
    Devide        = lambda x, y: x / y
    Modulo        = lambda x, y: x % y
    Power         = pow # lambda x, y: x**y
    Equals        = lambda x, y: x == y
    LessThan	= lambda x, y: x < y
    GreaterThan	= lambda x, y: x > y
    NotEqual	= lambda x, y: x != y
    LTE		= lambda x, y: x <= y
    GTE		= lambda x, y: x >= y
    And		= lambda x, y: x & y
    Or		= lambda x, y: x | y
    Xor		= lambda x, y: x ^ y
    ShiftLeft	= lambda x, y: x << y
    ShiftRight	= lambda x, y: x >> y

    BuiltInUnary = [ Positive, Negate, Not ]
    BuiltInBinary = [ Add, Subtract, Multiply, Devide, Modulo, Power, Equals, LessThan, GreaterThan, NotEqual, LTE, GTE, And, Or, Xor, ShiftLeft, ShiftRight ]

    def __init__(self):
        raise SyntaxError, "Cannot create instances of the Operator class."

def ParseString(s, shortform = 0):
    '''ParseString(s, shortform = 0)
    
    A Parser that can turn a string representation of a Polynomial "s",
    expressed using standard Python syntax, into a Polynomial Expression
    Tree in Reduced Expression Form.

    If the shortform flag is set, all variables are assumed to be single-
    character and multiplication is implicit.'''
    
    parsestack = [ ]
    UnaryMap = { }
    BinaryMap = { }
    
    templist = [ '+', '-', '~' ]
    for i in range(len(Operator.BuiltInUnary)):
        UnaryMap[templist[i]] = Operator.BuiltInUnary[i]
    
    templist = [ '+', '-', '*', '/', '%', '**', '==', '<', '>', '!=', '<=', '>=', '&', '|', '^', '<<', '>>' ]
    for i in range(len(Operator.BuiltInBinary)):
        BinaryMap[templist[i]] = Operator.BuiltInBinary[i]
    BinaryMap['='] = Operator.Equals
    
    ParenMap = { '{' : '}', '[' : ']', '(' : ')' }
    separators = [ ',' ]
    alpha = string.letters
    numeric = string.digits
    
    i = 0
    while (i < len(s)):
        # Parenthesis...
        if s[i] in ParenMap.keys():
            start = i + 1
            end = string.find(s, ParenMap[s[i]])
            if end == -1:
                raise ValueError, "Mismatched Parentheses."
    
            inside = self.ParseString(s[start:end])
            i = end
    
            if len(paramstack) == 0:
                paramstack.append(inside)
            elif paramstack[-1] in Operator.BuiltInUnary:
                temp = Operator(paramstack[-1], inside)
                paramstack[-1] = temp
            elif paramstack[-1] in Operator.BuiltInUnary:
                if len(paramstack) < 2:
                    raise ValueError, "Binary Operator use without left hand term."
                temp = Operator(paramstack[-2], paramstack[-1], inside)
                del paramstack[-1]
                paramstack[-1] = temp
    
        elif s[i] in ParenMap.values():
            raise ValueError, "Mismatched Parentheses."
    
        # Separator (Comma)
        elif s[i] in separators:
            # Parse Beginning (Existing Stack)
            lhs = None
    
            # return Tuple:
            rhs = self.ParseString(s[i+1:])
            if (type(rhs) == types.TupleType):
                return ( lhs, ) + rhs
            else:
                return ( lhs, rhs )
    
        elif s[i] in operators:
            start = i
    
        # iterate
        i = i + 1

class Polynomial:
    def __init__(self, *x):
        if len(x) == 0:
            self.fn = None
            self.terms = ( )
        elif type(x[0]) == types.StringType and (len(x) == 1 or (len(x) == 2 and x[2] not in FunctionalTypes)):
            # call ParseString
            pass
        elif type(x[0]) in FunctionalTypes:
            # Generic Function (Prefix)
            self.fn = x[0]
            self.terms = x[1:]
        elif type(x[-1]) in FunctionalTypes:
            # Generic Postfix Function
            self.fn = x[-1]
            self.terms = x[:-1]
        elif len(x) > 1 and type(x[2]) in FunctionTypes:
            if len(x) != 3:
                raise ValueError, "Infix expressions must have exactly 2 parameters."
            else:
                # Infix Binary Expression
                self.fn = x[1]
                self.terms = (x[0], x[2])
        else:
            # Void function
            self.fn = None
            self.terms = x

    def Expand(self):
        # Expand Terms (Recursive)
        # If any Terms are bound by the same function as the current operator, promote them
        # if current fn is Multiply and term function uses Add, Distribute Terms
        pass

    def Factor(self):
        # Expand
        # Use Haps Magic Number Method or otherwise to find roots
        pass

    def __len__(self):
        return len(self.terms)

    def __add__(self, other):
        if self.exTree.fn == Operator.Add:
            self.exTree.append(other)
        else:
            self.exTree = Operator(self.exTree, Operator.Add, other)
    __radd__ = __add__

    def __sub__(self, other):
        if self.exTree.fn == Operator.Subtract:
            self.exTree.append(other)
        else:
            self.exTree = Operator(self.exTree, Operator.Subtract, other)
    __rsub__ = __sub__

    def __mul__(self, other):
        if self.exTree.fn == Operator.Multiply:
            self.exTree.append(other)
        else:
            self.exTree = Operator(self.exTree, Operator.Multiply, other)
    __rmul__ = __mul__

    def __div__(self, other):
        if self.exTree.fn == Operator.Divide:
            self.exTree.append(other)
        else:
            self.exTree = Operator(self.exTree, Operator.Divide, other)
    __rdiv__ = __div__

    def __pow__(self, other):
        if self.exTree.fn == Operator.Power:
            self.exTree.append(other)
        else:
            self.exTree = Operator(self.exTree, Operator.Power, other)
    __rpow__ = __pow__

    def __pos__(self):
        self.exTree = Operator(Operator.Positive, self.exTree)

    def __neg__(self):
        self.exTree = Operator(Operator.Negate, self.exTree)

    def __call__(self, *param):
        # Evaluate Polynomial where varaibles are replaced with *param
        pass

'''
Misc:

def listprimes(x):
	if x < 2:
		return [ ]
	elif x == 2:
		return [ 2 ]
	else:
		l = [ 2 ]
		for i in range(3, x, 2):
			for n in l:
				if n**2 > i:
					l.append(i)
					break;
				elif i % n == 0:
					break;
		return l

def choose(l, n):
	if n <= 0:
		return [ [ ] ]
	elif n >= len(l):
		return [ l ]
	else:
		combos = [ ]
		for i in range(len(l) - n + 1):
			with = choose(l[i + 1:], n - 1)
			for j in range(len(with)):
				with[j] = [ l[i] ] + with[j]
			combos = combos + with
		return combos

def sets(l):
	set = [ ]
	for n in range(len(l) + 1):
		set = set + choose(l, n)
	return set

def getdivodds(l):
	s = sets(l)
	odds = 0.0
	for i in s:
		term = 1.0 / reduce(lambda x, y: x * y, i, 1.0)
		if (len(i) & 1):
			odds = odds - term
		else:
			odds = odds + term
	return odds

'''