FST  openfst-1.7.1
OpenFst Library
queue.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Functions and classes for various FST state queues with a unified interface.
5 
6 #ifndef FST_QUEUE_H_
7 #define FST_QUEUE_H_
8 
9 #include <deque>
10 #include <memory>
11 #include <type_traits>
12 #include <utility>
13 #include <vector>
14 
15 #include <fst/log.h>
16 
17 #include <fst/arcfilter.h>
18 #include <fst/connect.h>
19 #include <fst/heap.h>
20 #include <fst/topsort.h>
21 
22 
23 namespace fst {
24 
25 // The Queue interface is:
26 //
27 // template <class S>
28 // class Queue {
29 // public:
30 // using StateId = S;
31 //
32 // // Constructor: may need args (e.g., FST, comparator) for some queues.
33 // Queue(...) override;
34 //
35 // // Returns the head of the queue.
36 // StateId Head() const override;
37 //
38 // // Inserts a state.
39 // void Enqueue(StateId s) override;
40 //
41 // // Removes the head of the queue.
42 // void Dequeue() override;
43 //
44 // // Updates ordering of state s when weight changes, if necessary.
45 // void Update(StateId s) override;
46 //
47 // // Is the queue empty?
48 // bool Empty() const override;
49 //
50 // // Removes all states from the queue.
51 // void Clear() override;
52 // };
53 
54 // State queue types.
55 enum QueueType {
56  TRIVIAL_QUEUE = 0, // Single state queue.
57  FIFO_QUEUE = 1, // First-in, first-out queue.
58  LIFO_QUEUE = 2, // Last-in, first-out queue.
59  SHORTEST_FIRST_QUEUE = 3, // Shortest-first queue.
60  TOP_ORDER_QUEUE = 4, // Topologically-ordered queue.
61  STATE_ORDER_QUEUE = 5, // State ID-ordered queue.
62  SCC_QUEUE = 6, // Component graph top-ordered meta-queue.
63  AUTO_QUEUE = 7, // Auto-selected queue.
65 };
66 
67 // QueueBase, templated on the StateId, is a virtual base class shared by all
68 // queues considered by AutoQueue.
69 template <class S>
70 class QueueBase {
71  public:
72  using StateId = S;
73 
74  virtual ~QueueBase() {}
75 
76  // Concrete implementation.
77 
78  explicit QueueBase(QueueType type) : queue_type_(type), error_(false) {}
79 
80  void SetError(bool error) { error_ = error; }
81 
82  bool Error() const { return error_; }
83 
84  QueueType Type() const { return queue_type_; }
85 
86  // Virtual interface.
87 
88  virtual StateId Head() const = 0;
89  virtual void Enqueue(StateId) = 0;
90  virtual void Dequeue() = 0;
91  virtual void Update(StateId) = 0;
92  virtual bool Empty() const = 0;
93  virtual void Clear() = 0;
94 
95  private:
96  QueueType queue_type_;
97  bool error_;
98 };
99 
100 // Trivial queue discipline; one may enqueue at most one state at a time. It
101 // can be used for strongly connected components with only one state and no
102 // self-loops.
103 template <class S>
104 class TrivialQueue : public QueueBase<S> {
105  public:
106  using StateId = S;
107 
109 
110  virtual ~TrivialQueue() = default;
111 
112  StateId Head() const final { return front_; }
113 
114  void Enqueue(StateId s) final { front_ = s; }
115 
116  void Dequeue() final { front_ = kNoStateId; }
117 
118  void Update(StateId) final {}
119 
120  bool Empty() const final { return front_ == kNoStateId; }
121 
122  void Clear() final { front_ = kNoStateId; }
123 
124  private:
125  StateId front_;
126 };
127 
128 // First-in, first-out queue discipline.
129 //
130 // This is not a final class.
131 template <class S>
132 class FifoQueue : public QueueBase<S> {
133  public:
134  using StateId = S;
135 
137 
138  virtual ~FifoQueue() = default;
139 
140  StateId Head() const override { return queue_.back(); }
141 
142  void Enqueue(StateId s) override { queue_.push_front(s); }
143 
144  void Dequeue() override { queue_.pop_back(); }
145 
146  void Update(StateId) override {}
147 
148  bool Empty() const override { return queue_.empty(); }
149 
150  void Clear() override { queue_.clear(); }
151 
152  private:
153  std::deque<StateId> queue_;
154 };
155 
156 // Last-in, first-out queue discipline.
157 template <class S>
158 class LifoQueue : public QueueBase<S> {
159  public:
160  using StateId = S;
161 
163 
164  virtual ~LifoQueue() = default;
165 
166  StateId Head() const final { return queue_.front(); }
167 
168  void Enqueue(StateId s) final { queue_.push_front(s); }
169 
170  void Dequeue() final { queue_.pop_front(); }
171 
172  void Update(StateId) final {}
173 
174  bool Empty() const final { return queue_.empty(); }
175 
176  void Clear() final { queue_.clear(); }
177 
178  private:
179  std::deque<StateId> queue_;
180 };
181 
182 // Shortest-first queue discipline, templated on the StateId and as well as a
183 // comparison functor used to compare two StateIds. If a (single) state's order
184 // changes, it can be reordered in the queue with a call to Update(). If update
185 // is false, call to Update() does not reorder the queue.
186 //
187 // This is not a final class.
188 template <typename S, typename Compare, bool update = true>
189 class ShortestFirstQueue : public QueueBase<S> {
190  public:
191  using StateId = S;
192 
193  explicit ShortestFirstQueue(Compare comp)
194  : QueueBase<StateId>(SHORTEST_FIRST_QUEUE), heap_(comp) {}
195 
196  virtual ~ShortestFirstQueue() = default;
197 
198  StateId Head() const override { return heap_.Top(); }
199 
200  void Enqueue(StateId s) override {
201  if (update) {
202  for (StateId i = key_.size(); i <= s; ++i) key_.push_back(kNoStateId);
203  key_[s] = heap_.Insert(s);
204  } else {
205  heap_.Insert(s);
206  }
207  }
208 
209  void Dequeue() override {
210  if (update) {
211  key_[heap_.Pop()] = kNoStateId;
212  } else {
213  heap_.Pop();
214  }
215  }
216 
217  void Update(StateId s) override {
218  if (!update) return;
219  if (s >= key_.size() || key_[s] == kNoStateId) {
220  Enqueue(s);
221  } else {
222  heap_.Update(key_[s], s);
223  }
224  }
225 
226  bool Empty() const override { return heap_.Empty(); }
227 
228  void Clear() override {
229  heap_.Clear();
230  if (update) key_.clear();
231  }
232 
233  const Compare &GetCompare() const { return heap_.GetCompare(); }
234 
235  private:
237  std::vector<ssize_t> key_;
238 };
239 
240 namespace internal {
241 
242 // Given a vector that maps from states to weights, and a comparison functor
243 // for weights, this class defines a comparison function object between states.
244 template <typename StateId, typename Less>
246  public:
247  using Weight = typename Less::Weight;
248 
249  StateWeightCompare(const std::vector<Weight> &weights, const Less &less)
250  : weights_(weights), less_(less) {}
251 
252  bool operator()(const StateId s1, const StateId s2) const {
253  return less_(weights_[s1], weights_[s2]);
254  }
255 
256  private:
257  // Borrowed references.
258  const std::vector<Weight> &weights_;
259  const Less &less_;
260 };
261 
262 } // namespace internal
263 
264 // Shortest-first queue discipline, templated on the StateId and Weight, is
265 // specialized to use the weight's natural order for the comparison function.
266 template <typename S, typename Weight>
268  : public ShortestFirstQueue<
269  S, internal::StateWeightCompare<S, NaturalLess<Weight>>> {
270  public:
271  using StateId = S;
273 
274  explicit NaturalShortestFirstQueue(const std::vector<Weight> &distance)
275  : ShortestFirstQueue<StateId, Compare>(Compare(distance, less_)) {}
276 
277  virtual ~NaturalShortestFirstQueue() = default;
278 
279  private:
280  // This is non-static because the constructor for non-idempotent weights will
281  // result in an error.
282  const NaturalLess<Weight> less_{};
283 };
284 
285 // Topological-order queue discipline, templated on the StateId. States are
286 // ordered in the queue topologically. The FST must be acyclic.
287 template <class S>
288 class TopOrderQueue : public QueueBase<S> {
289  public:
290  using StateId = S;
291 
292  // This constructor computes the topological order. It accepts an arc filter
293  // to limit the transitions considered in that computation (e.g., only the
294  // epsilon graph).
295  template <class Arc, class ArcFilter>
296  TopOrderQueue(const Fst<Arc> &fst, ArcFilter filter)
298  front_(0),
299  back_(kNoStateId),
300  order_(0),
301  state_(0) {
302  bool acyclic;
303  TopOrderVisitor<Arc> top_order_visitor(&order_, &acyclic);
304  DfsVisit(fst, &top_order_visitor, filter);
305  if (!acyclic) {
306  FSTERROR() << "TopOrderQueue: FST is not acyclic";
308  }
309  state_.resize(order_.size(), kNoStateId);
310  }
311 
312  // This constructor is passed the pre-computed topological order.
313  explicit TopOrderQueue(const std::vector<StateId> &order)
315  front_(0),
316  back_(kNoStateId),
317  order_(order),
318  state_(order.size(), kNoStateId) {}
319 
320  virtual ~TopOrderQueue() = default;
321 
322  StateId Head() const final { return state_[front_]; }
323 
324  void Enqueue(StateId s) final {
325  if (front_ > back_) {
326  front_ = back_ = order_[s];
327  } else if (order_[s] > back_) {
328  back_ = order_[s];
329  } else if (order_[s] < front_) {
330  front_ = order_[s];
331  }
332  state_[order_[s]] = s;
333  }
334 
335  void Dequeue() final {
336  state_[front_] = kNoStateId;
337  while ((front_ <= back_) && (state_[front_] == kNoStateId)) ++front_;
338  }
339 
340  void Update(StateId) final {}
341 
342  bool Empty() const final { return front_ > back_; }
343 
344  void Clear() final {
345  for (StateId s = front_; s <= back_; ++s) state_[s] = kNoStateId;
346  back_ = kNoStateId;
347  front_ = 0;
348  }
349 
350  private:
351  StateId front_;
352  StateId back_;
353  std::vector<StateId> order_;
354  std::vector<StateId> state_;
355 };
356 
357 // State order queue discipline, templated on the StateId. States are ordered in
358 // the queue by state ID.
359 template <class S>
360 class StateOrderQueue : public QueueBase<S> {
361  public:
362  using StateId = S;
363 
365  : QueueBase<StateId>(STATE_ORDER_QUEUE), front_(0), back_(kNoStateId) {}
366 
367  virtual ~StateOrderQueue() = default;
368 
369  StateId Head() const final { return front_; }
370 
371  void Enqueue(StateId s) final {
372  if (front_ > back_) {
373  front_ = back_ = s;
374  } else if (s > back_) {
375  back_ = s;
376  } else if (s < front_) {
377  front_ = s;
378  }
379  while (enqueued_.size() <= s) enqueued_.push_back(false);
380  enqueued_[s] = true;
381  }
382 
383  void Dequeue() final {
384  enqueued_[front_] = false;
385  while ((front_ <= back_) && (enqueued_[front_] == false)) ++front_;
386  }
387 
388  void Update(StateId) final {}
389 
390  bool Empty() const final { return front_ > back_; }
391 
392  void Clear() final {
393  for (StateId i = front_; i <= back_; ++i) enqueued_[i] = false;
394  front_ = 0;
395  back_ = kNoStateId;
396  }
397 
398  private:
399  StateId front_;
400  StateId back_;
401  std::vector<bool> enqueued_;
402 };
403 
404 // SCC topological-order meta-queue discipline, templated on the StateId and a
405 // queue used inside each SCC. It visits the SCCs of an FST in topological
406 // order. Its constructor is passed the queues to to use within an SCC.
407 template <class S, class Queue>
408 class SccQueue : public QueueBase<S> {
409  public:
410  using StateId = S;
411 
412  // Constructor takes a vector specifying the SCC number per state and a
413  // vector giving the queue to use per SCC number.
414  SccQueue(const std::vector<StateId> &scc,
415  std::vector<std::unique_ptr<Queue>> *queue)
417  queue_(queue),
418  scc_(scc),
419  front_(0),
420  back_(kNoStateId) {}
421 
422  virtual ~SccQueue() = default;
423 
424  StateId Head() const final {
425  while ((front_ <= back_) &&
426  (((*queue_)[front_] && (*queue_)[front_]->Empty()) ||
427  (((*queue_)[front_] == nullptr) &&
428  ((front_ >= trivial_queue_.size()) ||
429  (trivial_queue_[front_] == kNoStateId))))) {
430  ++front_;
431  }
432  if ((*queue_)[front_]) {
433  return (*queue_)[front_]->Head();
434  } else {
435  return trivial_queue_[front_];
436  }
437  }
438 
439  void Enqueue(StateId s) final {
440  if (front_ > back_) {
441  front_ = back_ = scc_[s];
442  } else if (scc_[s] > back_) {
443  back_ = scc_[s];
444  } else if (scc_[s] < front_) {
445  front_ = scc_[s];
446  }
447  if ((*queue_)[scc_[s]]) {
448  (*queue_)[scc_[s]]->Enqueue(s);
449  } else {
450  while (trivial_queue_.size() <= scc_[s]) {
451  trivial_queue_.push_back(kNoStateId);
452  }
453  trivial_queue_[scc_[s]] = s;
454  }
455  }
456 
457  void Dequeue() final {
458  if ((*queue_)[front_]) {
459  (*queue_)[front_]->Dequeue();
460  } else if (front_ < trivial_queue_.size()) {
461  trivial_queue_[front_] = kNoStateId;
462  }
463  }
464 
465  void Update(StateId s) final {
466  if ((*queue_)[scc_[s]]) (*queue_)[scc_[s]]->Update(s);
467  }
468 
469  bool Empty() const final {
470  // Queues SCC number back_ is not empty unless back_ == front_.
471  if (front_ < back_) {
472  return false;
473  } else if (front_ > back_) {
474  return true;
475  } else if ((*queue_)[front_]) {
476  return (*queue_)[front_]->Empty();
477  } else {
478  return (front_ >= trivial_queue_.size()) ||
479  (trivial_queue_[front_] == kNoStateId);
480  }
481  }
482 
483  void Clear() final {
484  for (StateId i = front_; i <= back_; ++i) {
485  if ((*queue_)[i]) {
486  (*queue_)[i]->Clear();
487  } else if (i < trivial_queue_.size()) {
488  trivial_queue_[i] = kNoStateId;
489  }
490  }
491  front_ = 0;
492  back_ = kNoStateId;
493  }
494 
495  private:
496  std::vector<std::unique_ptr<Queue>> *queue_;
497  const std::vector<StateId> &scc_;
498  mutable StateId front_;
499  StateId back_;
500  std::vector<StateId> trivial_queue_;
501 };
502 
503 // Automatic queue discipline. It selects a queue discipline for a given FST
504 // based on its properties.
505 template <class S>
506 class AutoQueue : public QueueBase<S> {
507  public:
508  using StateId = S;
509 
510  // This constructor takes a state distance vector that, if non-null and if
511  // the Weight type has the path property, will entertain the shortest-first
512  // queue using the natural order w.r.t to the distance.
513  template <class Arc, class ArcFilter>
515  const std::vector<typename Arc::Weight> *distance, ArcFilter filter)
517  using Weight = typename Arc::Weight;
518  using Less = NaturalLess<Weight>;
520  // First checks if the FST is known to have these properties.
521  const auto props =
523  if ((props & kTopSorted) || fst.Start() == kNoStateId) {
524  queue_.reset(new StateOrderQueue<StateId>());
525  VLOG(2) << "AutoQueue: using state-order discipline";
526  } else if (props & kAcyclic) {
527  queue_.reset(new TopOrderQueue<StateId>(fst, filter));
528  VLOG(2) << "AutoQueue: using top-order discipline";
529  } else if ((props & kUnweighted) && (Weight::Properties() & kIdempotent)) {
530  queue_.reset(new LifoQueue<StateId>());
531  VLOG(2) << "AutoQueue: using LIFO discipline";
532  } else {
533  uint64 properties;
534  // Decomposes into strongly-connected components.
535  SccVisitor<Arc> scc_visitor(&scc_, nullptr, nullptr, &properties);
536  DfsVisit(fst, &scc_visitor, filter);
537  auto nscc = *std::max_element(scc_.begin(), scc_.end()) + 1;
538  std::vector<QueueType> queue_types(nscc);
539  std::unique_ptr<Less> less;
540  std::unique_ptr<Compare> comp;
541  if (distance && (Weight::Properties() & kPath) == kPath) {
542  less.reset(new Less);
543  comp.reset(new Compare(*distance, *less));
544  }
545  // Finds the queue type to use per SCC.
546  bool unweighted;
547  bool all_trivial;
548  SccQueueType(fst, scc_, &queue_types, filter, less.get(), &all_trivial,
549  &unweighted);
550  // If unweighted and semiring is idempotent, uses LIFO queue.
551  if (unweighted) {
552  queue_.reset(new LifoQueue<StateId>());
553  VLOG(2) << "AutoQueue: using LIFO discipline";
554  return;
555  }
556  // If all the SCC are trivial, the FST is acyclic and the scc number gives
557  // the topological order.
558  if (all_trivial) {
559  queue_.reset(new TopOrderQueue<StateId>(scc_));
560  VLOG(2) << "AutoQueue: using top-order discipline";
561  return;
562  }
563  VLOG(2) << "AutoQueue: using SCC meta-discipline";
564  queues_.resize(nscc);
565  for (StateId i = 0; i < nscc; ++i) {
566  switch (queue_types[i]) {
567  case TRIVIAL_QUEUE:
568  queues_[i].reset();
569  VLOG(3) << "AutoQueue: SCC #" << i << ": using trivial discipline";
570  break;
572  queues_[i].reset(
574  VLOG(3) << "AutoQueue: SCC #" << i
575  << ": using shortest-first discipline";
576  break;
577  case LIFO_QUEUE:
578  queues_[i].reset(new LifoQueue<StateId>());
579  VLOG(3) << "AutoQueue: SCC #" << i << ": using LIFO discipline";
580  break;
581  case FIFO_QUEUE:
582  default:
583  queues_[i].reset(new FifoQueue<StateId>());
584  VLOG(3) << "AutoQueue: SCC #" << i << ": using FIFO discipine";
585  break;
586  }
587  }
588  queue_.reset(new SccQueue<StateId, QueueBase<StateId>>(scc_, &queues_));
589  }
590  }
591 
592  virtual ~AutoQueue() = default;
593 
594  StateId Head() const final { return queue_->Head(); }
595 
596  void Enqueue(StateId s) final { queue_->Enqueue(s); }
597 
598  void Dequeue() final { queue_->Dequeue(); }
599 
600  void Update(StateId s) final { queue_->Update(s); }
601 
602  bool Empty() const final { return queue_->Empty(); }
603 
604  void Clear() final { queue_->Clear(); }
605 
606  private:
607  template <class Arc, class ArcFilter, class Less>
608  static void SccQueueType(const Fst<Arc> &fst, const std::vector<StateId> &scc,
609  std::vector<QueueType> *queue_types,
610  ArcFilter filter, Less *less, bool *all_trivial,
611  bool *unweighted);
612 
613  std::unique_ptr<QueueBase<StateId>> queue_;
614  std::vector<std::unique_ptr<QueueBase<StateId>>> queues_;
615  std::vector<StateId> scc_;
616 };
617 
618 // Examines the states in an FST's strongly connected components and determines
619 // which type of queue to use per SCC. Stores result as a vector of QueueTypes
620 // which is assumed to have length equal to the number of SCCs. An arc filter
621 // is used to limit the transitions considered (e.g., only the epsilon graph).
622 // The argument all_trivial is set to true if every queue is the trivial queue.
623 // The argument unweighted is set to true if the semiring is idempotent and all
624 // the arc weights are equal to Zero() or One().
625 template <class StateId>
626 template <class Arc, class ArcFilter, class Less>
628  const std::vector<StateId> &scc,
629  std::vector<QueueType> *queue_type,
630  ArcFilter filter, Less *less,
631  bool *all_trivial, bool *unweighted) {
632  using StateId = typename Arc::StateId;
633  using Weight = typename Arc::Weight;
634  *all_trivial = true;
635  *unweighted = true;
636  for (StateId i = 0; i < queue_type->size(); ++i) {
637  (*queue_type)[i] = TRIVIAL_QUEUE;
638  }
639  for (StateIterator<Fst<Arc>> sit(fst); !sit.Done(); sit.Next()) {
640  const auto state = sit.Value();
641  for (ArcIterator<Fst<Arc>> ait(fst, state); !ait.Done(); ait.Next()) {
642  const auto &arc = ait.Value();
643  if (!filter(arc)) continue;
644  if (scc[state] == scc[arc.nextstate]) {
645  auto &type = (*queue_type)[scc[state]];
646  if (!less || ((*less)(arc.weight, Weight::One()))) {
647  type = FIFO_QUEUE;
648  } else if ((type == TRIVIAL_QUEUE) || (type == LIFO_QUEUE)) {
649  if (!(Weight::Properties() & kIdempotent) ||
650  (arc.weight != Weight::Zero() && arc.weight != Weight::One())) {
651  type = SHORTEST_FIRST_QUEUE;
652  } else {
653  type = LIFO_QUEUE;
654  }
655  }
656  if (type != TRIVIAL_QUEUE) *all_trivial = false;
657  }
658  if (!(Weight::Properties() & kIdempotent) ||
659  (arc.weight != Weight::Zero() && arc.weight != Weight::One())) {
660  *unweighted = false;
661  }
662  }
663  }
664 }
665 
666 // An A* estimate is a function object that maps from a state ID to an
667 // estimate of the shortest distance to the final states.
668 
669 // A trivial A* estimate, yielding a queue which behaves the same in Dijkstra's
670 // algorithm.
671 template <typename StateId, typename Weight>
673  constexpr Weight operator()(StateId) const { return Weight::One(); }
674 };
675 
676 // A non-trivial A* estimate using a vector of the estimated future costs.
677 template <typename StateId, typename Weight>
679  public:
680  NaturalAStarEstimate(const std::vector<Weight> &beta) :
681  beta_(beta) {}
682 
683  const Weight &operator()(StateId s) const { return beta_[s]; }
684 
685  private:
686  const std::vector<Weight> &beta_;
687 };
688 
689 // Given a vector that maps from states to weights representing the shortest
690 // distance from the initial state, a comparison function object between
691 // weights, and an estimate of the shortest distance to the final states, this
692 // class defines a comparison function object between states.
693 template <typename S, typename Less, typename Estimate>
695  public:
696  using StateId = S;
697  using Weight = typename Less::Weight;
698 
699  AStarWeightCompare(const std::vector<Weight> &weights, const Less &less,
700  const Estimate &estimate)
701  : weights_(weights), less_(less), estimate_(estimate) {}
702 
703  bool operator()(StateId s1, StateId s2) const {
704  const auto w1 = Times(weights_[s1], estimate_(s1));
705  const auto w2 = Times(weights_[s2], estimate_(s2));
706  return less_(w1, w2);
707  }
708 
709  const Estimate &GetEstimate() const { return estimate_; }
710 
711  private:
712  const std::vector<Weight> &weights_;
713  const Less &less_;
714  const Estimate &estimate_;
715 };
716 
717 // A* queue discipline templated on StateId, Weight, and Estimate.
718 template <typename S, typename Weight, typename Estimate>
720  S, AStarWeightCompare<S, NaturalLess<Weight>, Estimate>> {
721  public:
722  using StateId = S;
724 
725  NaturalAStarQueue(const std::vector<Weight> &distance,
726  const Estimate &estimate)
728  Compare(distance, less_, estimate)) {}
729 
730  ~NaturalAStarQueue() = default;
731 
732  private:
733  // This is non-static because the constructor for non-idempotent weights will
734  // result in an error.
735  const NaturalLess<Weight> less_{};
736 };
737 
738 // A state equivalence class is a function object that maps from a state ID to
739 // an equivalence class (state) ID. The trivial equivalence class maps a state
740 // ID to itself.
741 template <typename StateId>
743  StateId operator()(StateId s) const { return s; }
744 };
745 
746 // Distance-based pruning queue discipline: Enqueues a state only when its
747 // shortest distance (so far), as specified by distance, is less than (as
748 // specified by comp) the shortest distance Times() the threshold to any state
749 // in the same equivalence class, as specified by the functor class_func. The
750 // underlying queue discipline is specified by queue. The ownership of queue is
751 // given to this class.
752 //
753 // This is not a final class.
754 template <typename Queue, typename Less, typename ClassFnc>
755 class PruneQueue : public QueueBase<typename Queue::StateId> {
756  public:
757  using StateId = typename Queue::StateId;
758  using Weight = typename Less::Weight;
759 
760  PruneQueue(const std::vector<Weight> &distance, Queue *queue,
761  const Less &less, const ClassFnc &class_fnc, Weight threshold)
763  distance_(distance),
764  queue_(queue),
765  less_(less),
766  class_fnc_(class_fnc),
767  threshold_(std::move(threshold)) {}
768 
769  virtual ~PruneQueue() = default;
770 
771  StateId Head() const override { return queue_->Head(); }
772 
773  void Enqueue(StateId s) override {
774  const auto c = class_fnc_(s);
775  if (c >= class_distance_.size()) {
776  class_distance_.resize(c + 1, Weight::Zero());
777  }
778  if (less_(distance_[s], class_distance_[c])) {
779  class_distance_[c] = distance_[s];
780  }
781  // Enqueues only if below threshold limit.
782  const auto limit = Times(class_distance_[c], threshold_);
783  if (less_(distance_[s], limit)) queue_->Enqueue(s);
784  }
785 
786  void Dequeue() override { queue_->Dequeue(); }
787 
788  void Update(StateId s) override {
789  const auto c = class_fnc_(s);
790  if (less_(distance_[s], class_distance_[c])) {
791  class_distance_[c] = distance_[s];
792  }
793  queue_->Update(s);
794  }
795 
796  bool Empty() const override { return queue_->Empty(); }
797 
798  void Clear() override { queue_->Clear(); }
799 
800  private:
801  const std::vector<Weight> &distance_; // Shortest distance to state.
802  std::unique_ptr<Queue> queue_;
803  const Less &less_; // Borrowed reference.
804  const ClassFnc &class_fnc_; // Equivalence class functor.
805  Weight threshold_; // Pruning weight threshold.
806  std::vector<Weight> class_distance_; // Shortest distance to class.
807 };
808 
809 // Pruning queue discipline (see above) using the weight's natural order for the
810 // comparison function. The ownership of the queue argument is given to this
811 // class.
812 template <typename Queue, typename Weight, typename ClassFnc>
813 class NaturalPruneQueue final
814  : public PruneQueue<Queue, NaturalLess<Weight>, ClassFnc> {
815  public:
816  using StateId = typename Queue::StateId;
817 
818  NaturalPruneQueue(const std::vector<Weight> &distance, Queue *queue,
819  const ClassFnc &class_fnc, Weight threshold)
820  : PruneQueue<Queue, NaturalLess<Weight>, ClassFnc>(
821  distance, queue, NaturalLess<Weight>(), class_fnc, threshold) {}
822 
823  virtual ~NaturalPruneQueue() = default;
824 };
825 
826 // Filter-based pruning queue discipline: enqueues a state only if allowed by
827 // the filter, specified by the state filter functor argument. The underlying
828 // queue discipline is specified by the queue argument. The ownership of the
829 // queue is given to this class.
830 template <typename Queue, typename Filter>
831 class FilterQueue : public QueueBase<typename Queue::StateId> {
832  public:
833  using StateId = typename Queue::StateId;
834 
835  FilterQueue(Queue *queue, const Filter &filter)
836  : QueueBase<StateId>(OTHER_QUEUE), queue_(queue), filter_(filter) {}
837 
838  virtual ~FilterQueue() = default;
839 
840  StateId Head() const final { return queue_->Head(); }
841 
842  // Enqueues only if allowed by state filter.
843  void Enqueue(StateId s) final {
844  if (filter_(s)) queue_->Enqueue(s);
845  }
846 
847  void Dequeue() final { queue_->Dequeue(); }
848 
849  void Update(StateId s) final {}
850 
851  bool Empty() const final { return queue_->Empty(); }
852 
853  void Clear() final { queue_->Clear(); }
854 
855  private:
856  std::unique_ptr<Queue> queue_;
857  const Filter &filter_;
858 };
859 
860 } // namespace fst
861 
862 #endif // FST_QUEUE_H_
virtual bool Empty() const =0
void Clear() override
Definition: queue.h:150
bool Empty() const final
Definition: queue.h:174
bool Empty() const final
Definition: queue.h:120
void Enqueue(StateId s) override
Definition: queue.h:142
StateId Head() const final
Definition: queue.h:322
void Update(StateId s) override
Definition: queue.h:788
void Enqueue(StateId s) override
Definition: queue.h:200
typename NaturalLess< Weight >::Weight Weight
Definition: queue.h:247
void Clear() final
Definition: queue.h:122
StateId Head() const final
Definition: queue.h:166
void SetError(bool error)
Definition: queue.h:80
void Clear() override
Definition: queue.h:228
uint64_t uint64
Definition: types.h:32
void Update(StateId) final
Definition: queue.h:118
QueueType
Definition: queue.h:55
NaturalAStarQueue(const std::vector< Weight > &distance, const Estimate &estimate)
Definition: queue.h:725
PruneQueue(const std::vector< Weight > &distance, Queue *queue, const Less &less, const ClassFnc &class_fnc, Weight threshold)
Definition: queue.h:760
NaturalShortestFirstQueue(const std::vector< Weight > &distance)
Definition: queue.h:274
StateWeightCompare(const std::vector< Weight > &weights, const Less &less)
Definition: queue.h:249
bool Empty() const final
Definition: queue.h:390
StateId Head() const final
Definition: queue.h:112
typename Queue::StateId StateId
Definition: queue.h:833
void Enqueue(StateId s) final
Definition: queue.h:439
void Clear() final
Definition: queue.h:392
void Enqueue(StateId s) final
Definition: queue.h:114
constexpr uint64 kTopSorted
Definition: properties.h:100
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:94
ShortestFirstQueue(Compare comp)
Definition: queue.h:193
void Enqueue(StateId s) final
Definition: queue.h:596
void Enqueue(StateId s) final
Definition: queue.h:371
ExpectationWeight< X1, X2 > Times(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
StateId Head() const override
Definition: queue.h:198
void Clear() final
Definition: queue.h:483
void Update(StateId) override
Definition: queue.h:146
bool operator()(StateId s1, StateId s2) const
Definition: queue.h:703
typename NaturalLess< Weight >::Weight Weight
Definition: queue.h:758
void Update(StateId) final
Definition: queue.h:172
bool Empty() const override
Definition: queue.h:148
TopOrderQueue(const Fst< Arc > &fst, ArcFilter filter)
Definition: queue.h:296
const Weight & operator()(StateId s) const
Definition: queue.h:683
NaturalAStarEstimate(const std::vector< Weight > &beta)
Definition: queue.h:680
void Dequeue() final
Definition: queue.h:116
bool Error() const
Definition: queue.h:82
StateId Head() const override
Definition: queue.h:771
constexpr int kNoStateId
Definition: fst.h:180
virtual void Dequeue()=0
void Dequeue() final
Definition: queue.h:383
QueueBase(QueueType type)
Definition: queue.h:78
virtual uint64 Properties(uint64 mask, bool test) const =0
void Update(StateId) final
Definition: queue.h:340
StateId Head() const final
Definition: queue.h:424
#define FSTERROR()
Definition: util.h:35
void Enqueue(StateId s) override
Definition: queue.h:773
constexpr uint64 kUnweighted
Definition: properties.h:87
void Update(StateId s) final
Definition: queue.h:849
StateId operator()(StateId s) const
Definition: queue.h:743
bool Empty() const final
Definition: queue.h:469
virtual void Update(StateId)=0
void Update(StateId s) final
Definition: queue.h:600
void Enqueue(StateId s) final
Definition: queue.h:168
virtual void Clear()=0
virtual void Enqueue(StateId)=0
constexpr Weight operator()(StateId) const
Definition: queue.h:673
typename NaturalLess< Weight >::Weight Weight
Definition: queue.h:697
constexpr uint64 kIdempotent
Definition: weight.h:123
AutoQueue(const Fst< Arc > &fst, const std::vector< typename Arc::Weight > *distance, ArcFilter filter)
Definition: queue.h:514
#define VLOG(level)
Definition: log.h:49
virtual StateId Start() const =0
void Dequeue() final
Definition: queue.h:335
NaturalPruneQueue(const std::vector< Weight > &distance, Queue *queue, const ClassFnc &class_fnc, Weight threshold)
Definition: queue.h:818
void Dequeue() final
Definition: queue.h:847
void Dequeue() override
Definition: queue.h:209
const Estimate & GetEstimate() const
Definition: queue.h:709
void Clear() final
Definition: queue.h:344
bool Empty() const override
Definition: queue.h:796
void Dequeue() override
Definition: queue.h:144
TopOrderQueue(const std::vector< StateId > &order)
Definition: queue.h:313
AStarWeightCompare(const std::vector< Weight > &weights, const Less &less, const Estimate &estimate)
Definition: queue.h:699
StateId Head() const final
Definition: queue.h:840
virtual ~QueueBase()
Definition: queue.h:74
void Dequeue() final
Definition: queue.h:457
StateId Head() const final
Definition: queue.h:369
StateId Head() const final
Definition: queue.h:594
void Enqueue(StateId s) final
Definition: queue.h:324
void Dequeue() final
Definition: queue.h:170
void Update(StateId s) override
Definition: queue.h:217
void Clear() final
Definition: queue.h:176
void Update(StateId) final
Definition: queue.h:388
constexpr uint64 kAcyclic
Definition: properties.h:92
SccQueue(const std::vector< StateId > &scc, std::vector< std::unique_ptr< Queue >> *queue)
Definition: queue.h:414
constexpr uint64 kPath
Definition: weight.h:126
bool Empty() const override
Definition: queue.h:226
void Update(StateId s) final
Definition: queue.h:465
FilterQueue(Queue *queue, const Filter &filter)
Definition: queue.h:835
QueueType Type() const
Definition: queue.h:84
Queue::StateId StateId
Definition: queue.h:72
bool operator()(const StateId s1, const StateId s2) const
Definition: queue.h:252
void Enqueue(StateId s) final
Definition: queue.h:843
void Dequeue() override
Definition: queue.h:786
bool Empty() const final
Definition: queue.h:851
void Clear() final
Definition: queue.h:604
virtual StateId Head() const =0
typename Queue::StateId StateId
Definition: queue.h:816
void Clear() override
Definition: queue.h:798
void Clear() final
Definition: queue.h:853
void Dequeue() final
Definition: queue.h:598
StateId Head() const override
Definition: queue.h:140
bool Empty() const final
Definition: queue.h:342
bool Empty() const final
Definition: queue.h:602
constexpr uint64 kCyclic
Definition: properties.h:90
const Compare & GetCompare() const
Definition: queue.h:233