import random
import sys
import multiprocessing
from euclid import *
from elementtree.ElementTree import ElementTree as etree
from elementtree.ElementTree import fromstring

class LSystem:

    """
    Takes an XML string.
    """
    def __init__(self, rules):
        self._tree = fromstring(rules)
        self._maxDepth = int(self._tree.get("max_depth"))
        self._maxThreads = multiprocessing.cpu_count()
        self._availableThreads = self._maxThreads - 1;
        self._progressCount = 0

    """
    Returns a list of "shapes".
    Each shape is a 2-tuple: (shape name, transform matrix).
    """
    def evaluate(self, seed = 0):
        random.seed(seed)
        rule = _pickRule(self._tree, "entry")
        entry = (rule, 0, Matrix4.new_identity())
        shapes = self._evaluate(entry)
        return shapes
        
    def _evaluate(self, entry):
        stack = [entry]
        shapes = []
        while len(stack) > 0:
    
            if len(shapes) > self._progressCount + 1000:
                print len(shapes), "curve segments so far"
                self._progressCount = len(shapes)
        
            rule, depth, matrix = stack.pop()
    
            local_max_depth = self._maxDepth
            if "max_depth" in rule.attrib:
                local_max_depth = int(rule.get("max_depth"))
    
            if len(stack) >= self._maxDepth:
                shapes.append(None)
                continue
    
            if depth >= local_max_depth:
                if "successor" in rule.attrib:
                    successor = rule.get("successor")
                    rule = _pickRule(self._tree, successor)
                    stack.append((rule, 0, matrix))
                shapes.append(None)
                continue
        
            for statement in rule:
                xform = _parseXform(statement.get("transforms", ""))
                count = int(statement.get("count", 1))
                for n in xrange(count):
                    matrix *= xform
                    
                    if statement.tag == "call":
                        rule = _pickRule(self._tree, statement.get("rule"))
                        cloned_matrix = matrix.copy()
                        entry = (rule, depth + 1, cloned_matrix)
                        if True or self._availableThreads <= 0:
                            stack.append(entry)
                        else:
                            self._spawn(entry)
                           
                    elif statement.tag == "instance":
                        name = statement.get("shape")
                        if name == "curve":
                            P = Point3(0, 0, 0)
                            N = Vector3(0, 0, 1)
                            P = matrix * P
                            N = matrix.upperLeft() * N
                            shapes.append((P, N))
                        else:
                            shape = (name, matrix)
                            shapes.append(shape)
                    else:
                        print "malformed xml"
                        quit()
    
        print "\nGenerated %d shapes." % len(shapes)
        return shapes
        # end of _evaluate
        
#    def _spawn(self, entry):
#        with LOCK:
#            self._availableThreads = self._availableThreads - 1
#            insertionPoint = len(self._shapes)
#            
#        def closure():
#            shapes = self._evaluate(entry)
            
           
        
def _pickRule(tree, name):

    rules = tree.findall("rule")
    elements = []
    for r in rules:
        if r.get("name") == name:
            elements.append(r)

    if len(elements) == 0:
        print "Error, no rules found with name '%s'" % name
        quit()

    sum, tuples = 0, []
    for e in elements:
        weight = int(e.get("weight", 1))
        sum = sum + weight
        tuples.append((e, weight))
    n = random.randint(0, sum - 1)
    for (item, weight) in tuples:
        if n < weight:
            break
        n = n - weight
    return item

_xformCache = {}

def _parseXform(xform_string):
    if xform_string in _xformCache:
        return _xformCache[xform_string]
        
    matrix = Matrix4.new_identity()
    tokens = xform_string.split(' ')
    t = 0
    while t < len(tokens) - 1:
        command, t = tokens[t], t + 1

        # Translation
        if command == 'tx':
            x, t = float(tokens[t]), t + 1
            matrix *= Matrix4.new_translate(x, 0, 0)
        elif command == 'ty':
            y, t = float(tokens[t]), t + 1
            matrix *= Matrix4.new_translate(0, y, 0)
        elif command == 'tz':
            z, t = float(tokens[t]), t + 1
            matrix *= Matrix4.new_translate(0, 0, z)
        elif command == 't':
            x, t = float(tokens[t]), t + 1
            y, t = float(tokens[t]), t + 1
            z, t = float(tokens[t]), t + 1
            matrix *= Matrix4.new_translate(x, y, z)

        # Rotation
        elif command == 'rx':
            theta, t = _radians(float(tokens[t])), t + 1
            matrix *= Matrix4.new_rotatex(theta)
        elif command == 'ry':
            theta, t = _radians(float(tokens[t])), t + 1
            matrix *= Matrix4.new_rotatey(theta)
        elif command == 'rz':
            theta, t = _radians(float(tokens[t])), t + 1
            matrix *= Matrix4.new_rotatez(theta)

        # Scale
        elif command == 'sx':
            x, t = float(tokens[t]), t + 1
            matrix *= Matrix4.new_scale(x, 1, 1)
        elif command == 'sy':
            y, t = float(tokens[t]), t + 1
            matrix *= Matrix4.new_scale(1, y, 1)
        elif command == 'sz':
            z, t = float(tokens[t]), t + 1
            matrix *= Matrix4.new_scale(1, 1, z)
        elif command == 'sa':
            v, t = float(tokens[t]), t + 1
            x, y, z = v, v, v
            matrix *= Matrix4.new_scale(x, y, z)
        elif command == 's':
            x, t = float(tokens[t]), t + 1
            y, t = float(tokens[t]), t + 1
            z, t = float(tokens[t]), t + 1
            matrix *= Matrix4.new_scale(x, y, z)

        else:
            print "unrecognized transformation: '%s' at position %d in '%s'" % (command, t, xform_string)
            quit()

    _xformCache[xform_string] = matrix
    return matrix

def _radians(d):
    return float(d * 3.141 / 180.0)
