All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
fst::pre_determinize_helpers Namespace Reference

Functions

bool HasBannedPrefixPlusDigits (SymbolTable *symTable, std::string prefix, std::string *bad_sym)
 
template<class T >
void CopySetToVector (const std::set< T > s, vector< T > *v)
 
template<class T >
vector< T > * InsertMember (const vector< T > m, vector< vector< T > * > *S)
 
template<class Arc >
void Closure (MutableFst< Arc > *fst, std::set< typename Arc::StateId > *S, const vector< bool > &pVec)
 

Function Documentation

void fst::pre_determinize_helpers::Closure ( MutableFst< Arc > *  fst,
std::set< typename Arc::StateId > *  S,
const vector< bool > &  pVec 
)

Definition at line 291 of file pre-determinize-inl.h.

References CopySetToVector().

Referenced by fst::MakeLoopFstCompare(), and fst::PreDeterminize().

292  {
293  typedef typename Arc::StateId StateId;
294  vector<StateId> Q;
295  CopySetToVector(*S, &Q);
296  while (Q.size() != 0) {
297  StateId s = Q.back();
298  Q.pop_back();
299  for (ArcIterator<MutableFst<Arc> > aiter(*fst, s); ! aiter.Done(); aiter.Next()) {
300  const Arc &arc = aiter.Value();
301  if (arc.ilabel != 0) break; // Break from the loop: due to sorting there will be no
302  // more transitions with epsilons as input labels.
303  if (!pVec[arc.nextstate]) { // Next state is not problematic -> we can use this transition.
304  pair< typename std::set<StateId>::iterator, bool > p = S->insert(arc.nextstate);
305  if (p.second) { // True means: was inserted into S (wasn't already there).
306  Q.push_back(arc.nextstate);
307  }
308  }
309  }
310  }
311 } // end function Closure.
fst::StdArc::StateId StateId
Definition: graph.dox:21
void CopySetToVector(const std::set< T > s, vector< T > *v)
void fst::pre_determinize_helpers::CopySetToVector ( const std::set< T >  s,
vector< T > *  v 
)

Definition at line 256 of file pre-determinize-inl.h.

Referenced by Closure(), and fst::PreDeterminize().

256  {
257  // adds members of s to v, in sorted order from lowest to highest
258  // (because the set was in sorted order).
259  assert(v != NULL);
260  v->resize(s.size());
261  typename std::set<T>::const_iterator siter = s.begin();
262  typename vector<T>::iterator viter = v->begin();
263  for (; siter != s.end(); ++siter, ++viter) {
264  assert(viter != v->end());
265  *viter = *siter;
266  }
267 }
bool fst::pre_determinize_helpers::HasBannedPrefixPlusDigits ( SymbolTable *  symTable,
std::string  prefix,
std::string *  bad_sym 
)
inline

Definition at line 230 of file pre-determinize-inl.h.

230  {
231  // returns true if the symbol table contains any string consisting of this
232  // (possibly empty) prefix followed by a nonempty sequence of digits (0 to 9).
233  // requires symTable to be non-NULL.
234  // if bad_sym != NULL, puts the first bad symbol it finds in *bad_sym.
235  assert(symTable != NULL);
236  const char *prefix_ptr = prefix.c_str();
237  size_t prefix_len = strlen(prefix_ptr); // allowed to be zero but not encouraged.
238  for (SymbolTableIterator siter(*symTable); !siter.Done(); siter.Next()) {
239  const char *sym = siter.Symbol().c_str();
240  if (!strncmp(prefix_ptr, sym, prefix_len)) { // has prefix.
241  if (isdigit(sym[prefix_len])) { // we don't allow prefix followed by a digit, as a symbol.
242  // Has at least one digit.
243  size_t pos;
244  for (pos = prefix_len;sym[pos] != '\0'; pos++)
245  if (!isdigit(sym[pos])) break;
246  if (sym[pos] == '\0') { // All remaining characters were digits.
247  if (bad_sym != NULL) *bad_sym = (std::string) sym;
248  return true;
249  }
250  } // else OK because prefix was followed by '\0' or a non-digit.
251  }
252  }
253  return false; // doesn't have banned symbol.
254 }
vector<T>* fst::pre_determinize_helpers::InsertMember ( const vector< T >  m,
vector< vector< T > * > *  S 
)

Definition at line 271 of file pre-determinize-inl.h.

Referenced by fst::PreDeterminize().

271  {
272  assert(m.size() > 0);
273  T idx = m[0];
274  assert(idx>=(T)0 && idx < (T)S->size());
275  if ( (*S)[idx] != NULL) {
276  assert( *((*S)[idx]) == m );
277  // The vectors should be the same. Otherwise this is a bug in the algorithm.
278  // It could either be a programming error or a deeper conceptual bug.
279  return NULL; // nothing was inserted.
280  } else {
281  vector<T> *ret = (*S)[idx] = new vector<T>(m); // New copy of m.
282  return ret; // was inserted.
283  }
284 }