Generated by Cython 0.26
Yellow lines hint at Python interaction.
Click on a line that starts with a "+" to see the C code that Cython generated for it.
Raw output: kbest.cpp
+001: """Extract the k-best derivations from a probabilistic parse forest.
__pyx_t_4 = PyDict_New(); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 1, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); if (PyDict_SetItem(__pyx_d, __pyx_n_s_test, __pyx_t_4) < 0) __PYX_ERR(0, 1, __pyx_L1_error) __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
002:
003: Implementation of Huang & Chiang (2005): Better k-best parsing.
004: http://www.cis.upenn.edu/~lhuang3/huang-iwpt-correct.pdf"""
005: from __future__ import print_function
+006: from operator import itemgetter
__pyx_t_4 = PyList_New(1); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 6, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); __Pyx_INCREF(__pyx_n_s_itemgetter); __Pyx_GIVEREF(__pyx_n_s_itemgetter); PyList_SET_ITEM(__pyx_t_4, 0, __pyx_n_s_itemgetter); __pyx_t_5 = __Pyx_Import(__pyx_n_s_operator, __pyx_t_4, 0); if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 6, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_5); __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0; __pyx_t_4 = __Pyx_ImportFrom(__pyx_t_5, __pyx_n_s_itemgetter); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 6, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); if (PyDict_SetItem(__pyx_d, __pyx_n_s_itemgetter, __pyx_t_4) < 0) __PYX_ERR(0, 6, __pyx_L1_error) __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0; __Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0;
+007: from .containers import Grammar
__pyx_t_5 = PyList_New(1); if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 7, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_5); __Pyx_INCREF(__pyx_n_s_Grammar); __Pyx_GIVEREF(__pyx_n_s_Grammar); PyList_SET_ITEM(__pyx_t_5, 0, __pyx_n_s_Grammar); __pyx_t_4 = __Pyx_Import(__pyx_n_s_containers, __pyx_t_5, 1); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 7, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); __Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0; __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
008:
009: cimport cython
010: from libcpp.string cimport string
011: from libc.stdio cimport sprintf
012: from libc.stdlib cimport abort
013: include "constants.pxi"
014:
+015: cdef RankedEdgeAgenda[Prob] getcandidates(Chart chart, ItemNo v, int k):
static RankedEdgeAgenda<Prob> __pyx_f_8discodop_5kbest_getcandidates(struct __pyx_obj_8discodop_10containers_Chart *__pyx_v_chart, ItemNo __pyx_v_v, int __pyx_v_k) {
RankedEdgeAgenda<Prob> __pyx_v_agenda;
std::vector<std::pair<RankedEdge,Prob> > __pyx_v_entries;
std::pair<RankedEdge,Prob> __pyx_v_entry;
RankedEdge __pyx_v_re;
Edge __pyx_v_e;
Prob __pyx_v_prob;
long __pyx_v_left;
long __pyx_v_right;
RankedEdgeAgenda<Prob> __pyx_r;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("getcandidates", 0);
/* … */
/* function exit code */
__pyx_L1_error:;
__Pyx_WriteUnraisable("discodop.kbest.getcandidates", __pyx_clineno, __pyx_lineno, __pyx_filename, 1, 0);
__Pyx_pretend_to_initialize(&__pyx_r);
__pyx_L0:;
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
016: """:returns: a heap with up to k candidate arcs starting from vertex v."""
017: # NB: the priority queue should either do a stable sort, or should
018: # sort on rank vector as well to have ties resolved in FIFO order;
019: # otherwise the sequence (0, 0) -> (1, 0) -> (1, 1) -> (0, 1) -> (1, 1)
020: # can occur (given that the first two have probability x and the latter
021: # three probability y), in which case insertion order should count.
022: # Otherwise (1, 1) ends up in chart.rankededges[v] after which (0, 1)
023: # generates it as a neighbor and puts it in cand[v] for a second time.
024: cdef RankedEdgeAgenda[Prob] agenda
025: cdef vector[pair[RankedEdge, Prob]] entries
026: cdef pair[RankedEdge, Prob] entry
027: cdef RankedEdge re
028: cdef Edge e
029: cdef Prob prob
030: # loop over edges
031: # compute viterbi prob from rule.prob + viterbi probs of children
+032: for e in chart.parseforest[v]:
__pyx_t_2 = &(__pyx_v_chart->parseforest[__pyx_v_v]);
__pyx_t_1 = __pyx_t_2->begin();
for (;;) {
if (!(__pyx_t_1 != __pyx_t_2->end())) break;
__pyx_t_3 = *__pyx_t_1;
++__pyx_t_1;
__pyx_v_e = __pyx_t_3;
/* … */
}
+033: if e.rule is NULL:
__pyx_t_4 = ((__pyx_v_e.rule == NULL) != 0);
if (__pyx_t_4) {
/* … */
goto __pyx_L5;
}
034: # there can only be one lexical edge for this combination of
035: # POS tag and terminal, use viterbi probability directly
+036: prob = chart.subtreeprob(v)
__pyx_v_prob = ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->subtreeprob(__pyx_v_chart, __pyx_v_v);
+037: left = right = -1
__pyx_v_left = -1L;
__pyx_v_right = -1L;
038: else:
+039: left = right = 0
/*else*/ {
__pyx_v_left = 0;
__pyx_v_right = 0;
+040: prob = e.rule.prob
__pyx_t_5 = __pyx_v_e.rule->prob;
__pyx_v_prob = __pyx_t_5;
+041: prob += chart.subtreeprob(chart._left(v, e))
__pyx_v_prob = (__pyx_v_prob + ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->subtreeprob(__pyx_v_chart, ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->_left(__pyx_v_chart, __pyx_v_v, __pyx_v_e)));
+042: if e.rule.rhs2: # unary rule?
__pyx_t_4 = (__pyx_v_e.rule->rhs2 != 0);
if (__pyx_t_4) {
/* … */
goto __pyx_L6;
}
+043: prob += chart.subtreeprob(chart._right(v, e))
__pyx_v_prob = (__pyx_v_prob + ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->subtreeprob(__pyx_v_chart, ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->_right(__pyx_v_chart, __pyx_v_v, __pyx_v_e)));
044: else:
+045: right = -1
/*else*/ {
__pyx_v_right = -1L;
}
__pyx_L6:;
}
__pyx_L5:;
+046: re = RankedEdge(v, e, left, right)
__pyx_v_re = RankedEdge(__pyx_v_v, __pyx_v_e, __pyx_v_left, __pyx_v_right);
+047: entry.first = re
__pyx_v_entry.first = __pyx_v_re;
+048: entry.second = prob
__pyx_v_entry.second = __pyx_v_prob;
+049: entries.push_back(entry)
try {
__pyx_v_entries.push_back(__pyx_v_entry);
} catch(...) {
__Pyx_CppExn2PyErr();
__PYX_ERR(0, 49, __pyx_L1_error)
}
050: # FIXME: can we guarantee that 'entries' does not have duplicates?
+051: agenda.kbest_entries(entries, k)
__pyx_v_agenda.kbest_entries(__pyx_v_entries, __pyx_v_k);
+052: return agenda
__pyx_r = __pyx_v_agenda; goto __pyx_L0;
053:
054:
+055: cdef lazykthbest(ItemNo v, int k, int k1, agendas_type& cand, Chart chart,
static PyObject *__pyx_f_8discodop_5kbest_lazykthbest(ItemNo __pyx_v_v, int __pyx_v_k, int __pyx_v_k1, __pyx_t_8discodop_5kbest_agendas_type &__pyx_v_cand, struct __pyx_obj_8discodop_10containers_Chart *__pyx_v_chart, RankedEdgeSet &__pyx_v_explored, int __pyx_v_depthlimit) {
std::pair<RankedEdge,Prob> __pyx_v_entry;
RankedEdge __pyx_v_ej;
RankedEdge __pyx_v_ej1;
int __pyx_v_ji;
int __pyx_v_inrankededges;
long __pyx_v_i;
ItemNo __pyx_v_ei;
PyObject *__pyx_r = NULL;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("lazykthbest", 0);
/* … */
/* function exit code */
__pyx_r = Py_None; __Pyx_INCREF(Py_None);
goto __pyx_L0;
__pyx_L1_error:;
__Pyx_XDECREF(__pyx_t_6);
__Pyx_AddTraceback("discodop.kbest.lazykthbest", __pyx_clineno, __pyx_lineno, __pyx_filename);
__pyx_r = 0;
__pyx_L0:;
__Pyx_XGIVEREF(__pyx_r);
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
056: RankedEdgeSet& explored, int depthlimit):
057: """"Explore up to *k*-best derivations headed by vertex *v*.
058:
059: :param k1: the global k, with ``k <= k1``
060: :param cand: contains a queue of edges to consider for each vertex
061: :param explored: a set of all edges already visited."""
062: cdef pair[RankedEdge, Prob] entry
063: cdef RankedEdge ej, ej1
064: cdef int ji
+065: cdef bint inrankededges = chart.rankededges[v].size() != 0
__pyx_v_inrankededges = ((__pyx_v_chart->rankededges[__pyx_v_v]).size() != 0);
066: # FIXME: cand could be a vector; but need to distinguish first visit from
067: # empty agenda.
068: # first visit of vertex v?
+069: if cand.find(v) == cand.end():
__pyx_t_1 = ((__pyx_v_cand.find(__pyx_v_v) == __pyx_v_cand.end()) != 0);
if (__pyx_t_1) {
/* … */
}
070: # initialize the heap
+071: cand[v] = getcandidates(chart, v, k1)
(__pyx_v_cand[__pyx_v_v]) = __pyx_f_8discodop_5kbest_getcandidates(__pyx_v_chart, __pyx_v_v, __pyx_v_k1);
+072: while not inrankededges or <int>chart.rankededges[v].size() < k:
while (1) {
__pyx_t_2 = ((!(__pyx_v_inrankededges != 0)) != 0);
if (!__pyx_t_2) {
} else {
__pyx_t_1 = __pyx_t_2;
goto __pyx_L6_bool_binop_done;
}
__pyx_t_2 = ((((int)(__pyx_v_chart->rankededges[__pyx_v_v]).size()) < __pyx_v_k) != 0);
__pyx_t_1 = __pyx_t_2;
__pyx_L6_bool_binop_done:;
if (!__pyx_t_1) break;
+073: inrankededges = inrankededges or chart.rankededges[v].size() != 0
__pyx_t_2 = (__pyx_v_inrankededges != 0);
if (!__pyx_t_2) {
} else {
__pyx_t_1 = __pyx_t_2;
goto __pyx_L8_bool_binop_done;
}
__pyx_t_2 = (((__pyx_v_chart->rankededges[__pyx_v_v]).size() != 0) != 0);
__pyx_t_1 = __pyx_t_2;
__pyx_L8_bool_binop_done:;
__pyx_v_inrankededges = __pyx_t_1;
+074: if inrankededges:
__pyx_t_1 = (__pyx_v_inrankededges != 0);
if (__pyx_t_1) {
/* … */
}
075: # last derivation
+076: entry = chart.rankededges[v][chart.rankededges[v].size() - 1]
__pyx_v_entry = ((__pyx_v_chart->rankededges[__pyx_v_v])[((__pyx_v_chart->rankededges[__pyx_v_v]).size() - 1)]);
+077: ej = entry.first
__pyx_t_3 = __pyx_v_entry.first;
__pyx_v_ej = __pyx_t_3;
078: # update the heap, adding the successors of last derivation
079: # start of inlined lazynext(v, ej, k1, cand, chart, explored)
+080: for i in range(2): # add the |e| neighbors
for (__pyx_t_4 = 0; __pyx_t_4 < 2; __pyx_t_4+=1) {
__pyx_v_i = __pyx_t_4;
+081: if i == 0 and ej.left >= 0:
__pyx_t_2 = ((__pyx_v_i == 0) != 0);
if (__pyx_t_2) {
} else {
__pyx_t_1 = __pyx_t_2;
goto __pyx_L14_bool_binop_done;
}
__pyx_t_2 = ((__pyx_v_ej.left >= 0) != 0);
__pyx_t_1 = __pyx_t_2;
__pyx_L14_bool_binop_done:;
if (__pyx_t_1) {
/* … */
goto __pyx_L13;
}
+082: ei = chart.left(ej)
__pyx_v_ei = ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->left(__pyx_v_chart, __pyx_v_ej);
+083: ej1 = RankedEdge(v, ej.edge, ej.left + 1, ej.right)
__pyx_v_ej1 = RankedEdge(__pyx_v_v, __pyx_v_ej.edge, (__pyx_v_ej.left + 1), __pyx_v_ej.right);
+084: elif i == 1 and ej.right >= 0:
__pyx_t_2 = ((__pyx_v_i == 1) != 0);
if (__pyx_t_2) {
} else {
__pyx_t_1 = __pyx_t_2;
goto __pyx_L16_bool_binop_done;
}
__pyx_t_2 = ((__pyx_v_ej.right >= 0) != 0);
__pyx_t_1 = __pyx_t_2;
__pyx_L16_bool_binop_done:;
if (__pyx_t_1) {
/* … */
goto __pyx_L13;
}
+085: ei = chart.right(ej)
__pyx_v_ei = ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->right(__pyx_v_chart, __pyx_v_ej);
+086: ej1 = RankedEdge(v, ej.edge, ej.left, ej.right + 1)
__pyx_v_ej1 = RankedEdge(__pyx_v_v, __pyx_v_ej.edge, __pyx_v_ej.left, (__pyx_v_ej.right + 1));
087: else:
+088: break
/*else*/ {
goto __pyx_L12_break;
}
__pyx_L13:;
+089: ji = ej1.left if i == 0 else ej1.right
if (((__pyx_v_i == 0) != 0)) {
__pyx_t_5 = __pyx_v_ej1.left;
} else {
__pyx_t_5 = __pyx_v_ej1.right;
}
__pyx_v_ji = __pyx_t_5;
+090: if depthlimit > 0:
__pyx_t_1 = ((__pyx_v_depthlimit > 0) != 0);
if (__pyx_t_1) {
/* … */
}
}
__pyx_L12_break:;
091: # recursively solve a subproblem
092: # NB: increment j[i] again, j is zero-based and k is not
+093: lazykthbest(ei, ji + 1, k1, cand, chart, explored,
__pyx_t_6 = __pyx_f_8discodop_5kbest_lazykthbest(__pyx_v_ei, (__pyx_v_ji + 1), __pyx_v_k1, __pyx_v_cand, __pyx_v_chart, __pyx_v_explored, (__pyx_v_depthlimit - 1)); if (unlikely(!__pyx_t_6)) __PYX_ERR(0, 93, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_6);
__Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0;
094: depthlimit - 1)
095: # if it exists and is not in heap yet
+096: if (chart.rankededges[ei].size() != 0
__pyx_t_2 = (((__pyx_v_chart->rankededges[__pyx_v_ei]).size() != 0) != 0);
if (__pyx_t_2) {
} else {
__pyx_t_1 = __pyx_t_2;
goto __pyx_L20_bool_binop_done;
}
/* … */
if (__pyx_t_1) {
/* … */
}
+097: and ji < <int>chart.rankededges[ei].size()
__pyx_t_2 = ((__pyx_v_ji < ((int)(__pyx_v_chart->rankededges[__pyx_v_ei]).size())) != 0);
if (__pyx_t_2) {
} else {
__pyx_t_1 = __pyx_t_2;
goto __pyx_L20_bool_binop_done;
}
+098: and explored.count(ej1) == 0):
__pyx_t_2 = ((__pyx_v_explored.count(__pyx_v_ej1) == 0) != 0);
__pyx_t_1 = __pyx_t_2;
__pyx_L20_bool_binop_done:;
099: # and cand[ej1.head]): gives duplicates
100: # add it to the heap
+101: cand[v].setitem(ej1, getprob(chart, v, ej1))
__pyx_t_7 = __pyx_f_8discodop_5kbest_getprob(__pyx_v_chart, __pyx_v_v, __pyx_v_ej1); if (unlikely(__pyx_t_7 == -1.0)) __PYX_ERR(0, 101, __pyx_L1_error)
(__pyx_v_cand[__pyx_v_v]).setitem(__pyx_v_ej1, __pyx_t_7);
+102: explored.insert(ej1)
__pyx_v_explored.insert(__pyx_v_ej1);
103: # end of lazynext
+104: if cand[v].empty():
__pyx_t_1 = ((__pyx_v_cand[__pyx_v_v]).empty() != 0);
if (__pyx_t_1) {
/* … */
}
+105: break
goto __pyx_L5_break;
106: # get the next best derivation and delete it from the heap
+107: entry = cand[v].pop()
__pyx_v_entry = (__pyx_v_cand[__pyx_v_v]).pop();
+108: chart.rankededges[v].push_back(entry)
try {
(__pyx_v_chart->rankededges[__pyx_v_v]).push_back(__pyx_v_entry);
} catch(...) {
__Pyx_CppExn2PyErr();
__PYX_ERR(0, 108, __pyx_L1_error)
}
}
__pyx_L5_break:;
109:
110:
+111: cdef inline Prob getprob(Chart chart, ItemNo v, RankedEdge& ej) except -1:
static CYTHON_INLINE Prob __pyx_f_8discodop_5kbest_getprob(struct __pyx_obj_8discodop_10containers_Chart *__pyx_v_chart, ItemNo __pyx_v_v, RankedEdge &__pyx_v_ej) {
Prob __pyx_v_prob;
ItemNo __pyx_v_ei;
Prob __pyx_r;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("getprob", 0);
/* … */
/* function exit code */
__pyx_L1_error:;
__Pyx_XDECREF(__pyx_t_3);
__Pyx_XDECREF(__pyx_t_4);
__Pyx_XDECREF(__pyx_t_5);
__Pyx_XDECREF(__pyx_t_6);
__Pyx_XDECREF(__pyx_t_7);
__Pyx_XDECREF(__pyx_t_8);
__Pyx_AddTraceback("discodop.kbest.getprob", __pyx_clineno, __pyx_lineno, __pyx_filename);
__pyx_r = -1.0;
__pyx_L0:;
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
112: """Get subtree probability of ``ej``.
113:
114: Try looking in ``chart.rankededges``, or else use viterbi probability."""
+115: cdef Prob prob = ej.edge.rule.prob
__pyx_t_1 = __pyx_v_ej.edge.rule->prob; __pyx_v_prob = __pyx_t_1;
+116: ei = chart.left(ej)
__pyx_v_ei = ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->left(__pyx_v_chart, __pyx_v_ej);
+117: if ej.left == 0:
__pyx_t_2 = ((__pyx_v_ej.left == 0) != 0);
if (__pyx_t_2) {
/* … */
goto __pyx_L3;
}
+118: prob += chart.subtreeprob(ei)
__pyx_v_prob = (__pyx_v_prob + ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->subtreeprob(__pyx_v_chart, __pyx_v_ei));
+119: elif chart.rankededges[ei].size():
__pyx_t_2 = ((__pyx_v_chart->rankededges[__pyx_v_ei]).size() != 0);
if (__pyx_t_2) {
/* … */
goto __pyx_L3;
}
+120: prob += chart.rankededges[ei][ej.left].second
__pyx_v_prob = (__pyx_v_prob + ((__pyx_v_chart->rankededges[__pyx_v_ei])[__pyx_v_ej.left]).second);
121: else:
+122: raise ValueError('non-zero rank vector %d not in explored '
/*else*/ {
/* … */
__pyx_t_5 = PyTuple_New(1); if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 122, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_5);
__Pyx_GIVEREF(__pyx_t_4);
PyTuple_SET_ITEM(__pyx_t_5, 0, __pyx_t_4);
__pyx_t_4 = 0;
__pyx_t_4 = __Pyx_PyObject_Call(__pyx_builtin_ValueError, __pyx_t_5, NULL); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 122, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_4);
__Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0;
__Pyx_Raise(__pyx_t_4, 0, 0, 0);
__Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
__PYX_ERR(0, 122, __pyx_L1_error)
}
__pyx_L3:;
+123: 'derivations for %s' % (ej.right, chart.itemstr(v)))
__pyx_t_3 = __Pyx_PyInt_From_int(__pyx_v_ej.right); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 123, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_3); __pyx_t_5 = __Pyx_PyObject_GetAttrStr(((PyObject *)__pyx_v_chart), __pyx_n_s_itemstr); if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 123, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_5); __pyx_t_6 = __Pyx_PyInt_From_uint32_t(__pyx_v_v); if (unlikely(!__pyx_t_6)) __PYX_ERR(0, 123, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_6); __pyx_t_7 = NULL; if (CYTHON_UNPACK_METHODS && likely(PyMethod_Check(__pyx_t_5))) { __pyx_t_7 = PyMethod_GET_SELF(__pyx_t_5); if (likely(__pyx_t_7)) { PyObject* function = PyMethod_GET_FUNCTION(__pyx_t_5); __Pyx_INCREF(__pyx_t_7); __Pyx_INCREF(function); __Pyx_DECREF_SET(__pyx_t_5, function); } } if (!__pyx_t_7) { __pyx_t_4 = __Pyx_PyObject_CallOneArg(__pyx_t_5, __pyx_t_6); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 123, __pyx_L1_error) __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0; __Pyx_GOTREF(__pyx_t_4); } else { #if CYTHON_FAST_PYCALL if (PyFunction_Check(__pyx_t_5)) { PyObject *__pyx_temp[2] = {__pyx_t_7, __pyx_t_6}; __pyx_t_4 = __Pyx_PyFunction_FastCall(__pyx_t_5, __pyx_temp+1-1, 1+1); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 123, __pyx_L1_error) __Pyx_XDECREF(__pyx_t_7); __pyx_t_7 = 0; __Pyx_GOTREF(__pyx_t_4); __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0; } else #endif #if CYTHON_FAST_PYCCALL if (__Pyx_PyFastCFunction_Check(__pyx_t_5)) { PyObject *__pyx_temp[2] = {__pyx_t_7, __pyx_t_6}; __pyx_t_4 = __Pyx_PyCFunction_FastCall(__pyx_t_5, __pyx_temp+1-1, 1+1); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 123, __pyx_L1_error) __Pyx_XDECREF(__pyx_t_7); __pyx_t_7 = 0; __Pyx_GOTREF(__pyx_t_4); __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0; } else #endif { __pyx_t_8 = PyTuple_New(1+1); if (unlikely(!__pyx_t_8)) __PYX_ERR(0, 123, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_8); __Pyx_GIVEREF(__pyx_t_7); PyTuple_SET_ITEM(__pyx_t_8, 0, __pyx_t_7); __pyx_t_7 = NULL; __Pyx_GIVEREF(__pyx_t_6); PyTuple_SET_ITEM(__pyx_t_8, 0+1, __pyx_t_6); __pyx_t_6 = 0; __pyx_t_4 = __Pyx_PyObject_Call(__pyx_t_5, __pyx_t_8, NULL); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 123, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); __Pyx_DECREF(__pyx_t_8); __pyx_t_8 = 0; } } __Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0; __pyx_t_5 = PyTuple_New(2); if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 123, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_5); __Pyx_GIVEREF(__pyx_t_3); PyTuple_SET_ITEM(__pyx_t_5, 0, __pyx_t_3); __Pyx_GIVEREF(__pyx_t_4); PyTuple_SET_ITEM(__pyx_t_5, 1, __pyx_t_4); __pyx_t_3 = 0; __pyx_t_4 = 0; __pyx_t_4 = PyUnicode_Format(__pyx_kp_u_non_zero_rank_vector_d_not_in_ex, __pyx_t_5); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 123, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); __Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0;
+124: if ej.right == -1:
__pyx_t_2 = ((__pyx_v_ej.right == -1L) != 0);
if (__pyx_t_2) {
/* … */
}
+125: return prob
__pyx_r = __pyx_v_prob;
goto __pyx_L0;
+126: ei = chart.right(ej)
__pyx_v_ei = ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->right(__pyx_v_chart, __pyx_v_ej);
+127: if ej.right == 0:
__pyx_t_2 = ((__pyx_v_ej.right == 0) != 0);
if (__pyx_t_2) {
/* … */
goto __pyx_L5;
}
+128: prob += chart.subtreeprob(ei)
__pyx_v_prob = (__pyx_v_prob + ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->subtreeprob(__pyx_v_chart, __pyx_v_ei));
+129: elif chart.rankededges[ei].size():
__pyx_t_2 = ((__pyx_v_chart->rankededges[__pyx_v_ei]).size() != 0);
if (__pyx_t_2) {
/* … */
goto __pyx_L5;
}
+130: prob += chart.rankededges[ei][ej.right].second
__pyx_v_prob = (__pyx_v_prob + ((__pyx_v_chart->rankededges[__pyx_v_ei])[__pyx_v_ej.right]).second);
131: else:
+132: raise ValueError('non-zero rank vector %d not in explored '
/*else*/ {
/* … */
__pyx_t_3 = PyTuple_New(1); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 132, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_3);
__Pyx_GIVEREF(__pyx_t_5);
PyTuple_SET_ITEM(__pyx_t_3, 0, __pyx_t_5);
__pyx_t_5 = 0;
__pyx_t_5 = __Pyx_PyObject_Call(__pyx_builtin_ValueError, __pyx_t_3, NULL); if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 132, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_5);
__Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
__Pyx_Raise(__pyx_t_5, 0, 0, 0);
__Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0;
__PYX_ERR(0, 132, __pyx_L1_error)
}
__pyx_L5:;
+133: 'derivations for %s' % (ej.right, chart.itemstr(v)))
__pyx_t_4 = __Pyx_PyInt_From_int(__pyx_v_ej.right); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 133, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); __pyx_t_3 = __Pyx_PyObject_GetAttrStr(((PyObject *)__pyx_v_chart), __pyx_n_s_itemstr); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 133, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_3); __pyx_t_8 = __Pyx_PyInt_From_uint32_t(__pyx_v_v); if (unlikely(!__pyx_t_8)) __PYX_ERR(0, 133, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_8); __pyx_t_6 = NULL; if (CYTHON_UNPACK_METHODS && likely(PyMethod_Check(__pyx_t_3))) { __pyx_t_6 = PyMethod_GET_SELF(__pyx_t_3); if (likely(__pyx_t_6)) { PyObject* function = PyMethod_GET_FUNCTION(__pyx_t_3); __Pyx_INCREF(__pyx_t_6); __Pyx_INCREF(function); __Pyx_DECREF_SET(__pyx_t_3, function); } } if (!__pyx_t_6) { __pyx_t_5 = __Pyx_PyObject_CallOneArg(__pyx_t_3, __pyx_t_8); if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 133, __pyx_L1_error) __Pyx_DECREF(__pyx_t_8); __pyx_t_8 = 0; __Pyx_GOTREF(__pyx_t_5); } else { #if CYTHON_FAST_PYCALL if (PyFunction_Check(__pyx_t_3)) { PyObject *__pyx_temp[2] = {__pyx_t_6, __pyx_t_8}; __pyx_t_5 = __Pyx_PyFunction_FastCall(__pyx_t_3, __pyx_temp+1-1, 1+1); if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 133, __pyx_L1_error) __Pyx_XDECREF(__pyx_t_6); __pyx_t_6 = 0; __Pyx_GOTREF(__pyx_t_5); __Pyx_DECREF(__pyx_t_8); __pyx_t_8 = 0; } else #endif #if CYTHON_FAST_PYCCALL if (__Pyx_PyFastCFunction_Check(__pyx_t_3)) { PyObject *__pyx_temp[2] = {__pyx_t_6, __pyx_t_8}; __pyx_t_5 = __Pyx_PyCFunction_FastCall(__pyx_t_3, __pyx_temp+1-1, 1+1); if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 133, __pyx_L1_error) __Pyx_XDECREF(__pyx_t_6); __pyx_t_6 = 0; __Pyx_GOTREF(__pyx_t_5); __Pyx_DECREF(__pyx_t_8); __pyx_t_8 = 0; } else #endif { __pyx_t_7 = PyTuple_New(1+1); if (unlikely(!__pyx_t_7)) __PYX_ERR(0, 133, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_7); __Pyx_GIVEREF(__pyx_t_6); PyTuple_SET_ITEM(__pyx_t_7, 0, __pyx_t_6); __pyx_t_6 = NULL; __Pyx_GIVEREF(__pyx_t_8); PyTuple_SET_ITEM(__pyx_t_7, 0+1, __pyx_t_8); __pyx_t_8 = 0; __pyx_t_5 = __Pyx_PyObject_Call(__pyx_t_3, __pyx_t_7, NULL); if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 133, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_5); __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0; } } __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; __pyx_t_3 = PyTuple_New(2); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 133, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_3); __Pyx_GIVEREF(__pyx_t_4); PyTuple_SET_ITEM(__pyx_t_3, 0, __pyx_t_4); __Pyx_GIVEREF(__pyx_t_5); PyTuple_SET_ITEM(__pyx_t_3, 1, __pyx_t_5); __pyx_t_4 = 0; __pyx_t_5 = 0; __pyx_t_5 = PyUnicode_Format(__pyx_kp_u_non_zero_rank_vector_d_not_in_ex, __pyx_t_3); if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 133, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_5); __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
+134: return prob
__pyx_r = __pyx_v_prob; goto __pyx_L0;
135:
136:
+137: cdef int explorederivation(ItemNo v, RankedEdge& ej, Chart chart,
static int __pyx_f_8discodop_5kbest_explorederivation(ItemNo __pyx_v_v, RankedEdge &__pyx_v_ej, struct __pyx_obj_8discodop_10containers_Chart *__pyx_v_chart, RankedEdgeSet &__pyx_v_explored, int __pyx_v_depthlimit) {
std::pair<RankedEdge,Prob> __pyx_v_entry;
RankedEdgeAgenda<Prob> __pyx_v_tmp;
ItemNo __pyx_v_leftitem;
ItemNo __pyx_v_rightitem;
int __pyx_r;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("explorederivation", 0);
/* … */
/* function exit code */
__pyx_L1_error:;
__Pyx_XDECREF(__pyx_t_2);
__Pyx_XDECREF(__pyx_t_3);
__Pyx_XDECREF(__pyx_t_4);
__Pyx_XDECREF(__pyx_t_5);
__Pyx_XDECREF(__pyx_t_6);
__Pyx_XDECREF(__pyx_t_7);
__Pyx_AddTraceback("discodop.kbest.explorederivation", __pyx_clineno, __pyx_lineno, __pyx_filename);
__pyx_r = -2;
__pyx_L0:;
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
138: RankedEdgeSet& explored, int depthlimit) except -2:
139: """Traverse derivation to ensure all 1-best RankedEdges are present.
140:
141: :returns: True when ``ej`` is a valid, complete derivation."""
142: cdef pair[RankedEdge, Prob] entry
143: cdef RankedEdgeAgenda[Prob] tmp
+144: if depthlimit <= 0: # to prevent cycles
__pyx_t_1 = ((__pyx_v_depthlimit <= 0) != 0);
if (__pyx_t_1) {
/* … */
}
+145: return False
__pyx_r = 0;
goto __pyx_L0;
+146: if ej.edge.rule is NULL:
__pyx_t_1 = ((__pyx_v_ej.edge.rule == NULL) != 0);
if (__pyx_t_1) {
/* … */
}
+147: return True
__pyx_r = 1;
goto __pyx_L0;
+148: if ej.left != -1:
__pyx_t_1 = ((__pyx_v_ej.left != -1L) != 0);
if (__pyx_t_1) {
/* … */
}
+149: leftitem = chart.left(ej)
__pyx_v_leftitem = ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->left(__pyx_v_chart, __pyx_v_ej);
+150: if not chart.rankededges[leftitem].size():
__pyx_t_1 = ((!((__pyx_v_chart->rankededges[__pyx_v_leftitem]).size() != 0)) != 0);
if (__pyx_t_1) {
/* … */
}
+151: assert ej.left == 0, '%d-best edge for %s of left item missing' % (
#ifndef CYTHON_WITHOUT_ASSERTIONS
if (unlikely(!Py_OptimizeFlag)) {
if (unlikely(!((__pyx_v_ej.left == 0) != 0))) {
/* … */
__pyx_t_3 = PyUnicode_Format(__pyx_kp_u_d_best_edge_for_s_of_left_item, __pyx_t_4); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 151, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_3);
__Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
PyErr_SetObject(PyExc_AssertionError, __pyx_t_3);
__Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;
__PYX_ERR(0, 151, __pyx_L1_error)
}
}
#endif
+152: ej.left, chart.itemstr(v))
__pyx_t_2 = __Pyx_PyInt_From_int(__pyx_v_ej.left); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 152, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_2); __pyx_t_4 = __Pyx_PyObject_GetAttrStr(((PyObject *)__pyx_v_chart), __pyx_n_s_itemstr); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 152, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); __pyx_t_5 = __Pyx_PyInt_From_uint32_t(__pyx_v_v); if (unlikely(!__pyx_t_5)) __PYX_ERR(0, 152, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_5); __pyx_t_6 = NULL; if (CYTHON_UNPACK_METHODS && likely(PyMethod_Check(__pyx_t_4))) { __pyx_t_6 = PyMethod_GET_SELF(__pyx_t_4); if (likely(__pyx_t_6)) { PyObject* function = PyMethod_GET_FUNCTION(__pyx_t_4); __Pyx_INCREF(__pyx_t_6); __Pyx_INCREF(function); __Pyx_DECREF_SET(__pyx_t_4, function); } } if (!__pyx_t_6) { __pyx_t_3 = __Pyx_PyObject_CallOneArg(__pyx_t_4, __pyx_t_5); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 152, __pyx_L1_error) __Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0; __Pyx_GOTREF(__pyx_t_3); } else { #if CYTHON_FAST_PYCALL if (PyFunction_Check(__pyx_t_4)) { PyObject *__pyx_temp[2] = {__pyx_t_6, __pyx_t_5}; __pyx_t_3 = __Pyx_PyFunction_FastCall(__pyx_t_4, __pyx_temp+1-1, 1+1); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 152, __pyx_L1_error) __Pyx_XDECREF(__pyx_t_6); __pyx_t_6 = 0; __Pyx_GOTREF(__pyx_t_3); __Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0; } else #endif #if CYTHON_FAST_PYCCALL if (__Pyx_PyFastCFunction_Check(__pyx_t_4)) { PyObject *__pyx_temp[2] = {__pyx_t_6, __pyx_t_5}; __pyx_t_3 = __Pyx_PyCFunction_FastCall(__pyx_t_4, __pyx_temp+1-1, 1+1); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 152, __pyx_L1_error) __Pyx_XDECREF(__pyx_t_6); __pyx_t_6 = 0; __Pyx_GOTREF(__pyx_t_3); __Pyx_DECREF(__pyx_t_5); __pyx_t_5 = 0; } else #endif { __pyx_t_7 = PyTuple_New(1+1); if (unlikely(!__pyx_t_7)) __PYX_ERR(0, 152, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_7); __Pyx_GIVEREF(__pyx_t_6); PyTuple_SET_ITEM(__pyx_t_7, 0, __pyx_t_6); __pyx_t_6 = NULL; __Pyx_GIVEREF(__pyx_t_5); PyTuple_SET_ITEM(__pyx_t_7, 0+1, __pyx_t_5); __pyx_t_5 = 0; __pyx_t_3 = __Pyx_PyObject_Call(__pyx_t_4, __pyx_t_7, NULL); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 152, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_3); __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0; } } __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0; __pyx_t_4 = PyTuple_New(2); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 152, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); __Pyx_GIVEREF(__pyx_t_2); PyTuple_SET_ITEM(__pyx_t_4, 0, __pyx_t_2); __Pyx_GIVEREF(__pyx_t_3); PyTuple_SET_ITEM(__pyx_t_4, 1, __pyx_t_3); __pyx_t_2 = 0; __pyx_t_3 = 0;
+153: tmp = getcandidates(chart, leftitem, 1)
__pyx_v_tmp = __pyx_f_8discodop_5kbest_getcandidates(__pyx_v_chart, __pyx_v_leftitem, 1);
+154: if tmp.size() < 1:
__pyx_t_1 = ((__pyx_v_tmp.size() < 1) != 0);
if (__pyx_t_1) {
/* … */
}
+155: abort()
abort();
+156: entry = tmp.pop()
__pyx_v_entry = __pyx_v_tmp.pop();
+157: chart.rankededges[leftitem].push_back(entry)
try {
(__pyx_v_chart->rankededges[__pyx_v_leftitem]).push_back(__pyx_v_entry);
} catch(...) {
__Pyx_CppExn2PyErr();
__PYX_ERR(0, 157, __pyx_L1_error)
}
+158: explored.insert(entry.first)
__pyx_v_explored.insert(__pyx_v_entry.first);
+159: if not explorederivation(leftitem,
__pyx_t_8 = __pyx_f_8discodop_5kbest_explorederivation(__pyx_v_leftitem, ((__pyx_v_chart->rankededges[__pyx_v_leftitem])[__pyx_v_ej.left]).first, __pyx_v_chart, __pyx_v_explored, (__pyx_v_depthlimit - 1)); if (unlikely(__pyx_t_8 == -2)) __PYX_ERR(0, 159, __pyx_L1_error)
__pyx_t_1 = ((!(__pyx_t_8 != 0)) != 0);
if (__pyx_t_1) {
/* … */
}
160: chart.rankededges[leftitem][ej.left].first,
161: chart, explored, depthlimit - 1):
+162: return False
__pyx_r = 0;
goto __pyx_L0;
+163: if ej.right != -1:
__pyx_t_1 = ((__pyx_v_ej.right != -1L) != 0);
if (__pyx_t_1) {
/* … */
}
+164: rightitem = chart.right(ej)
__pyx_v_rightitem = ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->right(__pyx_v_chart, __pyx_v_ej);
+165: if not chart.rankededges[rightitem].size():
__pyx_t_1 = ((!((__pyx_v_chart->rankededges[__pyx_v_rightitem]).size() != 0)) != 0);
if (__pyx_t_1) {
/* … */
}
+166: assert ej.right == 0, (('%d-best edge for right child '
#ifndef CYTHON_WITHOUT_ASSERTIONS
if (unlikely(!Py_OptimizeFlag)) {
if (unlikely(!((__pyx_v_ej.right == 0) != 0))) {
+167: 'of %s missing') % (ej.right, chart.itemstr(v)))
__pyx_t_3 = __Pyx_PyInt_From_int(__pyx_v_ej.right); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 167, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_3); __pyx_t_2 = __Pyx_PyObject_GetAttrStr(((PyObject *)__pyx_v_chart), __pyx_n_s_itemstr); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 167, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_2); __pyx_t_7 = __Pyx_PyInt_From_uint32_t(__pyx_v_v); if (unlikely(!__pyx_t_7)) __PYX_ERR(0, 167, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_7); __pyx_t_5 = NULL; if (CYTHON_UNPACK_METHODS && likely(PyMethod_Check(__pyx_t_2))) { __pyx_t_5 = PyMethod_GET_SELF(__pyx_t_2); if (likely(__pyx_t_5)) { PyObject* function = PyMethod_GET_FUNCTION(__pyx_t_2); __Pyx_INCREF(__pyx_t_5); __Pyx_INCREF(function); __Pyx_DECREF_SET(__pyx_t_2, function); } } if (!__pyx_t_5) { __pyx_t_4 = __Pyx_PyObject_CallOneArg(__pyx_t_2, __pyx_t_7); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 167, __pyx_L1_error) __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0; __Pyx_GOTREF(__pyx_t_4); } else { #if CYTHON_FAST_PYCALL if (PyFunction_Check(__pyx_t_2)) { PyObject *__pyx_temp[2] = {__pyx_t_5, __pyx_t_7}; __pyx_t_4 = __Pyx_PyFunction_FastCall(__pyx_t_2, __pyx_temp+1-1, 1+1); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 167, __pyx_L1_error) __Pyx_XDECREF(__pyx_t_5); __pyx_t_5 = 0; __Pyx_GOTREF(__pyx_t_4); __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0; } else #endif #if CYTHON_FAST_PYCCALL if (__Pyx_PyFastCFunction_Check(__pyx_t_2)) { PyObject *__pyx_temp[2] = {__pyx_t_5, __pyx_t_7}; __pyx_t_4 = __Pyx_PyCFunction_FastCall(__pyx_t_2, __pyx_temp+1-1, 1+1); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 167, __pyx_L1_error) __Pyx_XDECREF(__pyx_t_5); __pyx_t_5 = 0; __Pyx_GOTREF(__pyx_t_4); __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0; } else #endif { __pyx_t_6 = PyTuple_New(1+1); if (unlikely(!__pyx_t_6)) __PYX_ERR(0, 167, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_6); __Pyx_GIVEREF(__pyx_t_5); PyTuple_SET_ITEM(__pyx_t_6, 0, __pyx_t_5); __pyx_t_5 = NULL; __Pyx_GIVEREF(__pyx_t_7); PyTuple_SET_ITEM(__pyx_t_6, 0+1, __pyx_t_7); __pyx_t_7 = 0; __pyx_t_4 = __Pyx_PyObject_Call(__pyx_t_2, __pyx_t_6, NULL); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 167, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); __Pyx_DECREF(__pyx_t_6); __pyx_t_6 = 0; } } __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; __pyx_t_2 = PyTuple_New(2); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 167, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_2); __Pyx_GIVEREF(__pyx_t_3); PyTuple_SET_ITEM(__pyx_t_2, 0, __pyx_t_3); __Pyx_GIVEREF(__pyx_t_4); PyTuple_SET_ITEM(__pyx_t_2, 1, __pyx_t_4); __pyx_t_3 = 0; __pyx_t_4 = 0; __pyx_t_4 = PyUnicode_Format(__pyx_kp_u_d_best_edge_for_right_child_of, __pyx_t_2); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 167, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; PyErr_SetObject(PyExc_AssertionError, __pyx_t_4); __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0; __PYX_ERR(0, 166, __pyx_L1_error) } } #endif
+168: tmp = getcandidates(chart, rightitem, 1)
__pyx_v_tmp = __pyx_f_8discodop_5kbest_getcandidates(__pyx_v_chart, __pyx_v_rightitem, 1);
+169: if tmp.size() < 1:
__pyx_t_1 = ((__pyx_v_tmp.size() < 1) != 0);
if (__pyx_t_1) {
/* … */
}
+170: abort()
abort();
+171: entry = tmp.pop()
__pyx_v_entry = __pyx_v_tmp.pop();
+172: chart.rankededges[rightitem].push_back(entry)
try {
(__pyx_v_chart->rankededges[__pyx_v_rightitem]).push_back(__pyx_v_entry);
} catch(...) {
__Pyx_CppExn2PyErr();
__PYX_ERR(0, 172, __pyx_L1_error)
}
+173: explored.insert(entry.first)
__pyx_v_explored.insert(__pyx_v_entry.first);
+174: return explorederivation(rightitem,
__pyx_t_8 = __pyx_f_8discodop_5kbest_explorederivation(__pyx_v_rightitem, ((__pyx_v_chart->rankededges[__pyx_v_rightitem])[__pyx_v_ej.right]).first, __pyx_v_chart, __pyx_v_explored, (__pyx_v_depthlimit - 1)); if (unlikely(__pyx_t_8 == -2)) __PYX_ERR(0, 174, __pyx_L1_error)
__pyx_r = __pyx_t_8;
goto __pyx_L0;
175: chart.rankededges[rightitem][ej.right].first,
176: chart, explored, depthlimit - 1)
+177: return True
__pyx_r = 1; goto __pyx_L0;
178:
179:
+180: cdef inline _getderiv(string &result, ItemNo v, RankedEdge& ej, Chart chart):
static CYTHON_INLINE PyObject *__pyx_f_8discodop_5kbest__getderiv(std::string &__pyx_v_result, ItemNo __pyx_v_v, RankedEdge &__pyx_v_ej, struct __pyx_obj_8discodop_10containers_Chart *__pyx_v_chart) {
RankedEdge __pyx_v_rankededge;
Label __pyx_v_label;
char __pyx_v_buf[10];
int __pyx_v_retval;
ItemNo __pyx_v_item;
PyObject *__pyx_r = NULL;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("_getderiv", 0);
/* … */
/* function exit code */
__pyx_r = Py_None; __Pyx_INCREF(Py_None);
goto __pyx_L0;
__pyx_L1_error:;
__Pyx_XDECREF(__pyx_t_3);
__Pyx_XDECREF(__pyx_t_4);
__Pyx_AddTraceback("discodop.kbest._getderiv", __pyx_clineno, __pyx_lineno, __pyx_filename);
__pyx_r = 0;
__pyx_L0:;
__Pyx_XGIVEREF(__pyx_r);
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
181: """Auxiliary function for ``getderiv()``.
182:
183: :param result: provide an empty list for the initial call."""
184: cdef RankedEdge rankededge
+185: cdef Label label = chart.label(v)
__pyx_v_label = ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->label(__pyx_v_chart, __pyx_v_v);
186: cdef char buf[10]
187: cdef int retval
+188: result.append(b'(')
__pyx_v_result.append(((char *)"("));
+189: result.append(chart.grammar.tolabel.ob[label])
__pyx_v_result.append((__pyx_v_chart->grammar->tolabel->ob[__pyx_v_label]));
+190: if ej.edge.rule is NULL: # lexical rule, left child is terminal
__pyx_t_1 = ((__pyx_v_ej.edge.rule == NULL) != 0);
if (__pyx_t_1) {
/* … */
goto __pyx_L3;
}
191: # C++ way to convert int to string requires streams, C++11, or boost
+192: retval = sprintf(buf, ' %d)', chart.lexidx(ej.edge))
__pyx_t_2 = ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->lexidx(__pyx_v_chart, __pyx_v_ej.edge); if (unlikely(__pyx_t_2 == -1)) __PYX_ERR(0, 192, __pyx_L1_error)
__pyx_v_retval = sprintf(__pyx_v_buf, ((char const *)" %d)"), __pyx_t_2);
+193: if retval <= 0:
__pyx_t_1 = ((__pyx_v_retval <= 0) != 0);
if (__pyx_t_1) {
/* … */
}
+194: raise ValueError('sprintf error; return value %d' % retval)
__pyx_t_3 = __Pyx_PyInt_From_int(__pyx_v_retval); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 194, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_3); __pyx_t_4 = PyUnicode_Format(__pyx_kp_u_sprintf_error_return_value_d, __pyx_t_3); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 194, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; __pyx_t_3 = PyTuple_New(1); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 194, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_3); __Pyx_GIVEREF(__pyx_t_4); PyTuple_SET_ITEM(__pyx_t_3, 0, __pyx_t_4); __pyx_t_4 = 0; __pyx_t_4 = __Pyx_PyObject_Call(__pyx_builtin_ValueError, __pyx_t_3, NULL); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 194, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; __Pyx_Raise(__pyx_t_4, 0, 0, 0); __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0; __PYX_ERR(0, 194, __pyx_L1_error)
+195: result.append(buf)
__pyx_v_result.append(__pyx_v_buf);
196: else:
+197: result.append(b' ')
/*else*/ {
__pyx_v_result.append(((char *)" "));
+198: item = chart.left(ej)
__pyx_v_item = ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->left(__pyx_v_chart, __pyx_v_ej);
+199: rankededge = chart.rankededges[item][ej.left].first
__pyx_t_5 = ((__pyx_v_chart->rankededges[__pyx_v_item])[__pyx_v_ej.left]).first;
__pyx_v_rankededge = __pyx_t_5;
+200: _getderiv(result, item, rankededge, chart)
__pyx_t_4 = __pyx_f_8discodop_5kbest__getderiv(__pyx_v_result, __pyx_v_item, __pyx_v_rankededge, __pyx_v_chart); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 200, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_4);
__Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
+201: if ej.right != -1:
__pyx_t_1 = ((__pyx_v_ej.right != -1L) != 0);
if (__pyx_t_1) {
/* … */
}
+202: item = chart.right(ej)
__pyx_v_item = ((struct __pyx_vtabstruct_8discodop_10containers_Chart *)__pyx_v_chart->__pyx_vtab)->right(__pyx_v_chart, __pyx_v_ej);
+203: result.append(b' ')
__pyx_v_result.append(((char *)" "));
+204: rankededge = chart.rankededges[item][ej.right].first
__pyx_t_5 = ((__pyx_v_chart->rankededges[__pyx_v_item])[__pyx_v_ej.right]).first;
__pyx_v_rankededge = __pyx_t_5;
+205: _getderiv(result, item, rankededge, chart)
__pyx_t_4 = __pyx_f_8discodop_5kbest__getderiv(__pyx_v_result, __pyx_v_item, __pyx_v_rankededge, __pyx_v_chart); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 205, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_4);
__Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
+206: result.append(b')')
__pyx_v_result.append(((char *)")")); } __pyx_L3:;
207:
208:
+209: cdef string getderiv(ItemNo v, RankedEdge ej, Chart chart):
static std::string __pyx_f_8discodop_5kbest_getderiv(ItemNo __pyx_v_v, RankedEdge __pyx_v_ej, struct __pyx_obj_8discodop_10containers_Chart *__pyx_v_chart) {
std::string __pyx_v_result;
std::string __pyx_r;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("getderiv", 0);
/* … */
/* function exit code */
__pyx_L1_error:;
__Pyx_XDECREF(__pyx_t_1);
__Pyx_WriteUnraisable("discodop.kbest.getderiv", __pyx_clineno, __pyx_lineno, __pyx_filename, 1, 0);
__Pyx_pretend_to_initialize(&__pyx_r);
__pyx_L0:;
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
210: """Convert a RankedEdge to a string with a tree in bracket notation.
211:
212: A RankedEdge consists of an edge and a rank tuple: ``(e, j)`` notation
213: ('derivation with backpointers'). For example, given an edge based on the
214: rule ``S => NP VP`` and the tuple ``(2, 1)``, this identifies a derivation
215: headed by S and having the 2nd best NP and the 1st best VP as children."""
216: cdef string result
+217: _getderiv(result, v, ej, chart)
__pyx_t_1 = __pyx_f_8discodop_5kbest__getderiv(__pyx_v_result, __pyx_v_v, __pyx_v_ej, __pyx_v_chart); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 217, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_1); __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
+218: return result # result.decode('utf8')
__pyx_r = __pyx_v_result; goto __pyx_L0;
219:
220:
+221: def lazykbest(Chart chart, int k, bint derivs=True):
/* Python wrapper */
static PyObject *__pyx_pw_8discodop_5kbest_1lazykbest(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/
static char __pyx_doc_8discodop_5kbest_lazykbest[] = "lazykbest(Chart chart, int k, bool derivs=True)\nWrapper function to run ``lazykthbest``.\n\n\tProduces the ranked chart, as well as derivations as strings (when\n\t``derivs`` is True). ``chart.parseforest`` should be a monotone hypergraph;\n\tshould be acyclic unless probabilities resolve the cycles (maybe nonzero\n\tweights for unary productions are sufficient?).\n\n\t:param k: the number of derivations to enumerate.";
static PyMethodDef __pyx_mdef_8discodop_5kbest_1lazykbest = {"lazykbest", (PyCFunction)__pyx_pw_8discodop_5kbest_1lazykbest, METH_VARARGS|METH_KEYWORDS, __pyx_doc_8discodop_5kbest_lazykbest};
static PyObject *__pyx_pw_8discodop_5kbest_1lazykbest(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
struct __pyx_obj_8discodop_10containers_Chart *__pyx_v_chart = 0;
int __pyx_v_k;
int __pyx_v_derivs;
PyObject *__pyx_r = 0;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("lazykbest (wrapper)", 0);
{
static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_chart,&__pyx_n_s_k,&__pyx_n_s_derivs,0};
PyObject* values[3] = {0,0,0};
if (unlikely(__pyx_kwds)) {
Py_ssize_t kw_args;
const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);
switch (pos_args) {
case 3: values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
CYTHON_FALLTHROUGH;
case 2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
CYTHON_FALLTHROUGH;
case 1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
CYTHON_FALLTHROUGH;
case 0: break;
default: goto __pyx_L5_argtuple_error;
}
kw_args = PyDict_Size(__pyx_kwds);
switch (pos_args) {
case 0:
if (likely((values[0] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_chart)) != 0)) kw_args--;
else goto __pyx_L5_argtuple_error;
CYTHON_FALLTHROUGH;
case 1:
if (likely((values[1] = PyDict_GetItem(__pyx_kwds, __pyx_n_s_k)) != 0)) kw_args--;
else {
__Pyx_RaiseArgtupleInvalid("lazykbest", 0, 2, 3, 1); __PYX_ERR(0, 221, __pyx_L3_error)
}
CYTHON_FALLTHROUGH;
case 2:
if (kw_args > 0) {
PyObject* value = PyDict_GetItem(__pyx_kwds, __pyx_n_s_derivs);
if (value) { values[2] = value; kw_args--; }
}
}
if (unlikely(kw_args > 0)) {
if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, "lazykbest") < 0)) __PYX_ERR(0, 221, __pyx_L3_error)
}
} else {
switch (PyTuple_GET_SIZE(__pyx_args)) {
case 3: values[2] = PyTuple_GET_ITEM(__pyx_args, 2);
CYTHON_FALLTHROUGH;
case 2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);
values[0] = PyTuple_GET_ITEM(__pyx_args, 0);
break;
default: goto __pyx_L5_argtuple_error;
}
}
__pyx_v_chart = ((struct __pyx_obj_8discodop_10containers_Chart *)values[0]);
__pyx_v_k = __Pyx_PyInt_As_int(values[1]); if (unlikely((__pyx_v_k == (int)-1) && PyErr_Occurred())) __PYX_ERR(0, 221, __pyx_L3_error)
if (values[2]) {
__pyx_v_derivs = __Pyx_PyObject_IsTrue(values[2]); if (unlikely((__pyx_v_derivs == (int)-1) && PyErr_Occurred())) __PYX_ERR(0, 221, __pyx_L3_error)
} else {
__pyx_v_derivs = ((int)1);
}
}
goto __pyx_L4_argument_unpacking_done;
__pyx_L5_argtuple_error:;
__Pyx_RaiseArgtupleInvalid("lazykbest", 0, 2, 3, PyTuple_GET_SIZE(__pyx_args)); __PYX_ERR(0, 221, __pyx_L3_error)
__pyx_L3_error:;
__Pyx_AddTraceback("discodop.kbest.lazykbest", __pyx_clineno, __pyx_lineno, __pyx_filename);
__Pyx_RefNannyFinishContext();
return NULL;
__pyx_L4_argument_unpacking_done:;
if (unlikely(!__Pyx_ArgTypeTest(((PyObject *)__pyx_v_chart), __pyx_ptype_8discodop_10containers_Chart, 1, "chart", 0))) __PYX_ERR(0, 221, __pyx_L1_error)
__pyx_r = __pyx_pf_8discodop_5kbest_lazykbest(__pyx_self, __pyx_v_chart, __pyx_v_k, __pyx_v_derivs);
/* function exit code */
goto __pyx_L0;
__pyx_L1_error:;
__pyx_r = NULL;
__pyx_L0:;
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
static PyObject *__pyx_pf_8discodop_5kbest_lazykbest(CYTHON_UNUSED PyObject *__pyx_self, struct __pyx_obj_8discodop_10containers_Chart *__pyx_v_chart, int __pyx_v_k, int __pyx_v_derivs) {
__pyx_t_8discodop_5kbest_agendas_type __pyx_v_cand;
RankedEdgeSet __pyx_v_explored;
std::pair<RankedEdge,Prob> __pyx_v_entry;
std::vector<std::pair<RankedEdge,Prob> > __pyx_v_tmp;
ItemNo __pyx_v_root;
int __pyx_v_n;
PyObject *__pyx_r = NULL;
__Pyx_RefNannyDeclarations
__Pyx_RefNannySetupContext("lazykbest", 0);
/* … */
/* function exit code */
__pyx_L1_error:;
__Pyx_XDECREF(__pyx_t_1);
__Pyx_XDECREF(__pyx_t_2);
__Pyx_XDECREF(__pyx_t_3);
__Pyx_XDECREF(__pyx_t_10);
__Pyx_AddTraceback("discodop.kbest.lazykbest", __pyx_clineno, __pyx_lineno, __pyx_filename);
__pyx_r = NULL;
__pyx_L0:;
__Pyx_XGIVEREF(__pyx_r);
__Pyx_RefNannyFinishContext();
return __pyx_r;
}
/* … */
__pyx_tuple__3 = PyTuple_Pack(9, __pyx_n_s_chart, __pyx_n_s_k, __pyx_n_s_derivs, __pyx_n_s_cand, __pyx_n_s_explored, __pyx_n_s_entry, __pyx_n_s_tmp, __pyx_n_s_root, __pyx_n_s_n); if (unlikely(!__pyx_tuple__3)) __PYX_ERR(0, 221, __pyx_L1_error)
__Pyx_GOTREF(__pyx_tuple__3);
__Pyx_GIVEREF(__pyx_tuple__3);
/* … */
__pyx_t_4 = PyCFunction_NewEx(&__pyx_mdef_8discodop_5kbest_1lazykbest, NULL, __pyx_n_s_discodop_kbest); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 221, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_4);
if (PyDict_SetItem(__pyx_d, __pyx_n_s_lazykbest, __pyx_t_4) < 0) __PYX_ERR(0, 221, __pyx_L1_error)
__Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;
222: """Wrapper function to run ``lazykthbest``.
223:
224: Produces the ranked chart, as well as derivations as strings (when
225: ``derivs`` is True). ``chart.parseforest`` should be a monotone hypergraph;
226: should be acyclic unless probabilities resolve the cycles (maybe nonzero
227: weights for unary productions are sufficient?).
228:
229: :param k: the number of derivations to enumerate."""
230: cdef agendas_type cand
231: cdef RankedEdgeSet explored
232: cdef pair[RankedEdge, Prob] entry
233: cdef vector[pair[RankedEdge, Prob]] tmp
+234: cdef ItemNo root = chart.root()
__pyx_t_2 = __Pyx_PyObject_GetAttrStr(((PyObject *)__pyx_v_chart), __pyx_n_s_root); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 234, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_2); __pyx_t_3 = NULL; if (CYTHON_UNPACK_METHODS && likely(PyMethod_Check(__pyx_t_2))) { __pyx_t_3 = PyMethod_GET_SELF(__pyx_t_2); if (likely(__pyx_t_3)) { PyObject* function = PyMethod_GET_FUNCTION(__pyx_t_2); __Pyx_INCREF(__pyx_t_3); __Pyx_INCREF(function); __Pyx_DECREF_SET(__pyx_t_2, function); } } if (__pyx_t_3) { __pyx_t_1 = __Pyx_PyObject_CallOneArg(__pyx_t_2, __pyx_t_3); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 234, __pyx_L1_error) __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0; } else { __pyx_t_1 = __Pyx_PyObject_CallNoArg(__pyx_t_2); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 234, __pyx_L1_error) } __Pyx_GOTREF(__pyx_t_1); __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0; __pyx_t_4 = __Pyx_PyInt_As_uint32_t(__pyx_t_1); if (unlikely((__pyx_t_4 == ((ItemNo)-1)) && PyErr_Occurred())) __PYX_ERR(0, 234, __pyx_L1_error) __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; __pyx_v_root = __pyx_t_4;
+235: cdef int n = 0
__pyx_v_n = 0;
+236: if root == 0:
__pyx_t_5 = ((__pyx_v_root == 0) != 0);
if (__pyx_t_5) {
/* … */
}
+237: raise ValueError('kbest: no complete derivation in chart')
__pyx_t_1 = __Pyx_PyObject_Call(__pyx_builtin_ValueError, __pyx_tuple_, NULL); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 237, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_1); __Pyx_Raise(__pyx_t_1, 0, 0, 0); __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0; __PYX_ERR(0, 237, __pyx_L1_error) /* … */ __pyx_tuple_ = PyTuple_Pack(1, __pyx_kp_u_kbest_no_complete_derivation_in); if (unlikely(!__pyx_tuple_)) __PYX_ERR(0, 237, __pyx_L1_error) __Pyx_GOTREF(__pyx_tuple_); __Pyx_GIVEREF(__pyx_tuple_);
+238: chart.rankededges.clear()
__pyx_v_chart->rankededges.clear();
+239: chart.rankededges.resize(chart.parseforest.size())
try {
__pyx_v_chart->rankededges.resize(__pyx_v_chart->parseforest.size());
} catch(...) {
__Pyx_CppExn2PyErr();
__PYX_ERR(0, 239, __pyx_L1_error)
}
+240: lazykthbest(root, k, k, cand, chart, explored, MAX_DEPTH)
__pyx_t_1 = __pyx_f_8discodop_5kbest_lazykthbest(__pyx_v_root, __pyx_v_k, __pyx_v_k, __pyx_v_cand, __pyx_v_chart, __pyx_v_explored, 0xC8); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 240, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_1); __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;
+241: for entry in chart.rankededges[root]:
__pyx_t_7 = &(__pyx_v_chart->rankededges[__pyx_v_root]);
__pyx_t_6 = __pyx_t_7->begin();
for (;;) {
if (!(__pyx_t_6 != __pyx_t_7->end())) break;
__pyx_t_8 = *__pyx_t_6;
++__pyx_t_6;
__pyx_v_entry = __pyx_t_8;
/* … */
}
__pyx_L5_break:;
+242: if explorederivation(root, entry.first, chart, explored, MAX_DEPTH):
__pyx_t_9 = __pyx_f_8discodop_5kbest_explorederivation(__pyx_v_root, __pyx_v_entry.first, __pyx_v_chart, __pyx_v_explored, 0xC8); if (unlikely(__pyx_t_9 == -2)) __PYX_ERR(0, 242, __pyx_L1_error)
__pyx_t_5 = (__pyx_t_9 != 0);
if (__pyx_t_5) {
/* … */
}
+243: tmp.push_back(entry)
try {
__pyx_v_tmp.push_back(__pyx_v_entry);
} catch(...) {
__Pyx_CppExn2PyErr();
__PYX_ERR(0, 243, __pyx_L1_error)
}
+244: n += 1
__pyx_v_n = (__pyx_v_n + 1);
+245: if n >= k:
__pyx_t_5 = ((__pyx_v_n >= __pyx_v_k) != 0);
if (__pyx_t_5) {
/* … */
}
+246: break
goto __pyx_L5_break;
+247: chart.rankededges[root] = tmp
(__pyx_v_chart->rankededges[__pyx_v_root]) = __pyx_v_tmp;
+248: if derivs:
__pyx_t_5 = (__pyx_v_derivs != 0);
if (__pyx_t_5) {
/* … */
}
249: # for entry in chart.rankededges[root]:
250: # chart.derivations.push_back(getderiv(root, entry.first, chart))
+251: return [(getderiv(root, entry.first, chart).decode('utf8'),
__Pyx_XDECREF(__pyx_r); { /* enter inner scope */ std::pair<RankedEdge,Prob> __pyx_7genexpr__pyx_v_entry; __pyx_t_1 = PyList_New(0); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 251, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_1); /* … */ __pyx_t_2 = __Pyx_decode_cpp_string(__pyx_f_8discodop_5kbest_getderiv(__pyx_v_root, __pyx_7genexpr__pyx_v_entry.first, __pyx_v_chart), 0, PY_SSIZE_T_MAX, NULL, NULL, PyUnicode_DecodeUTF8); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 251, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_2); /* … */ __pyx_t_10 = PyTuple_New(2); if (unlikely(!__pyx_t_10)) __PYX_ERR(0, 251, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_10); __Pyx_GIVEREF(__pyx_t_2); PyTuple_SET_ITEM(__pyx_t_10, 0, __pyx_t_2); __Pyx_GIVEREF(__pyx_t_3); PyTuple_SET_ITEM(__pyx_t_10, 1, __pyx_t_3); __pyx_t_2 = 0; __pyx_t_3 = 0; if (unlikely(__Pyx_ListComp_Append(__pyx_t_1, (PyObject*)__pyx_t_10))) __PYX_ERR(0, 251, __pyx_L1_error) __Pyx_DECREF(__pyx_t_10); __pyx_t_10 = 0;
+252: entry.second) for entry in chart.rankededges[root]]
__pyx_t_7 = &(__pyx_v_chart->rankededges[__pyx_v_root]);
__pyx_t_6 = __pyx_t_7->begin();
for (;;) {
if (!(__pyx_t_6 != __pyx_t_7->end())) break;
__pyx_t_8 = *__pyx_t_6;
++__pyx_t_6;
__pyx_7genexpr__pyx_v_entry = __pyx_t_8;
/* … */
__pyx_t_3 = PyFloat_FromDouble(__pyx_7genexpr__pyx_v_entry.second); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 252, __pyx_L1_error)
__Pyx_GOTREF(__pyx_t_3);
/* … */
}
} /* exit inner scope */
__pyx_r = __pyx_t_1;
__pyx_t_1 = 0;
goto __pyx_L0;
+253: return None
__Pyx_XDECREF(__pyx_r); __Pyx_INCREF(Py_None); __pyx_r = Py_None; goto __pyx_L0;
254:
+255: __all__ = ['getderiv', 'lazykbest']
__pyx_t_4 = PyList_New(2); if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 255, __pyx_L1_error) __Pyx_GOTREF(__pyx_t_4); __Pyx_INCREF(__pyx_n_u_getderiv); __Pyx_GIVEREF(__pyx_n_u_getderiv); PyList_SET_ITEM(__pyx_t_4, 0, __pyx_n_u_getderiv); __Pyx_INCREF(__pyx_n_u_lazykbest); __Pyx_GIVEREF(__pyx_n_u_lazykbest); PyList_SET_ITEM(__pyx_t_4, 1, __pyx_n_u_lazykbest); if (PyDict_SetItem(__pyx_d, __pyx_n_s_all, __pyx_t_4) < 0) __PYX_ERR(0, 255, __pyx_L1_error) __Pyx_DECREF(__pyx_t_4); __pyx_t_4 = 0;