# Natural Language Toolkit: Probabilistic Chart Parsers
#
# Copyright (C) 2001-2006 University of Pennsylvania
# Author: Edward Loper <edloper@gradient.cis.upenn.edu>
#         Steven Bird <sb@csse.unimelb.edu.au>
# URL: <http://nltk.sf.net>
# For license information, see LICENSE.TXT

"""
Classes and interfaces for associating probabilities with tree
structures that represent the internal organization of a text.  The
probabilistic parser module defines C{BottomUpChartParse}.

C{BottomUpChartParse} is an abstract class that implements a
bottom-up chart parser for C{PCFG}s.  It maintains a queue of edges,
and adds them to the chart one at a time.  The ordering of this queue
is based on the probabilities associated with the edges, allowing the
parser to expand more likely edges before less likely ones.  Each
subclass implements a different queue ordering, producing different
search strategies.  Currently the following subclasses are defined:

  - C{InsideParse} searches edges in decreasing order of
    their trees' inside probabilities.
  - C{RandomParse} searches edges in random order.
  - C{LongestParse} searches edges in decreasing order of their
    location's length.
  - C{BeamParse} limits the number of edges in the queue, and
    searches edges in decreasing order of their trees' inside
    probabilities.

"""

##//////////////////////////////////////////////////////
##  Bottom-Up PCFG Chart Parser
##//////////////////////////////////////////////////////

# [XX] This might not be implemented quite right -- it would be better
# to associate probabilities with child pointer lists.

from en.parser.nltk_lite.parse.chart import *
from en.parser.nltk_lite.parse.tree import ProbabilisticTree
from en.parser.nltk_lite.parse.cfg import Nonterminal

# Probabilistic edges
class ProbabilisticLeafEdge(LeafEdge):
    def prob(self): return 1.0

class ProbabilisticTreeEdge(TreeEdge):
    def __init__(self, prob, *args, **kwargs):
        self._prob = prob
        TreeEdge.__init__(self, *args, **kwargs)
    def prob(self): return self._prob
    def __cmp__(self, other):
        if self._prob != other.prob(): return -1
        return TreeEdge.__cmp__(self, other)
    def from_production(production, index, p):
        return ProbabilisticTreeEdge(p, (index, index), production.lhs(),
                                     production.rhs(), 0)
    from_production = staticmethod(from_production)

# Rules using probabilistic edges
class BottomUpInitRule(AbstractChartRule):
    NUM_EDGES=0
    def apply_iter(self, chart, grammar):
        for index in range(chart.num_leaves()):
            new_edge = ProbabilisticLeafEdge(chart.leaf(index), index)
            if chart.insert(new_edge, ()):
                yield new_edge

class BottomUpPredictRule(AbstractChartRule):
    NUM_EDGES=1
    def apply_iter(self, chart, grammar, edge):
        if edge.is_incomplete(): return
        for prod in grammar.productions():
            if edge.lhs() == prod.rhs()[0]:
                new_edge = ProbabilisticTreeEdge.from_production(prod, edge.start(), prod.prob())
                if chart.insert(new_edge, ()):
                    yield new_edge
                    
class FundamentalRule(AbstractChartRule):