svgfig.py

Go to the documentation of this file.

# svgfig.py copyright (C) 2008 Jim Pivarski <jpivarski@gmail.com>
# 
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
# 
# Full licence is in the file COPYING and at http://www.gnu.org/copyleft/gpl.html

import re, codecs, os, platform, copy, itertools, math, cmath, random, sys, copy
_epsilon = 1e-5


if re.search("windows", platform.system(), re.I):
  try:
    import _winreg
    _default_directory = _winreg.QueryValueEx(_winreg.OpenKey(_winreg.HKEY_CURRENT_USER, \
                       r"Software\Microsoft\Windows\Current Version\Explorer\Shell Folders"), "Desktop")[0]
#   tmpdir = _winreg.QueryValueEx(_winreg.OpenKey(_winreg.HKEY_CURRENT_USER, "Environment"), "TEMP")[0]
#   if tmpdir[0:13] != "%USERPROFILE%":
#     tmpdir = os.path.expanduser("~") + tmpdir[13:]
  except:
    _default_directory = os.path.expanduser("~") + os.sep + "Desktop"

_default_fileName = "tmp.svg"

_hacks = {}
_hacks["inkscape-text-vertical-shift"] = False

def rgb(r, g, b, maximum=1.):
  """Create an SVG color string "#xxyyzz" from r, g, and b.

  r,g,b = 0 is black and r,g,b = maximum is white.
  """
  return "#%02x%02x%02x" % (max(0, min(r*255./maximum, 255)), max(0, min(g*255./maximum, 255)), max(0, min(b*255./maximum, 255)))

def attr_preprocess(attr):
  for name in attr.keys():
    name_colon = re.sub("__", ":", name)
    if name_colon != name:
      attr[name_colon] = attr[name]
      del attr[name]
      name = name_colon

    name_dash = re.sub("_", "-", name)
    if name_dash != name:
      attr[name_dash] = attr[name]
      del attr[name]
      name = name_dash

  return attr

class SVG:
  """A tree representation of an SVG image or image fragment.

  SVG(t, sub, sub, sub..., attribute=value)

  t                       required             SVG type name
  sub                     optional list        nested SVG elements or text/Unicode
  attribute=value pairs   optional keywords    SVG attributes

  In attribute names, "__" becomes ":" and "_" becomes "-".

  SVG in XML

  <g id="mygroup" fill="blue">
      <rect x="1" y="1" width="2" height="2" />
      <rect x="3" y="3" width="2" height="2" />
  </g>

  SVG in Python

  >>> svg = SVG("g", SVG("rect", x=1, y=1, width=2, height=2), \ 
  ...                SVG("rect", x=3, y=3, width=2, height=2), \ 
  ...           id="mygroup", fill="blue")

  Sub-elements and attributes may be accessed through tree-indexing:

  >>> svg = SVG("text", SVG("tspan", "hello there"), stroke="none", fill="black")
  >>> svg[0]
  <tspan (1 sub) />
  >>> svg[0, 0]
  'hello there'
  >>> svg["fill"]
  'black'

  Iteration is depth-first:

  >>> svg = SVG("g", SVG("g", SVG("line", x1=0, y1=0, x2=1, y2=1)), \
  ...                SVG("text", SVG("tspan", "hello again")))
  ... 
  >>> for ti, s in svg:
  ...     print ti, repr(s)
  ... 
  (0,) <g (1 sub) />
  (0, 0) <line x2=1 y1=0 x1=0 y2=1 />
  (0, 0, 'x2') 1
  (0, 0, 'y1') 0
  (0, 0, 'x1') 0
  (0, 0, 'y2') 1
  (1,) <text (1 sub) />
  (1, 0) <tspan (1 sub) />
  (1, 0, 0) 'hello again'

  Use "print" to navigate:

  >>> print svg
  None                 <g (2 sub) />
  [0]                      <g (1 sub) />
  [0, 0]                       <line x2=1 y1=0 x1=0 y2=1 />
  [1]                      <text (1 sub) />
  [1, 0]                       <tspan (1 sub) />
  """
  def __init__(self, *t_sub, **attr):
    if len(t_sub) == 0: raise TypeError("SVG element must have a t (SVG type)")

    # first argument is t (SVG type)
    self.t = t_sub[0]
    # the rest are sub-elements
    self.sub = list(t_sub[1:])
    
    # keyword arguments are attributes
    # need to preprocess to handle differences between SVG and Python syntax
    self.attr = attr_preprocess(attr)

  def __getitem__(self, ti):
    """Index is a list that descends tree, returning a sub-element if
    it ends with a number and an attribute if it ends with a string."""
    obj = self
    if isinstance(ti, (list, tuple)):
      for i in ti[:-1]: obj = obj[i]
      ti = ti[-1]

    if isinstance(ti, (int, long, slice)): return obj.sub[ti]
    else: return obj.attr[ti]

  def __setitem__(self, ti, value):
    """Index is a list that descends tree, returning a sub-element if
    it ends with a number and an attribute if it ends with a string."""
    obj = self
    if isinstance(ti, (list, tuple)):
      for i in ti[:-1]: obj = obj[i]
      ti = ti[-1]

    if isinstance(ti, (int, long, slice)): obj.sub[ti] = value
    else: obj.attr[ti] = value

  def __delitem__(self, ti):
    """Index is a list that descends tree, returning a sub-element if
    it ends with a number and an attribute if it ends with a string."""
    obj = self
    if isinstance(ti, (list, tuple)):
      for i in ti[:-1]: obj = obj[i]
      ti = ti[-1]

    if isinstance(ti, (int, long, slice)): del obj.sub[ti]
    else: del obj.attr[ti]

  def __contains__(self, value):
    """x in svg == True iff x is an attribute in svg."""
    return value in self.attr

  def __eq__(self, other):
    """x == y iff x represents the same SVG as y."""
    if id(self) == id(other): return True
    return isinstance(other, SVG) and self.t == other.t and self.sub == other.sub and self.attr == other.attr

  def __ne__(self, other):
    """x != y iff x does not represent the same SVG as y."""
    return not (self == other)

  def append(self, x):
    """Appends x to the list of sub-elements (drawn last, overlaps
    other primatives)."""
    self.sub.append(x)

  def prepend(self, x):
    """Prepends x to the list of sub-elements (drawn first may be
    overlapped by other primatives)."""
    self.sub[0:0] = [x]

  def extend(self, x):
    """Extends list of sub-elements by a list x."""
    self.sub.extend(x)

  def clone(self, shallow=False):
    """Deep copy of SVG tree.  Set shallow=True for a shallow copy."""
    if shallow:
      return copy.copy(self)
    else:
      return copy.deepcopy(self)

  ### nested class
  class SVGDepthIterator:
    """Manages SVG iteration."""

    def __init__(self, svg, ti, depth_limit):
      self.svg = svg
      self.ti = ti
      self.shown = False
      self.depth_limit = depth_limit

    def __iter__(self): return self

    def next(self):
      if not self.shown:
        self.shown = True
        if self.ti != ():
          return self.ti, self.svg

      if not isinstance(self.svg, SVG): raise StopIteration
      if self.depth_limit != None and len(self.ti) >= self.depth_limit: raise StopIteration

      if "iterators" not in self.__dict__:
        self.iterators = []
        for i, s in enumerate(self.svg.sub):
          self.iterators.append(self.__class__(s, self.ti + (i,), self.depth_limit))
        for k, s in self.svg.attr.items():
          self.iterators.append(self.__class__(s, self.ti + (k,), self.depth_limit))
        self.iterators = itertools.chain(*self.iterators)

      return next(self.iterators)
  ### end nested class

  def depth_first(self, depth_limit=None):
    """Returns a depth-first generator over the SVG.  If depth_limit
    is a number, stop recursion at that depth."""
    return self.SVGDepthIterator(self, (), depth_limit)

  def breadth_first(self, depth_limit=None):
    """Not implemented yet.  Any ideas on how to do it?

    Returns a breadth-first generator over the SVG.  If depth_limit
    is a number, stop recursion at that depth."""
    raise NotImplementedError("Got an algorithm for breadth-first searching a tree without effectively copying the tree?")

  def __iter__(self): return self.depth_first()

  def items(self, sub=True, attr=True, text=True):
    """Get a recursively-generated list of tree-index, sub-element/attribute pairs.

    If sub == False, do not show sub-elements.
    If attr == False, do not show attributes.
    If text == False, do not show text/Unicode sub-elements.
    """
    output = []
    for ti, s in self:
      show = False
      if isinstance(ti[-1], (int, long)):
        if isinstance(s, str): show = text
        else: show = sub
      else: show = attr

      if show: output.append((ti, s))
    return output

  def keys(self, sub=True, attr=True, text=True):
    """Get a recursively-generated list of tree-indexes.

    If sub == False, do not show sub-elements.
    If attr == False, do not show attributes.
    If text == False, do not show text/Unicode sub-elements.
    """
    return [ti for ti, s in self.items(sub, attr, text)]

  def values(self, sub=True, attr=True, text=True):
    """Get a recursively-generated list of sub-elements and attributes.

    If sub == False, do not show sub-elements.
    If attr == False, do not show attributes.
    If text == False, do not show text/Unicode sub-elements.
    """
    return [s for ti, s in self.items(sub, attr, text)]

  def __repr__(self): return self.xml(depth_limit=0)

  def __str__(self):
    """Print (actually, return a string of) the tree in a form useful for browsing."""
    return self.tree(sub=True, attr=False, text=False)

  def tree(self, depth_limit=None, sub=True, attr=True, text=True, tree_width=20, obj_width=80):
    """Print (actually, return a string of) the tree in a form useful for browsing.

    If depth_limit == a number, stop recursion at that depth.
    If sub == False, do not show sub-elements.
    If attr == False, do not show attributes.
    If text == False, do not show text/Unicode sub-elements.
    tree_width is the number of characters reserved for printing tree indexes.
    obj_width is the number of characters reserved for printing sub-elements/attributes.
    """

    output = []

    line = "%s %s" % (("%%-%ds" % tree_width) % repr(None), ("%%-%ds" % obj_width) % (repr(self))[0:obj_width])
    output.append(line)

    for ti, s in self.depth_first(depth_limit):
      show = False
      if isinstance(ti[-1], (int, long)):
        if isinstance(s, str): show = text
        else: show = sub
      else: show = attr

      if show:
        line = "%s %s" % (("%%-%ds" % tree_width) % repr(list(ti)), ("%%-%ds" % obj_width) % ("    "*len(ti) + repr(s))[0:obj_width])
        output.append(line)

    return "\n".join(output)

  def xml(self, indent="    ", newl="\n", depth_limit=None, depth=0):
    """Get an XML representation of the SVG.

    indent      string used for indenting
    newl        string used for newlines
    If depth_limit == a number, stop recursion at that depth.
    depth       starting depth (not useful for users)

    print svg.xml()
    """

    attrstr = []
    for n, v in self.attr.items():
      if isinstance(v, dict):
        v = "; ".join(["%s:%s" % (ni, vi) for ni, vi in v.items()])
      elif isinstance(v, (list, tuple)):
        v = ", ".join(v)
      attrstr.append(" %s=%s" % (n, repr(v)))
    attrstr = "".join(attrstr)

    if len(self.sub) == 0: return "%s<%s%s />" % (indent * depth, self.t, attrstr)

    if depth_limit == None or depth_limit > depth:
      substr = []
      for s in self.sub:
        if isinstance(s, SVG):
          substr.append(s.xml(indent, newl, depth_limit, depth + 1) + newl)
        elif isinstance(s, str):
          substr.append("%s%s%s" % (indent * (depth + 1), s, newl))
        else:
          substr.append("%s%s%s" % (indent * (depth + 1), repr(s), newl))
      substr = "".join(substr)

      return "%s<%s%s>%s%s%s</%s>" % (indent * depth, self.t, attrstr, newl, substr, indent * depth, self.t)

    else:
      return "%s<%s (%d sub)%s />" % (indent * depth, self.t, len(self.sub), attrstr)

  def standalone_xml(self, indent="    ", newl="\n"):
    """Get an XML representation of the SVG that can be saved/rendered.

    indent      string used for indenting
    newl        string used for newlines
    """

    if self.t == "svg": top = self
    else: top = canvas(self)
    return """\
<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">

""" + ("".join(top.__standalone_xml(indent, newl)))  # end of return statement

  def __standalone_xml(self, indent, newl):
    output = [u"<%s" % self.t]

    for n, v in self.attr.items():
      if isinstance(v, dict):
        v = "; ".join(["%s:%s" % (ni, vi) for ni, vi in v.items()])
      elif isinstance(v, (list, tuple)):
        v = ", ".join(v)
      output.append(u" %s=\"%s\"" % (n, v))

    if len(self.sub) == 0:
      output.append(u" />%s%s" % (newl, newl))
      return output

    elif self.t == "text" or self.t == "tspan" or self.t == "style":
      output.append(u">")

    else:
      output.append(u">%s%s" % (newl, newl))

    for s in self.sub:
      if isinstance(s, SVG): output.extend(s.__standalone_xml(indent, newl))
      else: output.append(unicode(s))

    if self.t == "tspan": output.append(u"</%s>" % self.t)
    else: output.append(u"</%s>%s%s" % (self.t, newl, newl))

    return output

  def interpret_fileName(self, fileName=None):
    if fileName == None:
      fileName = _default_fileName
    if re.search("windows", platform.system(), re.I) and not os.path.isabs(fileName):
      fileName = _default_directory + os.sep + fileName
    return fileName

  def save(self, fileName=None, encoding="utf-8", compresslevel=None):
    """Save to a file for viewing.  Note that svg.save() overwrites the file named _default_fileName.

    fileName        default=None            note that _default_fileName will be overwritten if
                                            no fileName is specified. If the extension
                                            is ".svgz" or ".gz", the output will be gzipped
    encoding        default="utf-8"       file encoding (default is Unicode)
    compresslevel   default=None            if a number, the output will be gzipped with that
                                            compression level (1-9, 1 being fastest and 9 most
                                            thorough)
    """
    fileName = self.interpret_fileName(fileName)

    if compresslevel != None or re.search("\.svgz$", fileName, re.I) or re.search("\.gz$", fileName, re.I):
      import gzip
      if compresslevel == None:
        f = gzip.GzipFile(fileName, "w")
      else:
        f = gzip.GzipFile(fileName, "w", compresslevel)

      f = codecs.EncodedFile(f, "utf-8", encoding)
      f.write(self.standalone_xml())
      f.close()

    else:
      f = codecs.open(fileName, "w", encoding=encoding)
      f.write(self.standalone_xml())
      f.close()

  def inkview(self, fileName=None, encoding="utf-8"):
    """View in "inkview", assuming that program is available on your system.

    fileName        default=None            note that any file named _default_fileName will be
                                            overwritten if no fileName is specified. If the extension
                                            is ".svgz" or ".gz", the output will be gzipped
    encoding        default="utf-8"       file encoding (default is Unicode)
    """
    fileName = self.interpret_fileName(fileName)
    self.save(fileName, encoding)
    os.spawnvp(os.P_NOWAIT, "inkview", ("inkview", fileName))

  def inkscape(self, fileName=None, encoding="utf-8"):
    """View in "inkscape", assuming that program is available on your system.

    fileName        default=None            note that any file named _default_fileName will be
                                            overwritten if no fileName is specified. If the extension
                                            is ".svgz" or ".gz", the output will be gzipped
    encoding        default="utf-8"       file encoding (default is Unicode)
    """
    fileName = self.interpret_fileName(fileName)
    self.save(fileName, encoding)
    os.spawnvp(os.P_NOWAIT, "inkscape", ("inkscape", fileName))

  def firefox(self, fileName=None, encoding="utf-8"):
    """View in "firefox", assuming that program is available on your system.

    fileName        default=None            note that any file named _default_fileName will be
                                            overwritten if no fileName is specified. If the extension
                                            is ".svgz" or ".gz", the output will be gzipped
    encoding        default="utf-8"       file encoding (default is Unicode)
    """
    fileName = self.interpret_fileName(fileName)
    self.save(fileName, encoding)
    os.spawnvp(os.P_NOWAIT, "firefox", ("firefox", fileName))

######################################################################

_canvas_defaults = {"width": "400px", "height": "400px", "viewBox": "0 0 100 100", \
                   "xmlns": "http://www.w3.org/2000/svg", "xmlns:xlink": "http://www.w3.org/1999/xlink", "version":"1.1", \
                   "style": {"stroke":"black", "fill":"none", "stroke-width":"0.5pt", "stroke-linejoin":"round", "text-anchor":"middle"}, \
                   "font-family": ["Helvetica", "Arial", "FreeSans", "Sans", "sans", "sans-serif"], \
                   }

def canvas(*sub, **attr):
  """Creates a top-level SVG object, allowing the user to control the
  image size and aspect ratio.

  canvas(sub, sub, sub..., attribute=value)

  sub                     optional list       nested SVG elements or text/Unicode
  attribute=value pairs   optional keywords   SVG attributes

  Default attribute values:

  width           "400px"
  height          "400px"
  viewBox         "0 0 100 100"
  xmlns           "http://www.w3.org/2000/svg"
  xmlns:xlink     "http://www.w3.org/1999/xlink"
  version         "1.1"
  style           "stroke:black; fill:none; stroke-width:0.5pt; stroke-linejoin:round; text-anchor:middle"
  font-family     "Helvetica,Arial,FreeSans?,Sans,sans,sans-serif"
  """
  attributes = dict(_canvas_defaults)
  attributes.update(attr)

  if sub == None or sub == ():
    return SVG("svg", **attributes)
  else:
    return SVG("svg", *sub, **attributes)

def canvas_outline(*sub, **attr):
  """Same as canvas(), but draws an outline around the drawable area,
  so that you know how close your image is to the edges."""
  svg = canvas(*sub, **attr)
  match = re.match("[, \t]*([0-9e.+\-]+)[, \t]+([0-9e.+\-]+)[, \t]+([0-9e.+\-]+)[, \t]+([0-9e.+\-]+)[, \t]*", svg["viewBox"])
  if match == None: raise ValueError("canvas viewBox is incorrectly formatted")
  x, y, width, height = [float(x) for x in match.groups()]
  svg.prepend(SVG("rect", x=x, y=y, width=width, height=height, stroke="none", fill="cornsilk"))
  svg.append(SVG("rect", x=x, y=y, width=width, height=height, stroke="black", fill="none"))
  return svg

def template(fileName, svg, replaceme="REPLACEME"):
  """Loads an SVG image from a file, replacing instances of
  <REPLACEME /> with a given svg object.

  fileName         required                name of the template SVG
  svg              required                SVG object for replacement
  replaceme        default="REPLACEME"   fake SVG element to be replaced by the given object

  >>> print load("template.svg")
  None                 <svg (2 sub) style=u'stroke:black; fill:none; stroke-width:0.5pt; stroke-linejoi
  [0]                      <rect height=u'100' width=u'100' stroke=u'none' y=u'0' x=u'0' fill=u'yellow'
  [1]                      <REPLACEME />
  >>> 
  >>> print template("template.svg", SVG("circle", cx=50, cy=50, r=30))
  None                 <svg (2 sub) style=u'stroke:black; fill:none; stroke-width:0.5pt; stroke-linejoi
  [0]                      <rect height=u'100' width=u'100' stroke=u'none' y=u'0' x=u'0' fill=u'yellow'
  [1]                      <circle cy=50 cx=50 r=30 />
  """
  output = load(fileName)
  for ti, s in output:
    if isinstance(s, SVG) and s.t == replaceme:
      output[ti] = svg
  return output

######################################################################

def load(fileName):
  """Loads an SVG image from a file."""
  return load_stream(file(fileName))

def load_stream(stream):
  """Loads an SVG image from a stream (can be a string or a file object)."""

  from xml.sax import handler, make_parser
  from xml.sax.handler import feature_namespaces, feature_external_ges, feature_external_pes

  class ContentHandler(handler.ContentHandler):
    def __init__(self):
      self.stack = []
      self.output = None
      self.all_whitespace = re.compile("^\s*$")

    def startElement(self, name, attr):
      s = SVG(name)
      s.attr = dict(attr.items())
      if len(self.stack) > 0:
        last = self.stack[-1]
        last.sub.append(s)
      self.stack.append(s)

    def characters(self, ch):
      if not isinstance(ch, str) or self.all_whitespace.match(ch) == None:
        if len(self.stack) > 0:
          last = self.stack[-1]
          if len(last.sub) > 0 and isinstance(last.sub[-1], str):
            last.sub[-1] = last.sub[-1] + "\n" + ch
          else:
            last.sub.append(ch)

    def endElement(self, name):
      if len(self.stack) > 0:
        last = self.stack[-1]
        if isinstance(last, SVG) and last.t == "style" and "type" in last.attr and last.attr["type"] == "text/css" and len(last.sub) == 1 and isinstance(last.sub[0], str):
          last.sub[0] = "<![CDATA[\n" + last.sub[0] + "]]>"

      self.output = self.stack.pop()

  ch = ContentHandler()
  parser = make_parser()
  parser.setContentHandler(ch)
  parser.setFeature(feature_namespaces, 0)
  parser.setFeature(feature_external_ges, 0)
  parser.parse(stream)
  return ch.output

######################################################################

def totrans(expr, vars=("x", "y"), globals=None, locals=None):
  """Converts to a coordinate transformation (a function that accepts
  two arguments and returns two values).

  expr       required                  a string expression or a function
                                       of two real or one complex value
  vars       default=("x", "y")    independent variable names;
                                       a singleton ("z",) is interpreted
                                       as complex
  globals    default=None              dict of global variables
  locals     default=None              dict of local variables
  """

  if callable(expr):
    if expr.__code__.co_argcount == 2:
      return expr

    elif expr.__code__.co_argcount == 1:
      split = lambda z: (z.real, z.imag)
      output = lambda x, y: split(expr(x + y*1j))
      output.__name__ = expr.__name__
      return output

    else:
      raise TypeError("must be a function of 2 or 1 variables")

  if len(vars) == 2:
    g = math.__dict__
    if globals != None: g.update(globals)
    output = eval("lambda %s, %s: (%s)" % (vars[0], vars[1], expr), g, locals)
    output.__name__ = "%s,%s -> %s" % (vars[0], vars[1], expr)
    return output

  elif len(vars) == 1:
    g = cmath.__dict__
    if globals != None: g.update(globals)
    output = eval("lambda %s: (%s)" % (vars[0], expr), g, locals)
    split = lambda z: (z.real, z.imag)
    output2 = lambda x, y: split(output(x + y*1j))
    output2.__name__ = "%s -> %s" % (vars[0], expr)
    return output2

  else:
    raise TypeError("vars must have 2 or 1 elements")

def window(xmin, xmax, ymin, ymax, x=0, y=0, width=100, height=100, xlogbase=None, ylogbase=None, minusInfinity=-1000, flipx=False, flipy=True):
  """Creates and returns a coordinate transformation (a function that
  accepts two arguments and returns two values) that transforms from
      (xmin, ymin), (xmax, ymax)
  to
      (x, y), (x + width, y + height).

  xlogbase, ylogbase    default=None, None     if a number, transform
                                               logarithmically with given base
  minusInfinity         default=-1000          what to return if
                                               log(0 or negative) is attempted
  flipx                 default=False          if true, reverse the direction of x
  flipy                 default=True           if true, reverse the direction of y

  (When composing windows, be sure to set flipy=False.)
  """

  if flipx:
    ox1 = x + width
    ox2 = x
  else:
    ox1 = x
    ox2 = x + width
  if flipy:
    oy1 = y + height
    oy2 = y
  else:
    oy1 = y
    oy2 = y + height
  ix1 = xmin
  iy1 = ymin
  ix2 = xmax
  iy2 = ymax
  
  if xlogbase != None and (ix1 <= 0. or ix2 <= 0.): raise ValueError("x range incompatible with log scaling: (%g, %g)" % (ix1, ix2))

  if ylogbase != None and (iy1 <= 0. or iy2 <= 0.): raise ValueError("y range incompatible with log scaling: (%g, %g)" % (iy1, iy2))

  def maybelog(t, it1, it2, ot1, ot2, logbase):
    if t <= 0.: return minusInfinity
    else:
      return ot1 + 1.*(math.log(t, logbase) - math.log(it1, logbase))/(math.log(it2, logbase) - math.log(it1, logbase)) * (ot2 - ot1)

  xlogstr, ylogstr = "", ""

  if xlogbase == None:
    xfunc = lambda x: ox1 + 1.*(x - ix1)/(ix2 - ix1) * (ox2 - ox1)
  else:
    xfunc = lambda x: maybelog(x, ix1, ix2, ox1, ox2, xlogbase)
    xlogstr = " xlog=%g" % xlogbase

  if ylogbase == None:
    yfunc = lambda y: oy1 + 1.*(y - iy1)/(iy2 - iy1) * (oy2 - oy1)
  else:
    yfunc = lambda y: maybelog(y, iy1, iy2, oy1, oy2, ylogbase)
    ylogstr = " ylog=%g" % ylogbase

  output = lambda x, y: (xfunc(x), yfunc(y))

  output.__name__ = "(%g, %g), (%g, %g) -> (%g, %g), (%g, %g)%s%s" % (ix1, ix2, iy1, iy2, ox1, ox2, oy1, oy2, xlogstr, ylogstr)
  return output

def rotate(angle, cx=0, cy=0):
  """Creates and returns a coordinate transformation which rotates
  around (cx,cy) by "angle" degrees."""
  angle *= math.pi/180.
  return lambda x, y: (cx + math.cos(angle)*(x - cx) - math.sin(angle)*(y - cy), cy + math.sin(angle)*(x - cx) + math.cos(angle)*(y - cy))

class Fig:
  """Stores graphics primitive objects and applies a single coordinate
  transformation to them. To compose coordinate systems, nest Fig
  objects.

  Fig(obj, obj, obj..., trans=function)

  obj     optional list    a list of drawing primatives
  trans   default=None     a coordinate transformation function

  >>> fig = Fig(Line(0,0,1,1), Rect(0.2,0.2,0.8,0.8), trans="2*x, 2*y")
  >>> print fig.SVG().xml()
  <g>
      <path d='M0 0L2 2' />
      <path d='M0.4 0.4L1.6 0.4ZL1.6 1.6ZL0.4 1.6ZL0.4 0.4ZZ' />
  </g>
  >>> print Fig(fig, trans="x/2., y/2.").SVG().xml()
  <g>
      <path d='M0 0L1 1' />
      <path d='M0.2 0.2L0.8 0.2ZL0.8 0.8ZL0.2 0.8ZL0.2 0.2ZZ' />
  </g>
  """

  def __repr__(self):
    if self.trans == None:
      return "<Fig (%d items)>" % len(self.d)
    elif isinstance(self.trans, str):
      return "<Fig (%d items) x,y -> %s>" % (len(self.d), self.trans)
    else:
      return "<Fig (%d items) %s>" % (len(self.d), self.trans.__name__)

  def __init__(self, *d, **kwds):
    self.d = list(d)
    defaults = {"trans":None}
    defaults.update(kwds)
    kwds = defaults

    self.trans = kwds["trans"]; del kwds["trans"]
    if len(kwds) != 0:
      raise TypeError("Fig() got unexpected keyword arguments %s" % kwds.keys())

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object.

    Coordinate transformations in nested Figs will be composed.
    """

    if trans == None: trans = self.trans
    if isinstance(trans, str): trans = totrans(trans)

    output = SVG("g")
    for s in self.d:
      if isinstance(s, SVG):
        output.append(s)

      elif isinstance(s, Fig):
        strans = s.trans
        if isinstance(strans, str): strans = totrans(strans)

        if trans == None: subtrans = strans
        elif strans == None: subtrans = trans
        else: subtrans = lambda x,y: trans(*strans(x, y))

        output.sub += s.SVG(subtrans).sub

      elif s == None: pass

      else:
        output.append(s.SVG(trans))

    return output

class Plot:
  """Acts like Fig, but draws a coordinate axis. You also need to supply plot ranges.

  Plot(xmin, xmax, ymin, ymax, obj, obj, obj..., keyword options...)

  xmin, xmax      required        minimum and maximum x values (in the objs' coordinates)
  ymin, ymax      required        minimum and maximum y values (in the objs' coordinates)
  obj             optional list   drawing primatives
  keyword options keyword list    options defined below

  The following are keyword options, with their default values:

  trans           None          transformation function
  x, y            5, 5          upper-left corner of the Plot in SVG coordinates
  width, height   90, 90        width and height of the Plot in SVG coordinates
  flipx, flipy    False, True   flip the sign of the coordinate axis
  minusInfinity   -1000         if an axis is logarithmic and an object is plotted at 0 or
                                a negative value, -1000 will be used as a stand-in for NaN
  atx, aty        0, 0          the place where the coordinate axes cross
  xticks          -10           request ticks according to the standard tick specification
                                (see help(Ticks))
  xminiticks      True          request miniticks according to the standard minitick
                                specification
  xlabels         True          request tick labels according to the standard tick label
                                specification
  xlogbase        None          if a number, the axis and transformation are logarithmic
                                with ticks at the given base (10 being the most common)
  (same for y)
  arrows          None          if a new identifier, create arrow markers and draw them
                                at the ends of the coordinate axes
  text_attr       {}            a dictionary of attributes for label text
  axis_attr       {}            a dictionary of attributes for the axis lines
  """

  def __repr__(self):
    if self.trans == None:
      return "<Plot (%d items)>" % len(self.d)
    else:
      return "<Plot (%d items) %s>" % (len(self.d), self.trans.__name__)

  def __init__(self, xmin, xmax, ymin, ymax, *d, **kwds):
    self.xmin, self.xmax, self.ymin, self.ymax = xmin, xmax, ymin, ymax
    self.d = list(d)
    defaults = {"trans":None, "x":5, "y":5, "width":90, "height":90, "flipx":False, "flipy":True, "minusInfinity":-1000, \
                "atx":0, "xticks":-10, "xminiticks":True, "xlabels":True, "xlogbase":None, \
                "aty":0, "yticks":-10, "yminiticks":True, "ylabels":True, "ylogbase":None, \
                "arrows":None, "text_attr":{}, "axis_attr":{}}
    defaults.update(kwds)
    kwds = defaults

    self.trans = kwds["trans"]; del kwds["trans"]
    self.x = kwds["x"]; del kwds["x"]
    self.y = kwds["y"]; del kwds["y"]
    self.width = kwds["width"]; del kwds["width"]
    self.height = kwds["height"]; del kwds["height"]
    self.flipx = kwds["flipx"]; del kwds["flipx"]
    self.flipy = kwds["flipy"]; del kwds["flipy"]
    self.minusInfinity = kwds["minusInfinity"]; del kwds["minusInfinity"]
    self.atx = kwds["atx"]; del kwds["atx"]
    self.xticks = kwds["xticks"]; del kwds["xticks"]
    self.xminiticks = kwds["xminiticks"]; del kwds["xminiticks"]
    self.xlabels = kwds["xlabels"]; del kwds["xlabels"]
    self.xlogbase = kwds["xlogbase"]; del kwds["xlogbase"]
    self.aty = kwds["aty"]; del kwds["aty"]
    self.yticks = kwds["yticks"]; del kwds["yticks"]
    self.yminiticks = kwds["yminiticks"]; del kwds["yminiticks"]
    self.ylabels = kwds["ylabels"]; del kwds["ylabels"]
    self.ylogbase = kwds["ylogbase"]; del kwds["ylogbase"]
    self.arrows = kwds["arrows"]; del kwds["arrows"]
    self.text_attr = kwds["text_attr"]; del kwds["text_attr"]
    self.axis_attr = kwds["axis_attr"]; del kwds["axis_attr"]
    if len(kwds) != 0:
      raise TypeError("Plot() got unexpected keyword arguments %s" % kwds.keys())

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    if trans == None: trans = self.trans
    if isinstance(trans, str): trans = totrans(trans)

    self.last_window = window(self.xmin, self.xmax, self.ymin, self.ymax, x=self.x, y=self.y, width=self.width, height=self.height, \
                              xlogbase=self.xlogbase, ylogbase=self.ylogbase, minusInfinity=self.minusInfinity, flipx=self.flipx, flipy=self.flipy)

    d = [Axes(self.xmin, self.xmax, self.ymin, self.ymax, self.atx, self.aty, \
              self.xticks, self.xminiticks, self.xlabels, self.xlogbase, \
              self.yticks, self.yminiticks, self.ylabels, self.ylogbase, \
              self.arrows, self.text_attr, **self.axis_attr)] \
        + self.d

    return Fig(Fig(*d, **{"trans":trans})).SVG(self.last_window)
    
class Frame:
  text_defaults = {"stroke":"none", "fill":"black", "font-size":5}
  axis_defaults = {}

  tick_length = 1.5
  minitick_length = 0.75
  text_xaxis_offset = 1.
  text_yaxis_offset = 2.
  text_xtitle_offset = 6.
  text_ytitle_offset = 12.

  def __repr__(self):
    return "<Frame (%d items)>" % len(self.d)

  def __init__(self, xmin, xmax, ymin, ymax, *d, **kwds):
    """Acts like Fig, but draws a coordinate frame around the data. You also need to supply plot ranges.

    Frame(xmin, xmax, ymin, ymax, obj, obj, obj..., keyword options...)

    xmin, xmax      required        minimum and maximum x values (in the objs' coordinates)
    ymin, ymax      required        minimum and maximum y values (in the objs' coordinates)
    obj             optional list   drawing primatives
    keyword options keyword list    options defined below

    The following are keyword options, with their default values:

    x, y            20, 5         upper-left corner of the Frame in SVG coordinates
    width, height   75, 80        width and height of the Frame in SVG coordinates
    flipx, flipy    False, True   flip the sign of the coordinate axis
    minusInfinity   -1000         if an axis is logarithmic and an object is plotted at 0 or
                                  a negative value, -1000 will be used as a stand-in for NaN
    xtitle          None          if a string, label the x axis
    xticks          -10           request ticks according to the standard tick specification
                                  (see help(Ticks))
    xminiticks      True          request miniticks according to the standard minitick
                                  specification
    xlabels         True          request tick labels according to the standard tick label
                                  specification
    xlogbase        None          if a number, the axis and transformation are logarithmic
                                  with ticks at the given base (10 being the most common)
    (same for y)
    text_attr       {}            a dictionary of attributes for label text
    axis_attr       {}            a dictionary of attributes for the axis lines
    """

    self.xmin, self.xmax, self.ymin, self.ymax = xmin, xmax, ymin, ymax
    self.d = list(d)
    defaults = {"x":20, "y":5, "width":75, "height":80, "flipx":False, "flipy":True, "minusInfinity":-1000, \
                "xtitle":None, "xticks":-10, "xminiticks":True, "xlabels":True, "x2labels":None, "xlogbase":None, \
                "ytitle":None, "yticks":-10, "yminiticks":True, "ylabels":True, "y2labels":None, "ylogbase":None, \
                "text_attr":{}, "axis_attr":{}}
    defaults.update(kwds)
    kwds = defaults

    self.x = kwds["x"]; del kwds["x"]
    self.y = kwds["y"]; del kwds["y"]
    self.width = kwds["width"]; del kwds["width"]
    self.height = kwds["height"]; del kwds["height"]
    self.flipx = kwds["flipx"]; del kwds["flipx"]
    self.flipy = kwds["flipy"]; del kwds["flipy"]
    self.minusInfinity = kwds["minusInfinity"]; del kwds["minusInfinity"]
    self.xtitle = kwds["xtitle"]; del kwds["xtitle"]
    self.xticks = kwds["xticks"]; del kwds["xticks"]
    self.xminiticks = kwds["xminiticks"]; del kwds["xminiticks"]
    self.xlabels = kwds["xlabels"]; del kwds["xlabels"]
    self.x2labels = kwds["x2labels"]; del kwds["x2labels"]
    self.xlogbase = kwds["xlogbase"]; del kwds["xlogbase"]
    self.ytitle = kwds["ytitle"]; del kwds["ytitle"]
    self.yticks = kwds["yticks"]; del kwds["yticks"]
    self.yminiticks = kwds["yminiticks"]; del kwds["yminiticks"]
    self.ylabels = kwds["ylabels"]; del kwds["ylabels"]
    self.y2labels = kwds["y2labels"]; del kwds["y2labels"]
    self.ylogbase = kwds["ylogbase"]; del kwds["ylogbase"]

    self.text_attr = dict(self.text_defaults)
    self.text_attr.update(kwds["text_attr"]); del kwds["text_attr"]

    self.axis_attr = dict(self.axis_defaults)
    self.axis_attr.update(kwds["axis_attr"]); del kwds["axis_attr"]

    if len(kwds) != 0:
      raise TypeError("Frame() got unexpected keyword arguments %s" % kwds.keys())

  def SVG(self):
    """Apply the window transformation and return an SVG object."""

    self.last_window = window(self.xmin, self.xmax, self.ymin, self.ymax, x=self.x, y=self.y, width=self.width, height=self.height, \
                              xlogbase=self.xlogbase, ylogbase=self.ylogbase, minusInfinity=self.minusInfinity, flipx=self.flipx, flipy=self.flipy)

    left = YAxis(self.ymin, self.ymax, self.xmin, self.yticks, self.yminiticks, self.ylabels, self.ylogbase, None, None, None, self.text_attr, **self.axis_attr)
    right = YAxis(self.ymin, self.ymax, self.xmax, self.yticks, self.yminiticks, self.y2labels, self.ylogbase, None, None, None, self.text_attr, **self.axis_attr)
    bottom = XAxis(self.xmin, self.xmax, self.ymin, self.xticks, self.xminiticks, self.xlabels, self.xlogbase, None, None, None, self.text_attr, **self.axis_attr)
    top = XAxis(self.xmin, self.xmax, self.ymax, self.xticks, self.xminiticks, self.x2labels, self.xlogbase, None, None, None, self.text_attr, **self.axis_attr)

    left.tick_start = -self.tick_length
    left.tick_end = 0
    left.minitick_start = -self.minitick_length
    left.minitick_end = 0.
    left.text_start = self.text_yaxis_offset

    right.tick_start = 0.
    right.tick_end = self.tick_length
    right.minitick_start = 0.
    right.minitick_end = self.minitick_length
    right.text_start = -self.text_yaxis_offset
    right.text_attr["text-anchor"] = "start"

    bottom.tick_start = 0.
    bottom.tick_end = self.tick_length
    bottom.minitick_start = 0.
    bottom.minitick_end = self.minitick_length
    bottom.text_start = -self.text_xaxis_offset

    top.tick_start = -self.tick_length
    top.tick_end = 0.
    top.minitick_start = -self.minitick_length
    top.minitick_end = 0.
    top.text_start = self.text_xaxis_offset
    top.text_attr["dominant-baseline"] = "text-after-edge"

    output = Fig(*self.d).SVG(self.last_window)
    output.prepend(left.SVG(self.last_window))
    output.prepend(bottom.SVG(self.last_window))
    output.prepend(right.SVG(self.last_window))
    output.prepend(top.SVG(self.last_window))

    if self.xtitle != None:
      output.append(SVG("text", self.xtitle, transform="translate(%g, %g)" % ((self.x + self.width/2.), (self.y + self.height + self.text_xtitle_offset)), dominant_baseline="text-before-edge", **self.text_attr))
    if self.ytitle != None:
      output.append(SVG("text", self.ytitle, transform="translate(%g, %g) rotate(-90)" % ((self.x - self.text_ytitle_offset), (self.y + self.height/2.)), **self.text_attr))
    return output
    
######################################################################

def pathtoPath(svg):
  """Converts SVG("path", d="...") into Path(d=[...])."""
  if not isinstance(svg, SVG) or svg.t != "path":
    raise TypeError("Only SVG <path /> objects can be converted into Paths")
  attr = dict(svg.attr)
  d = attr["d"]
  del attr["d"]
  for key in attr.keys():
    if not isinstance(key, str):
      value = attr[key]
      del attr[key]
      attr[str(key)] = value
  return Path(d, **attr)

class Path:
  """Path represents an SVG path, an arbitrary set of curves and
  straight segments. Unlike SVG("path", d="..."), Path stores
  coordinates as a list of numbers, rather than a string, so that it is
  transformable in a Fig.

  Path(d, attribute=value)

  d                       required        path data
  attribute=value pairs   keyword list    SVG attributes

  See http://www.w3.org/TR/SVG/paths.html for specification of paths
  from text.

  Internally, Path data is a list of tuples with these definitions:

      * ("Z/z",): close the current path
      * ("H/h", x) or ("V/v", y): a horizontal or vertical line
        segment to x or y
      * ("M/m/L/l/T/t", x, y, global): moveto, lineto, or smooth
        quadratic curveto point (x, y). If global=True, (x, y) should
        not be transformed.
      * ("S/sQ/q", cx, cy, cglobal, x, y, global): polybezier or
        smooth quadratic curveto point (x, y) using (cx, cy) as a
        control point. If cglobal or global=True, (cx, cy) or (x, y)
        should not be transformed.
      * ("C/c", c1x, c1y, c1global, c2x, c2y, c2global, x, y, global):
        cubic curveto point (x, y) using (c1x, c1y) and (c2x, c2y) as
        control points. If c1global, c2global, or global=True, (c1x, c1y),
        (c2x, c2y), or (x, y) should not be transformed.
      * ("A/a", rx, ry, rglobal, x-axis-rotation, angle, large-arc-flag,
        sweep-flag, x, y, global): arcto point (x, y) using the
        aforementioned parameters.
      * (",/.", rx, ry, rglobal, angle, x, y, global): an ellipse at
        point (x, y) with radii (rx, ry). If angle is 0, the whole
        ellipse is drawn; otherwise, a partial ellipse is drawn.
  """
  defaults = {}

  def __repr__(self):
    return "<Path (%d nodes) %s>" % (len(self.d), self.attr)

  def __init__(self, d=[], **attr):
    if isinstance(d, str): self.d = self.parse(d)
    else: self.d = list(d)

    self.attr = dict(self.defaults)
    self.attr.update(attr)

  def parse_whitespace(self, index, pathdata):
    """Part of Path's text-command parsing algorithm; used internally."""
    while index < len(pathdata) and pathdata[index] in (" ", "\t", "\r", "\n", ","): index += 1
    return index, pathdata

  def parse_command(self, index, pathdata):
    """Part of Path's text-command parsing algorithm; used internally."""
    index, pathdata = self.parse_whitespace(index, pathdata)

    if index >= len(pathdata): return None, index, pathdata
    command = pathdata[index]
    if "A" <= command <= "Z" or "a" <= command <= "z":
      index += 1
      return command, index, pathdata
    else: 
      return None, index, pathdata

  def parse_number(self, index, pathdata):
    """Part of Path's text-command parsing algorithm; used internally."""
    index, pathdata = self.parse_whitespace(index, pathdata)

    if index >= len(pathdata): return None, index, pathdata
    first_digit = pathdata[index]

    if "0" <= first_digit <= "9" or first_digit in ("-", "+", "."):
      start = index
      while index < len(pathdata) and ("0" <= pathdata[index] <= "9" or pathdata[index] in ("-", "+", ".", "e", "E")):
        index += 1
      end = index

      index = end
      return float(pathdata[start:end]), index, pathdata
    else: 
      return None, index, pathdata

  def parse_boolean(self, index, pathdata):
    """Part of Path's text-command parsing algorithm; used internally."""
    index, pathdata = self.parse_whitespace(index, pathdata)

    if index >= len(pathdata): return None, index, pathdata
    first_digit = pathdata[index]

    if first_digit in ("0", "1"):
      index += 1
      return int(first_digit), index, pathdata
    else:
      return None, index, pathdata

  def parse(self, pathdata):
    """Parses text-commands, converting them into a list of tuples.
    Called by the constructor."""
    output = []
    index = 0
    while True:
      command, index, pathdata = self.parse_command(index, pathdata)
      index, pathdata = self.parse_whitespace(index, pathdata)

      if command == None and index == len(pathdata): break  # this is the normal way out of the loop
      if command in ("Z", "z"):
        output.append((command,))

      ######################
      elif command in ("H", "h", "V", "v"):
        errstring = "Path command \"%s\" requires a number at index %d" % (command, index)
        num1, index, pathdata = self.parse_number(index, pathdata)
        if num1 == None: raise ValueError(errstring)

        while num1 != None:
          output.append((command, num1))
          num1, index, pathdata = self.parse_number(index, pathdata)

      ######################
      elif command in ("M", "m", "L", "l", "T", "t"):
        errstring = "Path command \"%s\" requires an x,y pair at index %d" % (command, index)
        num1, index, pathdata = self.parse_number(index, pathdata)
        num2, index, pathdata = self.parse_number(index, pathdata)

        if num1 == None: raise ValueError(errstring)

        while num1 != None:
          if num2 == None: raise ValueError(errstring)
          output.append((command, num1, num2, False))

          num1, index, pathdata = self.parse_number(index, pathdata)
          num2, index, pathdata = self.parse_number(index, pathdata)

      ######################
      elif command in ("S", "s", "Q", "q"):
        errstring = "Path command \"%s\" requires a cx,cy,x,y quadruplet at index %d" % (command, index)
        num1, index, pathdata = self.parse_number(index, pathdata)
        num2, index, pathdata = self.parse_number(index, pathdata)
        num3, index, pathdata = self.parse_number(index, pathdata)
        num4, index, pathdata = self.parse_number(index, pathdata)

        if num1 == None: raise ValueError(errstring)

        while num1 != None:
          if num2 == None or num3 == None or num4 == None: raise ValueError(errstring)
          output.append((command, num1, num2, False, num3, num4, False))

          num1, index, pathdata = self.parse_number(index, pathdata)
          num2, index, pathdata = self.parse_number(index, pathdata)
          num3, index, pathdata = self.parse_number(index, pathdata)
          num4, index, pathdata = self.parse_number(index, pathdata)
          
      ######################
      elif command in ("C", "c"):
        errstring = "Path command \"%s\" requires a c1x,c1y,c2x,c2y,x,y sextuplet at index %d" % (command, index)
        num1, index, pathdata = self.parse_number(index, pathdata)
        num2, index, pathdata = self.parse_number(index, pathdata)
        num3, index, pathdata = self.parse_number(index, pathdata)
        num4, index, pathdata = self.parse_number(index, pathdata)
        num5, index, pathdata = self.parse_number(index, pathdata)
        num6, index, pathdata = self.parse_number(index, pathdata)
        
        if num1 == None: raise ValueError(errstring)

        while num1 != None:
          if num2 == None or num3 == None or num4 == None or num5 == None or num6 == None: raise ValueError(errstring)

          output.append((command, num1, num2, False, num3, num4, False, num5, num6, False))

          num1, index, pathdata = self.parse_number(index, pathdata)
          num2, index, pathdata = self.parse_number(index, pathdata)
          num3, index, pathdata = self.parse_number(index, pathdata)
          num4, index, pathdata = self.parse_number(index, pathdata)
          num5, index, pathdata = self.parse_number(index, pathdata)
          num6, index, pathdata = self.parse_number(index, pathdata)

      ######################
      elif command in ("A", "a"):
        errstring = "Path command \"%s\" requires a rx,ry,angle,large-arc-flag,sweep-flag,x,y septuplet at index %d" % (command, index)
        num1, index, pathdata = self.parse_number(index, pathdata)
        num2, index, pathdata = self.parse_number(index, pathdata)
        num3, index, pathdata = self.parse_number(index, pathdata)
        num4, index, pathdata = self.parse_boolean(index, pathdata)
        num5, index, pathdata = self.parse_boolean(index, pathdata)
        num6, index, pathdata = self.parse_number(index, pathdata)
        num7, index, pathdata = self.parse_number(index, pathdata)

        if num1 == None: raise ValueError(errstring)

        while num1 != None:
          if num2 == None or num3 == None or num4 == None or num5 == None or num6 == None or num7 == None: raise ValueError(errstring)

          output.append((command, num1, num2, False, num3, num4, num5, num6, num7, False))

          num1, index, pathdata = self.parse_number(index, pathdata)
          num2, index, pathdata = self.parse_number(index, pathdata)
          num3, index, pathdata = self.parse_number(index, pathdata)
          num4, index, pathdata = self.parse_boolean(index, pathdata)
          num5, index, pathdata = self.parse_boolean(index, pathdata)
          num6, index, pathdata = self.parse_number(index, pathdata)
          num7, index, pathdata = self.parse_number(index, pathdata)

    return output

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    if isinstance(trans, str): trans = totrans(trans)

    x, y, X, Y = None, None, None, None
    output = []
    for datum in self.d:
      if not isinstance(datum, (tuple, list)):
        raise TypeError("pathdata elements must be tuples/lists")

      command = datum[0]

      ######################
      if command in ("Z", "z"):
        x, y, X, Y = None, None, None, None
        output.append("Z")

      ######################
      elif command in ("H", "h", "V", "v"):
        command, num1 = datum

        if command == "H" or (command == "h" and x == None): x = num1
        elif command == "h": x += num1
        elif command == "V" or (command == "v" and y == None): y = num1
        elif command == "v": y += num1

        if trans == None: X, Y = x, y
        else: X, Y = trans(x, y)

        output.append("L%g %g" % (X, Y))
        
      ######################
      elif command in ("M", "m", "L", "l", "T", "t"):
        command, num1, num2, isglobal12 = datum

        if trans == None or isglobal12:
          if command.isupper() or X == None or Y == None:
            X, Y = num1, num2
          else:
            X += num1
            Y += num2
          x, y = X, Y

        else:
          if command.isupper() or x == None or y == None:
            x, y = num1, num2
          else:
            x += num1
            y += num2
          X, Y = trans(x, y)

        COMMAND = command.capitalize()
        output.append("%s%g %g" % (COMMAND, X, Y))

      ######################
      elif command in ("S", "s", "Q", "q"):
        command, num1, num2, isglobal12, num3, num4, isglobal34 = datum

        if trans == None or isglobal12:
          if command.isupper() or X == None or Y == None:
            CX, CY = num1, num2
          else:
            CX = X + num1
            CY = Y + num2

        else:
          if command.isupper() or x == None or y == None:
            cx, cy = num1, num2
          else:
            cx = x + num1
            cy = y + num2
          CX, CY = trans(cx, cy)

        if trans == None or isglobal34:
          if command.isupper() or X == None or Y == None:
            X, Y = num3, num4
          else:
            X += num3
            Y += num4
          x, y = X, Y

        else:
          if command.isupper() or x == None or y == None:
            x, y = num3, num4
          else:
            x += num3
            y += num4
          X, Y = trans(x, y)

        COMMAND = command.capitalize()
        output.append("%s%g %g %g %g" % (COMMAND, CX, CY, X, Y))

      ######################
      elif command in ("C", "c"):
        command, num1, num2, isglobal12, num3, num4, isglobal34, num5, num6, isglobal56 = datum

        if trans == None or isglobal12:
          if command.isupper() or X == None or Y == None:
            C1X, C1Y = num1, num2
          else:
            C1X = X + num1
            C1Y = Y + num2

        else:
          if command.isupper() or x == None or y == None:
            c1x, c1y = num1, num2
          else:
            c1x = x + num1
            c1y = y + num2
          C1X, C1Y = trans(c1x, c1y)

        if trans == None or isglobal34:
          if command.isupper() or X == None or Y == None:
            C2X, C2Y = num3, num4
          else:
            C2X = X + num3
            C2Y = Y + num4

        else:
          if command.isupper() or x == None or y == None:
            c2x, c2y = num3, num4
          else:
            c2x = x + num3
            c2y = y + num4
          C2X, C2Y = trans(c2x, c2y)

        if trans == None or isglobal56:
          if command.isupper() or X == None or Y == None:
            X, Y = num5, num6
          else:
            X += num5
            Y += num6
          x, y = X, Y

        else:
          if command.isupper() or x == None or y == None:
            x, y = num5, num6
          else:
            x += num5
            y += num6
          X, Y = trans(x, y)

        COMMAND = command.capitalize()
        output.append("%s%g %g %g %g %g %g" % (COMMAND, C1X, C1Y, C2X, C2Y, X, Y))

      ######################
      elif command in ("A", "a"):
        command, num1, num2, isglobal12, angle, large_arc_flag, sweep_flag, num3, num4, isglobal34 = datum

        oldx, oldy = x, y
        OLDX, OLDY = X, Y

        if trans == None or isglobal34:
          if command.isupper() or X == None or Y == None:
            X, Y = num3, num4
          else:
            X += num3
            Y += num4
          x, y = X, Y

        else:
          if command.isupper() or x == None or y == None:
            x, y = num3, num4
          else:
            x += num3
            y += num4
          X, Y = trans(x, y)
        
        if x != None and y != None:
          centerx, centery = (x + oldx)/2., (y + oldy)/2.
        CENTERX, CENTERY = (X + OLDX)/2., (Y + OLDY)/2.

        if trans == None or isglobal12:
          RX = CENTERX + num1
          RY = CENTERY + num2

        else:
          rx = centerx + num1
          ry = centery + num2
          RX, RY = trans(rx, ry)

        COMMAND = command.capitalize()
        output.append("%s%g %g %g %d %d %g %g" % (COMMAND, RX - CENTERX, RY - CENTERY, angle, large_arc_flag, sweep_flag, X, Y))

      elif command in (",", "."):
        command, num1, num2, isglobal12, angle, num3, num4, isglobal34 = datum
        if trans == None or isglobal34:
          if command == "." or X == None or Y == None:
            X, Y = num3, num4
          else:
            X += num3
            Y += num4
            x, y = None, None

        else:
          if command == "." or x == None or y == None:
            x, y = num3, num4
          else:
            x += num3
            y += num4
          X, Y = trans(x, y)

        if trans == None or isglobal12:
          RX = X + num1
          RY = Y + num2

        else:
          rx = x + num1
          ry = y + num2
          RX, RY = trans(rx, ry)

        RX, RY = RX - X, RY - Y

        X1, Y1 = X + RX * math.cos(angle*math.pi/180.), Y + RX * math.sin(angle*math.pi/180.)
        X2, Y2 = X + RY * math.sin(angle*math.pi/180.), Y - RY * math.cos(angle*math.pi/180.)
        X3, Y3 = X - RX * math.cos(angle*math.pi/180.), Y - RX * math.sin(angle*math.pi/180.)
        X4, Y4 = X - RY * math.sin(angle*math.pi/180.), Y + RY * math.cos(angle*math.pi/180.)

        output.append("M%g %gA%g %g %g 0 0 %g %gA%g %g %g 0 0 %g %gA%g %g %g 0 0 %g %gA%g %g %g 0 0 %g %g" \
                      % (X1, Y1, RX, RY, angle, X2, Y2, RX, RY, angle, X3, Y3, RX, RY, angle, X4, Y4, RX, RY, angle, X1, Y1))

    return SVG("path", d="".join(output), **self.attr)

######################################################################

def funcRtoC(expr, var="t", globals=None, locals=None):
  """Converts a complex "z(t)" string to a function acceptable for Curve.

  expr    required        string in the form "z(t)"
  var     default="t"   name of the independent variable
  globals default=None    dict of global variables used in the expression;
                          you may want to use Python's builtin globals()
  locals  default=None    dict of local variables
  """
  g = cmath.__dict__
  if globals != None: g.update(globals)
  output = eval("lambda %s: (%s)" % (var, expr), g, locals)
  split = lambda z: (z.real, z.imag)
  output2 = lambda t: split(output(t))
  output2.__name__ = "%s -> %s" % (var, expr)
  return output2

def funcRtoR2(expr, var="t", globals=None, locals=None):
  """Converts a "f(t), g(t)" string to a function acceptable for Curve.

  expr    required        string in the form "f(t), g(t)"
  var     default="t"   name of the independent variable
  globals default=None    dict of global variables used in the expression;
                          you may want to use Python's builtin globals()
  locals  default=None    dict of local variables
  """
  g = math.__dict__
  if globals != None: g.update(globals)
  output = eval("lambda %s: (%s)" % (var, expr), g, locals)
  output.__name__ = "%s -> %s" % (var, expr)
  return output

def funcRtoR(expr, var="x", globals=None, locals=None):
  """Converts a "f(x)" string to a function acceptable for Curve.

  expr    required        string in the form "f(x)"
  var     default="x"   name of the independent variable
  globals default=None    dict of global variables used in the expression;
                          you may want to use Python's builtin globals()
  locals  default=None    dict of local variables
  """
  g = math.__dict__
  if globals != None: g.update(globals)
  output = eval("lambda %s: (%s, %s)" % (var, var, expr), g, locals)
  output.__name__ = "%s -> %s" % (var, expr)
  return output

class Curve:
  """Draws a parametric function as a path.

  Curve(f, low, high, loop, attribute=value)

  f                      required         a Python callable or string in
                                          the form "f(t), g(t)"
  low, high              required         left and right endpoints
  loop                   default=False    if True, connect the endpoints
  attribute=value pairs  keyword list     SVG attributes
  """
  defaults = {}
  random_sampling = True
  recursion_limit = 15
  linearity_limit = 0.05
  discontinuity_limit = 5.

  def __repr__(self):
    return "<Curve %s [%s, %s] %s>" % (self.f, self.low, self.high, self.attr)

  def __init__(self, f, low, high, loop=False, **attr):
    self.f = f
    self.low = low
    self.high = high
    self.loop = loop

    self.attr = dict(self.defaults)
    self.attr.update(attr)

  ### nested class Sample
  class Sample:
    def __repr__(self):
      t, x, y, X, Y = self.t, self.x, self.y, self.X, self.Y
      if t != None: t = "%g" % t
      if x != None: x = "%g" % x
      if y != None: y = "%g" % y
      if X != None: X = "%g" % X
      if Y != None: Y = "%g" % Y
      return "<Curve.Sample t=%s x=%s y=%s X=%s Y=%s>" % (t, x, y, X, Y)

    def __init__(self, t): self.t = t

    def link(self, left, right): self.left, self.right = left, right

    def evaluate(self, f, trans):
      self.x, self.y = f(self.t)
      if trans == None:
        self.X, self.Y = self.x, self.y
      else:
        self.X, self.Y = trans(self.x, self.y)
  ### end Sample

  ### nested class Samples
  class Samples:
    def __repr__(self): return "<Curve.Samples (%d samples)>" % len(self)

    def __init__(self, left, right): self.left, self.right = left, right

    def __len__(self):
      count = 0
      current = self.left
      while current != None:
        count += 1
        current = current.right
      return count

    def __iter__(self):
      self.current = self.left
      return self

    def next(self):
      current = self.current
      if current == None: raise StopIteration
      self.current = self.current.right
      return current
  ### end nested class

  def sample(self, trans=None):
    """Adaptive-sampling algorithm that chooses the best sample points
    for a parametric curve between two endpoints and detects
    discontinuities.  Called by SVG()."""
    oldrecursionlimit = sys.getrecursionlimit()
    sys.setrecursionlimit(self.recursion_limit + 100)
    try:
      # the best way to keep all the information while sampling is to make a linked list
      if not (self.low < self.high): raise ValueError("low must be less than high")
      low, high = self.Sample(float(self.low)), self.Sample(float(self.high))
      low.link(None, high)
      high.link(low, None)

      low.evaluate(self.f, trans)
      high.evaluate(self.f, trans)

      # adaptive sampling between the low and high points
      self.subsample(low, high, 0, trans)

      # Prune excess points where the curve is nearly linear
      left = low
      while left.right != None:
        # increment mid and right
        mid = left.right
        right = mid.right
        if right != None and left.X != None and left.Y != None and mid.X != None and mid.Y != None and right.X != None and right.Y != None:
          numer = left.X*(right.Y - mid.Y) + mid.X*(left.Y - right.Y) + right.X*(mid.Y - left.Y)
          denom = math.sqrt((left.X - right.X)**2 + (left.Y - right.Y)**2)
          if denom != 0. and abs(numer/denom) < self.linearity_limit:
            # drop mid (the garbage collector will get it)
            left.right = right
            right.left = left
          else:
            # increment left
            left = left.right
        else:
          left = left.right

      self.last_samples = self.Samples(low, high)

    finally:
      sys.setrecursionlimit(oldrecursionlimit)

  def subsample(self, left, right, depth, trans=None):
    """Part of the adaptive-sampling algorithm that chooses the best
    sample points.  Called by sample()."""

    if self.random_sampling:
      mid = self.Sample(left.t + random.uniform(0.3, 0.7) * (right.t - left.t))
    else:
      mid = self.Sample(left.t + 0.5 * (right.t - left.t))

    left.right = mid
    right.left = mid
    mid.link(left, right)
    mid.evaluate(self.f, trans)

    # calculate the distance of closest approach of mid to the line between left and right
    numer = left.X*(right.Y - mid.Y) + mid.X*(left.Y - right.Y) + right.X*(mid.Y - left.Y)
    denom = math.sqrt((left.X - right.X)**2 + (left.Y - right.Y)**2)

    # if we haven't sampled enough or left fails to be close enough to right, or mid fails to be linear enough...
    if depth < 3 or (denom == 0 and left.t != right.t) or denom > self.discontinuity_limit or (denom != 0. and abs(numer/denom) > self.linearity_limit):

      # and we haven't sampled too many points
      if depth < self.recursion_limit:
        self.subsample(left, mid, depth+1, trans)
        self.subsample(mid, right, depth+1, trans)

      else:
        # We've sampled many points and yet it's still not a small linear gap.
        # Break the line: it's a discontinuity
        mid.y = mid.Y = None

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    return self.Path(trans).SVG()

  def Path(self, trans=None, local=False):
    """Apply the transformation "trans" and return a Path object in
    global coordinates.  If local=True, return a Path in local coordinates
    (which must be transformed again)."""

    if isinstance(trans, str): trans = totrans(trans)
    if isinstance(self.f, str): self.f = funcRtoR2(self.f)

    self.sample(trans)

    output = []
    for s in self.last_samples:
      if s.X != None and s.Y != None:
        if s.left == None or s.left.Y == None:
          command = "M"
        else:
          command = "L"

        if local: output.append((command, s.x, s.y, False))
        else: output.append((command, s.X, s.Y, True))

    if self.loop: output.append(("Z",))
    return Path(output, **self.attr)

######################################################################

class Poly:
  """Draws a curve specified by a sequence of points. The curve may be
  piecewise linear, like a polygon, or a Bezier curve.

  Poly(d, mode, loop, attribute=value)

  d                       required        list of tuples representing points
                                          and possibly control points
  mode                    default="L"   "lines", "bezier", "velocity",
                                          "foreback", "smooth", or an abbreviation
  loop                    default=False   if True, connect the first and last
                                          point, closing the loop
  attribute=value pairs   keyword list    SVG attributes

  The format of the tuples in d depends on the mode.

  "lines"/"L"         d=[(x,y), (x,y), ...]
                                          piecewise-linear segments joining the (x,y) points
  "bezier"/"B"        d=[(x, y, c1x, c1y, c2x, c2y), ...]
                                          Bezier curve with two control points (control points
                                          preceed (x,y), as in SVG paths). If (c1x,c1y) and
                                          (c2x,c2y) both equal (x,y), you get a linear
                                          interpolation ("lines")
  "velocity"/"V"      d=[(x, y, vx, vy), ...]
                                          curve that passes through (x,y) with velocity (vx,vy)
                                          (one unit of arclength per unit time); in other words,
                                          (vx,vy) is the tangent vector at (x,y). If (vx,vy) is
                                          (0,0), you get a linear interpolation ("lines").
  "foreback"/"F"      d=[(x, y, bx, by, fx, fy), ...]
                                          like "velocity" except that there is a left derivative
                                          (bx,by) and a right derivative (fx,fy). If (bx,by)
                                          equals (fx,fy) (with no minus sign), you get a
                                          "velocity" curve
  "smooth"/"S"        d=[(x,y), (x,y), ...]
                                          a "velocity" interpolation with (vx,vy)[i] equal to
                                          ((x,y)[i+1] - (x,y)[i-1])/2: the minimal derivative
  """
  defaults = {}

  def __repr__(self):
    return "<Poly (%d nodes) mode=%s loop=%s %s>" % (len(self.d), self.mode, repr(self.loop), self.attr)

  def __init__(self, d=[], mode="L", loop=False, **attr):
    self.d = list(d)
    self.mode = mode
    self.loop = loop

    self.attr = dict(self.defaults)
    self.attr.update(attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    return self.Path(trans).SVG()

  def Path(self, trans=None, local=False):
    """Apply the transformation "trans" and return a Path object in
    global coordinates.  If local=True, return a Path in local coordinates
    (which must be transformed again)."""
    if isinstance(trans, str): trans = totrans(trans)

    if self.mode[0] == "L" or self.mode[0] == "l": mode = "L"
    elif self.mode[0] == "B" or self.mode[0] == "b": mode = "B"
    elif self.mode[0] == "V" or self.mode[0] == "v": mode = "V"
    elif self.mode[0] == "F" or self.mode[0] == "f": mode = "F"
    elif self.mode[0] == "S" or self.mode[0] == "s":
      mode = "S"

      vx, vy = [0.]*len(self.d), [0.]*len(self.d)
      for i in xrange(len(self.d)):
        inext = (i+1) % len(self.d)
        iprev = (i-1) % len(self.d)

        vx[i] = (self.d[inext][0] - self.d[iprev][0])/2.
        vy[i] = (self.d[inext][1] - self.d[iprev][1])/2.
        if not self.loop and (i == 0 or i == len(self.d)-1):
          vx[i], vy[i] = 0., 0.

    else:
      raise ValueError("mode must be \"lines\", \"bezier\", \"velocity\", \"foreback\", \"smooth\", or an abbreviation")

    d = []
    indexes = range(len(self.d))
    if self.loop and len(self.d) > 0: indexes.append(0)

    for i in indexes:
      inext = (i+1) % len(self.d)
      iprev = (i-1) % len(self.d)

      x, y = self.d[i][0], self.d[i][1]

      if trans == None: X, Y = x, y
      else: X, Y = trans(x, y)

      if d == []:
        if local: d.append(("M", x, y, False))
        else: d.append(("M", X, Y, True))

      elif mode == "L":
        if local: d.append(("L", x, y, False))
        else: d.append(("L", X, Y, True))

      elif mode == "B":
        c1x, c1y = self.d[i][2], self.d[i][3]
        if trans == None: C1X, C1Y = c1x, c1y
        else: C1X, C1Y = trans(c1x, c1y)

        c2x, c2y = self.d[i][4], self.d[i][5]
        if trans == None: C2X, C2Y = c2x, c2y
        else: C2X, C2Y = trans(c2x, c2y)

        if local: d.append(("C", c1x, c1y, False, c2x, c2y, False, x, y, False))
        else: d.append(("C", C1X, C1Y, True, C2X, C2Y, True, X, Y, True))

      elif mode == "V":
        c1x, c1y = self.d[iprev][2]/3. + self.d[iprev][0], self.d[iprev][3]/3. + self.d[iprev][1]
        c2x, c2y = self.d[i][2]/-3. + x, self.d[i][3]/-3. + y

        if trans == None: C1X, C1Y = c1x, c1y
        else: C1X, C1Y = trans(c1x, c1y)
        if trans == None: C2X, C2Y = c2x, c2y
        else: C2X, C2Y = trans(c2x, c2y)

        if local: d.append(("C", c1x, c1y, False, c2x, c2y, False, x, y, False))
        else: d.append(("C", C1X, C1Y, True, C2X, C2Y, True, X, Y, True))

      elif mode == "F":
        c1x, c1y = self.d[iprev][4]/3. + self.d[iprev][0], self.d[iprev][5]/3. + self.d[iprev][1]
        c2x, c2y = self.d[i][2]/-3. + x, self.d[i][3]/-3. + y

        if trans == None: C1X, C1Y = c1x, c1y
        else: C1X, C1Y = trans(c1x, c1y)
        if trans == None: C2X, C2Y = c2x, c2y
        else: C2X, C2Y = trans(c2x, c2y)

        if local: d.append(("C", c1x, c1y, False, c2x, c2y, False, x, y, False))
        else: d.append(("C", C1X, C1Y, True, C2X, C2Y, True, X, Y, True))

      elif mode == "S":
        c1x, c1y = vx[iprev]/3. + self.d[iprev][0], vy[iprev]/3. + self.d[iprev][1]
        c2x, c2y = vx[i]/-3. + x, vy[i]/-3. + y

        if trans == None: C1X, C1Y = c1x, c1y
        else: C1X, C1Y = trans(c1x, c1y)
        if trans == None: C2X, C2Y = c2x, c2y
        else: C2X, C2Y = trans(c2x, c2y)

        if local: d.append(("C", c1x, c1y, False, c2x, c2y, False, x, y, False))
        else: d.append(("C", C1X, C1Y, True, C2X, C2Y, True, X, Y, True))

    if self.loop and len(self.d) > 0: d.append(("Z",))

    return Path(d, **self.attr)

######################################################################

class Text:
  """Draws at text string at a specified point in local coordinates.

  x, y                   required      location of the point in local coordinates
  d                      required      text/Unicode string
  attribute=value pairs  keyword list  SVG attributes 
  """

  defaults = {"stroke":"none", "fill":"black", "font-size":5}

  def __repr__(self):
    return "<Text %s at (%g, %g) %s>" % (repr(self.d), self.x, self.y, self.attr)

  def __init__(self, x, y, d, **attr):
    self.x = x
    self.y = y
    self.d = str(d)
    self.attr = dict(self.defaults)
    self.attr.update(attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    if isinstance(trans, str): trans = totrans(trans)

    X, Y = self.x, self.y
    if trans != None: X, Y = trans(X, Y)
    return SVG("text", self.d, x=X, y=Y, **self.attr)

class TextGlobal:
  """Draws at text string at a specified point in global coordinates.

  x, y                   required      location of the point in global coordinates
  d                      required      text/Unicode string
  attribute=value pairs  keyword list  SVG attributes 
  """
  defaults = {"stroke":"none", "fill":"black", "font-size":5}

  def __repr__(self):
    return "<TextGlobal %s at (%s, %s) %s>" % (repr(self.d), str(self.x), str(self.y), self.attr)

  def __init__(self, x, y, d, **attr):
    self.x = x
    self.y = y
    self.d = str(d)
    self.attr = dict(self.defaults)
    self.attr.update(attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    return SVG("text", self.d, x=self.x, y=self.y, **self.attr)

######################################################################

_symbol_templates = {"dot": SVG("symbol", SVG("circle", cx=0, cy=0, r=1, stroke="none", fill="black"), viewBox="0 0 1 1", overflow="visible"), \
                    "box": SVG("symbol", SVG("rect", x1=-1, y1=-1, x2=1, y2=1, stroke="none", fill="black"), viewBox="0 0 1 1", overflow="visible"), \
                    "uptri": SVG("symbol", SVG("path", d="M -1 0.866 L 1 0.866 L 0 -0.866 Z", stroke="none", fill="black"), viewBox="0 0 1 1", overflow="visible"), \
                    "downtri": SVG("symbol", SVG("path", d="M -1 -0.866 L 1 -0.866 L 0 0.866 Z", stroke="none", fill="black"), viewBox="0 0 1 1", overflow="visible"), \
                    }

def make_symbol(id, shape="dot", **attr):
  """Creates a new instance of an SVG symbol to avoid cross-linking objects.

  id                    required         a new identifier (string/Unicode)
  shape                 default="dot"  the shape name from _symbol_templates
  attribute=value list  keyword list     modify the SVG attributes of the new symbol
  """
  output = copy.deepcopy(_symbol_templates[shape])
  for i in output.sub: i.attr.update(attr_preprocess(attr))
  output["id"] = id
  return output

_circular_dot = make_symbol("circular_dot")

class Dots:
  """Dots draws SVG symbols at a set of points.

  d                      required               list of (x,y) points
  symbol                 default=None           SVG symbol or a new identifier to
                                                label an auto-generated symbol;
                                                if None, use pre-defined _circular_dot
  width, height          default=1, 1           width and height of the symbols
                                                in SVG coordinates
  attribute=value pairs  keyword list           SVG attributes
  """
  defaults = {}

  def __repr__(self):
    return "<Dots (%d nodes) %s>" % (len(self.d), self.attr)

  def __init__(self, d=[], symbol=None, width=1., height=1., **attr):
    self.d = list(d)
    self.width = width
    self.height = height

    self.attr = dict(self.defaults)
    self.attr.update(attr)

    if symbol == None:
      self.symbol = _circular_dot
    elif isinstance(symbol, SVG):
      self.symbol = symbol
    else:
      self.symbol = make_symbol(symbol)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    if isinstance(trans, str): trans = totrans(trans)

    output = SVG("g", SVG("defs", self.symbol))
    id = "#%s" % self.symbol["id"]

    for p in self.d:
      x, y = p[0], p[1]

      if trans == None: X, Y = x, y
      else: X, Y = trans(x, y)

      item = SVG("use", x=X, y=Y, xlink__href=id)
      if self.width != None: item["width"] = self.width
      if self.height != None: item["height"] = self.height
      output.append(item)
      
    return output

######################################################################

_marker_templates = {"arrow_start": SVG("marker", SVG("path", d="M 9 3.6 L 10.5 0 L 0 3.6 L 10.5 7.2 L 9 3.6 Z"), viewBox="0 0 10.5 7.2", refX="9", refY="3.6", markerWidth="10.5", markerHeight="7.2", markerUnits="strokeWidth", orient="auto", stroke="none", fill="black"), \
                    "arrow_end": SVG("marker", SVG("path", d="M 1.5 3.6 L 0 0 L 10.5 3.6 L 0 7.2 L 1.5 3.6 Z"), viewBox="0 0 10.5 7.2", refX="1.5", refY="3.6", markerWidth="10.5", markerHeight="7.2", markerUnits="strokeWidth", orient="auto", stroke="none", fill="black"), \
                    }

def make_marker(id, shape, **attr):
  """Creates a new instance of an SVG marker to avoid cross-linking objects.

  id                     required         a new identifier (string/Unicode)
  shape                  required         the shape name from _marker_templates
  attribute=value list   keyword list     modify the SVG attributes of the new marker
  """
  output = copy.deepcopy(_marker_templates[shape])
  for i in output.sub: i.attr.update(attr_preprocess(attr))
  output["id"] = id
  return output

class Line(Curve):
  """Draws a line between two points.

  Line(x1, y1, x2, y2, arrow_start, arrow_end, attribute=value)

  x1, y1                  required        the starting point
  x2, y2                  required        the ending point
  arrow_start             default=None    if an identifier string/Unicode,
                                          draw a new arrow object at the
                                          beginning of the line; if a marker,
                                          draw that marker instead
  arrow_end               default=None    same for the end of the line
  attribute=value pairs   keyword list    SVG attributes
  """
  defaults = {}

  def __repr__(self):
    return "<Line (%g, %g) to (%g, %g) %s>" % (self.x1, self.y1, self.x2, self.y2, self.attr)

  def __init__(self, x1, y1, x2, y2, arrow_start=None, arrow_end=None, **attr):
    self.x1, self.y1, self.x2, self.y2 = x1, y1, x2, y2
    self.arrow_start, self.arrow_end = arrow_start, arrow_end       

    self.attr = dict(self.defaults)
    self.attr.update(attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""

    line = self.Path(trans).SVG()

    if (self.arrow_start != False and self.arrow_start != None) or (self.arrow_end != False and self.arrow_end != None):
      defs = SVG("defs")

      if self.arrow_start != False and self.arrow_start != None:
        if isinstance(self.arrow_start, SVG):
          defs.append(self.arrow_start)
          line.attr["marker-start"] = "url(#%s)" % self.arrow_start["id"]
        elif isinstance(self.arrow_start, str):
          defs.append(make_marker(self.arrow_start, "arrow_start"))
          line.attr["marker-start"] = "url(#%s)" % self.arrow_start
        else:
          raise TypeError("arrow_start must be False/None or an id string for the new marker")

      if self.arrow_end != False and self.arrow_end != None:
        if isinstance(self.arrow_end, SVG):
          defs.append(self.arrow_end)
          line.attr["marker-end"] = "url(#%s)" % self.arrow_end["id"]
        elif isinstance(self.arrow_end, str):
          defs.append(make_marker(self.arrow_end, "arrow_end"))
          line.attr["marker-end"] = "url(#%s)" % self.arrow_end
        else:
          raise TypeError("arrow_end must be False/None or an id string for the new marker")

      return SVG("g", defs, line)

    return line

  def Path(self, trans=None, local=False):
    """Apply the transformation "trans" and return a Path object in
    global coordinates.  If local=True, return a Path in local coordinates
    (which must be transformed again)."""
    self.f = lambda t: (self.x1 + t*(self.x2 - self.x1), self.y1 + t*(self.y2 - self.y1))
    self.low = 0.
    self.high = 1.
    self.loop = False

    if trans == None:
      return Path([("M", self.x1, self.y1, not local), ("L", self.x2, self.y2, not local)], **self.attr)
    else:
      return Curve.Path(self, trans, local)

class LineGlobal:
  """Draws a line between two points, one or both of which is in
  global coordinates.

  Line(x1, y1, x2, y2, lcoal1, local2, arrow_start, arrow_end, attribute=value)

  x1, y1                  required        the starting point
  x2, y2                  required        the ending point
  local1                  default=False   if True, interpret first point as a
                                          local coordinate (apply transform)
  local2                  default=False   if True, interpret second point as a
                                          local coordinate (apply transform)
  arrow_start             default=None    if an identifier string/Unicode,
                                          draw a new arrow object at the
                                          beginning of the line; if a marker,
                                          draw that marker instead
  arrow_end               default=None    same for the end of the line
  attribute=value pairs   keyword list    SVG attributes
  """
  defaults = {}

  def __repr__(self):
    local1, local2 = "", ""
    if self.local1: local1 = "L"
    if self.local2: local2 = "L"

    return "<LineGlobal %s(%s, %s) to %s(%s, %s) %s>" % (local1, str(self.x1), str(self.y1), local2, str(self.x2), str(self.y2), self.attr)

  def __init__(self, x1, y1, x2, y2, local1=False, local2=False, arrow_start=None, arrow_end=None, **attr):
    self.x1, self.y1, self.x2, self.y2 = x1, y1, x2, y2
    self.local1, self.local2 = local1, local2
    self.arrow_start, self.arrow_end = arrow_start, arrow_end

    self.attr = dict(self.defaults)
    self.attr.update(attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    if isinstance(trans, str): trans = totrans(trans)

    X1, Y1, X2, Y2 = self.x1, self.y1, self.x2, self.y2

    if self.local1: X1, Y1 = trans(X1, Y1)
    if self.local2: X2, Y2 = trans(X2, Y2)

    line = SVG("path", d="M%s %s L%s %s" % (X1, Y1, X2, Y2), **self.attr)

    if (self.arrow_start != False and self.arrow_start != None) or (self.arrow_end != False and self.arrow_end != None):
      defs = SVG("defs")

      if self.arrow_start != False and self.arrow_start != None:
        if isinstance(self.arrow_start, SVG):
          defs.append(self.arrow_start)
          line.attr["marker-start"] = "url(#%s)" % self.arrow_start["id"]
        elif isinstance(self.arrow_start, str):
          defs.append(make_marker(self.arrow_start, "arrow_start"))
          line.attr["marker-start"] = "url(#%s)" % self.arrow_start
        else:
          raise TypeError("arrow_start must be False/None or an id string for the new marker")

      if self.arrow_end != False and self.arrow_end != None:
        if isinstance(self.arrow_end, SVG):
          defs.append(self.arrow_end)
          line.attr["marker-end"] = "url(#%s)" % self.arrow_end["id"]
        elif isinstance(self.arrow_end, str):
          defs.append(make_marker(self.arrow_end, "arrow_end"))
          line.attr["marker-end"] = "url(#%s)" % self.arrow_end
        else:
          raise TypeError("arrow_end must be False/None or an id string for the new marker")

      return SVG("g", defs, line)

    return line

class VLine(Line):
  """Draws a vertical line.

  VLine(y1, y2, x, attribute=value)

  y1, y2                  required        y range
  x                       required        x position
  attribute=value pairs   keyword list    SVG attributes
  """
  defaults = {}

  def __repr__(self):
    return "<VLine (%g, %g) at x=%s %s>" % (self.y1, self.y2, self.x, self.attr)

  def __init__(self, y1, y2, x, **attr):
    self.x = x
    self.attr = dict(self.defaults)
    self.attr.update(attr)
    Line.__init__(self, x, y1, x, y2, **self.attr)

  def Path(self, trans=None, local=False):
    """Apply the transformation "trans" and return a Path object in
    global coordinates.  If local=True, return a Path in local coordinates
    (which must be transformed again)."""
    self.x1 = self.x
    self.x2 = self.x
    return Line.Path(self, trans, local)

class HLine(Line):
  """Draws a horizontal line.

  HLine(x1, x2, y, attribute=value)

  x1, x2                  required        x range
  y                       required        y position
  attribute=value pairs   keyword list    SVG attributes
  """
  defaults = {}

  def __repr__(self):
    return "<HLine (%g, %g) at y=%s %s>" % (self.x1, self.x2, self.y, self.attr)

  def __init__(self, x1, x2, y, **attr):
    self.y = y
    self.attr = dict(self.defaults)
    self.attr.update(attr)
    Line.__init__(self, x1, y, x2, y, **self.attr)

  def Path(self, trans=None, local=False):
    """Apply the transformation "trans" and return a Path object in
    global coordinates.  If local=True, return a Path in local coordinates
    (which must be transformed again)."""
    self.y1 = self.y
    self.y2 = self.y
    return Line.Path(self, trans, local)

######################################################################

class Rect(Curve):
  """Draws a rectangle.

  Rect(x1, y1, x2, y2, attribute=value)

  x1, y1                  required        the starting point
  x2, y2                  required        the ending point
  attribute=value pairs   keyword list    SVG attributes
  """
  defaults = {}

  def __repr__(self):
    return "<Rect (%g, %g), (%g, %g) %s>" % (self.x1, self.y1, self.x2, self.y2, self.attr)

  def __init__(self, x1, y1, x2, y2, **attr):
    self.x1, self.y1, self.x2, self.y2 = x1, y1, x2, y2

    self.attr = dict(self.defaults)
    self.attr.update(attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    return self.Path(trans).SVG()

  def Path(self, trans=None, local=False):
    """Apply the transformation "trans" and return a Path object in
    global coordinates.  If local=True, return a Path in local coordinates
    (which must be transformed again)."""
    if trans == None:
      return Path([("M", self.x1, self.y1, not local), ("L", self.x2, self.y1, not local), ("L", self.x2, self.y2, not local), ("L", self.x1, self.y2, not local), ("Z",)], **self.attr)

    else:
      self.low = 0.
      self.high = 1.
      self.loop = False

      self.f = lambda t: (self.x1 + t*(self.x2 - self.x1), self.y1)
      d1 = Curve.Path(self, trans, local).d

      self.f = lambda t: (self.x2, self.y1 + t*(self.y2 - self.y1))
      d2 = Curve.Path(self, trans, local).d
      del d2[0]

      self.f = lambda t: (self.x2 + t*(self.x1 - self.x2), self.y2)
      d3 = Curve.Path(self, trans, local).d
      del d3[0]

      self.f = lambda t: (self.x1, self.y2 + t*(self.y1 - self.y2))
      d4 = Curve.Path(self, trans, local).d
      del d4[0]

      return Path(d=(d1 + d2 + d3 + d4 + [("Z",)]), **self.attr)

######################################################################

class Ellipse(Curve):
  """Draws an ellipse from a semimajor vector (ax,ay) and a semiminor
  length (b).

  Ellipse(x, y, ax, ay, b, attribute=value)

  x, y                    required        the center of the ellipse/circle
  ax, ay                  required        a vector indicating the length
                                          and direction of the semimajor axis
  b                       required        the length of the semiminor axis.
                                          If equal to sqrt(ax2 + ay2), the
                                          ellipse is a circle
  attribute=value pairs   keyword list    SVG attributes

  (If sqrt(ax**2 + ay**2) is less than b, then (ax,ay) is actually the
  semiminor axis.)
  """
  defaults = {}

  def __repr__(self):
    return "<Ellipse (%g, %g) a=(%g, %g), b=%g %s>" % (self.x, self.y, self.ax, self.ay, self.b, self.attr)

  def __init__(self, x, y, ax, ay, b, **attr):
    self.x, self.y, self.ax, self.ay, self.b = x, y, ax, ay, b

    self.attr = dict(self.defaults)
    self.attr.update(attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    return self.Path(trans).SVG()

  def Path(self, trans=None, local=False):
    """Apply the transformation "trans" and return a Path object in
    global coordinates.  If local=True, return a Path in local coordinates
    (which must be transformed again)."""
    angle = math.atan2(self.ay, self.ax) + math.pi/2.
    bx = self.b * math.cos(angle)
    by = self.b * math.sin(angle)

    self.f = lambda t: (self.x + self.ax*math.cos(t) + bx*math.sin(t), self.y + self.ay*math.cos(t) + by*math.sin(t))
    self.low = -math.pi
    self.high = math.pi
    self.loop = True
    return Curve.Path(self, trans, local)

######################################################################

def unumber(x):
  """Converts numbers to a Unicode string, taking advantage of special
  Unicode characters to make nice minus signs and scientific notation.
  """
  output = u"%g" % x

  if output[0] == u"-":
    output = u"\u2013" + output[1:]

  index = output.find(u"e")
  if index != -1:
    uniout = unicode(output[:index]) + u"\u00d710"
    saw_nonzero = False
    for n in output[index+1:]:
      if n == u"+": pass # uniout += u"\u207a"
      elif n == u"-": uniout += u"\u207b"
      elif n == u"0":
        if saw_nonzero: uniout += u"\u2070"
      elif n == u"1":
        saw_nonzero = True
        uniout += u"\u00b9"
      elif n == u"2":
        saw_nonzero = True
        uniout += u"\u00b2"
      elif n == u"3":
        saw_nonzero = True
        uniout += u"\u00b3"
      elif u"4" <= n <= u"9":
        saw_nonzero = True
        if saw_nonzero: uniout += eval("u\"\\u%x\"" % (0x2070 + ord(n) - ord(u"0")))
      else: uniout += n

    if uniout[:2] == u"1\u00d7": uniout = uniout[2:]
    return uniout

  return output

class Ticks:
  """Superclass for all graphics primatives that draw ticks,
  miniticks, and tick labels.  This class only draws the ticks.

  Ticks(f, low, high, ticks, miniticks, labels, logbase, arrow_start,
        arrow_end, text_attr, attribute=value)

  f                       required        parametric function along which ticks
                                          will be drawn; has the same format as
                                          the function used in Curve
  low, high               required        range of the independent variable
  ticks                   default=-10     request ticks according to the standard
                                          tick specification (see below)
  miniticks               default=True    request miniticks according to the
                                          standard minitick specification (below)
  labels                  True            request tick labels according to the
                                          standard tick label specification (below)
  logbase                 default=None    if a number, the axis is logarithmic with
                                          ticks at the given base (usually 10)
  arrow_start             default=None    if a new string identifier, draw an arrow
                                          at the low-end of the axis, referenced by
                                          that identifier; if an SVG marker object,
                                          use that marker
  arrow_end               default=None    if a new string identifier, draw an arrow
                                          at the high-end of the axis, referenced by
                                          that identifier; if an SVG marker object,
                                          use that marker
  text_attr               default={}      SVG attributes for the text labels
  attribute=value pairs   keyword list    SVG attributes for the tick marks 

  Standard tick specification:

      * True: same as -10 (below).
      * Positive number N: draw exactly N ticks, including the endpoints. To
        subdivide an axis into 10 equal-sized segments, ask for 11 ticks.
      * Negative number -N: draw at least N ticks. Ticks will be chosen with
        "natural" values, multiples of 2 or 5.
      * List of values: draw a tick mark at each value.
      * Dict of value, label pairs: draw a tick mark at each value, labeling
        it with the given string. This lets you say things like {3.14159: "pi"}.
      * False or None: no ticks.

  Standard minitick specification:

      * True: draw miniticks with "natural" values, more closely spaced than
        the ticks.
      * Positive number N: draw exactly N miniticks, including the endpoints.
        To subdivide an axis into 100 equal-sized segments, ask for 101 miniticks.
      * Negative number -N: draw at least N miniticks.
      * List of values: draw a minitick mark at each value.
      * False or None: no miniticks. 

  Standard tick label specification:

      * True: use the unumber function (described below)
      * Format string: standard format strings, e.g. "%5.2f" for 12.34
      * Python callable: function that converts numbers to strings
      * False or None: no labels 
  """
  defaults = {"stroke-width":"0.25pt"}
  text_defaults = {"stroke":"none", "fill":"black", "font-size":5}
  tick_start = -1.5
  tick_end = 1.5
  minitick_start = -0.75
  minitick_end = 0.75
  text_start = 2.5
  text_angle = 0.

  def __repr__(self):
    return "<Ticks %s from %s to %s ticks=%s labels=%s %s>" % (self.f, self.low, self.high, str(self.ticks), str(self.labels), self.attr)

  def __init__(self, f, low, high, ticks=-10, miniticks=True, labels=True, logbase=None, arrow_start=None, arrow_end=None, text_attr={}, **attr):
    self.f = f
    self.low = low
    self.high = high
    self.ticks = ticks
    self.miniticks = miniticks
    self.labels = labels
    self.logbase = logbase
    self.arrow_start = arrow_start
    self.arrow_end = arrow_end

    self.attr = dict(self.defaults)
    self.attr.update(attr)

    self.text_attr = dict(self.text_defaults)
    self.text_attr.update(text_attr)

  def orient_tickmark(self, t, trans=None):
    """Return the position, normalized local x vector, normalized
    local y vector, and angle of a tick at position t.

    Normally only used internally.
    """
    if isinstance(trans, str): trans = totrans(trans)
    if trans == None:
      f = self.f
    else:
      f = lambda t: trans(*self.f(t))

    eps = _epsilon * abs(self.high - self.low)

    X, Y = f(t)
    Xprime, Yprime = f(t + eps)
    xhatx, xhaty = (Xprime - X)/eps, (Yprime - Y)/eps

    norm = math.sqrt(xhatx**2 + xhaty**2)
    if norm != 0: xhatx, xhaty = xhatx/norm, xhaty/norm
    else: xhatx, xhaty = 1., 0.

    angle = math.atan2(xhaty, xhatx) + math.pi/2.
    yhatx, yhaty = math.cos(angle), math.sin(angle)

    return (X, Y), (xhatx, xhaty), (yhatx, yhaty), angle

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    if isinstance(trans, str): trans = totrans(trans)

    self.last_ticks, self.last_miniticks = self.interpret()
    tickmarks = Path([], **self.attr)
    minitickmarks = Path([], **self.attr)
    output = SVG("g")

    if (self.arrow_start != False and self.arrow_start != None) or (self.arrow_end != False and self.arrow_end != None):
      defs = SVG("defs")

      if self.arrow_start != False and self.arrow_start != None:
        if isinstance(self.arrow_start, SVG):
          defs.append(self.arrow_start)
        elif isinstance(self.arrow_start, str):
          defs.append(make_marker(self.arrow_start, "arrow_start"))
        else:
          raise TypeError("arrow_start must be False/None or an id string for the new marker")

      if self.arrow_end != False and self.arrow_end != None:
        if isinstance(self.arrow_end, SVG):
          defs.append(self.arrow_end)
        elif isinstance(self.arrow_end, str):
          defs.append(make_marker(self.arrow_end, "arrow_end"))
        else:
          raise TypeError("arrow_end must be False/None or an id string for the new marker")

      output.append(defs)

    eps = _epsilon * (self.high - self.low)

    for t, label in self.last_ticks.items():
      (X, Y), (xhatx, xhaty), (yhatx, yhaty), angle = self.orient_tickmark(t, trans)
      
      if (not self.arrow_start or abs(t - self.low) > eps) and (not self.arrow_end or abs(t - self.high) > eps):
        tickmarks.d.append(("M", X - yhatx*self.tick_start, Y - yhaty*self.tick_start, True))
        tickmarks.d.append(("L", X - yhatx*self.tick_end, Y - yhaty*self.tick_end, True))

      angle = (angle - math.pi/2.)*180./math.pi + self.text_angle

      ########### a HACK! ############ (to be removed when Inkscape handles baselines)
      if _hacks["inkscape-text-vertical-shift"]:
        if self.text_start > 0:
          X += math.cos(angle*math.pi/180. + math.pi/2.) * 2.
          Y += math.sin(angle*math.pi/180. + math.pi/2.) * 2.
        else:
          X += math.cos(angle*math.pi/180. + math.pi/2.) * 2. * 2.5
          Y += math.sin(angle*math.pi/180. + math.pi/2.) * 2. * 2.5
      ########### end hack ###########

      if label != "":
        output.append(SVG("text", label, transform="translate(%g, %g) rotate(%g)" % \
                          (X - yhatx*self.text_start, Y - yhaty*self.text_start, angle), **self.text_attr))

    for t in self.last_miniticks:
      skip = False
      for tt in self.last_ticks.keys():
        if abs(t - tt) < eps:
          skip = True
          break
      if not skip:
        (X, Y), (xhatx, xhaty), (yhatx, yhaty), angle = self.orient_tickmark(t, trans)

      if (not self.arrow_start or abs(t - self.low) > eps) and (not self.arrow_end or abs(t - self.high) > eps):
        minitickmarks.d.append(("M", X - yhatx*self.minitick_start, Y - yhaty*self.minitick_start, True))
        minitickmarks.d.append(("L", X - yhatx*self.minitick_end, Y - yhaty*self.minitick_end, True))

    output.prepend(tickmarks.SVG(trans))
    output.prepend(minitickmarks.SVG(trans))
    return output

  def interpret(self):
    """Evaluate and return optimal ticks and miniticks according to
    the standard minitick specification.

    Normally only used internally.
    """

    if self.labels == None or self.labels == False:
      format = lambda x: ""

    elif self.labels == True:
      format = unumber

    elif isinstance(self.labels, str):
      format = lambda x: (self.labels % x)

    elif callable(self.labels):
      format = self.labels

    else: raise TypeError("labels must be None/False, True, a format string, or a number->string function")

    # Now for the ticks
    ticks = self.ticks

    # Case 1: ticks is None/False
    if ticks == None or ticks == False: return {}, []

    # Case 2: ticks is the number of desired ticks
    elif isinstance(ticks, (int, long)):
      if ticks == True: ticks = -10

      if self.logbase == None:
        ticks = self.compute_ticks(ticks, format)
      else:
        ticks = self.compute_logticks(self.logbase, ticks, format)

      # Now for the miniticks
      if self.miniticks == True:
        if self.logbase == None:
          return ticks, self.compute_miniticks(ticks)
        else:
          return ticks, self.compute_logminiticks(self.logbase)

      elif isinstance(self.miniticks, (int, long)):
        return ticks, self.regular_miniticks(self.miniticks)

      elif getattr(self.miniticks, "__iter__", False):
        return ticks, self.miniticks

      elif self.miniticks == False or self.miniticks == None:
        return ticks, []

      else:
        raise TypeError("miniticks must be None/False, True, a number of desired miniticks, or a list of numbers")
        
    # Cases 3 & 4: ticks is iterable
    elif getattr(ticks, "__iter__", False):

      # Case 3: ticks is some kind of list
      if not isinstance(ticks, dict):
        output = {}
        eps = _epsilon * (self.high - self.low)
        for x in ticks:
          if format == unumber and abs(x) < eps:
            output[x] = u"0"
          else:
            output[x] = format(x)
        ticks = output

      # Case 4: ticks is a dict
      else: pass

      # Now for the miniticks
      if self.miniticks == True:
        if self.logbase == None:
          return ticks, self.compute_miniticks(ticks)
        else:
          return ticks, self.compute_logminiticks(self.logbase)

      elif isinstance(self.miniticks, (int, long)):
        return ticks, self.regular_miniticks(self.miniticks)

      elif getattr(self.miniticks, "__iter__", False):
        return ticks, self.miniticks

      elif self.miniticks == False or self.miniticks == None:
        return ticks, []

      else:
        raise TypeError("miniticks must be None/False, True, a number of desired miniticks, or a list of numbers")
        
    else:
      raise TypeError("ticks must be None/False, a number of desired ticks, a list of numbers, or a dictionary of explicit markers")

  def compute_ticks(self, N, format):
    """Return less than -N or exactly N optimal linear ticks.

    Normally only used internally.
    """
    if self.low >= self.high: raise ValueError("low must be less than high")
    if N == 1: raise ValueError("N can be 0 or >1 to specify the exact number of ticks or negative to specify a maximum")

    eps = _epsilon * (self.high - self.low)

    if N >= 0:
      output = {}
      x = self.low
      for i in xrange(N):
        if format == unumber and abs(x) < eps: label = u"0"
        else: label = format(x)
        output[x] = label
        x += (self.high - self.low)/(N-1.)
      return output

    N = -N

    counter = 0
    granularity = 10**math.ceil(math.log10(max(abs(self.low), abs(self.high))))
    lowN = math.ceil(1.*self.low / granularity)
    highN = math.floor(1.*self.high / granularity)

    while (lowN > highN):
      countermod3 = counter % 3
      if countermod3 == 0: granularity *= 0.5
      elif countermod3 == 1: granularity *= 0.4
      else: granularity *= 0.5
      counter += 1
      lowN = math.ceil(1.*self.low / granularity)
      highN = math.floor(1.*self.high / granularity)

    last_granularity = granularity
    last_trial = None

    while True:
      trial = {}
      for n in range(int(lowN), int(highN)+1):
        x = n * granularity
        if format == unumber and abs(x) < eps: label = u"0"
        else: label = format(x)
        trial[x] = label

      if int(highN)+1 - int(lowN) >= N:
        if last_trial == None:
          v1, v2 = self.low, self.high
          return {v1: format(v1), v2: format(v2)}
        else:
          low_in_ticks, high_in_ticks = False, False
          for t in last_trial.keys():
            if 1.*abs(t - self.low)/last_granularity < _epsilon: low_in_ticks = True
            if 1.*abs(t - self.high)/last_granularity < _epsilon: high_in_ticks = True

          lowN = 1.*self.low / last_granularity
          highN = 1.*self.high / last_granularity
          if abs(lowN - round(lowN)) < _epsilon and not low_in_ticks:
            last_trial[self.low] = format(self.low)
          if abs(highN - round(highN)) < _epsilon and not high_in_ticks:
            last_trial[self.high] = format(self.high)
          return last_trial

      last_granularity = granularity
      last_trial = trial

      countermod3 = counter % 3
      if countermod3 == 0: granularity *= 0.5
      elif countermod3 == 1: granularity *= 0.4
      else: granularity *= 0.5
      counter += 1
      lowN = math.ceil(1.*self.low / granularity)
      highN = math.floor(1.*self.high / granularity)

  def regular_miniticks(self, N):
    """Return exactly N linear ticks.

    Normally only used internally.
    """
    output = []
    x = self.low
    for i in xrange(N):
      output.append(x)
      x += (self.high - self.low)/(N-1.)
    return output

  def compute_miniticks(self, original_ticks):
    """Return optimal linear miniticks, given a set of ticks.

    Normally only used internally.
    """
    if len(original_ticks) < 2: original_ticks = ticks(self.low, self.high)
    original_ticks = sorted(original_ticks.keys())

    if self.low > original_ticks[0] + _epsilon or self.high < original_ticks[-1] - _epsilon:
      raise ValueError("original_ticks {%g...%g} extend beyond [%g, %g]" % (original_ticks[0], original_ticks[-1], self.low, self.high))

    granularities = []
    for i in range(len(original_ticks)-1):
      granularities.append(original_ticks[i+1] - original_ticks[i])
    spacing = 10**(math.ceil(math.log10(min(granularities)) - 1))

    output = []
    x = original_ticks[0] - math.ceil(1.*(original_ticks[0] - self.low) / spacing) * spacing

    while x <= self.high:
      if x >= self.low:
        already_in_ticks = False
        for t in original_ticks:
          if abs(x-t) < _epsilon * (self.high - self.low): already_in_ticks = True
        if not already_in_ticks: output.append(x)
      x += spacing
    return output

  def compute_logticks(self, base, N, format):
    """Return less than -N or exactly N optimal logarithmic ticks.

    Normally only used internally.
    """
    if self.low >= self.high: raise ValueError("low must be less than high")
    if N == 1: raise ValueError("N can be 0 or >1 to specify the exact number of ticks or negative to specify a maximum")

    eps = _epsilon * (self.high - self.low)

    if N >= 0:
      output = {}
      x = self.low
      for i in xrange(N):
        if format == unumber and abs(x) < eps: label = u"0"
        else: label = format(x)
        output[x] = label
        x += (self.high - self.low)/(N-1.)
      return output

    N = -N

    lowN = math.floor(math.log(self.low, base))
    highN = math.ceil(math.log(self.high, base))
    output = {}
    for n in range(int(lowN), int(highN)+1):
      x = base**n
      label = format(x)
      if self.low <= x <= self.high: output[x] = label

    for i in range(1, len(output)):
      keys = sorted(output.keys())
      keys = keys[::i]
      values = map(lambda k: output[k], keys)
      if len(values) <= N:
        for k in output.keys():
          if k not in keys:
            output[k] = ""
        break

    if len(output) <= 2:
      output2 = self.compute_ticks(N=-int(math.ceil(N/2.)), format=format)
      lowest = min(output2)

      for k in output:
        if k < lowest: output2[k] = output[k]
      output = output2

    return output

  def compute_logminiticks(self, base):
    """Return optimal logarithmic miniticks, given a set of ticks.

    Normally only used internally.
    """
    if self.low >= self.high: raise ValueError("low must be less than high")

    lowN = math.floor(math.log(self.low, base))
    highN = math.ceil(math.log(self.high, base))
    output = []
    num_ticks = 0
    for n in range(int(lowN), int(highN)+1):
      x = base**n
      if self.low <= x <= self.high: num_ticks += 1
      for m in range(2, int(math.ceil(base))):
        minix = m * x
        if self.low <= minix <= self.high: output.append(minix)

    if num_ticks <= 2: return []
    else: return output

######################################################################

class CurveAxis(Curve, Ticks):
  """Draw an axis with tick marks along a parametric curve.

  CurveAxis(f, low, high, ticks, miniticks, labels, logbase, arrow_start, arrow_end,
  text_attr, attribute=value)

  f                      required         a Python callable or string in
                                          the form "f(t), g(t)", just like Curve
  low, high              required         left and right endpoints
  ticks                  default=-10      request ticks according to the standard
                                          tick specification (see help(Ticks))
  miniticks              default=True     request miniticks according to the
                                          standard minitick specification
  labels                 True             request tick labels according to the
                                          standard tick label specification
  logbase                default=None     if a number, the x axis is logarithmic
                                          with ticks at the given base (10 being
                                          the most common)
  arrow_start            default=None     if a new string identifier, draw an
                                          arrow at the low-end of the axis,
                                          referenced by that identifier; if an
                                          SVG marker object, use that marker
  arrow_end              default=None     if a new string identifier, draw an
                                          arrow at the high-end of the axis,
                                          referenced by that identifier; if an
                                          SVG marker object, use that marker
  text_attr              default={}       SVG attributes for the text labels
  attribute=value pairs  keyword list     SVG attributes
  """
  defaults = {"stroke-width":"0.25pt"}
  text_defaults = {"stroke":"none", "fill":"black", "font-size":5}

  def __repr__(self):
    return "<CurveAxis %s [%s, %s] ticks=%s labels=%s %s>" % (self.f, self.low, self.high, str(self.ticks), str(self.labels), self.attr)

  def __init__(self, f, low, high, ticks=-10, miniticks=True, labels=True, logbase=None, arrow_start=None, arrow_end=None, text_attr={}, **attr):
    tattr = dict(self.text_defaults)
    tattr.update(text_attr)
    Curve.__init__(self, f, low, high)
    Ticks.__init__(self, f, low, high, ticks, miniticks, labels, logbase, arrow_start, arrow_end, tattr, **attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    func = Curve.SVG(self, trans)
    ticks = Ticks.SVG(self, trans) # returns a <g />

    if self.arrow_start != False and self.arrow_start != None:
      if isinstance(self.arrow_start, str):
        func.attr["marker-start"] = "url(#%s)" % self.arrow_start
      else:
        func.attr["marker-start"] = "url(#%s)" % self.arrow_start.id

    if self.arrow_end != False and self.arrow_end != None:
      if isinstance(self.arrow_end, str):
        func.attr["marker-end"] = "url(#%s)" % self.arrow_end
      else:
        func.attr["marker-end"] = "url(#%s)" % self.arrow_end.id

    ticks.append(func)
    return ticks

class LineAxis(Line, Ticks):
  """Draws an axis with tick marks along a line.

  LineAxis(x1, y1, x2, y2, start, end, ticks, miniticks, labels, logbase,
  arrow_start, arrow_end, text_attr, attribute=value)

  x1, y1                  required        starting point
  x2, y2                  required        ending point
  start, end              default=0, 1    values to start and end labeling
  ticks                   default=-10     request ticks according to the standard
                                          tick specification (see help(Ticks))
  miniticks               default=True    request miniticks according to the
                                          standard minitick specification
  labels                  True            request tick labels according to the
                                          standard tick label specification
  logbase                 default=None    if a number, the x axis is logarithmic
                                          with ticks at the given base (usually 10)
  arrow_start             default=None    if a new string identifier, draw an arrow
                                          at the low-end of the axis, referenced by
                                          that identifier; if an SVG marker object,
                                          use that marker
  arrow_end               default=None    if a new string identifier, draw an arrow
                                          at the high-end of the axis, referenced by
                                          that identifier; if an SVG marker object,
                                          use that marker
  text_attr               default={}      SVG attributes for the text labels
  attribute=value pairs   keyword list    SVG attributes
  """
  defaults = {"stroke-width":"0.25pt"}
  text_defaults = {"stroke":"none", "fill":"black", "font-size":5}

  def __repr__(self):
    return "<LineAxis (%g, %g) to (%g, %g) ticks=%s labels=%s %s>" % (self.x1, self.y1, self.x2, self.y2, str(self.ticks), str(self.labels), self.attr)

  def __init__(self, x1, y1, x2, y2, start=0., end=1., ticks=-10, miniticks=True, labels=True, logbase=None, arrow_start=None, arrow_end=None, exclude=None, text_attr={}, **attr):
    self.start = start
    self.end = end
    self.exclude = exclude
    tattr = dict(self.text_defaults)
    tattr.update(text_attr)
    Line.__init__(self, x1, y1, x2, y2, **attr)
    Ticks.__init__(self, None, None, None, ticks, miniticks, labels, logbase, arrow_start, arrow_end, tattr, **attr)

  def interpret(self):
    if self.exclude != None and not (isinstance(self.exclude, (tuple, list)) and len(self.exclude) == 2 and \
                                     isinstance(self.exclude[0], (int, long, float)) and isinstance(self.exclude[1], (int, long, float))):
      raise TypeError("exclude must either be None or (low, high)")

    ticks, miniticks = Ticks.interpret(self)
    if self.exclude == None: return ticks, miniticks

    ticks2 = {}
    for loc, label in ticks.items():
      if self.exclude[0] <= loc <= self.exclude[1]:
        ticks2[loc] = ""
      else:
        ticks2[loc] = label

    return ticks2, miniticks

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    line = Line.SVG(self, trans) # must be evaluated first, to set self.f, self.low, self.high

    f01 = self.f
    self.f = lambda t: f01(1. * (t - self.start) / (self.end - self.start))
    self.low = self.start
    self.high = self.end

    if self.arrow_start != False and self.arrow_start != None:
      if isinstance(self.arrow_start, str):
        line.attr["marker-start"] = "url(#%s)" % self.arrow_start
      else:
        line.attr["marker-start"] = "url(#%s)" % self.arrow_start.id

    if self.arrow_end != False and self.arrow_end != None:
      if isinstance(self.arrow_end, str):
        line.attr["marker-end"] = "url(#%s)" % self.arrow_end
      else:
        line.attr["marker-end"] = "url(#%s)" % self.arrow_end.id

    ticks = Ticks.SVG(self, trans) # returns a <g />
    ticks.append(line)
    return ticks
  
class XAxis(LineAxis):
  """Draws an x axis with tick marks.

  XAxis(xmin, xmax, aty, ticks, miniticks, labels, logbase, arrow_start, arrow_end,
  exclude, text_attr, attribute=value)

  xmin, xmax              required        the x range
  aty                     default=0       y position to draw the axis
  ticks                   default=-10     request ticks according to the standard
                                          tick specification (see help(Ticks))
  miniticks               default=True    request miniticks according to the
                                          standard minitick specification
  labels                  True            request tick labels according to the
                                          standard tick label specification
  logbase                 default=None    if a number, the x axis is logarithmic
                                          with ticks at the given base (usually 10)
  arrow_start             default=None    if a new string identifier, draw an arrow
                                          at the low-end of the axis, referenced by
                                          that identifier; if an SVG marker object,
                                          use that marker
  arrow_end               default=None    if a new string identifier, draw an arrow
                                          at the high-end of the axis, referenced by
                                          that identifier; if an SVG marker object,
                                          use that marker
  exclude                 default=None    if a (low, high) pair, don't draw text
                                          labels within this range
  text_attr               default={}      SVG attributes for the text labels
  attribute=value pairs   keyword list    SVG attributes for all lines

  The exclude option is provided for Axes to keep text from overlapping
  where the axes cross. Normal users are not likely to need it.
  """
  defaults = {"stroke-width":"0.25pt"}
  text_defaults = {"stroke":"none", "fill":"black", "font-size":5, "dominant-baseline":"text-before-edge"}
  text_start = -1.
  text_angle = 0.

  def __repr__(self):
    return "<XAxis (%g, %g) at y=%g ticks=%s labels=%s %s>" % (self.xmin, self.xmax, self.aty, str(self.ticks), str(self.labels), self.attr)

  def __init__(self, xmin, xmax, aty=0, ticks=-10, miniticks=True, labels=True, logbase=None, arrow_start=None, arrow_end=None, exclude=None, text_attr={}, **attr):
    self.aty = aty
    tattr = dict(self.text_defaults)
    tattr.update(text_attr)
    LineAxis.__init__(self, xmin, aty, xmax, aty, xmin, xmax, ticks, miniticks, labels, logbase, arrow_start, arrow_end, exclude, tattr, **attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    self.y1 = self.aty
    self.y2 = self.aty
    return LineAxis.SVG(self, trans)

class YAxis(LineAxis):
  """Draws a y axis with tick marks.

  YAxis(ymin, ymax, atx, ticks, miniticks, labels, logbase, arrow_start, arrow_end,
  exclude, text_attr, attribute=value)

  ymin, ymax              required        the y range
  atx                     default=0       x position to draw the axis
  ticks                   default=-10     request ticks according to the standard
                                          tick specification (see help(Ticks))
  miniticks               default=True    request miniticks according to the
                                          standard minitick specification
  labels                  True            request tick labels according to the
                                          standard tick label specification
  logbase                 default=None    if a number, the y axis is logarithmic
                                          with ticks at the given base (usually 10)
  arrow_start             default=None    if a new string identifier, draw an arrow
                                          at the low-end of the axis, referenced by
                                          that identifier; if an SVG marker object,
                                          use that marker
  arrow_end               default=None    if a new string identifier, draw an arrow
                                          at the high-end of the axis, referenced by
                                          that identifier; if an SVG marker object,
                                          use that marker
  exclude                 default=None    if a (low, high) pair, don't draw text
                                          labels within this range
  text_attr               default={}      SVG attributes for the text labels
  attribute=value pairs   keyword list    SVG attributes for all lines

  The exclude option is provided for Axes to keep text from overlapping
  where the axes cross. Normal users are not likely to need it.
  """
  defaults = {"stroke-width":"0.25pt"}
  text_defaults = {"stroke":"none", "fill":"black", "font-size":5, "text-anchor":"end", "dominant-baseline":"middle"}
  text_start = 2.5
  text_angle = 90.

  def __repr__(self):
    return "<YAxis (%g, %g) at x=%g ticks=%s labels=%s %s>" % (self.ymin, self.ymax, self.atx, str(self.ticks), str(self.labels), self.attr)

  def __init__(self, ymin, ymax, atx=0, ticks=-10, miniticks=True, labels=True, logbase=None, arrow_start=None, arrow_end=None, exclude=None, text_attr={}, **attr):
    self.atx = atx
    tattr = dict(self.text_defaults)
    tattr.update(text_attr)
    LineAxis.__init__(self, atx, ymin, atx, ymax, ymin, ymax, ticks, miniticks, labels, logbase, arrow_start, arrow_end, exclude, tattr, **attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    self.x1 = self.atx
    self.x2 = self.atx
    return LineAxis.SVG(self, trans)

class Axes:
  """Draw a pair of intersecting x-y axes.

  Axes(xmin, xmax, ymin, ymax, atx, aty, xticks, xminiticks, xlabels, xlogbase,
  yticks, yminiticks, ylabels, ylogbase, arrows, text_attr, attribute=value)

  xmin, xmax               required       the x range
  ymin, ymax               required       the y range
  atx, aty                 default=0, 0   point where the axes try to cross;
                                          if outside the range, the axes will
                                          cross at the closest corner
  xticks                   default=-10    request ticks according to the standard
                                          tick specification (see help(Ticks))
  xminiticks               default=True   request miniticks according to the
                                          standard minitick specification
  xlabels                  True           request tick labels according to the
                                          standard tick label specification
  xlogbase                 default=None   if a number, the x axis is logarithmic
                                          with ticks at the given base (usually 10)
  yticks                   default=-10    request ticks according to the standard
                                          tick specification
  yminiticks               default=True   request miniticks according to the
                                          standard minitick specification
  ylabels                  True           request tick labels according to the
                                          standard tick label specification
  ylogbase                 default=None   if a number, the y axis is logarithmic
                                          with ticks at the given base (usually 10)
  arrows                   default=None   if a new string identifier, draw arrows
                                          referenced by that identifier
  text_attr                default={}     SVG attributes for the text labels
  attribute=value pairs    keyword list   SVG attributes for all lines
  """
  defaults = {"stroke-width":"0.25pt"}
  text_defaults = {"stroke":"none", "fill":"black", "font-size":5}

  def __repr__(self):
    return "<Axes x=(%g, %g) y=(%g, %g) at (%g, %g) %s>" % (self.xmin, self.xmax, self.ymin, self.ymax, self.atx, self.aty, self.attr)

  def __init__(self, xmin, xmax, ymin, ymax, atx=0, aty=0, xticks=-10, xminiticks=True, xlabels=True, xlogbase=None, yticks=-10, yminiticks=True, ylabels=True, ylogbase=None, arrows=None, text_attr={}, **attr):
    self.xmin, self.xmax = xmin, xmax
    self.ymin, self.ymax = ymin, ymax
    self.atx, self.aty = atx, aty
    self.xticks, self.xminiticks, self.xlabels, self.xlogbase = xticks, xminiticks, xlabels, xlogbase
    self.yticks, self.yminiticks, self.ylabels, self.ylogbase = yticks, yminiticks, ylabels, ylogbase
    self.arrows = arrows

    self.text_attr = dict(self.text_defaults)
    self.text_attr.update(text_attr)

    self.attr = dict(self.defaults)
    self.attr.update(attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    atx, aty = self.atx, self.aty
    if atx < self.xmin: atx = self.xmin
    if atx > self.xmax: atx = self.xmax
    if aty < self.ymin: aty = self.ymin
    if aty > self.ymax: aty = self.ymax

    xmargin = 0.1 * abs(self.ymin - self.ymax)
    xexclude = atx - xmargin, atx + xmargin
    
    ymargin = 0.1 * abs(self.xmin - self.xmax)
    yexclude = aty - ymargin, aty + ymargin

    if self.arrows != None and self.arrows != False:
      xarrow_start = self.arrows + ".xstart"
      xarrow_end = self.arrows + ".xend"
      yarrow_start = self.arrows + ".ystart"
      yarrow_end = self.arrows + ".yend"
    else:
      xarrow_start = xarrow_end = yarrow_start = yarrow_end = None

    xaxis = XAxis(self.xmin, self.xmax, aty, self.xticks, self.xminiticks, self.xlabels, self.xlogbase, xarrow_start, xarrow_end, exclude=xexclude, text_attr=self.text_attr, **self.attr).SVG(trans)
    yaxis = YAxis(self.ymin, self.ymax, atx, self.yticks, self.yminiticks, self.ylabels, self.ylogbase, yarrow_start, yarrow_end, exclude=yexclude, text_attr=self.text_attr, **self.attr).SVG(trans)
    return SVG("g", *(xaxis.sub + yaxis.sub))

######################################################################

class HGrid(Ticks):
  """Draws the horizontal lines of a grid over a specified region
  using the standard tick specification (see help(Ticks)) to place the
  grid lines.

  HGrid(xmin, xmax, low, high, ticks, miniticks, logbase, mini_attr, attribute=value)

  xmin, xmax              required        the x range
  low, high               required        the y range
  ticks                   default=-10     request ticks according to the standard
                                          tick specification (see help(Ticks))
  miniticks               default=False   request miniticks according to the
                                          standard minitick specification
  logbase                 default=None    if a number, the axis is logarithmic
                                          with ticks at the given base (usually 10)
  mini_attr               default={}      SVG attributes for the minitick-lines
                                          (if miniticks != False)
  attribute=value pairs   keyword list    SVG attributes for the major tick lines
  """
  defaults = {"stroke-width":"0.25pt", "stroke":"gray"}
  mini_defaults = {"stroke-width":"0.25pt", "stroke":"lightgray", "stroke-dasharray":"1,1"}

  def __repr__(self):
    return "<HGrid x=(%g, %g) %g <= y <= %g ticks=%s miniticks=%s %s>" % (self.xmin, self.xmax, self.low, self.high, str(self.ticks), str(self.miniticks), self.attr)

  def __init__(self, xmin, xmax, low, high, ticks=-10, miniticks=False, logbase=None, mini_attr={}, **attr):
    self.xmin, self.xmax = xmin, xmax

    self.mini_attr = dict(self.mini_defaults)
    self.mini_attr.update(mini_attr)

    Ticks.__init__(self, None, low, high, ticks, miniticks, None, logbase)

    self.attr = dict(self.defaults)
    self.attr.update(attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    self.last_ticks, self.last_miniticks = Ticks.interpret(self)

    ticksd = []
    for t in self.last_ticks.keys():
      ticksd += Line(self.xmin, t, self.xmax, t).Path(trans).d

    miniticksd = []
    for t in self.last_miniticks:
      miniticksd += Line(self.xmin, t, self.xmax, t).Path(trans).d

    return SVG("g", Path(d=ticksd, **self.attr).SVG(), Path(d=miniticksd, **self.mini_attr).SVG())
    
class VGrid(Ticks):
  """Draws the vertical lines of a grid over a specified region
  using the standard tick specification (see help(Ticks)) to place the
  grid lines.

  HGrid(ymin, ymax, low, high, ticks, miniticks, logbase, mini_attr, attribute=value)

  ymin, ymax              required        the y range
  low, high               required        the x range
  ticks                   default=-10     request ticks according to the standard
                                          tick specification (see help(Ticks))
  miniticks               default=False   request miniticks according to the
                                          standard minitick specification
  logbase                 default=None    if a number, the axis is logarithmic
                                          with ticks at the given base (usually 10)
  mini_attr               default={}      SVG attributes for the minitick-lines
                                          (if miniticks != False)
  attribute=value pairs   keyword list    SVG attributes for the major tick lines
  """
  defaults = {"stroke-width":"0.25pt", "stroke":"gray"}
  mini_defaults = {"stroke-width":"0.25pt", "stroke":"lightgray", "stroke-dasharray":"1,1"}

  def __repr__(self):
    return "<VGrid y=(%g, %g) %g <= x <= %g ticks=%s miniticks=%s %s>" % (self.ymin, self.ymax, self.low, self.high, str(self.ticks), str(self.miniticks), self.attr)

  def __init__(self, ymin, ymax, low, high, ticks=-10, miniticks=False, logbase=None, mini_attr={}, **attr):
    self.ymin, self.ymax = ymin, ymax

    self.mini_attr = dict(self.mini_defaults)
    self.mini_attr.update(mini_attr)

    Ticks.__init__(self, None, low, high, ticks, miniticks, None, logbase)

    self.attr = dict(self.defaults)
    self.attr.update(attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    self.last_ticks, self.last_miniticks = Ticks.interpret(self)

    ticksd = []
    for t in self.last_ticks.keys():
      ticksd += Line(t, self.ymin, t, self.ymax).Path(trans).d

    miniticksd = []
    for t in self.last_miniticks:
      miniticksd += Line(t, self.ymin, t, self.ymax).Path(trans).d

    return SVG("g", Path(d=ticksd, **self.attr).SVG(), Path(d=miniticksd, **self.mini_attr).SVG())

class Grid(Ticks):
  """Draws a grid over a specified region using the standard tick
  specification (see help(Ticks)) to place the grid lines.

  Grid(xmin, xmax, ymin, ymax, ticks, miniticks, logbase, mini_attr, attribute=value)

  xmin, xmax              required        the x range
  ymin, ymax              required        the y range
  ticks                   default=-10     request ticks according to the standard
                                          tick specification (see help(Ticks))
  miniticks               default=False   request miniticks according to the
                                          standard minitick specification
  logbase                 default=None    if a number, the axis is logarithmic
                                          with ticks at the given base (usually 10)
  mini_attr               default={}      SVG attributes for the minitick-lines
                                          (if miniticks != False)
  attribute=value pairs   keyword list    SVG attributes for the major tick lines
  """
  defaults = {"stroke-width":"0.25pt", "stroke":"gray"}
  mini_defaults = {"stroke-width":"0.25pt", "stroke":"lightgray", "stroke-dasharray":"1,1"}

  def __repr__(self):
    return "<Grid x=(%g, %g) y=(%g, %g) ticks=%s miniticks=%s %s>" % (self.xmin, self.xmax, self.ymin, self.ymax, str(self.ticks), str(self.miniticks), self.attr)

  def __init__(self, xmin, xmax, ymin, ymax, ticks=-10, miniticks=False, logbase=None, mini_attr={}, **attr):
    self.xmin, self.xmax = xmin, xmax
    self.ymin, self.ymax = ymin, ymax

    self.mini_attr = dict(self.mini_defaults)
    self.mini_attr.update(mini_attr)

    Ticks.__init__(self, None, None, None, ticks, miniticks, None, logbase)

    self.attr = dict(self.defaults)
    self.attr.update(attr)

  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    self.low, self.high = self.xmin, self.xmax
    self.last_xticks, self.last_xminiticks = Ticks.interpret(self)
    self.low, self.high = self.ymin, self.ymax
    self.last_yticks, self.last_yminiticks = Ticks.interpret(self)

    ticksd = []
    for t in self.last_xticks.keys():
      ticksd += Line(t, self.ymin, t, self.ymax).Path(trans).d
    for t in self.last_yticks.keys():
      ticksd += Line(self.xmin, t, self.xmax, t).Path(trans).d

    miniticksd = []
    for t in self.last_xminiticks:
      miniticksd += Line(t, self.ymin, t, self.ymax).Path(trans).d
    for t in self.last_yminiticks:
      miniticksd += Line(self.xmin, t, self.xmax, t).Path(trans).d

    return SVG("g", Path(d=ticksd, **self.attr).SVG(), Path(d=miniticksd, **self.mini_attr).SVG())

######################################################################

class XErrorBars:
  """Draws x error bars at a set of points. This is usually used
  before (under) a set of Dots at the same points.

  XErrorBars(d, attribute=value)

  d                       required        list of (x,y,xerr...) points
  attribute=value pairs   keyword list    SVG attributes

  If points in d have

      * 3 elements, the third is the symmetric error bar
      * 4 elements, the third and fourth are the asymmetric lower and
        upper error bar. The third element should be negative,
        e.g. (5, 5, -1, 2) is a bar from 4 to 7.
      * more than 4, a tick mark is placed at each value. This lets
        you nest errors from different sources, correlated and
        uncorrelated, statistical and systematic, etc.
  """
  defaults = {"stroke-width":"0.25pt"}

  def __repr__(self):
    return "<XErrorBars (%d nodes)>" % len(self.d)

  def __init__(self, d=[], **attr):
    self.d = list(d)

    self.attr = dict(self.defaults)
    self.attr.update(attr)
    
  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    if isinstance(trans, str): trans = totrans(trans) # only once

    output = SVG("g")
    for p in self.d:
      x, y = p[0], p[1]

      if len(p) == 3: bars = [x - p[2], x + p[2]]
      else: bars = [x + pi for pi in p[2:]]
      
      start, end = min(bars), max(bars)
      output.append(LineAxis(start, y, end, y, start, end, bars, False, False, **self.attr).SVG(trans))

    return output

class YErrorBars:
  """Draws y error bars at a set of points. This is usually used
  before (under) a set of Dots at the same points.

  YErrorBars(d, attribute=value)

  d                       required        list of (x,y,yerr...) points
  attribute=value pairs   keyword list    SVG attributes

  If points in d have

      * 3 elements, the third is the symmetric error bar
      * 4 elements, the third and fourth are the asymmetric lower and
        upper error bar. The third element should be negative,
        e.g. (5, 5, -1, 2) is a bar from 4 to 7.
      * more than 4, a tick mark is placed at each value. This lets
        you nest errors from different sources, correlated and
        uncorrelated, statistical and systematic, etc.
  """
  defaults = {"stroke-width":"0.25pt"}

  def __repr__(self):
    return "<YErrorBars (%d nodes)>" % len(self.d)

  def __init__(self, d=[], **attr):
    self.d = list(d)

    self.attr = dict(self.defaults)
    self.attr.update(attr)
    
  def SVG(self, trans=None):
    """Apply the transformation "trans" and return an SVG object."""
    if isinstance(trans, str): trans = totrans(trans) # only once

    output = SVG("g")
    for p in self.d:
      x, y = p[0], p[1]

      if len(p) == 3: bars = [y - p[2], y + p[2]]
      else: bars = [y + pi for pi in p[2:]]
      
      start, end = min(bars), max(bars)
      output.append(LineAxis(x, start, x, end, start, end, bars, False, False, **self.attr).SVG(trans))

    return output