// 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: allauzen@google.com (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(