def filter(shape):
    """Serve as a template for future functions that filter geometry"""
    if shape is None:
        return None
    t = Transform()
    t.rotate(45)
    return t.map(shape)

def align(shape, position, halign="center", valign="middle"):
    """Align a shape in relation to the origin."""
    if shape is None: return None
    x, y = position.x, position.y
    bounds = shape.bounds
    if halign == "left":
        dx = x - bounds.x
    elif halign == "right":
        dx = x - bounds.x - bounds.width
    elif halign == "center":
        dx = x - bounds.x - bounds.width / 2
    else:
        dx = 0
    if valign == "top":
        dy = y - bounds.y
    elif valign == "bottom":
        dy = y - bounds.y - bounds.height
    elif valign == "middle":
        dy = y - bounds.y - bounds.height / 2
    else:
        dy = 0
        
    t = Transform()
    t.translate(dx, dy)
    return t.map(shape)

def parse_transform(e, path):
    
    """ Transform the path according to a defined matrix.
    
    Attempts to extract a transform="matrix()|translate()" attribute.
    Transforms the path accordingly.
    
    """
    
    t = get_attribute(e, "transform", default="")
    
    for mode in ("matrix", "translate"):
        if t.startswith(mode):
            v = t.replace(mode, "").lstrip("(").rstrip(")")
            v = v.replace(", ", ",").replace(" ", ",")
            v = [float(x) for x in v.split(",")]
            from nodebox.graphics import Transform
            if mode == "matrix":
                t = Transform(*v)
            elif mode == "translate":
                t = Transform()            
                t.translate(*v)
            path = t.map(path)
            break

    # Transformations can also be defined as <g transform="matrix()"><path /><g>
    # instead of <g><path transform="matrix() /></g>.
    e = e.parentNode
    if e and e.tagName == "g":
        path = parse_transform(e, path)
        
    return path

def wiggle_contours(contours, offset):
    new_contours = []
    for contour in contours:
        dx = (uniform(0, 1) - 0.5) * offset.x * 2
        dy = (uniform(0, 1) - 0.5) * offset.y * 2
        t = Transform()
        t.translate(dx, dy)
        new_contours.append(Contour(t.map(contour.points), contour.closed))
    return new_contours

def wiggle_paths(paths, offset):
    new_paths = []
    for path in paths:
        dx = (uniform(0, 1) - 0.5) * offset.x * 2
        dy = (uniform(0, 1) - 0.5) * offset.y * 2
        t = Transform()
        t.translate(dx, dy)
        new_paths.append(t.map(path))
    return new_paths

def copy(shape, copies, transform_order='tsr', translate=Point.ZERO, rotate=0, scale=Point.ZERO):
    """Create multiple copies of a shape."""
    if shape is None: return None
    if isinstance(shape, Path):
        shape = shape.asGeometry()
    g = Geometry()
    tx = ty = r = 0.0
    sx = sy = 1.0
    for i in xrange(copies):
        t = Transform()
        # Each letter of the order describes an operation.
        for op in transform_order:
            if op == 't':
                t.translate(tx, ty)
            elif op == 'r':
                t.rotate(r)
            elif op == 's':
                t.scale(sx, sy)
        g.extend(t.map(shape))
        tx += translate.x
        ty += translate.y
        r += rotate
        sx += scale.x / 100.0
        sy += scale.y / 100.0
    return g

 def shape_intersects(distance):
     tx, ty = coordinates(0, 0, distance, angle)
     t = Transform()
     t.translate(tx, ty)
     translated_shape = t.map(shape)
     if use_bounding_box:
         b = Path()
         b.cornerRect(translated_shape.bounds)
     else:
         b = translated_shape
     # If the shape intersects it is too close (the distance is too low).
     if bounding_path.intersects(b):
         return -1
     return 1

def fit(shape, position, width, height, keep_proportions):
    """Fit a shape within bounds."""
    if shape is None: return None

    px, py, pw, ph = list(shape.bounds)

    # Make sure pw and ph aren't infinitely small numbers.
    # This will lead to incorrect transformations with for examples lines.
    if 0 < pw <= 0.000000000001: pw = 0
    if 0 < ph <= 0.000000000001: ph = 0

    t = Transform()
    t.translate(position.x, position.y)
    if keep_proportions:
        # Don't scale widths or heights that are equal to zero.
        w = pw and width / pw or float("inf")
        h = ph and height / ph or float("inf")
        w = h = min(w, h)
    else:
        # Don't scale widths or heights that are equal to zero.
        w = pw and width / pw or 1
        h = ph and height / ph or 1
    t.scale(w, h)
    t.translate(-pw / 2 - px, -ph / 2 - py)

    return t.map(shape)

def scale(shape, scale, origin=Point.ZERO):
    """Scale the given shape."""
    if shape is None: return None
    t = Transform()
    t.translate(origin)
    t.scale(scale.x / 100.0, scale.y / 100.0)
    t.translate(Point(-origin.x, -origin.y))
    return t.map(shape)

def rotate(shape, angle, origin=Point.ZERO):
    """Rotate the given shape."""
    if shape is None: return None
    t = Transform()
    t.translate(origin)
    t.rotate(angle)
    t.translate(Point(-origin.x, -origin.y))
    return t.map(shape)

 def scale(s):
     a = to_number_array(s)
     sx = a[0]
     sy = sx
     if len(a) > 1:
         sy = a[1]
     return Transform.scaled(sx, sy)

 def translate(s):
     a = to_number_array(s)
     tx = a[0]
     ty = 0
     if len(a) > 1:
         ty = a[1]
     return Transform.translated(tx, ty)

def get_svg_attributes(node, parent_attributes={}):
    if parent_attributes:
        attributes = dict(parent_attributes)
    else:
        attributes = dict()

    transform = parse_transform(node)
    if transform and not transform.equals(Transform()):
        if attributes.has_key("transform"):
            t = Transform(attributes["transform"])
            t.append(transform)
            attributes["transform"] = t
        else:
            attributes["transform"] = transform

    color_attrs = parse_color_info(node)
    attributes.update(color_attrs)

    return attributes

def shape_on_path(shape, template, amount, dist, start, keep_geometry):
    if shape is None: return None
    if template is None: return None
    
    if isinstance(shape, Path):
        shape = shape.asGeometry()
    if isinstance(template, Path):
        template = template.asGeometry()
        
    g = Geometry()

    if keep_geometry:
        g.extend(template.clone())
           
    first = True  
    for i in range(amount):
        if first:
            t = start / 100
            first = False
        else:
            t += dist / 500.0
        pt1 = template.pointAt(t)
        pt2 = template.pointAt(t + 0.00001)
        a = angle(pt2.x, pt2.y, pt1.x, pt1.y)
        tp = Transform()
        tp.translate(pt1.x, pt1.y)
        tp.rotate(a - 180)
        new_shape = tp.map(shape)
        g.extend(new_shape)
    return g

def angle_pack(shapes, seed, limit, maximum_radius, angle_tries=1, use_bounding_box=False):
    if shapes is None: return None
    _seed(seed)

    def center_and_translate(shape, tx=0, ty=0):
        bx, by, bw, bh = list(shape.bounds)
        t = Transform()
        t.translate(-bw / 2 - bx, -bh / 2 - by)
        return t.map(shape)

    geo = Geometry()
    bounding_path = Path()

    # Center first shape
    first_shape = center_and_translate(shapes[0])
    geo.add(first_shape)
    bounding_path.cornerRect(first_shape.bounds)

    for shape in shapes[1:]:
        centered_shape = center_and_translate(shape)

        angles = []
        for i in range(angle_tries):
            a = uniform(0, 360)
            if use_bounding_box:
                d = try_angle(bounding_path, centered_shape, a, limit, maximum_radius, use_bounding_box)
            else:
                d = try_angle(geo, centered_shape, a, limit, maximum_radius, use_bounding_box)
            angles.append([d, a])
        chosen_distance, chosen_angle = sorted(angles)[0]

        tx, ty = coordinates(0, 0, chosen_distance, chosen_angle)
        t = Transform()
        t.translate(tx, ty)
        translated_shape = t.map(centered_shape)
        bounding_path.cornerRect(translated_shape.bounds)
        geo.add(translated_shape)

    return geo

def add_transform_matrix(e, path):
    
    """ Transform the path according to a defined matrix.
    
    Attempts to extract a transform="matrix()" attribute.
    Transforms the path according to this matrix.
    
    """
    
    matrix = get_attribute(e, "transform", default="")
    if matrix.startswith("matrix("):
        
        matrix = matrix.replace("matrix(", "").rstrip(")")
        matrix = matrix.split(",")
        matrix = [float(v) for v in matrix]
    
        from nodebox.graphics import Transform
        t = Transform()
        t._set_matrix(matrix)
        path = t.transformBezierPath(path)
        
    return path

def pack(shapes, iterations, padding, seed):
    _seed(seed)
    packed_objects = []
    for path in shapes:
        packed_objects.append(PackObject(path))
    for i in xrange(1, iterations):
        _pack(packed_objects, damping=0.1/i, padding=padding)


    geo = Geometry()
    for po in packed_objects:
        print po.x, po.y
        p = Transform.translated(po.x, po.y).map(po.path)
        geo.add(p)
    return geo

 def rotate(s):
     a = to_number_array(s)
     r = a[0]
     tx = 0
     ty = 0
     if len(a) > 1:
         tx = a[1]
     if len(a) > 2:
         ty = a[2]
     t = Transform()
     t.translate(tx, ty)
     t.rotate(r)
     t.translate(-tx, -ty)
     return t

def import_svg(file_name, centered=False, position=Point.ZERO):
    """Import geometry from a SVG file."""
    # We defer loading the SVG library until we need it.
    # This makes creating a node faster.
    import svg
    if not file_name: return None
    f = file(file_name, 'r')
    s = f.read()
    f.close()
    g = Geometry()
    paths = svg.parse(s, True)
    for path in paths:
        g.add(path)
    t = Transform()
    if centered:
        x, y, w, h = list(g.bounds)
        t.translate(-x-w/2, -y-h/2)
    t.translate(position)
    g = t.map(g)
    return g

def shape_on_path(shapes, path, amount, alignment, spacing, margin, baseline_offset):
    if not shapes:
        return []
    if path is None:
        return []

    if alignment == "trailing":
        shapes = list(shapes)
        shapes.reverse()

    length = path.length - margin
    m = margin / path.length
    c = 0

    new_shapes = []
    for i in xrange(amount):
        for shape in shapes:
            if alignment == "distributed":
                p = length / ((amount * len(shapes)) - 1)
                pos = c * p / length
                pos = m + (pos * (1 - 2 * m))
            else:
                pos = ((c * spacing) % length) / length
                pos = m + (pos * (1 - m))

                if alignment == "trailing":
                    pos = 1 - pos

            p1 = path.pointAt(pos)
            p2 = path.pointAt(pos + 0.0000001)
            a = angle(p1.x, p1.y, p2.x, p2.y)
            if baseline_offset:
                coords = coordinates(p1.x, p1.y, baseline_offset, a - 90)
                p1 = Point(*coords)
            t = Transform()
            t.translate(p1)
            t.rotate(a)
            new_shapes.append(t.map(shape))
            c += 1

    return new_shapes