src/include/fst/label-reachable.h - platform/external/openfst - Git at Google

 // label_reachable.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
 // Class to determine if a non-epsilon label can be read as the
 // first non-epsilon symbol along some path from a given state.


 #ifndef FST_LIB_LABEL_REACHABLE_H__
 #define FST_LIB_LABEL_REACHABLE_H__

 #include <unordered_map>
 using std::tr1::unordered_map;
 using std::tr1::unordered_multimap;
 #include <vector>
 using std::vector;

 #include <fst/accumulator.h>
 #include <fst/arcsort.h>
 #include <fst/interval-set.h>
 #include <fst/state-reachable.h>
 #include <fst/vector-fst.h>


 namespace fst {

 // Stores shareable data for label reachable class copies.
 template <typename L>
 class LabelReachableData {
  public:
   typedef L Label;
   typedef typename IntervalSet<L>::Interval Interval;

   explicit LabelReachableData(bool reach_input, bool keep_relabel_data = true)
       : reach_input_(reach_input),
         keep_relabel_data_(keep_relabel_data),
         have_relabel_data_(true),
         final_label_(kNoLabel) {}

   ~LabelReachableData() {}

   bool ReachInput() const { return reach_input_; }

   vector< IntervalSet<L> > *IntervalSets() { return &isets_; }

   unordered_map<L, L> *Label2Index() {
     if (!have_relabel_data_)
       FSTERROR() << "LabelReachableData: no relabeling data";
     return &label2index_;
   }

   Label FinalLabel() {
     if (final_label_ == kNoLabel)
       final_label_ = label2index_[kNoLabel];
     return final_label_;
   }

   static LabelReachableData<L> *Read(istream &istrm) {
     LabelReachableData<L> *data = new LabelReachableData<L>();

     ReadType(istrm, &data->reach_input_);
     ReadType(istrm, &data->keep_relabel_data_);
     data->have_relabel_data_ = data->keep_relabel_data_;
     if (data->keep_relabel_data_)
       ReadType(istrm, &data->label2index_);
     ReadType(istrm, &data->final_label_);
     ReadType(istrm, &data->isets_);
     return data;
   }

   bool Write(ostream &ostrm) {
     WriteType(ostrm, reach_input_);
     WriteType(ostrm, keep_relabel_data_);
     if (keep_relabel_data_)
       WriteType(ostrm, label2index_);
     WriteType(ostrm, FinalLabel());
     WriteType(ostrm, isets_);
     return true;
   }

   int RefCount() const { return ref_count_.count(); }
   int IncrRefCount() { return ref_count_.Incr(); }
   int DecrRefCount() { return ref_count_.Decr(); }

  private:
   LabelReachableData() {}

   bool reach_input_;                  // Input or output labels considered?
   bool keep_relabel_data_;            // Save label2index_ to file?
   bool have_relabel_data_;            // Using label2index_?
   Label final_label_;                 // Final label
   RefCounter ref_count_;              // Reference count.
   unordered_map<L, L> label2index_;        // Finds index for a label.
   vector<IntervalSet <L> > isets_;    // Interval sets per state.

   DISALLOW_COPY_AND_ASSIGN(LabelReachableData);
 };


 // Tests reachability of labels from a given state. If reach_input =
 // true, then input labels are considered, o.w. output labels are
 // considered. To test for reachability from a state s, first do
 // SetState(s). Then a label l can be reached from state s of FST f
 // iff Reach(r) is true where r = Relabel(l). The relabeling is
 // required to ensure a compact representation of the reachable
 // labels.

 // The whole FST can be relabeled instead with Relabel(&f,
 // reach_input) so that the test Reach(r) applies directly to the
 // labels of the transformed FST f. The relabeled FST will also be
 // sorted appropriately for composition.
 //
 // Reachablity of a final state from state s (via an epsilon path)
 // can be tested with ReachFinal();
 //
 // Reachability can also be tested on the set of labels specified by
 // an arc iterator, useful for FST composition.  In particular,
 // Reach(aiter, ...) is true if labels on the input (output) side of
 // the transitions of the arc iterator, when iter_input is true
 // (false), can be reached from the state s. The iterator labels must
 // have already been relabeled.
 //
 // With the arc iterator test of reachability, the begin position, end
 // position and accumulated arc weight of the matches can be
 // returned. The optional template argument controls how reachable arc
 // weights are accumulated.  The default uses the semiring
 // Plus(). Alternative ones can be used to distribute the weights in
 // composition in various ways.
 template <class A, class S = DefaultAccumulator<A> >
 class LabelReachable {
  public:
   typedef A Arc;
   typedef typename A::StateId StateId;
   typedef typename A::Label Label;
   typedef typename A::Weight Weight;
   typedef typename IntervalSet<Label>::Interval Interval;

   LabelReachable(const Fst<A> &fst, bool reach_input, S *s = 0,
                  bool keep_relabel_data = true)
       : fst_(new VectorFst<Arc>(fst)),
         s_(kNoStateId),
         data_(new LabelReachableData<Label>(reach_input, keep_relabel_data)),
         accumulator_(s ? s : new S()),
         ncalls_(0),
         nintervals_(0),
         error_(false) {
     StateId ins = fst_->NumStates();
     TransformFst();
     FindIntervals(ins);
     delete fst_;
   }

   explicit LabelReachable(LabelReachableData<Label> *data, S *s = 0)
     : fst_(0),
       s_(kNoStateId),
       data_(data),
       accumulator_(s ? s : new S()),
       ncalls_(0),
       nintervals_(0),
       error_(false) {
     data_->IncrRefCount();
   }

   LabelReachable(const LabelReachable<A, S> &reachable) :
       fst_(0),
       s_(kNoStateId),
       data_(reachable.data_),
       accumulator_(new S(*reachable.accumulator_)),
       ncalls_(0),
       nintervals_(0),
       error_(reachable.error_) {
     data_->IncrRefCount();
   }

   ~LabelReachable() {
     if (!data_->DecrRefCount())
       delete data_;
     delete accumulator_;
     if (ncalls_ > 0) {
       VLOG(2) << "# of calls: " << ncalls_;
       VLOG(2) << "# of intervals/call: " << (nintervals_ / ncalls_);
     }
   }

   // Relabels w.r.t labels that give compact label sets.
   Label Relabel(Label label) {
     if (label == 0 || error_)
       return label;
     unordered_map<Label, Label> &label2index = *data_->Label2Index();
     Label &relabel = label2index[label];
     if (!relabel)  // Add new label
       relabel = label2index.size() + 1;
     return relabel;
   }

   // Relabels Fst w.r.t to labels that give compact label sets.
   void Relabel(MutableFst<Arc> *fst, bool relabel_input) {
     for (StateIterator< MutableFst<Arc> > siter(*fst);
          !siter.Done(); siter.Next()) {
       StateId s = siter.Value();
       for (MutableArcIterator< MutableFst<Arc> > aiter(fst, s);
            !aiter.Done();
            aiter.Next()) {
         Arc arc = aiter.Value();
         if (relabel_input)
           arc.ilabel = Relabel(arc.ilabel);
         else
           arc.olabel = Relabel(arc.olabel);
         aiter.SetValue(arc);
       }
     }
     if (relabel_input) {
       ArcSort(fst, ILabelCompare<Arc>());
       fst->SetInputSymbols(0);
     } else {
       ArcSort(fst, OLabelCompare<Arc>());
       fst->SetOutputSymbols(0);
     }
   }

   // Returns relabeling pairs (cf. relabel.h::Relabel()).
   // If 'avoid_collisions' is true, extra pairs are added to
   // ensure no collisions when relabeling automata that have
   // labels unseen here.
   void RelabelPairs(vector<pair<Label, Label> > *pairs,
                     bool avoid_collisions = false) {
     pairs->clear();
     unordered_map<Label, Label> &label2index = *data_->Label2Index();
     // Maps labels to their new values in [1, label2index().size()]
     for (typename unordered_map<Label, Label>::const_iterator
              it = label2index.begin(); it != label2index.end(); ++it)
       if (it->second != data_->FinalLabel())
         pairs->push_back(pair<Label, Label>(it->first, it->second));
     if (avoid_collisions) {
       // Ensures any label in [1, label2index().size()] is mapped either
       // by the above step or to label2index() + 1 (to avoid collisions).
       for (int i = 1; i <= label2index.size(); ++i) {
         typename unordered_map<Label, Label>::const_iterator
             it = label2index.find(i);
         if (it == label2index.end() || it->second == data_->FinalLabel())
           pairs->push_back(pair<Label, Label>(i, label2index.size() + 1));
       }
     }
   }

   // Set current state. Optionally set state associated
   // with arc iterator to be passed to Reach.
   void SetState(StateId s, StateId aiter_s = kNoStateId) {
     s_ = s;
     if (aiter_s != kNoStateId) {
       accumulator_->SetState(aiter_s);
       if (accumulator_->Error()) error_ = true;
     }
   }

   // Can reach this label from current state?
   // Original labels must be transformed by the Relabel methods above.
   bool Reach(Label label) {
     if (label == 0 || error_)
       return false;
     vector< IntervalSet<Label> > &isets = *data_->IntervalSets();
     return isets[s_].Member(label);

   }

   // Can reach final state (via epsilon transitions) from this state?
   bool ReachFinal() {
     if (error_) return false;
     vector< IntervalSet<Label> > &isets = *data_->IntervalSets();
     return isets[s_].Member(data_->FinalLabel());
   }

   // Initialize with secondary FST to be used with Reach(Iterator,...).
   // If copy is true, then 'fst' is a copy of the FST used in the
   // previous call to this method (useful to avoid unnecessary updates).
   template <class F>
   void ReachInit(const F &fst, bool copy = false) {
     accumulator_->Init(fst, copy);
     if (accumulator_->Error()) error_ = true;
   }

   // Can reach any arc iterator label between iterator positions
   // aiter_begin and aiter_end?  If aiter_input = true, then iterator
   // input labels are considered, o.w. output labels are considered.
   // Arc iterator labels must be transformed by the Relabel methods
   // above. If compute_weight is true, user may call ReachWeight().
   template <class Iterator>
   bool Reach(Iterator *aiter, ssize_t aiter_begin,
              ssize_t aiter_end, bool aiter_input, bool compute_weight) {
     if (error_) return false;
     vector< IntervalSet<Label> > &isets = *data_->IntervalSets();
     const vector<Interval> *intervals = isets[s_].Intervals();
     ++ncalls_;
     nintervals_ += intervals->size();

     reach_begin_ = -1;
     reach_end_ = -1;
     reach_weight_ = Weight::Zero();

     uint32 flags = aiter->Flags();  // save flags to restore them on exit
     aiter->SetFlags(kArcNoCache, kArcNoCache);  // make caching optional
     aiter->Seek(aiter_begin);

     if (2 * (aiter_end - aiter_begin) < intervals->size()) {
       // Check each arc against intervals.
       // Set arc iterator flags to only compute the ilabel or olabel values,
       // since they are the only values required for most of the arcs processed.
       aiter->SetFlags(aiter_input ? kArcILabelValue : kArcOLabelValue,
                       kArcValueFlags);
       Label reach_label = kNoLabel;
       for (ssize_t aiter_pos = aiter_begin;
            aiter_pos < aiter_end; aiter->Next(), ++aiter_pos) {
         const A &arc = aiter->Value();
         Label label = aiter_input ? arc.ilabel : arc.olabel;
         if (label == reach_label || Reach(label)) {
           reach_label = label;
           if (reach_begin_ < 0)
             reach_begin_ = aiter_pos;
           reach_end_ = aiter_pos + 1;
           if (compute_weight) {
             if (!(aiter->Flags() & kArcWeightValue)) {
               // If the 'arc.weight' wasn't computed by the call
               // to 'aiter->Value()' above, we need to call
               // 'aiter->Value()' again after having set the arc iterator
               // flags to compute the arc weight value.
               aiter->SetFlags(kArcWeightValue, kArcValueFlags);
               const A &arcb = aiter->Value();
               // Call the accumulator.
               reach_weight_ = accumulator_->Sum(reach_weight_, arcb.weight);
               // Only ilabel or olabel required to process the following
               // arcs.
               aiter->SetFlags(aiter_input ? kArcILabelValue : kArcOLabelValue,
                               kArcValueFlags);
             } else {
               // Call the accumulator.
               reach_weight_ = accumulator_->Sum(reach_weight_, arc.weight);
             }
           }
         }
       }
     } else {
       // Check each interval against arcs
       ssize_t begin_low, end_low = aiter_begin;
       for (typename vector<Interval>::const_iterator
                iiter = intervals->begin();
            iiter != intervals->end(); ++iiter) {
         begin_low = LowerBound(aiter, end_low, aiter_end,
                                aiter_input, iiter->begin);
         end_low = LowerBound(aiter, begin_low, aiter_end,
                              aiter_input, iiter->end);
         if (end_low - begin_low > 0) {
           if (reach_begin_ < 0)
             reach_begin_ = begin_low;
           reach_end_ = end_low;
           if (compute_weight) {
             aiter->SetFlags(kArcWeightValue, kArcValueFlags);
             reach_weight_ = accumulator_->Sum(reach_weight_, aiter,
                                               begin_low, end_low);
           }
         }
       }
     }

     aiter->SetFlags(flags, kArcFlags);  // restore original flag values
     return reach_begin_ >= 0;
   }

   // Returns iterator position of first matching arc.
   ssize_t ReachBegin() const { return reach_begin_;  }

   // Returns iterator position one past last matching arc.
   ssize_t ReachEnd() const { return reach_end_; }

   // Return the sum of the weights for matching arcs.
   // Valid only if compute_weight was true in Reach() call.
   Weight ReachWeight() const { return reach_weight_; }

   // Access to the relabeling map. Excludes epsilon (0) label but
   // includes kNoLabel that is used internally for super-final
   // transitons.
   const unordered_map<Label, Label>& Label2Index() const {
     return *data_->Label2Index();
   }

   LabelReachableData<Label> *GetData() const { return data_; }

   bool Error() const { return error_ || accumulator_->Error(); }

  private:
   // Redirects labeled arcs (input or output labels determined by
   // ReachInput()) to new label-specific final states.  Each original
   // final state is redirected via a transition labeled with kNoLabel
   // to a new kNoLabel-specific final state.  Creates super-initial
   // state for all states with zero in-degree.
   void TransformFst() {
     StateId ins = fst_->NumStates();
     StateId ons = ins;

     vector<ssize_t> indeg(ins, 0);

     // Redirects labeled arcs to new final states.
     for (StateId s = 0; s < ins; ++s) {
       for (MutableArcIterator< VectorFst<Arc> > aiter(fst_, s);
            !aiter.Done();
            aiter.Next()) {
         Arc arc = aiter.Value();
         Label label = data_->ReachInput() ? arc.ilabel : arc.olabel;
         if (label) {
           if (label2state_.find(label) == label2state_.end()) {
             label2state_[label] = ons;
             indeg.push_back(0);
             ++ons;
           }
           arc.nextstate = label2state_[label];
           aiter.SetValue(arc);
         }
         ++indeg[arc.nextstate];      // Finds in-degrees for next step.
       }

       // Redirects final weights to new final state.
       Weight final = fst_->Final(s);
       if (final != Weight::Zero()) {
         if (label2state_.find(kNoLabel) == label2state_.end()) {
           label2state_[kNoLabel] = ons;
           indeg.push_back(0);
           ++ons;
         }
         Arc arc(kNoLabel, kNoLabel, final, label2state_[kNoLabel]);
         fst_->AddArc(s, arc);
         ++indeg[arc.nextstate];      // Finds in-degrees for next step.

         fst_->SetFinal(s, Weight::Zero());
       }
     }

     // Add new final states to Fst.
     while (fst_->NumStates() < ons) {
       StateId s = fst_->AddState();
       fst_->SetFinal(s, Weight::One());
     }

     // Creates a super-initial state for all states with zero in-degree.
     StateId start = fst_->AddState();
     fst_->SetStart(start);
     for (StateId s = 0; s < start; ++s) {
       if (indeg[s] == 0) {
         Arc arc(0, 0, Weight::One(), s);
         fst_->AddArc(start, arc);
       }
     }
   }

   void FindIntervals(StateId ins) {
     StateReachable<A, Label> state_reachable(*fst_);
     if (state_reachable.Error()) {
       error_ = true;
       return;
     }

     vector<Label> &state2index = state_reachable.State2Index();
     vector< IntervalSet<Label> > &isets = *data_->IntervalSets();
     isets = state_reachable.IntervalSets();
     isets.resize(ins);

     unordered_map<Label, Label> &label2index = *data_->Label2Index();
     for (typename unordered_map<Label, StateId>::const_iterator
              it = label2state_.begin();
          it != label2state_.end();
          ++it) {
       Label l = it->first;
       StateId s = it->second;
       Label i = state2index[s];
       label2index[l] = i;
     }
     label2state_.clear();

     double nintervals = 0;
     ssize_t non_intervals = 0;
     for (ssize_t s = 0; s < ins; ++s) {
       nintervals += isets[s].Size();
       if (isets[s].Size() > 1) {
         ++non_intervals;
         VLOG(3) << "state: " << s << " # of intervals: " << isets[s].Size();
       }
     }
     VLOG(2) << "# of states: " << ins;
     VLOG(2) << "# of intervals: " << nintervals;
     VLOG(2) << "# of intervals/state: " << nintervals/ins;
     VLOG(2) << "# of non-interval states: " << non_intervals;
   }

   template <class Iterator>
   ssize_t LowerBound(Iterator *aiter, ssize_t aiter_begin,
                      ssize_t aiter_end, bool aiter_input,
                      Label match_label) const {
     // Only need to compute the ilabel or olabel of arcs when
     // performing the binary search.
     aiter->SetFlags(aiter_input ?  kArcILabelValue : kArcOLabelValue,
                     kArcValueFlags);
     ssize_t low = aiter_begin;
     ssize_t high = aiter_end;
     while (low < high) {
       ssize_t mid = (low + high) / 2;
       aiter->Seek(mid);
       Label label = aiter_input ?
           aiter->Value().ilabel : aiter->Value().olabel;
       if (label > match_label) {
         high = mid;
       } else if (label < match_label) {
         low = mid + 1;
       } else {
         // Find first matching label (when non-deterministic)
         for (ssize_t i = mid; i > low; --i) {
           aiter->Seek(i - 1);
           label = aiter_input ? aiter->Value().ilabel : aiter->Value().olabel;
           if (label != match_label) {
             aiter->Seek(i);
             aiter->SetFlags(kArcValueFlags, kArcValueFlags);
             return i;
           }
         }
         aiter->SetFlags(kArcValueFlags, kArcValueFlags);
         return low;
       }
     }
     aiter->Seek(low);
     aiter->SetFlags(kArcValueFlags, kArcValueFlags);
     return low;
   }

   VectorFst<Arc> *fst_;
   StateId s_;                             // Current state
   unordered_map<Label, StateId> label2state_;  // Finds final state for a label

   ssize_t reach_begin_;                   // Iterator pos of first match
   ssize_t reach_end_;                     // Iterator pos after last match
   Weight reach_weight_;                   // Gives weight sum of arc iterator
                                           // arcs with reachable labels.
   LabelReachableData<Label> *data_;       // Shareable data between copies
   S *accumulator_;                        // Sums arc weights

   double ncalls_;
   double nintervals_;
   bool error_;

   void operator=(const LabelReachable<A, S> &);   // Disallow
 };

 }  // namespace fst

 #endif  // FST_LIB_LABEL_REACHABLE_H__
	// label_reachable.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
	// Class to determine if a non-epsilon label can be read as the
	// first non-epsilon symbol along some path from a given state.


	#ifndef FST_LIB_LABEL_REACHABLE_H__
	#define FST_LIB_LABEL_REACHABLE_H__

	#include <unordered_map>
	using std::tr1::unordered_map;
	using std::tr1::unordered_multimap;
	#include <vector>
	using std::vector;

	#include <fst/accumulator.h>
	#include <fst/arcsort.h>
	#include <fst/interval-set.h>
	#include <fst/state-reachable.h>
	#include <fst/vector-fst.h>


	namespace fst {

	// Stores shareable data for label reachable class copies.
	template <typename L>
	class LabelReachableData {
	public:
	typedef L Label;
	typedef typename IntervalSet<L>::Interval Interval;

	explicit LabelReachableData(bool reach_input, bool keep_relabel_data = true)
	: reach_input_(reach_input),
	keep_relabel_data_(keep_relabel_data),
	have_relabel_data_(true),
	final_label_(kNoLabel) {}

	~LabelReachableData() {}

	bool ReachInput() const { return reach_input_; }

	vector< IntervalSet<L> > *IntervalSets() { return &isets_; }

	unordered_map<L, L> *Label2Index() {
	if (!have_relabel_data_)
	FSTERROR() << "LabelReachableData: no relabeling data";
	return &label2index_;
	}

	Label FinalLabel() {
	if (final_label_ == kNoLabel)
	final_label_ = label2index_[kNoLabel];
	return final_label_;
	}

	static LabelReachableData<L> *Read(istream &istrm) {
	LabelReachableData<L> *data = new LabelReachableData<L>();

	ReadType(istrm, &data->reach_input_);
	ReadType(istrm, &data->keep_relabel_data_);
	data->have_relabel_data_ = data->keep_relabel_data_;
	if (data->keep_relabel_data_)
	ReadType(istrm, &data->label2index_);
	ReadType(istrm, &data->final_label_);
	ReadType(istrm, &data->isets_);
	return data;
	}

	bool Write(ostream &ostrm) {
	WriteType(ostrm, reach_input_);
	WriteType(ostrm, keep_relabel_data_);
	if (keep_relabel_data_)
	WriteType(ostrm, label2index_);
	WriteType(ostrm, FinalLabel());
	WriteType(ostrm, isets_);
	return true;
	}

	int RefCount() const { return ref_count_.count(); }
	int IncrRefCount() { return ref_count_.Incr(); }
	int DecrRefCount() { return ref_count_.Decr(); }

	private:
	LabelReachableData() {}

	bool reach_input_; // Input or output labels considered?
	bool keep_relabel_data_; // Save label2index_ to file?
	bool have_relabel_data_; // Using label2index_?
	Label final_label_; // Final label
	RefCounter ref_count_; // Reference count.
	unordered_map<L, L> label2index_; // Finds index for a label.
	vector<IntervalSet <L> > isets_; // Interval sets per state.

	DISALLOW_COPY_AND_ASSIGN(LabelReachableData);
	};


	// Tests reachability of labels from a given state. If reach_input =
	// true, then input labels are considered, o.w. output labels are
	// considered. To test for reachability from a state s, first do
	// SetState(s). Then a label l can be reached from state s of FST f
	// iff Reach(r) is true where r = Relabel(l). The relabeling is
	// required to ensure a compact representation of the reachable
	// labels.

	// The whole FST can be relabeled instead with Relabel(&f,
	// reach_input) so that the test Reach(r) applies directly to the
	// labels of the transformed FST f. The relabeled FST will also be
	// sorted appropriately for composition.
	//
	// Reachablity of a final state from state s (via an epsilon path)
	// can be tested with ReachFinal();
	//
	// Reachability can also be tested on the set of labels specified by
	// an arc iterator, useful for FST composition. In particular,
	// Reach(aiter, ...) is true if labels on the input (output) side of
	// the transitions of the arc iterator, when iter_input is true
	// (false), can be reached from the state s. The iterator labels must
	// have already been relabeled.
	//
	// With the arc iterator test of reachability, the begin position, end
	// position and accumulated arc weight of the matches can be
	// returned. The optional template argument controls how reachable arc
	// weights are accumulated. The default uses the semiring
	// Plus(). Alternative ones can be used to distribute the weights in
	// composition in various ways.
	template <class A, class S = DefaultAccumulator<A> >
	class LabelReachable {
	public:
	typedef A Arc;
	typedef typename A::StateId StateId;
	typedef typename A::Label Label;
	typedef typename A::Weight Weight;
	typedef typename IntervalSet<Label>::Interval Interval;

	LabelReachable(const Fst<A> &fst, bool reach_input, S *s = 0,
	bool keep_relabel_data = true)
	: fst_(new VectorFst<Arc>(fst)),
	s_(kNoStateId),
	data_(new LabelReachableData<Label>(reach_input, keep_relabel_data)),
	accumulator_(s ? s : new S()),
	ncalls_(0),
	nintervals_(0),
	error_(false) {
	StateId ins = fst_->NumStates();
	TransformFst();
	FindIntervals(ins);
	delete fst_;
	}

	explicit LabelReachable(LabelReachableData<Label> data, S s = 0)
	: fst_(0),
	s_(kNoStateId),
	data_(data),
	accumulator_(s ? s : new S()),
	ncalls_(0),
	nintervals_(0),
	error_(false) {
	data_->IncrRefCount();
	}

	LabelReachable(const LabelReachable<A, S> &reachable) :
	fst_(0),
	s_(kNoStateId),
	data_(reachable.data_),
	accumulator_(new S(*reachable.accumulator_)),
	ncalls_(0),
	nintervals_(0),
	error_(reachable.error_) {
	data_->IncrRefCount();
	}

	~LabelReachable() {
	if (!data_->DecrRefCount())
	delete data_;
	delete accumulator_;
	if (ncalls_ > 0) {
	VLOG(2) << "# of calls: " << ncalls_;
	VLOG(2) << "# of intervals/call: " << (nintervals_ / ncalls_);
	}
	}

	// Relabels w.r.t labels that give compact label sets.
	Label Relabel(Label label) {
	if (label == 0 \|\| error_)
	return label;
	unordered_map<Label, Label> &label2index = *data_->Label2Index();
	Label &relabel = label2index[label];
	if (!relabel) // Add new label
	relabel = label2index.size() + 1;
	return relabel;
	}

	// Relabels Fst w.r.t to labels that give compact label sets.
	void Relabel(MutableFst<Arc> *fst, bool relabel_input) {
	for (StateIterator< MutableFst<Arc> > siter(*fst);
	!siter.Done(); siter.Next()) {
	StateId s = siter.Value();
	for (MutableArcIterator< MutableFst<Arc> > aiter(fst, s);
	!aiter.Done();
	aiter.Next()) {
	Arc arc = aiter.Value();
	if (relabel_input)
	arc.ilabel = Relabel(arc.ilabel);
	else
	arc.olabel = Relabel(arc.olabel);
	aiter.SetValue(arc);
	}
	}
	if (relabel_input) {
	ArcSort(fst, ILabelCompare<Arc>());
	fst->SetInputSymbols(0);
	} else {
	ArcSort(fst, OLabelCompare<Arc>());
	fst->SetOutputSymbols(0);
	}
	}

	// Returns relabeling pairs (cf. relabel.h::Relabel()).
	// If 'avoid_collisions' is true, extra pairs are added to
	// ensure no collisions when relabeling automata that have
	// labels unseen here.
	void RelabelPairs(vector<pair<Label, Label> > *pairs,
	bool avoid_collisions = false) {
	pairs->clear();
	unordered_map<Label, Label> &label2index = *data_->Label2Index();
	// Maps labels to their new values in [1, label2index().size()]
	for (typename unordered_map<Label, Label>::const_iterator
	it = label2index.begin(); it != label2index.end(); ++it)
	if (it->second != data_->FinalLabel())
	pairs->push_back(pair<Label, Label>(it->first, it->second));
	if (avoid_collisions) {
	// Ensures any label in [1, label2index().size()] is mapped either
	// by the above step or to label2index() + 1 (to avoid collisions).
	for (int i = 1; i <= label2index.size(); ++i) {
	typename unordered_map<Label, Label>::const_iterator
	it = label2index.find(i);
	if (it == label2index.end() \|\| it->second == data_->FinalLabel())
	pairs->push_back(pair<Label, Label>(i, label2index.size() + 1));
	}
	}
	}

	// Set current state. Optionally set state associated
	// with arc iterator to be passed to Reach.
	void SetState(StateId s, StateId aiter_s = kNoStateId) {
	s_ = s;
	if (aiter_s != kNoStateId) {
	accumulator_->SetState(aiter_s);
	if (accumulator_->Error()) error_ = true;
	}
	}

	// Can reach this label from current state?
	// Original labels must be transformed by the Relabel methods above.
	bool Reach(Label label) {
	if (label == 0 \|\| error_)
	return false;
	vector< IntervalSet<Label> > &isets = *data_->IntervalSets();
	return isets[s_].Member(label);

	}

	// Can reach final state (via epsilon transitions) from this state?
	bool ReachFinal() {
	if (error_) return false;
	vector< IntervalSet<Label> > &isets = *data_->IntervalSets();
	return isets[s_].Member(data_->FinalLabel());
	}

	// Initialize with secondary FST to be used with Reach(Iterator,...).
	// If copy is true, then 'fst' is a copy of the FST used in the
	// previous call to this method (useful to avoid unnecessary updates).
	template <class F>
	void ReachInit(const F &fst, bool copy = false) {
	accumulator_->Init(fst, copy);
	if (accumulator_->Error()) error_ = true;
	}

	// Can reach any arc iterator label between iterator positions
	// aiter_begin and aiter_end? If aiter_input = true, then iterator
	// input labels are considered, o.w. output labels are considered.
	// Arc iterator labels must be transformed by the Relabel methods
	// above. If compute_weight is true, user may call ReachWeight().
	template <class Iterator>
	bool Reach(Iterator *aiter, ssize_t aiter_begin,
	ssize_t aiter_end, bool aiter_input, bool compute_weight) {
	if (error_) return false;
	vector< IntervalSet<Label> > &isets = *data_->IntervalSets();
	const vector<Interval> *intervals = isets[s_].Intervals();
	++ncalls_;
	nintervals_ += intervals->size();

	reach_begin_ = -1;
	reach_end_ = -1;
	reach_weight_ = Weight::Zero();

	uint32 flags = aiter->Flags(); // save flags to restore them on exit
	aiter->SetFlags(kArcNoCache, kArcNoCache); // make caching optional
	aiter->Seek(aiter_begin);

	if (2 * (aiter_end - aiter_begin) < intervals->size()) {
	// Check each arc against intervals.
	// Set arc iterator flags to only compute the ilabel or olabel values,
	// since they are the only values required for most of the arcs processed.
	aiter->SetFlags(aiter_input ? kArcILabelValue : kArcOLabelValue,
	kArcValueFlags);
	Label reach_label = kNoLabel;
	for (ssize_t aiter_pos = aiter_begin;
	aiter_pos < aiter_end; aiter->Next(), ++aiter_pos) {
	const A &arc = aiter->Value();
	Label label = aiter_input ? arc.ilabel : arc.olabel;
	if (label == reach_label \|\| Reach(label)) {
	reach_label = label;
	if (reach_begin_ < 0)
	reach_begin_ = aiter_pos;
	reach_end_ = aiter_pos + 1;
	if (compute_weight) {
	if (!(aiter->Flags() & kArcWeightValue)) {
	// If the 'arc.weight' wasn't computed by the call
	// to 'aiter->Value()' above, we need to call
	// 'aiter->Value()' again after having set the arc iterator
	// flags to compute the arc weight value.
	aiter->SetFlags(kArcWeightValue, kArcValueFlags);
	const A &arcb = aiter->Value();
	// Call the accumulator.
	reach_weight_ = accumulator_->Sum(reach_weight_, arcb.weight);
	// Only ilabel or olabel required to process the following
	// arcs.
	aiter->SetFlags(aiter_input ? kArcILabelValue : kArcOLabelValue,
	kArcValueFlags);
	} else {
	// Call the accumulator.
	reach_weight_ = accumulator_->Sum(reach_weight_, arc.weight);
	}
	}
	}
	}
	} else {
	// Check each interval against arcs
	ssize_t begin_low, end_low = aiter_begin;
	for (typename vector<Interval>::const_iterator
	iiter = intervals->begin();
	iiter != intervals->end(); ++iiter) {
	begin_low = LowerBound(aiter, end_low, aiter_end,
	aiter_input, iiter->begin);
	end_low = LowerBound(aiter, begin_low, aiter_end,
	aiter_input, iiter->end);
	if (end_low - begin_low > 0) {
	if (reach_begin_ < 0)
	reach_begin_ = begin_low;
	reach_end_ = end_low;
	if (compute_weight) {
	aiter->SetFlags(kArcWeightValue, kArcValueFlags);
	reach_weight_ = accumulator_->Sum(reach_weight_, aiter,
	begin_low, end_low);
	}
	}
	}
	}

	aiter->SetFlags(flags, kArcFlags); // restore original flag values
	return reach_begin_ >= 0;
	}

	// Returns iterator position of first matching arc.
	ssize_t ReachBegin() const { return reach_begin_; }

	// Returns iterator position one past last matching arc.
	ssize_t ReachEnd() const { return reach_end_; }

	// Return the sum of the weights for matching arcs.
	// Valid only if compute_weight was true in Reach() call.
	Weight ReachWeight() const { return reach_weight_; }

	// Access to the relabeling map. Excludes epsilon (0) label but
	// includes kNoLabel that is used internally for super-final
	// transitons.
	const unordered_map<Label, Label>& Label2Index() const {
	return *data_->Label2Index();
	}

	LabelReachableData<Label> *GetData() const { return data_; }

	bool Error() const { return error_ \|\| accumulator_->Error(); }

	private:
	// Redirects labeled arcs (input or output labels determined by
	// ReachInput()) to new label-specific final states. Each original
	// final state is redirected via a transition labeled with kNoLabel
	// to a new kNoLabel-specific final state. Creates super-initial
	// state for all states with zero in-degree.
	void TransformFst() {
	StateId ins = fst_->NumStates();
	StateId ons = ins;

	vector<ssize_t> indeg(ins, 0);

	// Redirects labeled arcs to new final states.
	for (StateId s = 0; s < ins; ++s) {
	for (MutableArcIterator< VectorFst<Arc> > aiter(fst_, s);
	!aiter.Done();
	aiter.Next()) {
	Arc arc = aiter.Value();
	Label label = data_->ReachInput() ? arc.ilabel : arc.olabel;
	if (label) {
	if (label2state_.find(label) == label2state_.end()) {
	label2state_[label] = ons;
	indeg.push_back(0);
	++ons;
	}
	arc.nextstate = label2state_[label];
	aiter.SetValue(arc);
	}
	++indeg[arc.nextstate]; // Finds in-degrees for next step.
	}

	// Redirects final weights to new final state.
	Weight final = fst_->Final(s);
	if (final != Weight::Zero()) {
	if (label2state_.find(kNoLabel) == label2state_.end()) {
	label2state_[kNoLabel] = ons;
	indeg.push_back(0);
	++ons;
	}
	Arc arc(kNoLabel, kNoLabel, final, label2state_[kNoLabel]);
	fst_->AddArc(s, arc);
	++indeg[arc.nextstate]; // Finds in-degrees for next step.

	fst_->SetFinal(s, Weight::Zero());
	}
	}

	// Add new final states to Fst.
	while (fst_->NumStates() < ons) {
	StateId s = fst_->AddState();
	fst_->SetFinal(s, Weight::One());
	}

	// Creates a super-initial state for all states with zero in-degree.
	StateId start = fst_->AddState();
	fst_->SetStart(start);
	for (StateId s = 0; s < start; ++s) {
	if (indeg[s] == 0) {
	Arc arc(0, 0, Weight::One(), s);
	fst_->AddArc(start, arc);
	}
	}
	}

	void FindIntervals(StateId ins) {
	StateReachable<A, Label> state_reachable(*fst_);
	if (state_reachable.Error()) {
	error_ = true;
	return;
	}

	vector<Label> &state2index = state_reachable.State2Index();
	vector< IntervalSet<Label> > &isets = *data_->IntervalSets();
	isets = state_reachable.IntervalSets();
	isets.resize(ins);

	unordered_map<Label, Label> &label2index = *data_->Label2Index();
	for (typename unordered_map<Label, StateId>::const_iterator
	it = label2state_.begin();
	it != label2state_.end();
	++it) {
	Label l = it->first;
	StateId s = it->second;
	Label i = state2index[s];
	label2index[l] = i;
	}
	label2state_.clear();

	double nintervals = 0;
	ssize_t non_intervals = 0;
	for (ssize_t s = 0; s < ins; ++s) {
	nintervals += isets[s].Size();
	if (isets[s].Size() > 1) {
	++non_intervals;
	VLOG(3) << "state: " << s << " # of intervals: " << isets[s].Size();
	}
	}
	VLOG(2) << "# of states: " << ins;
	VLOG(2) << "# of intervals: " << nintervals;
	VLOG(2) << "# of intervals/state: " << nintervals/ins;
	VLOG(2) << "# of non-interval states: " << non_intervals;
	}

	template <class Iterator>
	ssize_t LowerBound(Iterator *aiter, ssize_t aiter_begin,
	ssize_t aiter_end, bool aiter_input,
	Label match_label) const {
	// Only need to compute the ilabel or olabel of arcs when
	// performing the binary search.
	aiter->SetFlags(aiter_input ? kArcILabelValue : kArcOLabelValue,
	kArcValueFlags);
	ssize_t low = aiter_begin;
	ssize_t high = aiter_end;
	while (low < high) {
	ssize_t mid = (low + high) / 2;
	aiter->Seek(mid);
	Label label = aiter_input ?
	aiter->Value().ilabel : aiter->Value().olabel;
	if (label > match_label) {
	high = mid;
	} else if (label < match_label) {
	low = mid + 1;
	} else {
	// Find first matching label (when non-deterministic)
	for (ssize_t i = mid; i > low; --i) {
	aiter->Seek(i - 1);
	label = aiter_input ? aiter->Value().ilabel : aiter->Value().olabel;
	if (label != match_label) {
	aiter->Seek(i);
	aiter->SetFlags(kArcValueFlags, kArcValueFlags);
	return i;
	}
	}
	aiter->SetFlags(kArcValueFlags, kArcValueFlags);
	return low;
	}
	}
	aiter->Seek(low);
	aiter->SetFlags(kArcValueFlags, kArcValueFlags);
	return low;
	}

	VectorFst<Arc> *fst_;
	StateId s_; // Current state
	unordered_map<Label, StateId> label2state_; // Finds final state for a label

	ssize_t reach_begin_; // Iterator pos of first match
	ssize_t reach_end_; // Iterator pos after last match
	Weight reach_weight_; // Gives weight sum of arc iterator
	// arcs with reachable labels.
	LabelReachableData<Label> *data_; // Shareable data between copies
	S *accumulator_; // Sums arc weights

	double ncalls_;
	double nintervals_;
	bool error_;

	void operator=(const LabelReachable<A, S> &); // Disallow
	};

	} // namespace fst

	#endif // FST_LIB_LABEL_REACHABLE_H__