22 #ifndef FST_UNION_WEIGHT_H_ 23 #define FST_UNION_WEIGHT_H_ 68 template <
class W,
class O>
71 template <
class W,
class O>
74 template <
class W,
class O>
77 template <
class W,
class O>
83 template <
class W,
class O>
88 using Merge =
typename O::Merge;
102 if (!weight.Member()) rest_.push_back(W::NoWeight());
111 static const auto *
const one =
new UnionWeight(W::One());
116 static const auto *
const no_weight =
121 static const std::string &
Type() {
122 static const std::string *
const type =
123 new std::string(W::Type() +
"_union");
128 return W::Properties() &
134 std::istream &
Read(std::istream &strm);
136 std::ostream &
Write(std::ostream &strm)
const;
150 first_ = W::NoWeight();
154 size_t Size()
const {
return first_.Member() ? rest_.size() + 1 : 0; }
156 const W &
Back()
const {
return rest_.empty() ? first_ : rest_.back(); }
165 void Sort() { rest_.sort(comp_); }
176 UnionWeight(W w1, W w2) : first_(std::move(w1)), rest_(1, std::move(w2)) {}
184 template <
class W,
class O>
186 if (!weight.Member()) {
187 rest_.push_back(std::move(weight));
188 }
else if (!first_.Member()) {
189 first_ = std::move(weight);
192 if (comp_(back, weight)) {
193 rest_.push_back(std::move(weight));
195 back = merge_(back, std::move(weight));
198 if (comp_(first_, weight)) {
199 rest_.push_back(std::move(weight));
201 rest_.push_back(first_);
202 first_ = std::move(weight);
208 template <
class W,
class O>
212 : first_(weight.first_),
215 it_(rest_.begin()) {}
217 bool Done()
const {
return init_ ? !first_.Member() : it_ == rest_.end(); }
219 const W &
Value()
const {
return init_ ? first_ : *it_; }
236 const std::list<W> &rest_;
238 typename std::list<W>::const_iterator it_;
242 template <
typename L,
class O>
246 : first_(weight.first_),
249 it_(rest_.rbegin()) {}
251 bool Done()
const {
return fin_; }
253 const L &
Value()
const {
return it_ == rest_.rend() ? first_ : *it_; }
256 if (it_ == rest_.rend()) {
264 fin_ = !first_.Member();
265 it_ = rest_.rbegin();
270 const std::list<L> &rest_;
272 typename std::list<L>::const_reverse_iterator it_;
276 template <
class W,
class O>
281 for (
int i = 0; i < size; ++i) {
289 template <
class W,
class O>
291 const int32_t size =
Size();
299 template <
class W,
class O>
301 if (
Size() <= 1)
return true;
303 if (!it.Value().Member())
return false;
308 template <
class W,
class O>
312 weight.
PushBack(it.Value().Quantize(delta),
true);
317 template <
class W,
class O>
322 weight.
PushBack(it.Value().Reverse(),
false);
328 template <
class W,
class O>
331 static constexpr
int lshift = 5;
332 static constexpr
int rshift = CHAR_BIT *
sizeof(size_t) - lshift;
334 h = h << lshift ^ h >> rshift ^ it.Value().Hash();
340 template <
class W,
class O>
343 if (w1.
Size() != w2.
Size())
return false;
353 template <
class W,
class O>
360 template <
class W,
class O>
363 if (w1.
Size() != w2.
Size())
return false;
372 template <
class W,
class O>
377 return ostrm <<
"EmptySet";
378 }
else if (!weight.
Member()) {
379 return ostrm <<
"BadSet";
389 template <
class W,
class O>
394 if (s ==
"EmptySet") {
396 }
else if (s ==
"BadSet") {
400 std::istringstream sstrm(s);
414 template <
class W,
class O>
423 typename O::Compare comp;
424 while (!it1.
Done() && !it2.
Done()) {
425 const auto v1 = it1.
Value();
426 const auto v2 = it2.
Value();
440 template <
class W,
class O>
455 prod1 =
Plus(prod1, prod2);
461 template <
class W,
class O>
471 if (w1.
Size() == 1) {
475 }
else if (w2.
Size() == 1) {
488 template <
class W,
class O>
495 bool allow_zero =
true,
498 allow_zero_(allow_zero),
499 num_random_weights_(num_random_weights),
500 generate_(seed, false) {}
503 const int sample = std::uniform_int_distribution<>(
504 0, num_random_weights_ + allow_zero_ - 1)(rand_);
505 if (allow_zero_ && sample == num_random_weights_) {
506 return Weight::Zero();
507 }
else if (std::bernoulli_distribution(.5)(rand_)) {
508 return Weight(generate_());
515 mutable std::mt19937_64 rand_;
516 const bool allow_zero_;
517 const size_t num_random_weights_;
523 #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