def __init__(self, span, lhs, rhs, dot=0, bindings=None):
        """
        Construct a new edge.  If the edge is incomplete (i.e., if
        ``dot<len(rhs)``), then store the bindings as-is.  If the edge
        is complete (i.e., if ``dot==len(rhs)``), then apply the
        bindings to all nonterminals in ``lhs`` and ``rhs``, and then
        clear the bindings.  See ``TreeEdge`` for a description of
        the other arguments.
        """
        if bindings is None: bindings = {}

        # If the edge is complete, then substitute in the bindings,
        # and then throw them away.  (If we didn't throw them away, we
        # might think that 2 complete edges are different just because
        # they have different bindings, even though all bindings have
        # already been applied.)
        if dot == len(rhs) and bindings:
            lhs = self._bind(lhs, bindings)
            rhs = [self._bind(elt, bindings) for elt in rhs]
            bindings = {}

        # Initialize the edge.
        TreeEdge.__init__(self, span, lhs, rhs, dot)
        self._bindings = bindings
        self._comparison_key = (self._comparison_key, tuple(sorted(bindings.items())))

 def __str__(self):
     if self.is_complete():
         return TreeEdge.__unicode__(self)
     else:
         bindings = '{%s}' % ', '.join('%s: %r' % item for item in
                                        sorted(self._bindings.items()))
         return '%s %s' % (TreeEdge.__unicode__(self), bindings)

 def __init__(self, prob, *args, **kwargs):
     TreeEdge.__init__(self, *args, **kwargs)
     self._prob = prob
     # two edges with different probabilities are not equal.
     self._comparison_key = (self._comparison_key, prob)

 def __cmp__(self, other):
     if self._prob != other.prob(): return -1
     return TreeEdge.__cmp__(self, other)

 def __init__(self, prob, *args, **kwargs):
     self._prob = prob
     TreeEdge.__init__(self, *args, **kwargs)

 def __str__(self):
     if self.is_complete():
         return TreeEdge.__unicode__(self)
     else:
         bindings = "{%s}" % ", ".join("%s: %r" % item for item in sorted(self._bindings.items()))
         return "%s %s" % (TreeEdge.__unicode__(self), bindings)