22 #ifndef FST_UNION_WEIGHT_H_ 23 #define FST_UNION_WEIGHT_H_ 71 template <
class W,
class O>
73 template <
class W,
class O>
75 template <
class W,
class O>
78 template <
class W,
class O>
84 template <
class W,
class O>
89 using Merge =
typename O::Merge;
103 if (!weight.Member()) rest_.push_back(W::NoWeight());
112 static const auto *
const one =
new UnionWeight(W::One());
117 static const auto *
const no_weight =
122 static const std::string &
Type() {
123 static const std::string *
const type =
124 new std::string(W::Type() +
"_union");
129 return W::Properties() &
135 std::istream &
Read(std::istream &strm);
137 std::ostream &
Write(std::ostream &strm)
const;
151 first_ = W::NoWeight();
155 size_t Size()
const {
return first_.Member() ? rest_.size() + 1 : 0; }
157 const W &
Back()
const {
return rest_.empty() ? first_ : rest_.back(); }
166 void Sort() { rest_.sort(comp_); }
177 UnionWeight(W w1, W w2) : first_(std::move(w1)), rest_(1, std::move(w2)) {}
185 template <
class W,
class O>
187 if (!weight.Member()) {
188 rest_.push_back(std::move(weight));
189 }
else if (!first_.Member()) {
190 first_ = std::move(weight);
193 if (comp_(back, weight)) {
194 rest_.push_back(std::move(weight));
196 back = merge_(back, std::move(weight));
199 if (comp_(first_, weight)) {
200 rest_.push_back(std::move(weight));
202 rest_.push_back(first_);
203 first_ = std::move(weight);
209 template <
class W,
class O>
213 : first_(weight.first_),
216 it_(rest_.begin()) {}
218 bool Done()
const {
return init_ ? !first_.Member() : it_ == rest_.end(); }
220 const W &
Value()
const {
return init_ ? first_ : *it_; }
237 const std::list<W> &rest_;
239 typename std::list<W>::const_iterator it_;
243 template <
typename L,
class O>
247 : first_(weight.first_),
250 it_(rest_.rbegin()) {}
252 bool Done()
const {
return fin_; }
254 const L &
Value()
const {
return it_ == rest_.rend() ? first_ : *it_; }
257 if (it_ == rest_.rend()) {
265 fin_ = !first_.Member();
266 it_ = rest_.rbegin();
271 const std::list<L> &rest_;
273 typename std::list<L>::const_reverse_iterator it_;
277 template <
class W,
class O>
282 for (
int i = 0; i < size; ++i) {
290 template <
class W,
class O>
292 const int32_t size =
Size();
300 template <
class W,
class O>
302 if (
Size() <= 1)
return true;
304 if (!it.Value().Member())
return false;
309 template <
class W,
class O>
313 weight.
PushBack(it.Value().Quantize(delta),
true);
318 template <
class W,
class O>
323 weight.
PushBack(it.Value().Reverse(),
false);
329 template <
class W,
class O>
332 static constexpr
int lshift = 5;
333 static constexpr
int rshift = CHAR_BIT *
sizeof(size_t) - lshift;
335 h = h << lshift ^ h >> rshift ^ it.Value().Hash();
341 template <
class W,
class O>
344 if (w1.
Size() != w2.
Size())
return false;
354 template <
class W,
class O>
361 template <
class W,
class O>
364 if (w1.
Size() != w2.
Size())
return false;
373 template <
class W,
class O>
378 return ostrm <<
"EmptySet";
379 }
else if (!weight.
Member()) {
380 return ostrm <<
"BadSet";
390 template <
class W,
class O>
395 if (s ==
"EmptySet") {
397 }
else if (s ==
"BadSet") {
401 std::istringstream sstrm(s);
415 template <
class W,
class O>
424 typename O::Compare comp;
425 while (!it1.
Done() && !it2.
Done()) {
426 const auto v1 = it1.
Value();
427 const auto v2 = it2.
Value();
441 template <
class W,
class O>
456 prod1 =
Plus(prod1, prod2);
462 template <
class W,
class O>
472 if (w1.
Size() == 1) {
476 }
else if (w2.
Size() == 1) {
489 template <
class W,
class O>
496 bool allow_zero =
true,
499 allow_zero_(allow_zero),
500 num_random_weights_(num_random_weights),
501 generate_(seed, false) {}
504 const int sample = std::uniform_int_distribution<>(
505 0, num_random_weights_ + allow_zero_ - 1)(rand_);
506 if (allow_zero_ && sample == num_random_weights_) {
507 return Weight::Zero();
508 }
else if (std::bernoulli_distribution(.5)(rand_)) {
509 return Weight(generate_());
516 mutable std::mt19937_64 rand_;
517 const bool allow_zero_;
518 const size_t num_random_weights_;
524 #endif // FST_UNION_WEIGHT_H_
typename O::Compare Compare
static constexpr uint64_t Properties()
static const UnionWeight & One()
ErrorWeight Plus(const ErrorWeight &, const ErrorWeight &)
ErrorWeight Times(const ErrorWeight &, const ErrorWeight &)
std::ostream & Write(std::ostream &strm) const
constexpr uint64_t kIdempotent
std::istream & Read(std::istream &strm)
static const std::string & Type()
constexpr uint64_t kRightSemiring
std::ostream & WriteType(std::ostream &strm, const T t)
ReverseWeight Reverse() const
void PushBack(W weight, bool srt)
std::istream & operator>>(std::istream &strm, FloatWeightTpl< T > &w)
bool operator!=(const ErrorWeight &, const ErrorWeight &)
constexpr uint64_t kCommutative
std::ostream & operator<<(std::ostream &strm, const ErrorWeight &)
static const UnionWeight & Zero()
UnionWeightReverseIterator(const UnionWeight< L, O > &weight)
UnionWeightIterator(const UnionWeight< W, O > &weight)
static const UnionWeight & NoWeight()
bool ReadElement(T *comp, bool last=false)
ErrorWeight Divide(const ErrorWeight &, const ErrorWeight &)
bool operator==(const ErrorWeight &, const ErrorWeight &)
UnionWeight Quantize(float delta=kDelta) const
constexpr size_t kNumRandomWeights
WeightGenerate(uint64_t seed=std::random_device()(), bool allow_zero=true, size_t num_random_weights=kNumRandomWeights)
std::istream & ReadType(std::istream &strm, T *t)
void WriteElement(const T &comp)
constexpr uint64_t kLeftSemiring
bool ApproxEqual(const ErrorWeight &, const ErrorWeight &, float)
Weight operator()() const