1 // queue.h 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // Author: allauzen (at) cs.nyu.edu (Cyril Allauzen) 16 // 17 // \file 18 // Functions and classes for various Fst state queues with 19 // a unified interface. 20 21 #ifndef FST_LIB_QUEUE_H__ 22 #define FST_LIB_QUEUE_H__ 23 24 #include <deque> 25 #include <vector> 26 27 #include "fst/lib/arcfilter.h" 28 #include "fst/lib/connect.h" 29 #include "fst/lib/heap.h" 30 #include "fst/lib/topsort.h" 31 32 namespace fst { 33 34 // template <class S> 35 // class Queue { 36 // public: 37 // typedef typename S StateId; 38 // 39 // // Ctr: may need args (e.g., Fst, comparator) for some queues 40 // Queue(...); 41 // // Returns the head of the queue 42 // StateId Head() const; 43 // // Inserts a state 44 // void Enqueue(StateId s); 45 // // Removes the head of the queue 46 // void Dequeue(); 47 // // Updates ordering of state s when weight changes, if necessary 48 // void Update(StateId s); 49 // // Does the queue contain no elements? 50 // bool Empty() const; 51 // // Remove all states from queue 52 // void Clear(); 53 // }; 54 55 // State queue types. 56 enum QueueType { 57 TRIVIAL_QUEUE = 0, // Single state queue 58 FIFO_QUEUE = 1, // First-in, first-out queue 59 LIFO_QUEUE = 2, // Last-in, first-out queue 60 SHORTEST_FIRST_QUEUE = 3, // Shortest-first queue 61 TOP_ORDER_QUEUE = 4, // Topologically-ordered queue 62 STATE_ORDER_QUEUE = 5, // State-ID ordered queue 63 SCC_QUEUE = 6, // Component graph top-ordered meta-queue 64 AUTO_QUEUE = 7, // Auto-selected queue 65 OTHER_QUEUE = 8 66 }; 67 68 69 // QueueBase, templated on the StateId, is the base class shared by the 70 // queues considered by AutoQueue. 71 template <class S> 72 class QueueBase { 73 public: 74 typedef S StateId; 75 76 QueueBase(QueueType type) : queue_type_(type) {} 77 virtual ~QueueBase() {} 78 StateId Head() const { return Head_(); } 79 void Enqueue(StateId s) { Enqueue_(s); } 80 void Dequeue() { Dequeue_(); } 81 void Update(StateId s) { Update_(s); } 82 bool Empty() const { return Empty_(); } 83 void Clear() { Clear_(); } 84 QueueType Type() { return queue_type_; } 85 86 private: 87 virtual StateId Head_() const = 0; 88 virtual void Enqueue_(StateId s) = 0; 89 virtual void Dequeue_() = 0; 90 virtual void Update_(StateId s) = 0; 91 virtual bool Empty_() const = 0; 92 virtual void Clear_() = 0; 93 94 QueueType queue_type_; 95 }; 96 97 98 // Trivial queue discipline, templated on the StateId. You may enqueue 99 // at most one state at a time. It is used for strongly connected components 100 // with only one state and no self loops. 101 template <class S> 102 class TrivialQueue : public QueueBase<S> { 103 public: 104 typedef S StateId; 105 106 TrivialQueue() : QueueBase<S>(TRIVIAL_QUEUE), front_(kNoStateId) {} 107 StateId Head() const { return front_; } 108 void Enqueue(StateId s) { front_ = s; } 109 void Dequeue() { front_ = kNoStateId; } 110 void Update(StateId s) {} 111 bool Empty() const { return front_ == kNoStateId; } 112 void Clear() { front_ = kNoStateId; } 113 114 115 private: 116 virtual StateId Head_() const { return Head(); } 117 virtual void Enqueue_(StateId s) { Enqueue(s); } 118 virtual void Dequeue_() { Dequeue(); } 119 virtual void Update_(StateId s) { Update(s); } 120 virtual bool Empty_() const { return Empty(); } 121 virtual void Clear_() { return Clear(); } 122 123 StateId front_; 124 }; 125 126 127 // First-in, first-out queue discipline, templated on the StateId. 128 template <class S> 129 class FifoQueue : public QueueBase<S>, public deque<S> { 130 public: 131 using deque<S>::back; 132 using deque<S>::push_front; 133 using deque<S>::pop_back; 134 using deque<S>::empty; 135 using deque<S>::clear; 136 137 typedef S StateId; 138 139 FifoQueue() : QueueBase<S>(FIFO_QUEUE) {} 140 StateId Head() const { return back(); } 141 void Enqueue(StateId s) { push_front(s); } 142 void Dequeue() { pop_back(); } 143 void Update(StateId s) {} 144 bool Empty() const { return empty(); } 145 void Clear() { clear(); } 146 147 private: 148 virtual StateId Head_() const { return Head(); } 149 virtual void Enqueue_(StateId s) { Enqueue(s); } 150 virtual void Dequeue_() { Dequeue(); } 151 virtual void Update_(StateId s) { Update(s); } 152 virtual bool Empty_() const { return Empty(); } 153 virtual void Clear_() { return Clear(); } 154 }; 155 156 157 // Last-in, first-out queue discipline, templated on the StateId. 158 template <class S> 159 class LifoQueue : public QueueBase<S>, public deque<S> { 160 public: 161 using deque<S>::front; 162 using deque<S>::push_front; 163 using deque<S>::pop_front; 164 using deque<S>::empty; 165 using deque<S>::clear; 166 167 typedef S StateId; 168 169 LifoQueue() : QueueBase<S>(LIFO_QUEUE) {} 170 StateId Head() const { return front(); } 171 void Enqueue(StateId s) { push_front(s); } 172 void Dequeue() { pop_front(); } 173 void Update(StateId s) {} 174 bool Empty() const { return empty(); } 175 void Clear() { clear(); } 176 177 private: 178 virtual StateId Head_() const { return Head(); } 179 virtual void Enqueue_(StateId s) { Enqueue(s); } 180 virtual void Dequeue_() { Dequeue(); } 181 virtual void Update_(StateId s) { Update(s); } 182 virtual bool Empty_() const { return Empty(); } 183 virtual void Clear_() { return Clear(); } 184 }; 185 186 187 // Shortest-first queue discipline, templated on the StateId and 188 // comparison function object. Comparison function object COMP is 189 // used to compare two StateIds. If a (single) state's order changes, 190 // it can be reordered in the queue with a call to Update(). 191 template <typename S, typename C> 192 class ShortestFirstQueue : public QueueBase<S> { 193 public: 194 typedef S StateId; 195 typedef C Compare; 196 197 ShortestFirstQueue(C comp) 198 : QueueBase<S>(SHORTEST_FIRST_QUEUE), heap_(comp) {} 199 200 StateId Head() const { return heap_.Top(); } 201 202 void Enqueue(StateId s) { 203 for (StateId i = key_.size(); i <= s; ++i) 204 key_.push_back(kNoKey); 205 key_[s] = heap_.Insert(s); 206 } 207 208 void Dequeue() { 209 key_[heap_.Pop()] = kNoKey; 210 } 211 212 void Update(StateId s) { 213 if (s >= (StateId)key_.size() || key_[s] == kNoKey) { 214 Enqueue(s); 215 } else { 216 heap_.Update(key_[s], s); 217 } 218 } 219 220 bool Empty() const { return heap_.Empty(); } 221 222 void Clear() { 223 heap_.Clear(); 224 key_.clear(); 225 } 226 227 private: 228 Heap<S, C> heap_; 229 vector<ssize_t> key_; 230 231 virtual StateId Head_() const { return Head(); } 232 virtual void Enqueue_(StateId s) { Enqueue(s); } 233 virtual void Dequeue_() { Dequeue(); } 234 virtual void Update_(StateId s) { Update(s); } 235 virtual bool Empty_() const { return Empty(); } 236 virtual void Clear_() { return Clear(); } 237 }; 238 239 240 // Given a vector that maps from states to weights and a Less 241 // comparison function object between weights, this class defines a 242 // comparison function object between states. 243 template <typename S, typename L> 244 class StateWeightCompare { 245 public: 246 typedef L Less; 247 typedef typename L::Weight Weight; 248 typedef S StateId; 249 250 StateWeightCompare(const vector<Weight>* weights, const L &less) 251 : weights_(weights), less_(less) {} 252 253 bool operator()(const S x, const S y) const { 254 return less_((*weights_)[x], (*weights_)[y]); 255 } 256 257 private: 258 const vector<Weight>* weights_; 259 L less_; 260 }; 261 262 263 // Shortest-first queue discipline, templated on the StateId and Weight is 264 // specialized to use the weight's natural order for the comparion function. 265 template <typename S, typename W> 266 class NaturalShortestFirstQueue : 267 public ShortestFirstQueue<S, StateWeightCompare<S, NaturalLess<W> > > { 268 public: 269 typedef StateWeightCompare<S, NaturalLess<W> > C; 270 271 NaturalShortestFirstQueue(vector<W> *distance) : 272 ShortestFirstQueue<S, C>(C(distance, less_)) {} 273 274 private: 275 NaturalLess<W> less_; 276 }; 277 278 279 // Topological-order queue discipline, templated on the StateId. 280 // States are ordered in the queue topologically. The FST must be acyclic. 281 template <class S> 282 class TopOrderQueue : public QueueBase<S> { 283 public: 284 typedef S StateId; 285 286 // This constructor computes the top. order. It accepts an arc filter 287 // to limit the transitions considered in that computation (e.g., only 288 // the epsilon graph). 289 template <class Arc, class ArcFilter> 290 291 TopOrderQueue(const Fst<Arc> &fst, ArcFilter filter) 292 : QueueBase<S>(TOP_ORDER_QUEUE), front_(0), back_(kNoStateId), 293 order_(0), state_(0) { 294 bool acyclic; 295 TopOrderVisitor<Arc> top_order_visitor(&order_, &acyclic); 296 DfsVisit(fst, &top_order_visitor, filter); 297 if (!acyclic) 298 LOG(FATAL) << "TopOrderQueue: fst is not acyclic."; 299 state_.resize(order_.size(), kNoStateId); 300 } 301 302 // This constructor is passed the top. order, useful when we know it 303 // beforehand. 304 TopOrderQueue(const vector<StateId> &order) 305 : QueueBase<S>(TOP_ORDER_QUEUE), front_(0), back_(kNoStateId), 306 order_(order), state_(order.size(), kNoStateId) {} 307 308 StateId Head() const { return state_[front_]; } 309 310 void Enqueue(StateId s) { 311 if (front_ > back_) front_ = back_ = order_[s]; 312 else if (order_[s] > back_) back_ = order_[s]; 313 else if (order_[s] < front_) front_ = order_[s]; 314 state_[order_[s]] = s; 315 } 316 317 void Dequeue() { 318 state_[front_] = kNoStateId; 319 while ((front_ <= back_) && (state_[front_] == kNoStateId)) ++front_; 320 } 321 322 void Update(StateId s) {} 323 324 bool Empty() const { return front_ > back_; } 325 326 void Clear() { 327 for (StateId i = front_; i <= back_; ++i) state_[i] = kNoStateId; 328 back_ = kNoStateId; 329 front_ = 0; 330 } 331 332 private: 333 StateId front_; 334 StateId back_; 335 vector<StateId> order_; 336 vector<StateId> state_; 337 338 virtual StateId Head_() const { return Head(); } 339 virtual void Enqueue_(StateId s) { Enqueue(s); } 340 virtual void Dequeue_() { Dequeue(); } 341 virtual void Update_(StateId s) { Update(s); } 342 virtual bool Empty_() const { return Empty(); } 343 virtual void Clear_() { return Clear(); } 344 345 }; 346 347 348 // State order queue discipline, templated on the StateId. 349 // States are ordered in the queue by state Id. 350 template <class S> 351 class StateOrderQueue : public QueueBase<S> { 352 public: 353 typedef S StateId; 354 355 StateOrderQueue() 356 : QueueBase<S>(STATE_ORDER_QUEUE), front_(0), back_(kNoStateId) {} 357 358 StateId Head() const { return front_; } 359 360 void Enqueue(StateId s) { 361 if (front_ > back_) front_ = back_ = s; 362 else if (s > back_) back_ = s; 363 else if (s < front_) front_ = s; 364 while ((StateId)enqueued_.size() <= s) enqueued_.push_back(false); 365 enqueued_[s] = true; 366 } 367 368 void Dequeue() { 369 enqueued_[front_] = false; 370 while ((front_ <= back_) && (enqueued_[front_] == false)) ++front_; 371 } 372 373 void Update(StateId s) {} 374 375 bool Empty() const { return front_ > back_; } 376 377 void Clear() { 378 for (StateId i = front_; i <= back_; ++i) enqueued_[i] = false; 379 front_ = 0; 380 back_ = kNoStateId; 381 } 382 383 private: 384 StateId front_; 385 StateId back_; 386 vector<bool> enqueued_; 387 388 virtual StateId Head_() const { return Head(); } 389 virtual void Enqueue_(StateId s) { Enqueue(s); } 390 virtual void Dequeue_() { Dequeue(); } 391 virtual void Update_(StateId s) { Update(s); } 392 virtual bool Empty_() const { return Empty(); } 393 virtual void Clear_() { return Clear(); } 394 395 }; 396 397 398 // SCC topological-order meta-queue discipline, templated on the StateId S 399 // and a queue Q, which is used inside each SCC. It visits the SCC's 400 // of an FST in topological order. Its constructor is passed the queues to 401 // to use within an SCC. 402 template <class S, class Q> 403 class SccQueue : public QueueBase<S> { 404 public: 405 typedef S StateId; 406 typedef Q Queue; 407 408 // Constructor takes a vector specifying the SCC number per state 409 // and a vector giving the queue to use per SCC number. 410 SccQueue(const vector<StateId> &scc, vector<Queue*> *queue) 411 : QueueBase<S>(SCC_QUEUE), queue_(queue), scc_(scc), front_(0), 412 back_(kNoStateId) {} 413 414 StateId Head() const { 415 while ((front_ <= back_) && 416 (((*queue_)[front_] && (*queue_)[front_]->Empty()) 417 || (((*queue_)[front_] == 0) && 418 ((front_ > (StateId)trivial_queue_.size()) 419 || (trivial_queue_[front_] == kNoStateId))))) 420 ++front_; 421 if (front_ > back_) 422 LOG(FATAL) << "SccQueue: head of empty queue"; 423 if ((*queue_)[front_]) 424 return (*queue_)[front_]->Head(); 425 else 426 return trivial_queue_[front_]; 427 } 428 429 void Enqueue(StateId s) { 430 if (front_ > back_) front_ = back_ = scc_[s]; 431 else if (scc_[s] > back_) back_ = scc_[s]; 432 else if (scc_[s] < front_) front_ = scc_[s]; 433 if ((*queue_)[scc_[s]]) { 434 (*queue_)[scc_[s]]->Enqueue(s); 435 } else { 436 while ( (StateId)trivial_queue_.size() <= scc_[s]) 437 trivial_queue_.push_back(kNoStateId); 438 trivial_queue_[scc_[s]] = s; 439 } 440 } 441 442 void Dequeue() { 443 if (front_ > back_) 444 LOG(FATAL) << "SccQueue: dequeue of empty queue"; 445 if ((*queue_)[front_]) 446 (*queue_)[front_]->Dequeue(); 447 else if (front_ < (StateId)trivial_queue_.size()) 448 trivial_queue_[front_] = kNoStateId; 449 } 450 451 void Update(StateId s) { 452 if ((*queue_)[scc_[s]]) 453 (*queue_)[scc_[s]]->Update(s); 454 } 455 456 bool Empty() const { 457 if (front_ < back_) // Queue scc # back_ not empty unless back_==front_ 458 return false; 459 else if (front_ > back_) 460 return true; 461 else if ((*queue_)[front_]) 462 return (*queue_)[front_]->Empty(); 463 else 464 return (front_ > (StateId)trivial_queue_.size()) 465 || (trivial_queue_[front_] == kNoStateId); 466 } 467 468 void Clear() { 469 for (StateId i = front_; i <= back_; ++i) 470 if ((*queue_)[i]) 471 (*queue_)[i]->Clear(); 472 else if (i < (StateId)trivial_queue_.size()) 473 trivial_queue_[i] = kNoStateId; 474 front_ = 0; 475 back_ = kNoStateId; 476 } 477 478 private: 479 vector<Queue*> *queue_; 480 const vector<StateId> &scc_; 481 mutable StateId front_; 482 StateId back_; 483 vector<StateId> trivial_queue_; 484 485 virtual StateId Head_() const { return Head(); } 486 virtual void Enqueue_(StateId s) { Enqueue(s); } 487 virtual void Dequeue_() { Dequeue(); } 488 virtual void Update_(StateId s) { Update(s); } 489 virtual bool Empty_() const { return Empty(); } 490 virtual void Clear_() { return Clear(); } 491 }; 492 493 494 // Automatic queue discipline, templated on the StateId. It selects a 495 // queue discipline for a given FST based on its properties. 496 template <class S> 497 class AutoQueue : public QueueBase<S> { 498 public: 499 typedef S StateId; 500 501 // This constructor takes a state distance vector that, if non-null and if 502 // the Weight type has the path property, will entertain the 503 // shortest-first queue using the natural order w.r.t to the distance. 504 template <class Arc, class ArcFilter> 505 AutoQueue(const Fst<Arc> &fst, const vector<typename Arc::Weight> *distance, 506 ArcFilter filter) : QueueBase<S>(AUTO_QUEUE) { 507 typedef typename Arc::Weight Weight; 508 typedef StateWeightCompare< StateId, NaturalLess<Weight> > Compare; 509 510 // First check if the FST is known to have these properties. 511 uint64 props = fst.Properties(kAcyclic | kCyclic | 512 kTopSorted | kUnweighted, false); 513 if ((props & kTopSorted) || fst.Start() == kNoStateId) { 514 queue_ = new StateOrderQueue<StateId>(); 515 VLOG(2) << "AutoQueue: using state-order discipline"; 516 } else if (props & kAcyclic) { 517 queue_ = new TopOrderQueue<StateId>(fst, filter); 518 VLOG(2) << "AutoQueue: using top-order discipline"; 519 } else if ((props & kUnweighted) && (Weight::Properties() & kIdempotent)) { 520 queue_ = new LifoQueue<StateId>(); 521 VLOG(2) << "AutoQueue: using LIFO discipline"; 522 } else { 523 uint64 props; 524 // Decompose into strongly-connected components. 525 SccVisitor<Arc> scc_visitor(&scc_, 0, 0, &props); 526 DfsVisit(fst, &scc_visitor, filter); 527 StateId nscc = *max_element(scc_.begin(), scc_.end()) + 1; 528 vector<QueueType> queue_types(nscc); 529 NaturalLess<Weight> *less = 0; 530 Compare *comp = 0; 531 if (distance && (Weight::Properties() & kPath)) { 532 less = new NaturalLess<Weight>; 533 comp = new Compare(distance, *less); 534 } 535 // Find the queue type to use per SCC. 536 bool unweighted; 537 bool all_trivial; 538 SccQueueType(fst, scc_, &queue_types, filter, less, &all_trivial, 539 &unweighted); 540 // If unweighted and semiring is idempotent, use lifo queue. 541 if (unweighted) { 542 queue_ = new LifoQueue<StateId>(); 543 VLOG(2) << "AutoQueue: using LIFO discipline"; 544 delete comp; 545 delete less; 546 return; 547 } 548 // If all the scc are trivial, FST is acyclic and the scc# gives 549 // the topological order. 550 if (all_trivial) { 551 queue_ = new TopOrderQueue<StateId>(scc_); 552 VLOG(2) << "AutoQueue: using top-order discipline"; 553 delete comp; 554 delete less; 555 return; 556 } 557 VLOG(2) << "AutoQueue: using SCC meta-discipline"; 558 queues_.resize(nscc); 559 for (StateId i = 0; i < nscc; ++i) { 560 switch(queue_types[i]) { 561 case TRIVIAL_QUEUE: 562 queues_[i] = 0; 563 VLOG(3) << "AutoQueue: SCC #" << i 564 << ": using trivial discipline"; 565 break; 566 case SHORTEST_FIRST_QUEUE: 567 CHECK(comp); 568 queues_[i] = new ShortestFirstQueue<StateId, Compare>(*comp); 569 VLOG(3) << "AutoQueue: SCC #" << i << 570 ": using shortest-first discipline"; 571 break; 572 case LIFO_QUEUE: 573 queues_[i] = new LifoQueue<StateId>(); 574 VLOG(3) << "AutoQueue: SCC #" << i 575 << ": using LIFO disciplle"; 576 break; 577 case FIFO_QUEUE: 578 default: 579 queues_[i] = new FifoQueue<StateId>(); 580 VLOG(3) << "AutoQueue: SCC #" << i 581 << ": using FIFO disciplle"; 582 break; 583 } 584 } 585 queue_ = new SccQueue< StateId, QueueBase<StateId> >(scc_, &queues_); 586 delete comp; 587 delete less; 588 } 589 } 590 591 ~AutoQueue() { 592 for (StateId i = 0; i < (StateId)queues_.size(); ++i) /*naucen-edit*/ 593 delete queues_[i]; 594 delete queue_; 595 } 596 597 StateId Head() const { return queue_->Head(); } 598 599 void Enqueue(StateId s) { queue_->Enqueue(s); } 600 601 void Dequeue() { queue_->Dequeue(); } 602 603 void Update(StateId s) { queue_->Update(s); } 604 605 bool Empty() const { return queue_->Empty(); } 606 607 void Clear() { queue_->Clear(); } 608 609 610 private: 611 QueueBase<StateId> *queue_; 612 vector< QueueBase<StateId>* > queues_; 613 vector<StateId> scc_; 614 615 template <class Arc, class ArcFilter, class Less> 616 static void SccQueueType(const Fst<Arc> &fst, 617 const vector<StateId> &scc, 618 vector<QueueType> *queue_types, 619 ArcFilter filter, Less *less, 620 bool *all_trivial, bool *unweighted); 621 622 virtual StateId Head_() const { return Head(); } 623 624 virtual void Enqueue_(StateId s) { Enqueue(s); } 625 626 virtual void Dequeue_() { Dequeue(); } 627 628 virtual void Update_(StateId s) { Update(s); } 629 630 virtual bool Empty_() const { return Empty(); } 631 632 virtual void Clear_() { return Clear(); } 633 }; 634 635 636 // Examines the states in an Fst's strongly connected components and 637 // determines which type of queue to use per SCC. Stores result in 638 // vector QUEUE_TYPES, which is assumed to have length equal to the 639 // number of SCCs. An arc filter is used to limit the transitions 640 // considered (e.g., only the epsilon graph). ALL_TRIVIAL is set 641 // to true if every queue is the trivial queue. UNWEIGHTED is set to 642 // true if the semiring is idempotent and all the arc weights are equal to 643 // Zero() or One(). 644 template <class StateId> 645 template <class A, class ArcFilter, class Less> 646 void AutoQueue<StateId>::SccQueueType(const Fst<A> &fst, 647 const vector<StateId> &scc, 648 vector<QueueType> *queue_type, 649 ArcFilter filter, Less *less, 650 bool *all_trivial, bool *unweighted) { 651 typedef A Arc; 652 typedef typename A::StateId StateId; 653 typedef typename A::Weight Weight; 654 655 *all_trivial = true; 656 *unweighted = true; 657 658 for (StateId i = 0; i < (StateId)queue_type->size(); ++i) 659 (*queue_type)[i] = TRIVIAL_QUEUE; 660 661 for (StateIterator< Fst<Arc> > sit(fst); !sit.Done(); sit.Next()) { 662 StateId state = sit.Value(); 663 for (ArcIterator< Fst<Arc> > ait(fst, state); 664 !ait.Done(); 665 ait.Next()) { 666 const Arc &arc = ait.Value(); 667 if (!filter(arc)) continue; 668 if (scc[state] == scc[arc.nextstate]) { 669 QueueType &type = (*queue_type)[scc[state]]; 670 if (!less || ((*less)(arc.weight, Weight::One()))) 671 type = FIFO_QUEUE; 672 else if ((type == TRIVIAL_QUEUE) || (type == LIFO_QUEUE)) 673 if (!(Weight::Properties() & kIdempotent) || 674 (arc.weight != Weight::Zero() && arc.weight != Weight::One())) 675 type = SHORTEST_FIRST_QUEUE; 676 else 677 type = LIFO_QUEUE; 678 if (type != TRIVIAL_QUEUE) *all_trivial = false; 679 } 680 if (!(Weight::Properties() & kIdempotent) || 681 (arc.weight != Weight::Zero() && arc.weight != Weight::One())) 682 *unweighted = false; 683 } 684 } 685 } 686 687 } // namespace fst 688 689 #endif 690