1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License"); 3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License. 4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at 5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://www.apache.org/licenses/LICENSE-2.0 7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software 9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS, 10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and 12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License. 13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc. 15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: jpr@google.com (Jake Ratkiewicz) 16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_SCRIPT_SHORTEST_DISTANCE_H_ 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_SCRIPT_SHORTEST_DISTANCE_H_ 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <vector> 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::vector; 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/script/arg-packs.h> 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/script/fst-class.h> 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/script/weight-class.h> 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/script/prune.h> // for ArcFilterType 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/queue.h> // for QueueType 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/shortest-distance.h> 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace script { 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonenum ArcFilterType { ANY_ARC_FILTER, EPSILON_ARC_FILTER, 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson INPUT_EPSILON_ARC_FILTER, OUTPUT_EPSILON_ARC_FILTER }; 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See nlp/fst/lib/shortest-distance.h for the template options class 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// that this one shadows 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct ShortestDistanceOptions { 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const QueueType queue_type; 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const ArcFilterType arc_filter_type; 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const int64 source; 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const float delta; 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const bool first_path; 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistanceOptions(QueueType qt, ArcFilterType aft, int64 s, 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson float d) 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson : queue_type(qt), arc_filter_type(aft), source(s), delta(d), 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson first_path(false) { } 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 1 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontypedef args::Package<const FstClass &, vector<WeightClass> *, 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const ShortestDistanceOptions &> ShortestDistanceArgs1; 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Queue, class Arc, class ArcFilter> 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct QueueConstructor { 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // template<class Arc, class ArcFilter> 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static Queue *Construct(const Fst<Arc> &, 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<typename Arc::Weight> *) { 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return new Queue(); 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Specializations to deal with AutoQueue, NaturalShortestFirstQueue, 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// and TopOrderQueue's different constructors 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class ArcFilter> 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct QueueConstructor<AutoQueue<typename Arc::StateId>, Arc, ArcFilter> { 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // template<class Arc, class ArcFilter> 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static AutoQueue<typename Arc::StateId> *Construct( 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &fst, 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<typename Arc::Weight> *distance) { 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return new AutoQueue<typename Arc::StateId>(fst, distance, ArcFilter()); 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class ArcFilter> 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct QueueConstructor<NaturalShortestFirstQueue<typename Arc::StateId, 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename Arc::Weight>, 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Arc, ArcFilter> { 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // template<class Arc, class ArcFilter> 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static NaturalShortestFirstQueue<typename Arc::StateId, typename Arc::Weight> 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson *Construct(const Fst<Arc> &fst, 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const vector<typename Arc::Weight> *distance) { 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return new NaturalShortestFirstQueue<typename Arc::StateId, 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typename Arc::Weight>(*distance); 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class ArcFilter> 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstruct QueueConstructor<TopOrderQueue<typename Arc::StateId>, Arc, ArcFilter> { 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // template<class Arc, class ArcFilter> 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson static TopOrderQueue<typename Arc::StateId> *Construct( 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &fst, const vector<typename Arc::Weight> *weights) { 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return new TopOrderQueue<typename Arc::StateId>(fst, ArcFilter()); 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc, class Queue> 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestDistanceHelper(ShortestDistanceArgs1 *args) { 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &fst = *(args->arg1.GetFst<Arc>()); 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const ShortestDistanceOptions &opts = args->arg3; 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<typename Arc::Weight> weights; 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson switch (opts.arc_filter_type) { 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case ANY_ARC_FILTER: { 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *queue = 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson QueueConstructor<Queue, Arc, AnyArcFilter<Arc> >::Construct( 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst, &weights); 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst::ShortestDistanceOptions<Arc, Queue, AnyArcFilter<Arc> > sdopts( 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue, AnyArcFilter<Arc>(), opts.source, opts.delta); 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(fst, &weights, sdopts); 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete queue; 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson break; 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case EPSILON_ARC_FILTER: { 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *queue = 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson QueueConstructor<Queue, Arc, AnyArcFilter<Arc> >::Construct( 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst, &weights); 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst::ShortestDistanceOptions<Arc, Queue, 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson EpsilonArcFilter<Arc> > sdopts( 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue, EpsilonArcFilter<Arc>(), opts.source, opts.delta); 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(fst, &weights, sdopts); 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete queue; 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson break; 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case INPUT_EPSILON_ARC_FILTER: { 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *queue = 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson QueueConstructor<Queue, Arc, InputEpsilonArcFilter<Arc> >::Construct( 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst, &weights); 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst::ShortestDistanceOptions<Arc, Queue, 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson InputEpsilonArcFilter<Arc> > sdopts( 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue, InputEpsilonArcFilter<Arc>(), opts.source, opts.delta); 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(fst, &weights, sdopts); 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete queue; 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson break; 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case OUTPUT_EPSILON_ARC_FILTER: { 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Queue *queue = 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson QueueConstructor<Queue, Arc, 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson OutputEpsilonArcFilter<Arc> >::Construct( 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst, &weights); 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson fst::ShortestDistanceOptions<Arc, Queue, 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson OutputEpsilonArcFilter<Arc> > sdopts( 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson queue, OutputEpsilonArcFilter<Arc>(), opts.source, opts.delta); 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(fst, &weights, sdopts); 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson delete queue; 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson break; 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Copy the weights back 156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson args->arg2->resize(weights.size()); 157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (unsigned i = 0; i < weights.size(); ++i) { 158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (*args->arg2)[i] = WeightClass(weights[i]); 159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 160f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 161f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 162f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> 163f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestDistance(ShortestDistanceArgs1 *args) { 164f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const ShortestDistanceOptions &opts = args->arg3; 165f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::StateId StateId; 166f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson typedef typename Arc::Weight Weight; 167f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 168f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Must consider (opts.queue_type x opts.filter_type) options 169f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson switch (opts.queue_type) { 170f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson default: 171f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson FSTERROR() << "Unknown queue type." << opts.queue_type; 172f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 173f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case AUTO_QUEUE: 174f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistanceHelper<Arc, AutoQueue<StateId> >(args); 175f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 176f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 177f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case FIFO_QUEUE: 1785b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin ShortestDistanceHelper<Arc, FifoQueue<StateId> >(args); 179f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 180f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 181f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case LIFO_QUEUE: 1825b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin ShortestDistanceHelper<Arc, LifoQueue<StateId> >(args); 183f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 184f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 185f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case SHORTEST_FIRST_QUEUE: 186f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistanceHelper<Arc, 187f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson NaturalShortestFirstQueue<StateId, Weight> >(args); 188f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 189f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 190f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case STATE_ORDER_QUEUE: 1915b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin ShortestDistanceHelper<Arc, StateOrderQueue<StateId> >(args); 192f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 193f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 194f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson case TOP_ORDER_QUEUE: 1955b6dc79427b8f7eeb6a7ff68034ab8548ce670eaAlexander Gutkin ShortestDistanceHelper<Arc, TopOrderQueue<StateId> >(args); 196f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return; 197f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 198f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 199f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 200f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 2 201f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontypedef args::Package<const FstClass&, vector<WeightClass>*, 202f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool, double> ShortestDistanceArgs2; 203f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 204f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> 205f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestDistance(ShortestDistanceArgs2 *args) { 206f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &fst = *(args->arg1.GetFst<Arc>()); 207f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<typename Arc::Weight> distance; 208f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 209f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ShortestDistance(fst, &distance, args->arg3, args->arg4); 210f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 211f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // convert the typed weights back into weightclass 212f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<WeightClass> *retval = args->arg2; 213f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson retval->resize(distance.size()); 214f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 215f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson for (unsigned i = 0; i < distance.size(); ++i) { 216f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson (*retval)[i] = WeightClass(distance[i]); 217f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 218f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 219f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 220f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 3 221f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontypedef args::WithReturnValue<WeightClass, 222f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const FstClass &> ShortestDistanceArgs3; 223f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 224f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate<class Arc> 225f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestDistance(ShortestDistanceArgs3 *args) { 226f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const Fst<Arc> &fst = *(args->args.GetFst<Arc>()); 227f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 228f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson args->retval = WeightClass(ShortestDistance(fst)); 229f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} 230f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 231f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 232f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 1 233f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestDistance(const FstClass &fst, vector<WeightClass> *distance, 234f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson const ShortestDistanceOptions &opts); 235f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 236f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 2 237f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonvoid ShortestDistance(const FstClass &ifst, vector<WeightClass> *distance, 238f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool reverse = false, double delta = fst::kDelta); 239f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 240f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef SWIG 241f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 3 242f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian HodsonWeightClass ShortestDistance(const FstClass &ifst); 243f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif 244f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 245f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace script 246f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 247f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 248f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 249f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 250f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_SCRIPT_SHORTEST_DISTANCE_H_ 251