14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// queue.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Author: allauzen@cs.nyu.edu (Cyril Allauzen) 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Functions and classes for various Fst state queues with 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// a unified interface. 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_QUEUE_H__ 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_QUEUE_H__ 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <deque> 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <vector> 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/arcfilter.h" 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/connect.h" 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/heap.h" 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/topsort.h" 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// template <class S> 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// class Queue { 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// public: 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// typedef typename S StateId; 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Ctr: may need args (e.g., Fst, comparator) for some queues 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Queue(...); 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Returns the head of the queue 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// StateId Head() const; 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Inserts a state 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// void Enqueue(StateId s); 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Removes the head of the queue 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// void Dequeue(); 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Updates ordering of state s when weight changes, if necessary 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// void Update(StateId s); 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Does the queue contain no elements? 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// bool Empty() const; 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// // Remove all states from queue 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// void Clear(); 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// }; 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// State queue types. 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectenum QueueType { 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project TRIVIAL_QUEUE = 0, // Single state queue 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FIFO_QUEUE = 1, // First-in, first-out queue 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LIFO_QUEUE = 2, // Last-in, first-out queue 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SHORTEST_FIRST_QUEUE = 3, // Shortest-first queue 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project TOP_ORDER_QUEUE = 4, // Topologically-ordered queue 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project STATE_ORDER_QUEUE = 5, // State-ID ordered queue 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SCC_QUEUE = 6, // Component graph top-ordered meta-queue 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AUTO_QUEUE = 7, // Auto-selected queue 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project OTHER_QUEUE = 8 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project }; 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// QueueBase, templated on the StateId, is the base class shared by the 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// queues considered by AutoQueue. 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class S> 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass QueueBase { 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef S StateId; 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project QueueBase(QueueType type) : queue_type_(type) {} 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual ~QueueBase() {} 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Head() const { return Head_(); } 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Enqueue(StateId s) { Enqueue_(s); } 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Dequeue() { Dequeue_(); } 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Update(StateId s) { Update_(s); } 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Empty() const { return Empty_(); } 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Clear() { Clear_(); } 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project QueueType Type() { return queue_type_; } 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Head_() const = 0; 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Enqueue_(StateId s) = 0; 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Dequeue_() = 0; 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Update_(StateId s) = 0; 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool Empty_() const = 0; 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Clear_() = 0; 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project QueueType queue_type_; 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Trivial queue discipline, templated on the StateId. You may enqueue 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// at most one state at a time. It is used for strongly connected components 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// with only one state and no self loops. 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class S> 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass TrivialQueue : public QueueBase<S> { 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectpublic: 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef S StateId; 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project TrivialQueue() : QueueBase<S>(TRIVIAL_QUEUE), front_(kNoStateId) {} 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Head() const { return front_; } 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Enqueue(StateId s) { front_ = s; } 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Dequeue() { front_ = kNoStateId; } 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Update(StateId s) {} 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Empty() const { return front_ == kNoStateId; } 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Clear() { front_ = kNoStateId; } 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectprivate: 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Head_() const { return Head(); } 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Enqueue_(StateId s) { Enqueue(s); } 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Dequeue_() { Dequeue(); } 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Update_(StateId s) { Update(s); } 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool Empty_() const { return Empty(); } 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Clear_() { return Clear(); } 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId front_; 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// First-in, first-out queue discipline, templated on the StateId. 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class S> 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass FifoQueue : public QueueBase<S>, public deque<S> { 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using deque<S>::back; 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using deque<S>::push_front; 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using deque<S>::pop_back; 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using deque<S>::empty; 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using deque<S>::clear; 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef S StateId; 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project FifoQueue() : QueueBase<S>(FIFO_QUEUE) {} 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Head() const { return back(); } 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Enqueue(StateId s) { push_front(s); } 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Dequeue() { pop_back(); } 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Update(StateId s) {} 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Empty() const { return empty(); } 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Clear() { clear(); } 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Head_() const { return Head(); } 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Enqueue_(StateId s) { Enqueue(s); } 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Dequeue_() { Dequeue(); } 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Update_(StateId s) { Update(s); } 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool Empty_() const { return Empty(); } 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Clear_() { return Clear(); } 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Last-in, first-out queue discipline, templated on the StateId. 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class S> 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass LifoQueue : public QueueBase<S>, public deque<S> { 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using deque<S>::front; 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using deque<S>::push_front; 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using deque<S>::pop_front; 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using deque<S>::empty; 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project using deque<S>::clear; 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef S StateId; 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LifoQueue() : QueueBase<S>(LIFO_QUEUE) {} 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Head() const { return front(); } 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Enqueue(StateId s) { push_front(s); } 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Dequeue() { pop_front(); } 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Update(StateId s) {} 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Empty() const { return empty(); } 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Clear() { clear(); } 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Head_() const { return Head(); } 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Enqueue_(StateId s) { Enqueue(s); } 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Dequeue_() { Dequeue(); } 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Update_(StateId s) { Update(s); } 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool Empty_() const { return Empty(); } 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Clear_() { return Clear(); } 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Shortest-first queue discipline, templated on the StateId and 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// comparison function object. Comparison function object COMP is 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// used to compare two StateIds. If a (single) state's order changes, 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// it can be reordered in the queue with a call to Update(). 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename S, typename C> 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass ShortestFirstQueue : public QueueBase<S> { 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef S StateId; 1954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef C Compare; 1964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestFirstQueue(C comp) 1984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : QueueBase<S>(SHORTEST_FIRST_QUEUE), heap_(comp) {} 1994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Head() const { return heap_.Top(); } 2014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Enqueue(StateId s) { 2034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId i = key_.size(); i <= s; ++i) 2044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project key_.push_back(kNoKey); 2054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project key_[s] = heap_.Insert(s); 2064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Dequeue() { 2094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project key_[heap_.Pop()] = kNoKey; 2104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Update(StateId s) { 2134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (s >= (StateId)key_.size() || key_[s] == kNoKey) { 2144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Enqueue(s); 2154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 2164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project heap_.Update(key_[s], s); 2174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Empty() const { return heap_.Empty(); } 2214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Clear() { 2234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project heap_.Clear(); 2244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project key_.clear(); 2254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 2284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Heap<S, C> heap_; 2294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<ssize_t> key_; 2304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Head_() const { return Head(); } 2324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Enqueue_(StateId s) { Enqueue(s); } 2334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Dequeue_() { Dequeue(); } 2344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Update_(StateId s) { Update(s); } 2354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool Empty_() const { return Empty(); } 2364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Clear_() { return Clear(); } 2374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Given a vector that maps from states to weights and a Less 2414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// comparison function object between weights, this class defines a 2424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// comparison function object between states. 2434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename S, typename L> 2444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateWeightCompare { 2454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef L Less; 2474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename L::Weight Weight; 2484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef S StateId; 2494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateWeightCompare(const vector<Weight>* weights, const L &less) 2514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : weights_(weights), less_(less) {} 2524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool operator()(const S x, const S y) const { 2544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return less_((*weights_)[x], (*weights_)[y]); 2554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 2564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 2584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const vector<Weight>* weights_; 2594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project L less_; 2604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Shortest-first queue discipline, templated on the StateId and Weight is 2644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// specialized to use the weight's natural order for the comparion function. 2654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <typename S, typename W> 2664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass NaturalShortestFirstQueue : 2674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public ShortestFirstQueue<S, StateWeightCompare<S, NaturalLess<W> > > { 2684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef StateWeightCompare<S, NaturalLess<W> > C; 2704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project NaturalShortestFirstQueue(vector<W> *distance) : 2724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ShortestFirstQueue<S, C>(C(distance, less_)) {} 2734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 2754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project NaturalLess<W> less_; 2764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 2774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Topological-order queue discipline, templated on the StateId. 2804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// States are ordered in the queue topologically. The FST must be acyclic. 2814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class S> 2824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass TopOrderQueue : public QueueBase<S> { 2834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 2844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef S StateId; 2854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // This constructor computes the top. order. It accepts an arc filter 2874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // to limit the transitions considered in that computation (e.g., only 2884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // the epsilon graph). 2894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project template <class Arc, class ArcFilter> 2904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 2914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project TopOrderQueue(const Fst<Arc> &fst, ArcFilter filter) 2924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : QueueBase<S>(TOP_ORDER_QUEUE), front_(0), back_(kNoStateId), 2934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project order_(0), state_(0) { 2944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool acyclic; 2954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project TopOrderVisitor<Arc> top_order_visitor(&order_, &acyclic); 2964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DfsVisit(fst, &top_order_visitor, filter); 2974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!acyclic) 2984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "TopOrderQueue: fst is not acyclic."; 2994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_.resize(order_.size(), kNoStateId); 3004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // This constructor is passed the top. order, useful when we know it 3034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // beforehand. 3044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project TopOrderQueue(const vector<StateId> &order) 3054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : QueueBase<S>(TOP_ORDER_QUEUE), front_(0), back_(kNoStateId), 3064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project order_(order), state_(order.size(), kNoStateId) {} 3074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Head() const { return state_[front_]; } 3094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Enqueue(StateId s) { 3114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (front_ > back_) front_ = back_ = order_[s]; 3124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (order_[s] > back_) back_ = order_[s]; 3134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (order_[s] < front_) front_ = order_[s]; 3144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_[order_[s]] = s; 3154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Dequeue() { 3184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project state_[front_] = kNoStateId; 3194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((front_ <= back_) && (state_[front_] == kNoStateId)) ++front_; 3204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Update(StateId s) {} 3234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Empty() const { return front_ > back_; } 3254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Clear() { 3274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId i = front_; i <= back_; ++i) state_[i] = kNoStateId; 3284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project back_ = kNoStateId; 3294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project front_ = 0; 3304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 3334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId front_; 3344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId back_; 3354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> order_; 3364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> state_; 3374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Head_() const { return Head(); } 3394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Enqueue_(StateId s) { Enqueue(s); } 3404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Dequeue_() { Dequeue(); } 3414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Update_(StateId s) { Update(s); } 3424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool Empty_() const { return Empty(); } 3434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Clear_() { return Clear(); } 3444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 3464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// State order queue discipline, templated on the StateId. 3494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// States are ordered in the queue by state Id. 3504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class S> 3514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass StateOrderQueue : public QueueBase<S> { 3524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectpublic: 3534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef S StateId; 3544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateOrderQueue() 3564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : QueueBase<S>(STATE_ORDER_QUEUE), front_(0), back_(kNoStateId) {} 3574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Head() const { return front_; } 3594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Enqueue(StateId s) { 3614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (front_ > back_) front_ = back_ = s; 3624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (s > back_) back_ = s; 3634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (s < front_) front_ = s; 3644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((StateId)enqueued_.size() <= s) enqueued_.push_back(false); 3654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued_[s] = true; 3664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Dequeue() { 3694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project enqueued_[front_] = false; 3704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((front_ <= back_) && (enqueued_[front_] == false)) ++front_; 3714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Update(StateId s) {} 3744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Empty() const { return front_ > back_; } 3764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Clear() { 3784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId i = front_; i <= back_; ++i) enqueued_[i] = false; 3794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project front_ = 0; 3804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project back_ = kNoStateId; 3814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 3824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectprivate: 3844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId front_; 3854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId back_; 3864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> enqueued_; 3874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Head_() const { return Head(); } 3894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Enqueue_(StateId s) { Enqueue(s); } 3904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Dequeue_() { Dequeue(); } 3914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Update_(StateId s) { Update(s); } 3924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool Empty_() const { return Empty(); } 3934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Clear_() { return Clear(); } 3944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 3964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 3984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// SCC topological-order meta-queue discipline, templated on the StateId S 3994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// and a queue Q, which is used inside each SCC. It visits the SCC's 4004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// of an FST in topological order. Its constructor is passed the queues to 4014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// to use within an SCC. 4024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class S, class Q> 4034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass SccQueue : public QueueBase<S> { 4044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 4054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef S StateId; 4064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef Q Queue; 4074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Constructor takes a vector specifying the SCC number per state 4094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // and a vector giving the queue to use per SCC number. 4104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SccQueue(const vector<StateId> &scc, vector<Queue*> *queue) 4114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project : QueueBase<S>(SCC_QUEUE), queue_(queue), scc_(scc), front_(0), 4124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project back_(kNoStateId) {} 4134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Head() const { 4154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ((front_ <= back_) && 4164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (((*queue_)[front_] && (*queue_)[front_]->Empty()) 4174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project || (((*queue_)[front_] == 0) && 4184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ((front_ > (StateId)trivial_queue_.size()) 4194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project || (trivial_queue_[front_] == kNoStateId))))) 4204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++front_; 4214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (front_ > back_) 4224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "SccQueue: head of empty queue"; 4234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*queue_)[front_]) 4244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return (*queue_)[front_]->Head(); 4254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 4264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return trivial_queue_[front_]; 4274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Enqueue(StateId s) { 4304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (front_ > back_) front_ = back_ = scc_[s]; 4314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (scc_[s] > back_) back_ = scc_[s]; 4324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (scc_[s] < front_) front_ = scc_[s]; 4334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*queue_)[scc_[s]]) { 4344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*queue_)[scc_[s]]->Enqueue(s); 4354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 4364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while ( (StateId)trivial_queue_.size() <= scc_[s]) 4374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project trivial_queue_.push_back(kNoStateId); 4384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project trivial_queue_[scc_[s]] = s; 4394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Dequeue() { 4434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (front_ > back_) 4444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project LOG(FATAL) << "SccQueue: dequeue of empty queue"; 4454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*queue_)[front_]) 4464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*queue_)[front_]->Dequeue(); 4474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (front_ < (StateId)trivial_queue_.size()) 4484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project trivial_queue_[front_] = kNoStateId; 4494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Update(StateId s) { 4524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*queue_)[scc_[s]]) 4534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*queue_)[scc_[s]]->Update(s); 4544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Empty() const { 4574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (front_ < back_) // Queue scc # back_ not empty unless back_==front_ 4584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return false; 4594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (front_ > back_) 4604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return true; 4614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if ((*queue_)[front_]) 4624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return (*queue_)[front_]->Empty(); 4634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 4644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return (front_ > (StateId)trivial_queue_.size()) 4654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project || (trivial_queue_[front_] == kNoStateId); 4664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Clear() { 4694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId i = front_; i <= back_; ++i) 4704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((*queue_)[i]) 4714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*queue_)[i]->Clear(); 4724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else if (i < (StateId)trivial_queue_.size()) 4734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project trivial_queue_[i] = kNoStateId; 4744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project front_ = 0; 4754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project back_ = kNoStateId; 4764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 4774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectprivate: 4794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<Queue*> *queue_; 4804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const vector<StateId> &scc_; 4814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project mutable StateId front_; 4824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId back_; 4834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> trivial_queue_; 4844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Head_() const { return Head(); } 4864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Enqueue_(StateId s) { Enqueue(s); } 4874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Dequeue_() { Dequeue(); } 4884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Update_(StateId s) { Update(s); } 4894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool Empty_() const { return Empty(); } 4904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Clear_() { return Clear(); } 4914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 4924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 4944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Automatic queue discipline, templated on the StateId. It selects a 4954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// queue discipline for a given FST based on its properties. 4964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class S> 4974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass AutoQueue : public QueueBase<S> { 4984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectpublic: 4994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef S StateId; 5004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // This constructor takes a state distance vector that, if non-null and if 5024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // the Weight type has the path property, will entertain the 5034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // shortest-first queue using the natural order w.r.t to the distance. 5044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project template <class Arc, class ArcFilter> 5054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project AutoQueue(const Fst<Arc> &fst, const vector<typename Arc::Weight> *distance, 5064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcFilter filter) : QueueBase<S>(AUTO_QUEUE) { 5074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename Arc::Weight Weight; 5084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef StateWeightCompare< StateId, NaturalLess<Weight> > Compare; 5094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // First check if the FST is known to have these properties. 5114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props = fst.Properties(kAcyclic | kCyclic | 5124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project kTopSorted | kUnweighted, false); 5134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if ((props & kTopSorted) || fst.Start() == kNoStateId) { 5144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project queue_ = new StateOrderQueue<StateId>(); 5154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(2) << "AutoQueue: using state-order discipline"; 5164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if (props & kAcyclic) { 5174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project queue_ = new TopOrderQueue<StateId>(fst, filter); 5184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(2) << "AutoQueue: using top-order discipline"; 5194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else if ((props & kUnweighted) && (Weight::Properties() & kIdempotent)) { 5204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project queue_ = new LifoQueue<StateId>(); 5214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(2) << "AutoQueue: using LIFO discipline"; 5224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 5234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props; 5244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Decompose into strongly-connected components. 5254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SccVisitor<Arc> scc_visitor(&scc_, 0, 0, &props); 5264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DfsVisit(fst, &scc_visitor, filter); 5274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId nscc = *max_element(scc_.begin(), scc_.end()) + 1; 5284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<QueueType> queue_types(nscc); 5294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project NaturalLess<Weight> *less = 0; 5304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Compare *comp = 0; 5314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (distance && (Weight::Properties() & kPath)) { 5324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project less = new NaturalLess<Weight>; 5334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project comp = new Compare(distance, *less); 5344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Find the queue type to use per SCC. 5364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool unweighted; 5374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool all_trivial; 5384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SccQueueType(fst, scc_, &queue_types, filter, less, &all_trivial, 5394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project &unweighted); 5404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // If unweighted and semiring is idempotent, use lifo queue. 5414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (unweighted) { 5424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project queue_ = new LifoQueue<StateId>(); 5434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(2) << "AutoQueue: using LIFO discipline"; 5444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete comp; 5454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete less; 5464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return; 5474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // If all the scc are trivial, FST is acyclic and the scc# gives 5494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // the topological order. 5504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (all_trivial) { 5514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project queue_ = new TopOrderQueue<StateId>(scc_); 5524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(2) << "AutoQueue: using top-order discipline"; 5534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete comp; 5544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete less; 5554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return; 5564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(2) << "AutoQueue: using SCC meta-discipline"; 5584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project queues_.resize(nscc); 5594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId i = 0; i < nscc; ++i) { 5604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project switch(queue_types[i]) { 5614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case TRIVIAL_QUEUE: 5624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project queues_[i] = 0; 5634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(3) << "AutoQueue: SCC #" << i 5644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << ": using trivial discipline"; 5654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 5664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case SHORTEST_FIRST_QUEUE: 5674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project CHECK(comp); 5684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project queues_[i] = new ShortestFirstQueue<StateId, Compare>(*comp); 5694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(3) << "AutoQueue: SCC #" << i << 5704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ": using shortest-first discipline"; 5714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 5724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case LIFO_QUEUE: 5734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project queues_[i] = new LifoQueue<StateId>(); 5744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(3) << "AutoQueue: SCC #" << i 5754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << ": using LIFO disciplle"; 5764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 5774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project case FIFO_QUEUE: 5784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project default: 5794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project queues_[i] = new FifoQueue<StateId>(); 5804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project VLOG(3) << "AutoQueue: SCC #" << i 5814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project << ": using FIFO disciplle"; 5824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 5834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project queue_ = new SccQueue< StateId, QueueBase<StateId> >(scc_, &queues_); 5864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete comp; 5874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete less; 5884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ~AutoQueue() { 5924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId i = 0; i < (StateId)queues_.size(); ++i) /*naucen-edit*/ 5934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete queues_[i]; 5944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project delete queue_; 5954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 5964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId Head() const { return queue_->Head(); } 5984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 5994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Enqueue(StateId s) { queue_->Enqueue(s); } 6004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Dequeue() { queue_->Dequeue(); } 6024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Update(StateId s) { queue_->Update(s); } 6044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Empty() const { return queue_->Empty(); } 6064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Clear() { queue_->Clear(); } 6084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 6114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project QueueBase<StateId> *queue_; 6124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector< QueueBase<StateId>* > queues_; 6134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<StateId> scc_; 6144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project template <class Arc, class ArcFilter, class Less> 6164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project static void SccQueueType(const Fst<Arc> &fst, 6174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const vector<StateId> &scc, 6184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<QueueType> *queue_types, 6194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcFilter filter, Less *less, 6204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool *all_trivial, bool *unweighted); 6214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual StateId Head_() const { return Head(); } 6234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Enqueue_(StateId s) { Enqueue(s); } 6254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Dequeue_() { Dequeue(); } 6274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Update_(StateId s) { Update(s); } 6294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual bool Empty_() const { return Empty(); } 6314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project virtual void Clear_() { return Clear(); } 6334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 6344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Examines the states in an Fst's strongly connected components and 6374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// determines which type of queue to use per SCC. Stores result in 6384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// vector QUEUE_TYPES, which is assumed to have length equal to the 6394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// number of SCCs. An arc filter is used to limit the transitions 6404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// considered (e.g., only the epsilon graph). ALL_TRIVIAL is set 6414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// to true if every queue is the trivial queue. UNWEIGHTED is set to 6424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// true if the semiring is idempotent and all the arc weights are equal to 6434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Zero() or One(). 6444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class StateId> 6454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class A, class ArcFilter, class Less> 6464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid AutoQueue<StateId>::SccQueueType(const Fst<A> &fst, 6474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const vector<StateId> &scc, 6484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<QueueType> *queue_type, 6494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ArcFilter filter, Less *less, 6504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool *all_trivial, bool *unweighted) { 6514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef A Arc; 6524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 6534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 6544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *all_trivial = true; 6564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *unweighted = true; 6574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateId i = 0; i < (StateId)queue_type->size(); ++i) 6594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (*queue_type)[i] = TRIVIAL_QUEUE; 6604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateIterator< Fst<Arc> > sit(fst); !sit.Done(); sit.Next()) { 6624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId state = sit.Value(); 6634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator< Fst<Arc> > ait(fst, state); 6644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project !ait.Done(); 6654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ait.Next()) { 6664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const Arc &arc = ait.Value(); 6674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!filter(arc)) continue; 6684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (scc[state] == scc[arc.nextstate]) { 6694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project QueueType &type = (*queue_type)[scc[state]]; 6704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!less || ((*less)(arc.weight, Weight::One()))) 6714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project type = FIFO_QUEUE; 67273018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers else if ((type == TRIVIAL_QUEUE) || (type == LIFO_QUEUE)) { 6734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!(Weight::Properties() & kIdempotent) || 6744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (arc.weight != Weight::Zero() && arc.weight != Weight::One())) 6754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project type = SHORTEST_FIRST_QUEUE; 6764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 6774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project type = LIFO_QUEUE; 67873018b4a1d088cdda0e7bd059fddf1f308a8195aIan Rogers } 6794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (type != TRIVIAL_QUEUE) *all_trivial = false; 6804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!(Weight::Properties() & kIdempotent) || 6824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project (arc.weight != Weight::Zero() && arc.weight != Weight::One())) 6834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project *unweighted = false; 6844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 6864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 6874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} // namespace fst 6894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 6904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif 691