src/include/fst/script/shortest-distance.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: jpr@google.com (Jake Ratkiewicz)

#ifndef FST_SCRIPT_SHORTEST_DISTANCE_H_
#define FST_SCRIPT_SHORTEST_DISTANCE_H_

#include <vector>
using std::vector;

#include <fst/script/arg-packs.h>
#include <fst/script/fst-class.h>
#include <fst/script/weight-class.h>
#include <fst/script/prune.h>  // for ArcFilterType
#include <fst/queue.h>  // for QueueType
#include <fst/shortest-distance.h>

namespace fst {
namespace script {

enum ArcFilterType { ANY_ARC_FILTER, EPSILON_ARC_FILTER,
                     INPUT_EPSILON_ARC_FILTER, OUTPUT_EPSILON_ARC_FILTER };

// See nlp/fst/lib/shortest-distance.h for the template options class
// that this one shadows
struct ShortestDistanceOptions {
  const QueueType queue_type;
  const ArcFilterType arc_filter_type;
  const int64 source;
  const float delta;
  const bool first_path;

  ShortestDistanceOptions(QueueType qt, ArcFilterType aft, int64 s,
                          float d)
      : queue_type(qt), arc_filter_type(aft), source(s), delta(d),
        first_path(false) { }
};



// 1
typedef args::Package<const FstClass &, vector<WeightClass> *,
                      const ShortestDistanceOptions &> ShortestDistanceArgs1;

template<class Queue, class Arc, class ArcFilter>
struct QueueConstructor {
  //  template<class Arc, class ArcFilter>
  static Queue *Construct(const Fst<Arc> &,
                          const vector<typename Arc::Weight> *) {
    return new Queue();
  }
};

// Specializations to deal with AutoQueue, NaturalShortestFirstQueue,
// and TopOrderQueue's different constructors
template<class Arc, class ArcFilter>
struct QueueConstructor<AutoQueue<typename Arc::StateId>, Arc, ArcFilter> {
  //  template<class Arc, class ArcFilter>
  static AutoQueue<typename Arc::StateId> *Construct(
      const Fst<Arc> &fst,
      const vector<typename Arc::Weight> *distance) {
    return new AutoQueue<typename Arc::StateId>(fst, distance, ArcFilter());
  }
};

template<class Arc, class ArcFilter>
struct QueueConstructor<NaturalShortestFirstQueue<typename Arc::StateId,
                                                  typename Arc::Weight>,
                        Arc, ArcFilter> {
  //  template<class Arc, class ArcFilter>
  static NaturalShortestFirstQueue<typename Arc::StateId, typename Arc::Weight>
  *Construct(const Fst<Arc> &fst,
            const vector<typename Arc::Weight> *distance) {
    return new NaturalShortestFirstQueue<typename Arc::StateId,
                                         typename Arc::Weight>(*distance);
  }
};

template<class Arc, class ArcFilter>
struct QueueConstructor<TopOrderQueue<typename Arc::StateId>, Arc, ArcFilter> {
  //  template<class Arc, class ArcFilter>
  static TopOrderQueue<typename Arc::StateId> *Construct(
      const Fst<Arc> &fst, const vector<typename Arc::Weight> *weights) {
    return new TopOrderQueue<typename Arc::StateId>(fst, ArcFilter());
  }
};


template<class Arc, class Queue>
void ShortestDistanceHelper(ShortestDistanceArgs1 *args) {
  const Fst<Arc> &fst = *(args->arg1.GetFst<Arc>());
  const ShortestDistanceOptions &opts = args->arg3;

  vector<typename Arc::Weight> weights;

  switch (opts.arc_filter_type) {
    case ANY_ARC_FILTER: {
      Queue *queue =
          QueueConstructor<Queue, Arc, AnyArcFilter<Arc> >::Construct(
              fst, &weights);
      fst::ShortestDistanceOptions<Arc, Queue, AnyArcFilter<Arc> > sdopts(
          queue, AnyArcFilter<Arc>(), opts.source, opts.delta);
      ShortestDistance(fst, &weights, sdopts);
      delete queue;
      break;
    }
    case EPSILON_ARC_FILTER: {
      Queue *queue =
          QueueConstructor<Queue, Arc, AnyArcFilter<Arc> >::Construct(
              fst, &weights);
      fst::ShortestDistanceOptions<Arc, Queue,
          EpsilonArcFilter<Arc> > sdopts(
              queue, EpsilonArcFilter<Arc>(), opts.source, opts.delta);
      ShortestDistance(fst, &weights, sdopts);
      delete queue;
      break;
    }
    case INPUT_EPSILON_ARC_FILTER: {
      Queue *queue =
          QueueConstructor<Queue, Arc, InputEpsilonArcFilter<Arc> >::Construct(
              fst, &weights);
      fst::ShortestDistanceOptions<Arc, Queue,
          InputEpsilonArcFilter<Arc> > sdopts(
              queue, InputEpsilonArcFilter<Arc>(), opts.source, opts.delta);
      ShortestDistance(fst, &weights, sdopts);
      delete queue;
      break;
    }
    case OUTPUT_EPSILON_ARC_FILTER: {
      Queue *queue =
          QueueConstructor<Queue, Arc,
          OutputEpsilonArcFilter<Arc> >::Construct(
              fst, &weights);
      fst::ShortestDistanceOptions<Arc, Queue,
          OutputEpsilonArcFilter<Arc> > sdopts(
              queue, OutputEpsilonArcFilter<Arc>(), opts.source, opts.delta);
      ShortestDistance(fst, &weights, sdopts);
      delete queue;
      break;
    }
  }

  // Copy the weights back
  args->arg2->resize(weights.size());
  for (unsigned i = 0; i < weights.size(); ++i) {
    (*args->arg2)[i] = WeightClass(weights[i]);
  }
}

template<class Arc>
void ShortestDistance(ShortestDistanceArgs1 *args) {
  const ShortestDistanceOptions &opts = args->arg3;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;

  // Must consider (opts.queue_type x opts.filter_type) options
  switch (opts.queue_type) {
    default:
      FSTERROR() << "Unknown queue type." << opts.queue_type;

    case AUTO_QUEUE:
      ShortestDistanceHelper<Arc, AutoQueue<StateId> >(args);
      return;

    case FIFO_QUEUE:
       ShortestDistanceHelper<Arc, FifoQueue<StateId> >(args);
      return;

    case LIFO_QUEUE:
       ShortestDistanceHelper<Arc, LifoQueue<StateId> >(args);
      return;

    case SHORTEST_FIRST_QUEUE:
      ShortestDistanceHelper<Arc,
        NaturalShortestFirstQueue<StateId, Weight> >(args);
      return;

    case STATE_ORDER_QUEUE:
       ShortestDistanceHelper<Arc, StateOrderQueue<StateId> >(args);
      return;

    case TOP_ORDER_QUEUE:
       ShortestDistanceHelper<Arc, TopOrderQueue<StateId> >(args);
      return;
  }
}

// 2
typedef args::Package<const FstClass&, vector<WeightClass>*,
                      bool, double> ShortestDistanceArgs2;

template<class Arc>
void ShortestDistance(ShortestDistanceArgs2 *args) {
  const Fst<Arc> &fst = *(args->arg1.GetFst<Arc>());
  vector<typename Arc::Weight> distance;

  ShortestDistance(fst, &distance, args->arg3, args->arg4);

  // convert the typed weights back into weightclass
  vector<WeightClass> *retval = args->arg2;
  retval->resize(distance.size());

  for (unsigned i = 0; i < distance.size(); ++i) {
    (*retval)[i] = WeightClass(distance[i]);
  }
}

// 3
typedef args::WithReturnValue<WeightClass,
                              const FstClass &> ShortestDistanceArgs3;

template<class Arc>
void ShortestDistance(ShortestDistanceArgs3 *args) {
  const Fst<Arc> &fst = *(args->args.GetFst<Arc>());

  args->retval = WeightClass(ShortestDistance(fst));
}


// 1
void ShortestDistance(const FstClass &fst, vector<WeightClass> *distance,
                      const ShortestDistanceOptions &opts);

// 2
void ShortestDistance(const FstClass &ifst, vector<WeightClass> *distance,
                      bool reverse = false, double delta = fst::kDelta);

#ifndef SWIG
// 3
WeightClass ShortestDistance(const FstClass &ifst);
#endif

}  // namespace script
}  // namespace fst



#endif  // FST_SCRIPT_SHORTEST_DISTANCE_H_