diff options
author | Ted Yin <[email protected]> | 2015-08-14 17:42:26 +0800 |
---|---|---|
committer | Ted Yin <[email protected]> | 2015-08-14 17:42:26 +0800 |
commit | c3cffb58b9921d78753336421b52b9ffdaa5515c (patch) | |
tree | bfea20e97c200cf734021e3756d749c892e658a4 /kaldi_io/src/tools/openfst/include/fst/queue.h | |
parent | 10cce5f6a5c9e2f8e00d5a2a4d87c9cb7c26bf4c (diff) | |
parent | dfdd17afc2e984ec6c32ea01290f5c76309a456a (diff) |
Merge pull request #2 from yimmon/master
remove needless files
Diffstat (limited to 'kaldi_io/src/tools/openfst/include/fst/queue.h')
-rw-r--r-- | kaldi_io/src/tools/openfst/include/fst/queue.h | 938 |
1 files changed, 0 insertions, 938 deletions
diff --git a/kaldi_io/src/tools/openfst/include/fst/queue.h b/kaldi_io/src/tools/openfst/include/fst/queue.h deleted file mode 100644 index 95a082d..0000000 --- a/kaldi_io/src/tools/openfst/include/fst/queue.h +++ /dev/null @@ -1,938 +0,0 @@ -// queue.h - -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. -// -// Copyright 2005-2010 Google, Inc. -// Author: [email protected] (Cyril Allauzen) -// -// \file -// Functions and classes for various Fst state queues with -// a unified interface. - -#ifndef FST_LIB_QUEUE_H__ -#define FST_LIB_QUEUE_H__ - -#include <deque> -using std::deque; -#include <vector> -using std::vector; - -#include <fst/arcfilter.h> -#include <fst/connect.h> -#include <fst/heap.h> -#include <fst/topsort.h> - - -namespace fst { - -// template <class S> -// class Queue { -// public: -// typedef typename S StateId; -// -// // Ctr: may need args (e.g., Fst, comparator) for some queues -// Queue(...); -// // Returns the head of the queue -// StateId Head() const; -// // Inserts a state -// void Enqueue(StateId s); -// // Removes the head of the queue -// void Dequeue(); -// // Updates ordering of state s when weight changes, if necessary -// void Update(StateId s); -// // Does the queue contain no elements? -// bool Empty() const; -// // Remove all states from queue -// void Clear(); -// }; - -// State queue types. -enum QueueType { - TRIVIAL_QUEUE = 0, // Single state queue - FIFO_QUEUE = 1, // First-in, first-out queue - LIFO_QUEUE = 2, // Last-in, first-out queue - SHORTEST_FIRST_QUEUE = 3, // Shortest-first queue - TOP_ORDER_QUEUE = 4, // Topologically-ordered queue - STATE_ORDER_QUEUE = 5, // State-ID ordered queue - SCC_QUEUE = 6, // Component graph top-ordered meta-queue - AUTO_QUEUE = 7, // Auto-selected queue - OTHER_QUEUE = 8 - }; - - -// QueueBase, templated on the StateId, is the base class shared by the -// queues considered by AutoQueue. -template <class S> -class QueueBase { - public: - typedef S StateId; - - QueueBase(QueueType type) : queue_type_(type), error_(false) {} - virtual ~QueueBase() {} - StateId Head() const { return Head_(); } - void Enqueue(StateId s) { Enqueue_(s); } - void Dequeue() { Dequeue_(); } - void Update(StateId s) { Update_(s); } - bool Empty() const { return Empty_(); } - void Clear() { Clear_(); } - QueueType Type() { return queue_type_; } - bool Error() const { return error_; } - void SetError(bool error) { error_ = error; } - - private: - // This allows base-class virtual access to non-virtual derived- - // class members of the same name. It makes the derived class more - // efficient to use but unsafe to further derive. - virtual StateId Head_() const = 0; - virtual void Enqueue_(StateId s) = 0; - virtual void Dequeue_() = 0; - virtual void Update_(StateId s) = 0; - virtual bool Empty_() const = 0; - virtual void Clear_() = 0; - - QueueType queue_type_; - bool error_; -}; - - -// Trivial queue discipline, templated on the StateId. You may enqueue -// at most one state at a time. It is used for strongly connected components -// with only one state and no self loops. -template <class S> -class TrivialQueue : public QueueBase<S> { -public: - typedef S StateId; - - TrivialQueue() : QueueBase<S>(TRIVIAL_QUEUE), front_(kNoStateId) {} - StateId Head() const { return front_; } - void Enqueue(StateId s) { front_ = s; } - void Dequeue() { front_ = kNoStateId; } - void Update(StateId s) {} - bool Empty() const { return front_ == kNoStateId; } - void Clear() { front_ = kNoStateId; } - - -private: - // This allows base-class virtual access to non-virtual derived- - // class members of the same name. It makes the derived class more - // efficient to use but unsafe to further derive. - virtual StateId Head_() const { return Head(); } - virtual void Enqueue_(StateId s) { Enqueue(s); } - virtual void Dequeue_() { Dequeue(); } - virtual void Update_(StateId s) { Update(s); } - virtual bool Empty_() const { return Empty(); } - virtual void Clear_() { return Clear(); } - - StateId front_; -}; - - -// First-in, first-out queue discipline, templated on the StateId. -template <class S> -class FifoQueue : public QueueBase<S>, public deque<S> { - public: - using deque<S>::back; - using deque<S>::push_front; - using deque<S>::pop_back; - using deque<S>::empty; - using deque<S>::clear; - - typedef S StateId; - - FifoQueue() : QueueBase<S>(FIFO_QUEUE) {} - StateId Head() const { return back(); } - void Enqueue(StateId s) { push_front(s); } - void Dequeue() { pop_back(); } - void Update(StateId s) {} - bool Empty() const { return empty(); } - void Clear() { clear(); } - - private: - // This allows base-class virtual access to non-virtual derived- - // class members of the same name. It makes the derived class more - // efficient to use but unsafe to further derive. - virtual StateId Head_() const { return Head(); } - virtual void Enqueue_(StateId s) { Enqueue(s); } - virtual void Dequeue_() { Dequeue(); } - virtual void Update_(StateId s) { Update(s); } - virtual bool Empty_() const { return Empty(); } - virtual void Clear_() { return Clear(); } -}; - - -// Last-in, first-out queue discipline, templated on the StateId. -template <class S> -class LifoQueue : public QueueBase<S>, public deque<S> { - public: - using deque<S>::front; - using deque<S>::push_front; - using deque<S>::pop_front; - using deque<S>::empty; - using deque<S>::clear; - - typedef S StateId; - - LifoQueue() : QueueBase<S>(LIFO_QUEUE) {} - StateId Head() const { return front(); } - void Enqueue(StateId s) { push_front(s); } - void Dequeue() { pop_front(); } - void Update(StateId s) {} - bool Empty() const { return empty(); } - void Clear() { clear(); } - - private: - // This allows base-class virtual access to non-virtual derived- - // class members of the same name. It makes the derived class more - // efficient to use but unsafe to further derive. - virtual StateId Head_() const { return Head(); } - virtual void Enqueue_(StateId s) { Enqueue(s); } - virtual void Dequeue_() { Dequeue(); } - virtual void Update_(StateId s) { Update(s); } - virtual bool Empty_() const { return Empty(); } - virtual void Clear_() { return Clear(); } -}; - - -// Shortest-first queue discipline, templated on the StateId and -// comparison function object. Comparison function object COMP is -// used to compare two StateIds. If a (single) state's order changes, -// it can be reordered in the queue with a call to Update(). -// If 'update == false', call to Update() does not reorder the queue. -template <typename S, typename C, bool update = true> -class ShortestFirstQueue : public QueueBase<S> { - public: - typedef S StateId; - typedef C Compare; - - ShortestFirstQueue(C comp) - : QueueBase<S>(SHORTEST_FIRST_QUEUE), heap_(comp) {} - - StateId Head() const { return heap_.Top(); } - - void Enqueue(StateId s) { - if (update) { - for (StateId i = key_.size(); i <= s; ++i) - key_.push_back(kNoKey); - key_[s] = heap_.Insert(s); - } else { - heap_.Insert(s); - } - } - - void Dequeue() { - if (update) - key_[heap_.Pop()] = kNoKey; - else - heap_.Pop(); - } - - void Update(StateId s) { - if (!update) - return; - if (s >= key_.size() || key_[s] == kNoKey) { - Enqueue(s); - } else { - heap_.Update(key_[s], s); - } - } - - bool Empty() const { return heap_.Empty(); } - - void Clear() { - heap_.Clear(); - if (update) key_.clear(); - } - - private: - Heap<S, C, false> heap_; - vector<ssize_t> key_; - - // This allows base-class virtual access to non-virtual derived- - // class members of the same name. It makes the derived class more - // efficient to use but unsafe to further derive. - virtual StateId Head_() const { return Head(); } - virtual void Enqueue_(StateId s) { Enqueue(s); } - virtual void Dequeue_() { Dequeue(); } - virtual void Update_(StateId s) { Update(s); } - virtual bool Empty_() const { return Empty(); } - virtual void Clear_() { return Clear(); } -}; - - -// Given a vector that maps from states to weights and a Less -// comparison function object between weights, this class defines a -// comparison function object between states. -template <typename S, typename L> -class StateWeightCompare { - public: - typedef L Less; - typedef typename L::Weight Weight; - typedef S StateId; - - StateWeightCompare(const vector<Weight>& weights, const L &less) - : weights_(weights), less_(less) {} - - bool operator()(const S x, const S y) const { - return less_(weights_[x], weights_[y]); - } - - private: - const vector<Weight>& weights_; - L less_; -}; - - -// Shortest-first queue discipline, templated on the StateId and Weight, is -// specialized to use the weight's natural order for the comparison function. -template <typename S, typename W> -class NaturalShortestFirstQueue : - public ShortestFirstQueue<S, StateWeightCompare<S, NaturalLess<W> > > { - public: - typedef StateWeightCompare<S, NaturalLess<W> > C; - - NaturalShortestFirstQueue(const vector<W> &distance) : - ShortestFirstQueue<S, C>(C(distance, less_)) {} - - private: - NaturalLess<W> less_; -}; - -// Topological-order queue discipline, templated on the StateId. -// States are ordered in the queue topologically. The FST must be acyclic. -template <class S> -class TopOrderQueue : public QueueBase<S> { - public: - typedef S StateId; - - // This constructor computes the top. order. It accepts an arc filter - // to limit the transitions considered in that computation (e.g., only - // the epsilon graph). - template <class Arc, class ArcFilter> - TopOrderQueue(const Fst<Arc> &fst, ArcFilter filter) - : QueueBase<S>(TOP_ORDER_QUEUE), front_(0), back_(kNoStateId), - order_(0), state_(0) { - bool acyclic; - TopOrderVisitor<Arc> top_order_visitor(&order_, &acyclic); - DfsVisit(fst, &top_order_visitor, filter); - if (!acyclic) { - FSTERROR() << "TopOrderQueue: fst is not acyclic."; - QueueBase<S>::SetError(true); - } - state_.resize(order_.size(), kNoStateId); - } - - // This constructor is passed the top. order, useful when we know it - // beforehand. - TopOrderQueue(const vector<StateId> &order) - : QueueBase<S>(TOP_ORDER_QUEUE), front_(0), back_(kNoStateId), - order_(order), state_(order.size(), kNoStateId) {} - - StateId Head() const { return state_[front_]; } - - void Enqueue(StateId s) { - if (front_ > back_) front_ = back_ = order_[s]; - else if (order_[s] > back_) back_ = order_[s]; - else if (order_[s] < front_) front_ = order_[s]; - state_[order_[s]] = s; - } - - void Dequeue() { - state_[front_] = kNoStateId; - while ((front_ <= back_) && (state_[front_] == kNoStateId)) ++front_; - } - - void Update(StateId s) {} - - bool Empty() const { return front_ > back_; } - - void Clear() { - for (StateId i = front_; i <= back_; ++i) state_[i] = kNoStateId; - back_ = kNoStateId; - front_ = 0; - } - - private: - StateId front_; - StateId back_; - vector<StateId> order_; - vector<StateId> state_; - - // This allows base-class virtual access to non-virtual derived- - // class members of the same name. It makes the derived class more - // efficient to use but unsafe to further derive. - virtual StateId Head_() const { return Head(); } - virtual void Enqueue_(StateId s) { Enqueue(s); } - virtual void Dequeue_() { Dequeue(); } - virtual void Update_(StateId s) { Update(s); } - virtual bool Empty_() const { return Empty(); } - virtual void Clear_() { return Clear(); } -}; - - -// State order queue discipline, templated on the StateId. -// States are ordered in the queue by state Id. -template <class S> -class StateOrderQueue : public QueueBase<S> { -public: - typedef S StateId; - - StateOrderQueue() - : QueueBase<S>(STATE_ORDER_QUEUE), front_(0), back_(kNoStateId) {} - - StateId Head() const { return front_; } - - void Enqueue(StateId s) { - if (front_ > back_) front_ = back_ = s; - else if (s > back_) back_ = s; - else if (s < front_) front_ = s; - while (enqueued_.size() <= s) enqueued_.push_back(false); - enqueued_[s] = true; - } - - void Dequeue() { - enqueued_[front_] = false; - while ((front_ <= back_) && (enqueued_[front_] == false)) ++front_; - } - - void Update(StateId s) {} - - bool Empty() const { return front_ > back_; } - - void Clear() { - for (StateId i = front_; i <= back_; ++i) enqueued_[i] = false; - front_ = 0; - back_ = kNoStateId; - } - -private: - StateId front_; - StateId back_; - vector<bool> enqueued_; - - // This allows base-class virtual access to non-virtual derived- - // class members of the same name. It makes the derived class more - // efficient to use but unsafe to further derive. - virtual StateId Head_() const { return Head(); } - virtual void Enqueue_(StateId s) { Enqueue(s); } - virtual void Dequeue_() { Dequeue(); } - virtual void Update_(StateId s) { Update(s); } - virtual bool Empty_() const { return Empty(); } - virtual void Clear_() { return Clear(); } - -}; - - -// SCC topological-order meta-queue discipline, templated on the StateId S -// and a queue Q, which is used inside each SCC. It visits the SCC's -// of an FST in topological order. Its constructor is passed the queues to -// to use within an SCC. -template <class S, class Q> -class SccQueue : public QueueBase<S> { - public: - typedef S StateId; - typedef Q Queue; - - // Constructor takes a vector specifying the SCC number per state - // and a vector giving the queue to use per SCC number. - SccQueue(const vector<StateId> &scc, vector<Queue*> *queue) - : QueueBase<S>(SCC_QUEUE), queue_(queue), scc_(scc), front_(0), - back_(kNoStateId) {} - - StateId Head() const { - while ((front_ <= back_) && - (((*queue_)[front_] && (*queue_)[front_]->Empty()) - || (((*queue_)[front_] == 0) && - ((front_ >= trivial_queue_.size()) - || (trivial_queue_[front_] == kNoStateId))))) - ++front_; - if ((*queue_)[front_]) - return (*queue_)[front_]->Head(); - else - return trivial_queue_[front_]; - } - - void Enqueue(StateId s) { - if (front_ > back_) front_ = back_ = scc_[s]; - else if (scc_[s] > back_) back_ = scc_[s]; - else if (scc_[s] < front_) front_ = scc_[s]; - if ((*queue_)[scc_[s]]) { - (*queue_)[scc_[s]]->Enqueue(s); - } else { - while (trivial_queue_.size() <= scc_[s]) - trivial_queue_.push_back(kNoStateId); - trivial_queue_[scc_[s]] = s; - } - } - - void Dequeue() { - if ((*queue_)[front_]) - (*queue_)[front_]->Dequeue(); - else if (front_ < trivial_queue_.size()) - trivial_queue_[front_] = kNoStateId; - } - - void Update(StateId s) { - if ((*queue_)[scc_[s]]) - (*queue_)[scc_[s]]->Update(s); - } - - bool Empty() const { - if (front_ < back_) // Queue scc # back_ not empty unless back_==front_ - return false; - else if (front_ > back_) - return true; - else if ((*queue_)[front_]) - return (*queue_)[front_]->Empty(); - else - return (front_ >= trivial_queue_.size()) - || (trivial_queue_[front_] == kNoStateId); - } - - void Clear() { - for (StateId i = front_; i <= back_; ++i) - if ((*queue_)[i]) - (*queue_)[i]->Clear(); - else if (i < trivial_queue_.size()) - trivial_queue_[i] = kNoStateId; - front_ = 0; - back_ = kNoStateId; - } - -private: - vector<Queue*> *queue_; - const vector<StateId> &scc_; - mutable StateId front_; - StateId back_; - vector<StateId> trivial_queue_; - - // This allows base-class virtual access to non-virtual derived- - // class members of the same name. It makes the derived class more - // efficient to use but unsafe to further derive. - virtual StateId Head_() const { return Head(); } - virtual void Enqueue_(StateId s) { Enqueue(s); } - virtual void Dequeue_() { Dequeue(); } - virtual void Update_(StateId s) { Update(s); } - virtual bool Empty_() const { return Empty(); } - virtual void Clear_() { return Clear(); } - - DISALLOW_COPY_AND_ASSIGN(SccQueue); -}; - - -// Automatic queue discipline, templated on the StateId. It selects a -// queue discipline for a given FST based on its properties. -template <class S> -class AutoQueue : public QueueBase<S> { -public: - typedef S StateId; - - // This constructor takes a state distance vector that, if non-null and if - // the Weight type has the path property, will entertain the - // shortest-first queue using the natural order w.r.t to the distance. - template <class Arc, class ArcFilter> - AutoQueue(const Fst<Arc> &fst, const vector<typename Arc::Weight> *distance, - ArcFilter filter) : QueueBase<S>(AUTO_QUEUE) { - typedef typename Arc::Weight Weight; - typedef StateWeightCompare< StateId, NaturalLess<Weight> > Compare; - - // First check if the FST is known to have these properties. - uint64 props = fst.Properties(kAcyclic | kCyclic | - kTopSorted | kUnweighted, false); - if ((props & kTopSorted) || fst.Start() == kNoStateId) { - queue_ = new StateOrderQueue<StateId>(); - VLOG(2) << "AutoQueue: using state-order discipline"; - } else if (props & kAcyclic) { - queue_ = new TopOrderQueue<StateId>(fst, filter); - VLOG(2) << "AutoQueue: using top-order discipline"; - } else if ((props & kUnweighted) && (Weight::Properties() & kIdempotent)) { - queue_ = new LifoQueue<StateId>(); - VLOG(2) << "AutoQueue: using LIFO discipline"; - } else { - uint64 properties; - // Decompose into strongly-connected components. - SccVisitor<Arc> scc_visitor(&scc_, 0, 0, &properties); - DfsVisit(fst, &scc_visitor, filter); - StateId nscc = *max_element(scc_.begin(), scc_.end()) + 1; - vector<QueueType> queue_types(nscc); - NaturalLess<Weight> *less = 0; - Compare *comp = 0; - if (distance && (Weight::Properties() & kPath)) { - less = new NaturalLess<Weight>; - comp = new Compare(*distance, *less); - } - // Find the queue type to use per SCC. - bool unweighted; - bool all_trivial; - SccQueueType(fst, scc_, &queue_types, filter, less, &all_trivial, - &unweighted); - // If unweighted and semiring is idempotent, use lifo queue. - if (unweighted) { - queue_ = new LifoQueue<StateId>(); - VLOG(2) << "AutoQueue: using LIFO discipline"; - delete comp; - delete less; - return; - } - // If all the scc are trivial, FST is acyclic and the scc# gives - // the topological order. - if (all_trivial) { - queue_ = new TopOrderQueue<StateId>(scc_); - VLOG(2) << "AutoQueue: using top-order discipline"; - delete comp; - delete less; - return; - } - VLOG(2) << "AutoQueue: using SCC meta-discipline"; - queues_.resize(nscc); - for (StateId i = 0; i < nscc; ++i) { - switch(queue_types[i]) { - case TRIVIAL_QUEUE: - queues_[i] = 0; - VLOG(3) << "AutoQueue: SCC #" << i - << ": using trivial discipline"; - break; - case SHORTEST_FIRST_QUEUE: - queues_[i] = new ShortestFirstQueue<StateId, Compare, false>(*comp); - VLOG(3) << "AutoQueue: SCC #" << i << - ": using shortest-first discipline"; - break; - case LIFO_QUEUE: - queues_[i] = new LifoQueue<StateId>(); - VLOG(3) << "AutoQueue: SCC #" << i - << ": using LIFO disciplle"; - break; - case FIFO_QUEUE: - default: - queues_[i] = new FifoQueue<StateId>(); - VLOG(3) << "AutoQueue: SCC #" << i - << ": using FIFO disciplle"; - break; - } - } - queue_ = new SccQueue< StateId, QueueBase<StateId> >(scc_, &queues_); - delete comp; - delete less; - } - } - - ~AutoQueue() { - for (StateId i = 0; i < queues_.size(); ++i) - delete queues_[i]; - delete queue_; - } - - StateId Head() const { return queue_->Head(); } - - void Enqueue(StateId s) { queue_->Enqueue(s); } - - void Dequeue() { queue_->Dequeue(); } - - void Update(StateId s) { queue_->Update(s); } - - bool Empty() const { return queue_->Empty(); } - - void Clear() { queue_->Clear(); } - - - private: - QueueBase<StateId> *queue_; - vector< QueueBase<StateId>* > queues_; - vector<StateId> scc_; - - template <class Arc, class ArcFilter, class Less> - static void SccQueueType(const Fst<Arc> &fst, - const vector<StateId> &scc, - vector<QueueType> *queue_types, - ArcFilter filter, Less *less, - bool *all_trivial, bool *unweighted); - - // This allows base-class virtual access to non-virtual derived- - // class members of the same name. It makes the derived class more - // efficient to use but unsafe to further derive. - virtual StateId Head_() const { return Head(); } - - virtual void Enqueue_(StateId s) { Enqueue(s); } - - virtual void Dequeue_() { Dequeue(); } - - virtual void Update_(StateId s) { Update(s); } - - virtual bool Empty_() const { return Empty(); } - - virtual void Clear_() { return Clear(); } - - DISALLOW_COPY_AND_ASSIGN(AutoQueue); -}; - - -// Examines the states in an Fst's strongly connected components and -// determines which type of queue to use per SCC. Stores result in -// vector QUEUE_TYPES, which is assumed to have length equal to the -// number of SCCs. An arc filter is used to limit the transitions -// considered (e.g., only the epsilon graph). ALL_TRIVIAL is set -// to true if every queue is the trivial queue. UNWEIGHTED is set to -// true if the semiring is idempotent and all the arc weights are equal to -// Zero() or One(). -template <class StateId> -template <class A, class ArcFilter, class Less> -void AutoQueue<StateId>::SccQueueType(const Fst<A> &fst, - const vector<StateId> &scc, - vector<QueueType> *queue_type, - ArcFilter filter, Less *less, - bool *all_trivial, bool *unweighted) { - typedef A Arc; - typedef typename A::StateId StateId; - typedef typename A::Weight Weight; - - *all_trivial = true; - *unweighted = true; - - for (StateId i = 0; i < queue_type->size(); ++i) - (*queue_type)[i] = TRIVIAL_QUEUE; - - for (StateIterator< Fst<Arc> > sit(fst); !sit.Done(); sit.Next()) { - StateId state = sit.Value(); - for (ArcIterator< Fst<Arc> > ait(fst, state); - !ait.Done(); - ait.Next()) { - const Arc &arc = ait.Value(); - if (!filter(arc)) continue; - if (scc[state] == scc[arc.nextstate]) { - QueueType &type = (*queue_type)[scc[state]]; - if (!less || ((*less)(arc.weight, Weight::One()))) - type = FIFO_QUEUE; - else if ((type == TRIVIAL_QUEUE) || (type == LIFO_QUEUE)) { - if (!(Weight::Properties() & kIdempotent) || - (arc.weight != Weight::Zero() && arc.weight != Weight::One())) - type = SHORTEST_FIRST_QUEUE; - else - type = LIFO_QUEUE; - } - if (type != TRIVIAL_QUEUE) *all_trivial = false; - } - if (!(Weight::Properties() & kIdempotent) || - (arc.weight != Weight::Zero() && arc.weight != Weight::One())) - *unweighted = false; - } - } -} - - -// An A* estimate is a function object that maps from a state ID to a -// an estimate of the shortest distance to the final states. -// The trivial A* estimate is always One(). -template <typename S, typename W> -struct TrivialAStarEstimate { - W operator()(S s) const { return W::One(); } -}; - - -// Given a vector that maps from states to weights representing the -// shortest distance from the initial state, a Less comparison -// function object between weights, and an estimate E of the -// shortest distance to the final states, this class defines a -// comparison function object between states. -template <typename S, typename L, typename E> -class AStarWeightCompare { - public: - typedef L Less; - typedef typename L::Weight Weight; - typedef S StateId; - - AStarWeightCompare(const vector<Weight>& weights, const L &less, - const E &estimate) - : weights_(weights), less_(less), estimate_(estimate) {} - - bool operator()(const S x, const S y) const { - Weight wx = Times(weights_[x], estimate_(x)); - Weight wy = Times(weights_[y], estimate_(y)); - return less_(wx, wy); - } - - private: - const vector<Weight>& weights_; - L less_; - const E &estimate_; -}; - - -// A* queue discipline, templated on the StateId, Weight and an -// estimate E of the shortest distance to the final states, is specialized -// to use the weight's natural order for the comparison function. -template <typename S, typename W, typename E> -class NaturalAStarQueue : - public ShortestFirstQueue<S, AStarWeightCompare<S, NaturalLess<W>, E> > { - public: - typedef AStarWeightCompare<S, NaturalLess<W>, E> C; - - NaturalAStarQueue(const vector<W> &distance, const E &estimate) : - ShortestFirstQueue<S, C>(C(distance, less_, estimate)) {} - - private: - NaturalLess<W> less_; -}; - - -// A state equivalence class is a function object that -// maps from a state ID to an equivalence class (state) ID. -// The trivial equivalence class maps a state to itself. -template <typename S> -struct TrivialStateEquivClass { - S operator()(S s) const { return s; } -}; - - -// Distance-based pruning queue discipline: Enqueues a state 's' -// only when its shortest distance (so far), as specified by -// 'distance', is less than (as specified by 'comp') the shortest -// distance Times() the 'threshold' to any state in the same -// equivalence class, as specified by the function object -// 'class_func'. The underlying queue discipline is specified by -// 'queue'. The ownership of 'queue' is given to this class. -template <typename Q, typename L, typename C> -class PruneQueue : public QueueBase<typename Q::StateId> { - public: - typedef typename Q::StateId StateId; - typedef typename L::Weight Weight; - - PruneQueue(const vector<Weight> &distance, Q *queue, L comp, - const C &class_func, Weight threshold) - : QueueBase<StateId>(OTHER_QUEUE), - distance_(distance), - queue_(queue), - less_(comp), - class_func_(class_func), - threshold_(threshold) {} - - ~PruneQueue() { delete queue_; } - - StateId Head() const { return queue_->Head(); } - - void Enqueue(StateId s) { - StateId c = class_func_(s); - if (c >= class_distance_.size()) - class_distance_.resize(c + 1, Weight::Zero()); - if (less_(distance_[s], class_distance_[c])) - class_distance_[c] = distance_[s]; - - // Enqueue only if below threshold limit - Weight limit = Times(class_distance_[c], threshold_); - if (less_(distance_[s], limit)) - queue_->Enqueue(s); - } - - void Dequeue() { queue_->Dequeue(); } - - void Update(StateId s) { - StateId c = class_func_(s); - if (less_(distance_[s], class_distance_[c])) - class_distance_[c] = distance_[s]; - queue_->Update(s); - } - - bool Empty() const { return queue_->Empty(); } - void Clear() { queue_->Clear(); } - - private: - // This allows base-class virtual access to non-virtual derived- - // class members of the same name. It makes the derived class more - // efficient to use but unsafe to further derive. - virtual StateId Head_() const { return Head(); } - virtual void Enqueue_(StateId s) { Enqueue(s); } - virtual void Dequeue_() { Dequeue(); } - virtual void Update_(StateId s) { Update(s); } - virtual bool Empty_() const { return Empty(); } - virtual void Clear_() { return Clear(); } - - const vector<Weight> &distance_; // shortest distance to state - Q *queue_; - L less_; - const C &class_func_; // eqv. class function object - Weight threshold_; // pruning weight threshold - vector<Weight> class_distance_; // shortest distance to class - - DISALLOW_COPY_AND_ASSIGN(PruneQueue); -}; - - -// Pruning queue discipline (see above) using the weight's natural -// order for the comparison function. The ownership of 'queue' is -// given to this class. -template <typename Q, typename W, typename C> -class NaturalPruneQueue : - public PruneQueue<Q, NaturalLess<W>, C> { - public: - typedef typename Q::StateId StateId; - typedef W Weight; - - NaturalPruneQueue(const vector<W> &distance, Q *queue, - const C &class_func_, Weight threshold) : - PruneQueue<Q, NaturalLess<W>, C>(distance, queue, less_, - class_func_, threshold) {} - - private: - NaturalLess<W> less_; -}; - - -// Filter-based pruning queue discipline: Enqueues a state 's' only -// if allowed by the filter, specified by the function object 'state_filter'. -// The underlying queue discipline is specified by 'queue'. The ownership -// of 'queue' is given to this class. -template <typename Q, typename F> -class FilterQueue : public QueueBase<typename Q::StateId> { - public: - typedef typename Q::StateId StateId; - - FilterQueue(Q *queue, const F &state_filter) - : QueueBase<StateId>(OTHER_QUEUE), - queue_(queue), - state_filter_(state_filter) {} - - ~FilterQueue() { delete queue_; } - - StateId Head() const { return queue_->Head(); } - - // Enqueues only if allowed by state filter. - void Enqueue(StateId s) { - if (state_filter_(s)) { - queue_->Enqueue(s); - } - } - - void Dequeue() { queue_->Dequeue(); } - - void Update(StateId s) {} - bool Empty() const { return queue_->Empty(); } - void Clear() { queue_->Clear(); } - - private: - // This allows base-class virtual access to non-virtual derived- - // class members of the same name. It makes the derived class more - // efficient to use but unsafe to further derive. - virtual StateId Head_() const { return Head(); } - virtual void Enqueue_(StateId s) { Enqueue(s); } - virtual void Dequeue_() { Dequeue(); } - virtual void Update_(StateId s) { Update(s); } - virtual bool Empty_() const { return Empty(); } - virtual void Clear_() { return Clear(); } - - Q *queue_; - const F &state_filter_; // Filter to prune states - - DISALLOW_COPY_AND_ASSIGN(FilterQueue); -}; - -} // namespace fst - -#endif |