1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// queue.h 2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License"); 4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License. 5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at 6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://www.apache.org/licenses/LICENSE-2.0 8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software 10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS, 11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and 13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License. 14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc. 16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: allauzen@google.com (Cyril Allauzen) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Functions and classes for various Fst state queues with 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// a unified interface. 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_LIB_QUEUE_H__ 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_LIB_QUEUE_H__ 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <deque> 265b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkinusing std::deque; 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <vector> 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::vector; 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/arcfilter.h> 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/connect.h> 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/heap.h> 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/topsort.h> 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// template <class S> 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// class Queue { 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// public: 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// typedef typename S StateId; 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Ctr: may need args (e.g., Fst, comparator) for some queues 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Queue(...); 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Returns the head of the queue 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// StateId Head() const; 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Inserts a state 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// void Enqueue(StateId s); 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Removes the head of the queue 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// void Dequeue(); 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Updates ordering of state s when weight changes, if necessary 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// void Update(StateId s); 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Does the queue contain no elements? 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// bool Empty() const; 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// // Remove all states from queue 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// void Clear(); 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// }; 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// State queue types. 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonenum QueueType { 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TRIVIAL_QUEUE = 0, // Single state queue 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FIFO_QUEUE = 1, // First-in, first-out queue 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson LIFO_QUEUE = 2, // Last-in, first-out queue 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SHORTEST_FIRST_QUEUE = 3, // Shortest-first queue 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TOP_ORDER_QUEUE = 4, // Topologically-ordered queue 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson STATE_ORDER_QUEUE = 5, // State-ID ordered queue 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SCC_QUEUE = 6, // Component graph top-ordered meta-queue 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AUTO_QUEUE = 7, // Auto-selected queue 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson OTHER_QUEUE = 8 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson }; 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// QueueBase, templated on the StateId, is the base class shared by the 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// queues considered by AutoQueue. 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class S> 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass QueueBase { 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson QueueBase(QueueType type) : queue_type_(type), error_(false) {} 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual ~QueueBase() {} 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId Head() const { return Head_(); } 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Enqueue(StateId s) { Enqueue_(s); } 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Dequeue() { Dequeue_(); } 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Update(StateId s) { Update_(s); } 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Empty() const { return Empty_(); } 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { Clear_(); } 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson QueueType Type() { return queue_type_; } 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Error() const { return error_; } 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void SetError(bool error) { error_ = error; } 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This allows base-class virtual access to non-virtual derived- 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // class members of the same name. It makes the derived class more 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // efficient to use but unsafe to further derive. 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual StateId Head_() const = 0; 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Enqueue_(StateId s) = 0; 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Dequeue_() = 0; 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Update_(StateId s) = 0; 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual bool Empty_() const = 0; 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Clear_() = 0; 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson QueueType queue_type_; 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool error_; 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Trivial queue discipline, templated on the StateId. You may enqueue 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// at most one state at a time. It is used for strongly connected components 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// with only one state and no self loops. 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class S> 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass TrivialQueue : public QueueBase<S> { 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonpublic: 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TrivialQueue() : QueueBase<S>(TRIVIAL_QUEUE), front_(kNoStateId) {} 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId Head() const { return front_; } 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Enqueue(StateId s) { front_ = s; } 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Dequeue() { front_ = kNoStateId; } 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Update(StateId s) {} 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Empty() const { return front_ == kNoStateId; } 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { front_ = kNoStateId; } 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonprivate: 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This allows base-class virtual access to non-virtual derived- 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // class members of the same name. It makes the derived class more 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // efficient to use but unsafe to further derive. 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual StateId Head_() const { return Head(); } 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Enqueue_(StateId s) { Enqueue(s); } 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Dequeue_() { Dequeue(); } 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Update_(StateId s) { Update(s); } 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual bool Empty_() const { return Empty(); } 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Clear_() { return Clear(); } 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId front_; 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// First-in, first-out queue discipline, templated on the StateId. 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class S> 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass FifoQueue : public QueueBase<S>, public deque<S> { 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using deque<S>::back; 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using deque<S>::push_front; 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using deque<S>::pop_back; 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using deque<S>::empty; 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using deque<S>::clear; 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FifoQueue() : QueueBase<S>(FIFO_QUEUE) {} 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId Head() const { return back(); } 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Enqueue(StateId s) { push_front(s); } 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Dequeue() { pop_back(); } 156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Update(StateId s) {} 157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Empty() const { return empty(); } 158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { clear(); } 159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 160f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 161f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This allows base-class virtual access to non-virtual derived- 162f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // class members of the same name. It makes the derived class more 163f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // efficient to use but unsafe to further derive. 164f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual StateId Head_() const { return Head(); } 165f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Enqueue_(StateId s) { Enqueue(s); } 166f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Dequeue_() { Dequeue(); } 167f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Update_(StateId s) { Update(s); } 168f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual bool Empty_() const { return Empty(); } 169f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Clear_() { return Clear(); } 170f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 171f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 172f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 173f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Last-in, first-out queue discipline, templated on the StateId. 174f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class S> 175f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass LifoQueue : public QueueBase<S>, public deque<S> { 176f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 177f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using deque<S>::front; 178f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using deque<S>::push_front; 179f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using deque<S>::pop_front; 180f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using deque<S>::empty; 181f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson using deque<S>::clear; 182f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 183f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 184f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 185f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson LifoQueue() : QueueBase<S>(LIFO_QUEUE) {} 186f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId Head() const { return front(); } 187f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Enqueue(StateId s) { push_front(s); } 188f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Dequeue() { pop_front(); } 189f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Update(StateId s) {} 190f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Empty() const { return empty(); } 191f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { clear(); } 192f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 193f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 194f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This allows base-class virtual access to non-virtual derived- 195f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // class members of the same name. It makes the derived class more 196f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // efficient to use but unsafe to further derive. 197f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual StateId Head_() const { return Head(); } 198f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Enqueue_(StateId s) { Enqueue(s); } 199f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Dequeue_() { Dequeue(); } 200f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Update_(StateId s) { Update(s); } 201f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual bool Empty_() const { return Empty(); } 202f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Clear_() { return Clear(); } 203f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 204f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 205f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 206f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Shortest-first queue discipline, templated on the StateId and 207f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// comparison function object. Comparison function object COMP is 208f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// used to compare two StateIds. If a (single) state's order changes, 209f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// it can be reordered in the queue with a call to Update(). 210f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// If 'update == false', call to Update() does not reorder the queue. 211f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename C, bool update = true> 212f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass ShortestFirstQueue : public QueueBase<S> { 213f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 214f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 215f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef C Compare; 216f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 217f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestFirstQueue(C comp) 218f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : QueueBase<S>(SHORTEST_FIRST_QUEUE), heap_(comp) {} 219f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 220f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId Head() const { return heap_.Top(); } 221f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 222f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Enqueue(StateId s) { 223f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (update) { 224f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId i = key_.size(); i <= s; ++i) 225f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson key_.push_back(kNoKey); 226f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson key_[s] = heap_.Insert(s); 227f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 228f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson heap_.Insert(s); 229f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 230f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 231f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 232f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Dequeue() { 233f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (update) 234f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson key_[heap_.Pop()] = kNoKey; 235f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else 236f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson heap_.Pop(); 237f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 238f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 239f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Update(StateId s) { 240f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!update) 241f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 242f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (s >= key_.size() || key_[s] == kNoKey) { 243f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Enqueue(s); 244f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 245f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson heap_.Update(key_[s], s); 246f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 247f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 248f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 249f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Empty() const { return heap_.Empty(); } 250f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 251f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { 252f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson heap_.Clear(); 253f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (update) key_.clear(); 254f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 255f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 256f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 257f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Heap<S, C, false> heap_; 258f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<ssize_t> key_; 259f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 260f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This allows base-class virtual access to non-virtual derived- 261f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // class members of the same name. It makes the derived class more 262f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // efficient to use but unsafe to further derive. 263f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual StateId Head_() const { return Head(); } 264f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Enqueue_(StateId s) { Enqueue(s); } 265f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Dequeue_() { Dequeue(); } 266f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Update_(StateId s) { Update(s); } 267f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual bool Empty_() const { return Empty(); } 268f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Clear_() { return Clear(); } 269f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 270f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 271f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 272f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Given a vector that maps from states to weights and a Less 273f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// comparison function object between weights, this class defines a 274f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// comparison function object between states. 275f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename L> 276f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass StateWeightCompare { 277f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 278f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef L Less; 279f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename L::Weight Weight; 280f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 281f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 282f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateWeightCompare(const vector<Weight>& weights, const L &less) 283f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : weights_(weights), less_(less) {} 284f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 285f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool operator()(const S x, const S y) const { 286f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return less_(weights_[x], weights_[y]); 287f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 288f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 289f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 290f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<Weight>& weights_; 291f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson L less_; 292f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 293f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 294f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 295f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Shortest-first queue discipline, templated on the StateId and Weight, is 296f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// specialized to use the weight's natural order for the comparison function. 297f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename W> 298f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass NaturalShortestFirstQueue : 299f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public ShortestFirstQueue<S, StateWeightCompare<S, NaturalLess<W> > > { 300f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 301f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef StateWeightCompare<S, NaturalLess<W> > C; 302f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 303f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson NaturalShortestFirstQueue(const vector<W> &distance) : 304f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestFirstQueue<S, C>(C(distance, less_)) {} 305f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 306f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 307f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson NaturalLess<W> less_; 308f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 309f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 310f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Topological-order queue discipline, templated on the StateId. 311f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// States are ordered in the queue topologically. The FST must be acyclic. 312f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class S> 313f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass TopOrderQueue : public QueueBase<S> { 314f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 315f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 316f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 317f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This constructor computes the top. order. It accepts an arc filter 318f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // to limit the transitions considered in that computation (e.g., only 319f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // the epsilon graph). 320f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson template <class Arc, class ArcFilter> 321f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TopOrderQueue(const Fst<Arc> &fst, ArcFilter filter) 322f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : QueueBase<S>(TOP_ORDER_QUEUE), front_(0), back_(kNoStateId), 323f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson order_(0), state_(0) { 324f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool acyclic; 325f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TopOrderVisitor<Arc> top_order_visitor(&order_, &acyclic); 326f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DfsVisit(fst, &top_order_visitor, filter); 327f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!acyclic) { 328f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "TopOrderQueue: fst is not acyclic."; 329f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson QueueBase<S>::SetError(true); 330f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 331f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_.resize(order_.size(), kNoStateId); 332f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 333f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 334f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This constructor is passed the top. order, useful when we know it 335f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // beforehand. 336f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson TopOrderQueue(const vector<StateId> &order) 337f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : QueueBase<S>(TOP_ORDER_QUEUE), front_(0), back_(kNoStateId), 338f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson order_(order), state_(order.size(), kNoStateId) {} 339f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 340f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId Head() const { return state_[front_]; } 341f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 342f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Enqueue(StateId s) { 343f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (front_ > back_) front_ = back_ = order_[s]; 344f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (order_[s] > back_) back_ = order_[s]; 345f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (order_[s] < front_) front_ = order_[s]; 346f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_[order_[s]] = s; 347f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 348f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 349f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Dequeue() { 350f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson state_[front_] = kNoStateId; 351f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while ((front_ <= back_) && (state_[front_] == kNoStateId)) ++front_; 352f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 353f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 354f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Update(StateId s) {} 355f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 356f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Empty() const { return front_ > back_; } 357f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 358f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { 359f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId i = front_; i <= back_; ++i) state_[i] = kNoStateId; 360f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson back_ = kNoStateId; 361f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson front_ = 0; 362f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 363f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 364f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 365f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId front_; 366f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId back_; 367f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> order_; 368f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> state_; 369f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 370f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This allows base-class virtual access to non-virtual derived- 371f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // class members of the same name. It makes the derived class more 372f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // efficient to use but unsafe to further derive. 373f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual StateId Head_() const { return Head(); } 374f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Enqueue_(StateId s) { Enqueue(s); } 375f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Dequeue_() { Dequeue(); } 376f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Update_(StateId s) { Update(s); } 377f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual bool Empty_() const { return Empty(); } 378f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Clear_() { return Clear(); } 379f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 380f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 381f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 382f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// State order queue discipline, templated on the StateId. 383f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// States are ordered in the queue by state Id. 384f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class S> 385f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass StateOrderQueue : public QueueBase<S> { 386f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonpublic: 387f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 388f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 389f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateOrderQueue() 390f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : QueueBase<S>(STATE_ORDER_QUEUE), front_(0), back_(kNoStateId) {} 391f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 392f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId Head() const { return front_; } 393f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 394f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Enqueue(StateId s) { 395f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (front_ > back_) front_ = back_ = s; 396f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (s > back_) back_ = s; 397f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (s < front_) front_ = s; 398f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (enqueued_.size() <= s) enqueued_.push_back(false); 399f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson enqueued_[s] = true; 400f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 401f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 402f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Dequeue() { 403f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson enqueued_[front_] = false; 404f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while ((front_ <= back_) && (enqueued_[front_] == false)) ++front_; 405f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 406f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 407f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Update(StateId s) {} 408f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 409f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Empty() const { return front_ > back_; } 410f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 411f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { 412f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId i = front_; i <= back_; ++i) enqueued_[i] = false; 413f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson front_ = 0; 414f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson back_ = kNoStateId; 415f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 416f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 417f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonprivate: 418f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId front_; 419f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId back_; 420f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<bool> enqueued_; 421f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 422f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This allows base-class virtual access to non-virtual derived- 423f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // class members of the same name. It makes the derived class more 424f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // efficient to use but unsafe to further derive. 425f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual StateId Head_() const { return Head(); } 426f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Enqueue_(StateId s) { Enqueue(s); } 427f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Dequeue_() { Dequeue(); } 428f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Update_(StateId s) { Update(s); } 429f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual bool Empty_() const { return Empty(); } 430f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Clear_() { return Clear(); } 431f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 432f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 433f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 434f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 435f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// SCC topological-order meta-queue discipline, templated on the StateId S 436f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// and a queue Q, which is used inside each SCC. It visits the SCC's 437f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// of an FST in topological order. Its constructor is passed the queues to 438f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// to use within an SCC. 439f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class S, class Q> 440f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass SccQueue : public QueueBase<S> { 441f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 442f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 443f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef Q Queue; 444f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 445f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Constructor takes a vector specifying the SCC number per state 446f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // and a vector giving the queue to use per SCC number. 447f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SccQueue(const vector<StateId> &scc, vector<Queue*> *queue) 448f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : QueueBase<S>(SCC_QUEUE), queue_(queue), scc_(scc), front_(0), 449f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson back_(kNoStateId) {} 450f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 451f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId Head() const { 452f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while ((front_ <= back_) && 453f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (((*queue_)[front_] && (*queue_)[front_]->Empty()) 454f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson || (((*queue_)[front_] == 0) && 455dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin ((front_ >= trivial_queue_.size()) 456f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson || (trivial_queue_[front_] == kNoStateId))))) 457f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ++front_; 458f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((*queue_)[front_]) 459f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return (*queue_)[front_]->Head(); 460f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else 461f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return trivial_queue_[front_]; 462f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 463f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 464f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Enqueue(StateId s) { 465f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (front_ > back_) front_ = back_ = scc_[s]; 466f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (scc_[s] > back_) back_ = scc_[s]; 467f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (scc_[s] < front_) front_ = scc_[s]; 468f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((*queue_)[scc_[s]]) { 469f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (*queue_)[scc_[s]]->Enqueue(s); 470f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 471f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (trivial_queue_.size() <= scc_[s]) 472f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson trivial_queue_.push_back(kNoStateId); 473f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson trivial_queue_[scc_[s]] = s; 474f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 475f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 476f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 477f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Dequeue() { 478f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((*queue_)[front_]) 479f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (*queue_)[front_]->Dequeue(); 480f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (front_ < trivial_queue_.size()) 481f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson trivial_queue_[front_] = kNoStateId; 482f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 483f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 484f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Update(StateId s) { 485f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((*queue_)[scc_[s]]) 486f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (*queue_)[scc_[s]]->Update(s); 487f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 488f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 489f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Empty() const { 490f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (front_ < back_) // Queue scc # back_ not empty unless back_==front_ 491f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return false; 492f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (front_ > back_) 493f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return true; 494f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if ((*queue_)[front_]) 495f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return (*queue_)[front_]->Empty(); 496f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else 497dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin return (front_ >= trivial_queue_.size()) 498f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson || (trivial_queue_[front_] == kNoStateId); 499f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 500f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 501f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { 502f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId i = front_; i <= back_; ++i) 503f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((*queue_)[i]) 504f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (*queue_)[i]->Clear(); 505f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if (i < trivial_queue_.size()) 506f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson trivial_queue_[i] = kNoStateId; 507f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson front_ = 0; 508f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson back_ = kNoStateId; 509f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 510f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 511f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonprivate: 512f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Queue*> *queue_; 513f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<StateId> &scc_; 514f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson mutable StateId front_; 515f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId back_; 516f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> trivial_queue_; 517f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 518f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This allows base-class virtual access to non-virtual derived- 519f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // class members of the same name. It makes the derived class more 520f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // efficient to use but unsafe to further derive. 521f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual StateId Head_() const { return Head(); } 522f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Enqueue_(StateId s) { Enqueue(s); } 523f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Dequeue_() { Dequeue(); } 524f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Update_(StateId s) { Update(s); } 525f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual bool Empty_() const { return Empty(); } 526f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Clear_() { return Clear(); } 527f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 528f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DISALLOW_COPY_AND_ASSIGN(SccQueue); 529f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 530f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 531f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 532f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Automatic queue discipline, templated on the StateId. It selects a 533f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// queue discipline for a given FST based on its properties. 534f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class S> 535f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass AutoQueue : public QueueBase<S> { 536f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonpublic: 537f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 538f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 539f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This constructor takes a state distance vector that, if non-null and if 540f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // the Weight type has the path property, will entertain the 541f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // shortest-first queue using the natural order w.r.t to the distance. 542f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson template <class Arc, class ArcFilter> 543f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AutoQueue(const Fst<Arc> &fst, const vector<typename Arc::Weight> *distance, 544f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcFilter filter) : QueueBase<S>(AUTO_QUEUE) { 545f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 546f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef StateWeightCompare< StateId, NaturalLess<Weight> > Compare; 547f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 548f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // First check if the FST is known to have these properties. 549f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 props = fst.Properties(kAcyclic | kCyclic | 550f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson kTopSorted | kUnweighted, false); 551f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if ((props & kTopSorted) || fst.Start() == kNoStateId) { 552f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue_ = new StateOrderQueue<StateId>(); 553f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(2) << "AutoQueue: using state-order discipline"; 554f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else if (props & kAcyclic) { 555f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue_ = new TopOrderQueue<StateId>(fst, filter); 556f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(2) << "AutoQueue: using top-order discipline"; 557f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else if ((props & kUnweighted) && (Weight::Properties() & kIdempotent)) { 558f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue_ = new LifoQueue<StateId>(); 559f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(2) << "AutoQueue: using LIFO discipline"; 560f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 561f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson uint64 properties; 562f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Decompose into strongly-connected components. 563f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SccVisitor<Arc> scc_visitor(&scc_, 0, 0, &properties); 564f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DfsVisit(fst, &scc_visitor, filter); 565f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId nscc = *max_element(scc_.begin(), scc_.end()) + 1; 566f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<QueueType> queue_types(nscc); 567f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson NaturalLess<Weight> *less = 0; 568f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Compare *comp = 0; 569f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (distance && (Weight::Properties() & kPath)) { 570f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson less = new NaturalLess<Weight>; 571f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson comp = new Compare(*distance, *less); 572f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 573f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Find the queue type to use per SCC. 574f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool unweighted; 575f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool all_trivial; 576f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson SccQueueType(fst, scc_, &queue_types, filter, less, &all_trivial, 577f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson &unweighted); 578f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // If unweighted and semiring is idempotent, use lifo queue. 579f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (unweighted) { 580f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue_ = new LifoQueue<StateId>(); 581f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(2) << "AutoQueue: using LIFO discipline"; 582f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete comp; 583f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete less; 584f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 585f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 586f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // If all the scc are trivial, FST is acyclic and the scc# gives 587f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // the topological order. 588f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (all_trivial) { 589f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue_ = new TopOrderQueue<StateId>(scc_); 590f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(2) << "AutoQueue: using top-order discipline"; 591f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete comp; 592f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete less; 593f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 594f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 595f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(2) << "AutoQueue: using SCC meta-discipline"; 596f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queues_.resize(nscc); 597f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId i = 0; i < nscc; ++i) { 598f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson switch(queue_types[i]) { 599f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case TRIVIAL_QUEUE: 600f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queues_[i] = 0; 601f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(3) << "AutoQueue: SCC #" << i 602f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << ": using trivial discipline"; 603f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson break; 604f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case SHORTEST_FIRST_QUEUE: 605f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queues_[i] = new ShortestFirstQueue<StateId, Compare, false>(*comp); 606f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(3) << "AutoQueue: SCC #" << i << 607f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ": using shortest-first discipline"; 608f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson break; 609f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case LIFO_QUEUE: 610f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queues_[i] = new LifoQueue<StateId>(); 611f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(3) << "AutoQueue: SCC #" << i 612f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << ": using LIFO disciplle"; 613f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson break; 614f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case FIFO_QUEUE: 615f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson default: 616f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queues_[i] = new FifoQueue<StateId>(); 617f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson VLOG(3) << "AutoQueue: SCC #" << i 618f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson << ": using FIFO disciplle"; 619f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson break; 620f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 621f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 622f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue_ = new SccQueue< StateId, QueueBase<StateId> >(scc_, &queues_); 623f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete comp; 624f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete less; 625f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 626f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 627f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 628f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ~AutoQueue() { 629f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId i = 0; i < queues_.size(); ++i) 630f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete queues_[i]; 631f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete queue_; 632f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 633f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 634f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId Head() const { return queue_->Head(); } 635f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 636f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Enqueue(StateId s) { queue_->Enqueue(s); } 637f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 638f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Dequeue() { queue_->Dequeue(); } 639f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 640f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Update(StateId s) { queue_->Update(s); } 641f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 642f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Empty() const { return queue_->Empty(); } 643f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 644f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { queue_->Clear(); } 645f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 646f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 647f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 648f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson QueueBase<StateId> *queue_; 649f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector< QueueBase<StateId>* > queues_; 650f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<StateId> scc_; 651f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 652f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson template <class Arc, class ArcFilter, class Less> 653f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static void SccQueueType(const Fst<Arc> &fst, 654f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<StateId> &scc, 655f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<QueueType> *queue_types, 656f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcFilter filter, Less *less, 657f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool *all_trivial, bool *unweighted); 658f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 659f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This allows base-class virtual access to non-virtual derived- 660f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // class members of the same name. It makes the derived class more 661f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // efficient to use but unsafe to further derive. 662f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual StateId Head_() const { return Head(); } 663f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 664f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Enqueue_(StateId s) { Enqueue(s); } 665f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 666f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Dequeue_() { Dequeue(); } 667f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 668f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Update_(StateId s) { Update(s); } 669f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 670f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual bool Empty_() const { return Empty(); } 671f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 672f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Clear_() { return Clear(); } 673f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 674f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DISALLOW_COPY_AND_ASSIGN(AutoQueue); 675f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 676f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 677f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 678f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Examines the states in an Fst's strongly connected components and 679f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// determines which type of queue to use per SCC. Stores result in 680f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// vector QUEUE_TYPES, which is assumed to have length equal to the 681f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// number of SCCs. An arc filter is used to limit the transitions 682f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// considered (e.g., only the epsilon graph). ALL_TRIVIAL is set 683f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// to true if every queue is the trivial queue. UNWEIGHTED is set to 684f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// true if the semiring is idempotent and all the arc weights are equal to 685f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Zero() or One(). 686f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class StateId> 687f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class A, class ArcFilter, class Less> 688f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid AutoQueue<StateId>::SccQueueType(const Fst<A> &fst, 689f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<StateId> &scc, 690f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<QueueType> *queue_type, 691f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ArcFilter filter, Less *less, 692f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool *all_trivial, bool *unweighted) { 693f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef A Arc; 694f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::StateId StateId; 695f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename A::Weight Weight; 696f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 697f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson *all_trivial = true; 698f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson *unweighted = true; 699f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 700f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateId i = 0; i < queue_type->size(); ++i) 701f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (*queue_type)[i] = TRIVIAL_QUEUE; 702f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 703f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (StateIterator< Fst<Arc> > sit(fst); !sit.Done(); sit.Next()) { 704f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId state = sit.Value(); 705f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (ArcIterator< Fst<Arc> > ait(fst, state); 706f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson !ait.Done(); 707f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ait.Next()) { 708f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Arc &arc = ait.Value(); 709f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!filter(arc)) continue; 710f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (scc[state] == scc[arc.nextstate]) { 711f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson QueueType &type = (*queue_type)[scc[state]]; 712f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!less || ((*less)(arc.weight, Weight::One()))) 713f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson type = FIFO_QUEUE; 714f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else if ((type == TRIVIAL_QUEUE) || (type == LIFO_QUEUE)) { 715f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!(Weight::Properties() & kIdempotent) || 716f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (arc.weight != Weight::Zero() && arc.weight != Weight::One())) 717f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson type = SHORTEST_FIRST_QUEUE; 718f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else 719f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson type = LIFO_QUEUE; 720f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 721f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (type != TRIVIAL_QUEUE) *all_trivial = false; 722f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 723f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (!(Weight::Properties() & kIdempotent) || 724f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (arc.weight != Weight::Zero() && arc.weight != Weight::One())) 725f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson *unweighted = false; 726f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 727f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 728f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 729f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 730f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 731f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// An A* estimate is a function object that maps from a state ID to a 732f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// an estimate of the shortest distance to the final states. 733f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The trivial A* estimate is always One(). 734f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename W> 735f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct TrivialAStarEstimate { 736f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson W operator()(S s) const { return W::One(); } 737f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 738f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 739f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 740f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Given a vector that maps from states to weights representing the 741f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// shortest distance from the initial state, a Less comparison 742f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// function object between weights, and an estimate E of the 743f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// shortest distance to the final states, this class defines a 744f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// comparison function object between states. 745f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename L, typename E> 746f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass AStarWeightCompare { 747f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 748f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef L Less; 749f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename L::Weight Weight; 750f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef S StateId; 751f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 752f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson AStarWeightCompare(const vector<Weight>& weights, const L &less, 753f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const E &estimate) 754f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : weights_(weights), less_(less), estimate_(estimate) {} 755f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 756f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool operator()(const S x, const S y) const { 757f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight wx = Times(weights_[x], estimate_(x)); 758f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight wy = Times(weights_[y], estimate_(y)); 759f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return less_(wx, wy); 760f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 761f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 762f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 763f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<Weight>& weights_; 764f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson L less_; 765f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const E &estimate_; 766f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 767f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 768f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 769f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// A* queue discipline, templated on the StateId, Weight and an 770f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// estimate E of the shortest distance to the final states, is specialized 771f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// to use the weight's natural order for the comparison function. 772f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S, typename W, typename E> 773f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass NaturalAStarQueue : 774f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public ShortestFirstQueue<S, AStarWeightCompare<S, NaturalLess<W>, E> > { 775f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 776f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef AStarWeightCompare<S, NaturalLess<W>, E> C; 777f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 778f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson NaturalAStarQueue(const vector<W> &distance, const E &estimate) : 779f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestFirstQueue<S, C>(C(distance, less_, estimate)) {} 780f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 781f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 782f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson NaturalLess<W> less_; 783f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 784f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 785f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 786f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// A state equivalence class is a function object that 787f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// maps from a state ID to an equivalence class (state) ID. 788f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The trivial equivalence class maps a state to itself. 789f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename S> 790f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct TrivialStateEquivClass { 791f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson S operator()(S s) const { return s; } 792f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 793f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 794f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 7955b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// Distance-based pruning queue discipline: Enqueues a state 's' 7965b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// only when its shortest distance (so far), as specified by 7975b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// 'distance', is less than (as specified by 'comp') the shortest 7985b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// distance Times() the 'threshold' to any state in the same 7995b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// equivalence class, as specified by the function object 8005b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// 'class_func'. The underlying queue discipline is specified by 8015b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// 'queue'. The ownership of 'queue' is given to this class. 802f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename Q, typename L, typename C> 803f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass PruneQueue : public QueueBase<typename Q::StateId> { 804f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 805f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Q::StateId StateId; 806f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename L::Weight Weight; 807f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 808f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PruneQueue(const vector<Weight> &distance, Q *queue, L comp, 809f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const C &class_func, Weight threshold) 810f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : QueueBase<StateId>(OTHER_QUEUE), 811f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson distance_(distance), 812f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue_(queue), 813f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson less_(comp), 814f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson class_func_(class_func), 815f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson threshold_(threshold) {} 816f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 817f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ~PruneQueue() { delete queue_; } 818f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 819f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId Head() const { return queue_->Head(); } 820f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 821f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Enqueue(StateId s) { 822f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId c = class_func_(s); 823f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (c >= class_distance_.size()) 824f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson class_distance_.resize(c + 1, Weight::Zero()); 825f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (less_(distance_[s], class_distance_[c])) 826f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson class_distance_[c] = distance_[s]; 827f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 828f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Enqueue only if below threshold limit 829f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight limit = Times(class_distance_[c], threshold_); 830f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (less_(distance_[s], limit)) 831f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue_->Enqueue(s); 832f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 833f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 834f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Dequeue() { queue_->Dequeue(); } 835f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 836f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Update(StateId s) { 837f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson StateId c = class_func_(s); 838f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (less_(distance_[s], class_distance_[c])) 839f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson class_distance_[c] = distance_[s]; 840f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue_->Update(s); 841f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 842f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 843f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Empty() const { return queue_->Empty(); } 844f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { queue_->Clear(); } 845f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 846f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 847f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // This allows base-class virtual access to non-virtual derived- 848f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // class members of the same name. It makes the derived class more 849f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // efficient to use but unsafe to further derive. 850f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual StateId Head_() const { return Head(); } 851f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Enqueue_(StateId s) { Enqueue(s); } 852f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Dequeue_() { Dequeue(); } 853f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Update_(StateId s) { Update(s); } 854f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual bool Empty_() const { return Empty(); } 855f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson virtual void Clear_() { return Clear(); } 856f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 857f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<Weight> &distance_; // shortest distance to state 858f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Q *queue_; 859f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson L less_; 860f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const C &class_func_; // eqv. class function object 861f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Weight threshold_; // pruning weight threshold 862f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<Weight> class_distance_; // shortest distance to class 863f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 864f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson DISALLOW_COPY_AND_ASSIGN(PruneQueue); 865f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 866f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 867f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 868f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Pruning queue discipline (see above) using the weight's natural 869f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// order for the comparison function. The ownership of 'queue' is 870f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// given to this class. 871f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <typename Q, typename W, typename C> 872f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass NaturalPruneQueue : 873f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public PruneQueue<Q, NaturalLess<W>, C> { 874f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 875f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Q::StateId StateId; 876f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef W Weight; 877f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 878f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson NaturalPruneQueue(const vector<W> &distance, Q *queue, 879f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const C &class_func_, Weight threshold) : 880f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson PruneQueue<Q, NaturalLess<W>, C>(distance, queue, less_, 881f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson class_func_, threshold) {} 882f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 883f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 884f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson NaturalLess<W> less_; 885f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 886f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 887f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 8885b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// Filter-based pruning queue discipline: Enqueues a state 's' only 8895b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// if allowed by the filter, specified by the function object 'state_filter'. 8905b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// The underlying queue discipline is specified by 'queue'. The ownership 8915b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin// of 'queue' is given to this class. 8925b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkintemplate <typename Q, typename F> 8935b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkinclass FilterQueue : public QueueBase<typename Q::StateId> { 8945b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin public: 8955b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin typedef typename Q::StateId StateId; 8965b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 8975b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin FilterQueue(Q *queue, const F &state_filter) 8985b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin : QueueBase<StateId>(OTHER_QUEUE), 8995b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin queue_(queue), 9005b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin state_filter_(state_filter) {} 9015b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 9025b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin ~FilterQueue() { delete queue_; } 9035b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 9045b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin StateId Head() const { return queue_->Head(); } 9055b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 9065b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin // Enqueues only if allowed by state filter. 9075b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin void Enqueue(StateId s) { 9085b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin if (state_filter_(s)) { 9095b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin queue_->Enqueue(s); 9105b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin } 9115b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin } 9125b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 9135b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin void Dequeue() { queue_->Dequeue(); } 9145b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 9155b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin void Update(StateId s) {} 9165b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin bool Empty() const { return queue_->Empty(); } 9175b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin void Clear() { queue_->Clear(); } 9185b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 9195b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin private: 9205b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin // This allows base-class virtual access to non-virtual derived- 9215b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin // class members of the same name. It makes the derived class more 9225b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin // efficient to use but unsafe to further derive. 9235b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin virtual StateId Head_() const { return Head(); } 9245b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin virtual void Enqueue_(StateId s) { Enqueue(s); } 9255b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin virtual void Dequeue_() { Dequeue(); } 9265b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin virtual void Update_(StateId s) { Update(s); } 9275b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin virtual bool Empty_() const { return Empty(); } 9285b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin virtual void Clear_() { return Clear(); } 9295b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 9305b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin Q *queue_; 9315b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin const F &state_filter_; // Filter to prune states 9325b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 9335b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin DISALLOW_COPY_AND_ASSIGN(FilterQueue); 9345b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin}; 9355b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin 936f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 937f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 938f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif 939