src/include/fst/arcsort.h

// arcsort.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: riley@google.com (Michael Riley)
//
// \file
// Functions and classes to sort arcs in an FST.

#ifndef FST_LIB_ARCSORT_H__
#define FST_LIB_ARCSORT_H__

#include <algorithm>
#include <string>
#include <vector>
using std::vector;

#include <fst/cache.h>
#include <fst/state-map.h>
#include <fst/test-properties.h>


namespace fst {

template <class Arc, class Compare>
class ArcSortMapper {
 public:
  typedef Arc FromArc;
  typedef Arc ToArc;

  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;

  ArcSortMapper(const Fst<Arc> &fst, const Compare &comp)
      : fst_(fst), comp_(comp), i_(0) {}

  // Allows updating Fst argument; pass only if changed.
  ArcSortMapper(const ArcSortMapper<Arc, Compare> &mapper,
                const Fst<Arc> *fst = 0)
      : fst_(fst ? *fst : mapper.fst_), comp_(mapper.comp_), i_(0) {}

  StateId Start() { return fst_.Start(); }
  Weight Final(StateId s) const { return fst_.Final(s); }

  void SetState(StateId s) {
    i_ = 0;
    arcs_.clear();
    arcs_.reserve(fst_.NumArcs(s));
    for (ArcIterator< Fst<Arc> > aiter(fst_, s); !aiter.Done(); aiter.Next())
      arcs_.push_back(aiter.Value());
    sort(arcs_.begin(), arcs_.end(), comp_);
  }

  bool Done() const { return i_ >= arcs_.size(); }
  const Arc &Value() const { return arcs_[i_]; }
  void Next() { ++i_; }

  MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
  MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS; }
  uint64 Properties(uint64 props) const { return comp_.Properties(props); }

 private:
  const Fst<Arc> &fst_;
  const Compare &comp_;
  vector<Arc> arcs_;
  ssize_t i_;               // current arc position

  void operator=(const ArcSortMapper<Arc, Compare> &);  // disallow
};


// Sorts the arcs in an FST according to function object 'comp' of
// type Compare. This version modifies its input.  Comparison function
// objects ILabelCompare and OLabelCompare are provived by the
// library. In general, Compare must meet the requirements for an STL
// sort comparision function object. It must also have a member
// Properties(uint64) that specifies the known properties of the
// sorted FST; it takes as argument the input FST's known properties
// before the sort.
//
// Complexity:
// - Time: O(V D log D)
// - Space: O(D)
// where V = # of states and D = maximum out-degree.
template<class Arc, class Compare>
void ArcSort(MutableFst<Arc> *fst, Compare comp) {
  ArcSortMapper<Arc, Compare> mapper(*fst, comp);
  StateMap(fst, mapper);
}

typedef CacheOptions ArcSortFstOptions;

// Sorts the arcs in an FST according to function object 'comp' of
// type Compare. This version is a delayed Fst.  Comparsion function
// objects ILabelCompare and OLabelCompare are provided by the
// library. In general, Compare must meet the requirements for an STL
// comparision function object (e.g. as used for STL sort). It must
// also have a member Properties(uint64) that specifies the known
// properties of the sorted FST; it takes as argument the input FST's
// known properties.
//
// Complexity:
// - Time: O(v d log d)
// - Space: O(d)
// where v = # of states visited, d = maximum out-degree of states
// visited. Constant time and space to visit an input state is assumed
// and exclusive of caching.
template <class A, class C>
class ArcSortFst : public StateMapFst<A, A, ArcSortMapper<A, C> > {
 public:
  typedef A Arc;
 typedef ArcSortMapper<A, C> M;

  ArcSortFst(const Fst<A> &fst, const C &comp)
      : StateMapFst<A, A, M>(fst, ArcSortMapper<A, C>(fst, comp)) {}

  ArcSortFst(const Fst<A> &fst, const C &comp, const ArcSortFstOptions &opts)
      : StateMapFst<A, A, M>(fst, ArcSortMapper<A, C>(fst, comp), opts) {}

  // See Fst<>::Copy() for doc.
  ArcSortFst(const ArcSortFst<A, C> &fst, bool safe = false)
      : StateMapFst<A, A, M>(fst, safe) {}

  // Get a copy of this ArcSortFst. See Fst<>::Copy() for further doc.
  virtual ArcSortFst<A, C> *Copy(bool safe = false) const {
    return new ArcSortFst(*this, safe);
  }
};


// Specialization for ArcSortFst.
template <class A, class C>
class StateIterator< ArcSortFst<A, C> >
    : public StateIterator< StateMapFst<A, A,  ArcSortMapper<A, C> > > {
 public:
  explicit StateIterator(const ArcSortFst<A, C> &fst)
      : StateIterator< StateMapFst<A, A,  ArcSortMapper<A, C> > >(fst) {}
};


// Specialization for ArcSortFst.
template <class A, class C>
class ArcIterator< ArcSortFst<A, C> >
    : public ArcIterator< StateMapFst<A, A,  ArcSortMapper<A, C> > > {
 public:
  ArcIterator(const ArcSortFst<A, C> &fst, typename A::StateId s)
      : ArcIterator< StateMapFst<A, A,  ArcSortMapper<A, C> > >(fst, s) {}
};


// Compare class for comparing input labels of arcs.
template<class A> class ILabelCompare {
 public:
  bool operator() (A arc1, A arc2) const {
    return arc1.ilabel < arc2.ilabel;
  }

  uint64 Properties(uint64 props) const {
    return (props & kArcSortProperties) | kILabelSorted |
        (props & kAcceptor ? kOLabelSorted : 0);
  }
};


// Compare class for comparing output labels of arcs.
template<class A> class OLabelCompare {
 public:
  bool operator() (const A &arc1, const A &arc2) const {
    return arc1.olabel < arc2.olabel;
  }

  uint64 Properties(uint64 props) const {
    return (props & kArcSortProperties) | kOLabelSorted |
        (props & kAcceptor ? kILabelSorted : 0);
  }
};


// Useful aliases when using StdArc.
template<class C> class StdArcSortFst : public ArcSortFst<StdArc, C> {
 public:
  typedef StdArc Arc;
  typedef C Compare;
};

typedef ILabelCompare<StdArc> StdILabelCompare;

typedef OLabelCompare<StdArc> StdOLabelCompare;

}  // namespace fst

#endif  // FST_LIB_ARCSORT_H__