LatticeStringRepository< IntType > Class Template Reference

#include <determinize-lattice-inl.h>

Collaboration diagram for LatticeStringRepository< IntType >:

Classes

struct  Entry
 
class  EntryEqual
 
class  EntryKey
 

Public Member Functions

const EntryEmptyString ()
 
const EntrySuccessor (const Entry *parent, IntType i)
 
const EntryConcatenate (const Entry *a, const Entry *b)
 
const EntryCommonPrefix (const Entry *a, const Entry *b)
 
void ReduceToCommonPrefix (const Entry *a, std::vector< IntType > *b)
 
const EntryRemovePrefix (const Entry *a, size_t n)
 
bool IsPrefixOf (const Entry *a, const Entry *b) const
 
size_t Size (const Entry *entry) const
 
void ConvertToVector (const Entry *entry, std::vector< IntType > *out) const
 
const EntryConvertFromVector (const std::vector< IntType > &vec)
 
 LatticeStringRepository ()
 
void Destroy ()
 
void Rebuild (const std::vector< const Entry *> &to_keep)
 
 ~LatticeStringRepository ()
 
int32 MemSize () const
 

Private Types

typedef std::unordered_set< const Entry *, EntryKey, EntryEqualSetType
 

Private Member Functions

void RebuildHelper (const Entry *to_add, SetType *tmp_set)
 
 KALDI_DISALLOW_COPY_AND_ASSIGN (LatticeStringRepository)
 

Private Attributes

Entrynew_entry_
 
SetType set_
 

Detailed Description

template<class IntType>
class fst::LatticeStringRepository< IntType >

Definition at line 37 of file determinize-lattice-inl.h.

Member Typedef Documentation

◆ SetType

typedef std::unordered_set<const Entry*, EntryKey, EntryEqual> SetType
private

Definition at line 223 of file determinize-lattice-inl.h.

Constructor & Destructor Documentation

◆ LatticeStringRepository()

◆ ~LatticeStringRepository()

Member Function Documentation

◆ CommonPrefix()

const Entry* CommonPrefix ( const Entry a,
const Entry b 
)
inline

Definition at line 83 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::ConvertToVector(), LatticeStringRepository< IntType >::Entry::i, and LatticeStringRepository< IntType >::Successor().

Referenced by fst::TestLatticeStringRepository().

83  {
84  std::vector<IntType> a_vec, b_vec;
85  ConvertToVector(a, &a_vec);
86  ConvertToVector(b, &b_vec);
87  const Entry *ans = NULL;
88  for(size_t i = 0; i < a_vec.size() && i < b_vec.size() &&
89  a_vec[i] == b_vec[i]; i++)
90  ans = Successor(ans, a_vec[i]);
91  return ans;
92  }
void ConvertToVector(const Entry *entry, std::vector< IntType > *out) const
const Entry * Successor(const Entry *parent, IntType i)

◆ Concatenate()

const Entry* Concatenate ( const Entry a,
const Entry b 
)
inline

Definition at line 73 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::ConvertToVector(), LatticeStringRepository< IntType >::Entry::i, and LatticeStringRepository< IntType >::Successor().

73  {
74  if (a == NULL) return b;
75  else if (b == NULL) return a;
76  std::vector<IntType> v;
77  ConvertToVector(b, &v);
78  const Entry *ans = a;
79  for(size_t i = 0; i < v.size(); i++)
80  ans = Successor(ans, v[i]);
81  return ans;
82  }
void ConvertToVector(const Entry *entry, std::vector< IntType > *out) const
const Entry * Successor(const Entry *parent, IntType i)

◆ ConvertFromVector()

const Entry* ConvertFromVector ( const std::vector< IntType > &  vec)
inline

Definition at line 162 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::Entry::i, and LatticeStringRepository< IntType >::Successor().

162  {
163  const Entry *e = NULL;
164  for(size_t i = 0; i < vec.size(); i++)
165  e = Successor(e, vec[i]);
166  return e;
167  }
const Entry * Successor(const Entry *parent, IntType i)

◆ ConvertToVector()

void ConvertToVector ( const Entry entry,
std::vector< IntType > *  out 
) const
inline

Definition at line 149 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::Entry::i, LatticeStringRepository< IntType >::Entry::parent, and LatticeStringRepository< IntType >::Size().

Referenced by LatticeStringRepository< IntType >::CommonPrefix(), LatticeStringRepository< IntType >::Concatenate(), LatticeStringRepository< IntType >::RemovePrefix(), and fst::TestLatticeStringRepository().

149  {
150  size_t length = Size(entry);
151  out->resize(length);
152  if (entry != NULL) {
153  typename std::vector<IntType>::reverse_iterator iter = out->rbegin();
154  while (entry != NULL) {
155  *iter = entry->i;
156  entry = entry->parent;
157  ++iter;
158  }
159  }
160  }
size_t Size(const Entry *entry) const

◆ Destroy()

void Destroy ( )
inline

Definition at line 171 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::new_entry_, and LatticeStringRepository< IntType >::set_.

Referenced by LatticeStringRepository< IntType >::~LatticeStringRepository().

171  {
172  for (typename SetType::iterator iter = set_.begin();
173  iter != set_.end();
174  ++iter)
175  delete *iter;
176  SetType tmp;
177  tmp.swap(set_);
178  if (new_entry_) {
179  delete new_entry_;
180  new_entry_ = NULL;
181  }
182  }
std::unordered_set< const Entry *, EntryKey, EntryEqual > SetType

◆ EmptyString()

const Entry* EmptyString ( )
inline

Definition at line 52 of file determinize-lattice-inl.h.

Referenced by fst::TestLatticeStringRepository().

52 { return NULL; }

◆ IsPrefixOf()

bool IsPrefixOf ( const Entry a,
const Entry b 
) const
inline

Definition at line 132 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::Entry::parent.

Referenced by fst::TestLatticeStringRepository().

132  {
133  if(a == NULL) return true; // empty string prefix of all.
134  if (a == b) return true;
135  if (b == NULL) return false;
136  return IsPrefixOf(a, b->parent);
137  }
bool IsPrefixOf(const Entry *a, const Entry *b) const

◆ KALDI_DISALLOW_COPY_AND_ASSIGN()

◆ MemSize()

int32 MemSize ( ) const
inline

Definition at line 204 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::Entry::Entry(), and LatticeStringRepository< IntType >::set_.

204  {
205  return set_.size() * sizeof(Entry) * 2; // this is a lower bound
206  // on the size this structure might take.
207  }

◆ Rebuild()

void Rebuild ( const std::vector< const Entry *> &  to_keep)
inline

Definition at line 188 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::RebuildHelper(), and LatticeStringRepository< IntType >::set_.

188  {
189  SetType tmp_set;
190  for (typename std::vector<const Entry*>::const_iterator
191  iter = to_keep.begin();
192  iter != to_keep.end(); ++iter)
193  RebuildHelper(*iter, &tmp_set);
194  // Now delete all elems not in tmp_set.
195  for (typename SetType::iterator iter = set_.begin();
196  iter != set_.end(); ++iter) {
197  if (tmp_set.count(*iter) == 0)
198  delete (*iter); // delete the Entry; not needed.
199  }
200  set_.swap(tmp_set);
201  }
std::unordered_set< const Entry *, EntryKey, EntryEqual > SetType
void RebuildHelper(const Entry *to_add, SetType *tmp_set)

◆ RebuildHelper()

void RebuildHelper ( const Entry to_add,
SetType tmp_set 
)
inlineprivate

Definition at line 225 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::KALDI_DISALLOW_COPY_AND_ASSIGN(), and LatticeStringRepository< IntType >::Entry::parent.

Referenced by LatticeStringRepository< IntType >::Rebuild().

225  {
226  while(true) {
227  if (to_add == NULL) return;
228  typename SetType::iterator iter = tmp_set->find(to_add);
229  if (iter == tmp_set->end()) { // not in tmp_set.
230  tmp_set->insert(to_add);
231  to_add = to_add->parent; // and loop.
232  } else {
233  return;
234  }
235  }
236  }

◆ ReduceToCommonPrefix()

void ReduceToCommonPrefix ( const Entry a,
std::vector< IntType > *  b 
)
inline

Definition at line 96 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::Entry::i, LatticeStringRepository< IntType >::Entry::parent, and LatticeStringRepository< IntType >::Size().

Referenced by fst::TestLatticeStringRepository().

97  {
98  size_t a_size = Size(a), b_size = b->size();
99  while (a_size> b_size) {
100  a = a->parent;
101  a_size--;
102  }
103  if (b_size > a_size)
104  b_size = a_size;
105  typename std::vector<IntType>::iterator b_begin = b->begin();
106  while (a_size != 0) {
107  if (a->i != *(b_begin + a_size - 1))
108  b_size = a_size - 1;
109  a = a->parent;
110  a_size--;
111  }
112  if (b_size != b->size())
113  b->resize(b_size);
114  }
size_t Size(const Entry *entry) const

◆ RemovePrefix()

const Entry* RemovePrefix ( const Entry a,
size_t  n 
)
inline

Definition at line 117 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::ConvertToVector(), LatticeStringRepository< IntType >::Entry::i, rnnlm::n, and LatticeStringRepository< IntType >::Successor().

117  {
118  if (n==0) return a;
119  std::vector<IntType> a_vec;
120  ConvertToVector(a, &a_vec);
121  assert(a_vec.size() >= n);
122  const Entry *ans = NULL;
123  for(size_t i = n; i < a_vec.size(); i++)
124  ans = Successor(ans, a_vec[i]);
125  return ans;
126  }
void ConvertToVector(const Entry *entry, std::vector< IntType > *out) const
const Entry * Successor(const Entry *parent, IntType i)
struct rnnlm::@11::@12 n

◆ Size()

size_t Size ( const Entry entry) const
inline

Definition at line 140 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::Entry::parent.

Referenced by LatticeStringRepository< IntType >::ConvertToVector(), and LatticeStringRepository< IntType >::ReduceToCommonPrefix().

140  {
141  size_t ans = 0;
142  while (entry != NULL) {
143  ans++;
144  entry = entry->parent;
145  }
146  return ans;
147  }

◆ Successor()

const Entry* Successor ( const Entry parent,
IntType  i 
)
inline

Definition at line 56 of file determinize-lattice-inl.h.

References LatticeStringRepository< IntType >::Entry::Entry(), LatticeStringRepository< IntType >::Entry::i, LatticeStringRepository< IntType >::new_entry_, LatticeStringRepository< IntType >::Entry::parent, and LatticeStringRepository< IntType >::set_.

Referenced by LatticeStringRepository< IntType >::CommonPrefix(), LatticeStringRepository< IntType >::Concatenate(), LatticeStringRepository< IntType >::ConvertFromVector(), LatticeStringRepository< IntType >::RemovePrefix(), and fst::TestLatticeStringRepository().

56  {
57  new_entry_->parent = parent;
58  new_entry_->i = i;
59 
60  std::pair<typename SetType::iterator, bool> pr = set_.insert(new_entry_);
61  if (pr.second) { // Was successfully inserted (was not there). We need to
62  // replace the element we inserted, which resides on the
63  // stack, with one from the heap.
64  const Entry *ans = new_entry_;
65  new_entry_ = new Entry();
66  return ans;
67  } else { // Was not inserted because an equivalent Entry already
68  // existed.
69  return *pr.first;
70  }
71  }

Member Data Documentation

◆ new_entry_

◆ set_


The documentation for this class was generated from the following file: