text: #include "earley_composer.h"
  
  #include <iostream>
  #include <fstream>
  #include <map>
  #include <queue>
  #ifndef HAVE_OLD_CPP
  # include <unordered_map>
  # include <unordered_set>
  #else
  # include <tr1/unordered_map>
  # include <tr1/unordered_set>
  namespace std { using std::tr1::unordered_map; using std::tr1::unordered_multiset; using std::tr1::unordered_set; }
  #endif
  
  #include <boost/shared_ptr.hpp>
  #include <boost/program_options.hpp>
  #include <boost/program_options/variables_map.hpp>
  #include "fast_lexical_cast.hpp"
  
  #include "phrasetable_fst.h"
  #include "sparse_vector.h"
  #include "tdict.h"
  #include "hg.h"
  #include "hg_remove_eps.h"
  
  using namespace std;
  
  // Define the following macro if you want to see lots of debugging output
  // when you run the chart parser
  #undef DEBUG_CHART_PARSER
  
  // A few constants used by the chart parser ///////////////
  static const int kMAX_NODES = 2000000;
  static const string kPHRASE_STRING = "X";
  static bool constants_need_init = true;
  static WordID kUNIQUE_START;
  static WordID kPHRASE;
  static TRulePtr kX1X2;
  static TRulePtr kX1;
  static WordID kEPS;
  static TRulePtr kEPSRule;
  
  static void InitializeConstants() {
    if (constants_need_init) {
      kPHRASE = TD::Convert(kPHRASE_STRING) * -1;
      kUNIQUE_START = TD::Convert("S") * -1;
      kX1X2.reset(new TRule("[X] ||| [X,1] [X,2] ||| [X,1] [X,2]"));
      kX1.reset(new TRule("[X] ||| [X,1] ||| [X,1]"));
      kEPSRule.reset(new TRule("[X] ||| <eps> ||| <eps>"));
      kEPS = TD::Convert("<eps>");
      constants_need_init = false;
    }
  }
  ////////////////////////////////////////////////////////////
  
  TRulePtr CreateBinaryRule(int lhs, int rhs1, int rhs2) {
    TRule* r = new TRule(*kX1X2);
    r->lhs_ = lhs;
    r->f_[0] = rhs1;
    r->f_[1] = rhs2;
    return TRulePtr(r);
  }
  
  TRulePtr CreateUnaryRule(int lhs, int rhs1) {
    TRule* r = new TRule(*kX1);
    r->lhs_ = lhs;
    r->f_[0] = rhs1;
    return TRulePtr(r);
  }
  
  TRulePtr CreateEpsilonRule(int lhs) {
    TRule* r = new TRule(*kEPSRule);
    r->lhs_ = lhs;
    return TRulePtr(r);
  }
  
  class EGrammarNode {
    friend bool EarleyComposer::Compose(const Hypergraph& src_forest, Hypergraph* trg_forest);
    friend void AddGrammarRule(const string& r, map<WordID, EGrammarNode>* g);
   public:
  #ifdef DEBUG_CHART_PARSER
    string hint;
  #endif
    EGrammarNode() : is_some_rule_complete(false), is_root(false) {}
    const map<WordID, EGrammarNode>& GetTerminals() const { return tptr; }
    const map<WordID, EGrammarNode>& GetNonTerminals() const { return ntptr; }
    bool HasNonTerminals() const { return (!ntptr.empty()); }
    bool HasTerminals() const { return (!tptr.empty()); }
    bool RuleCompletes() const {
      return (is_some_rule_complete || (ntptr.empty() && tptr.empty()));
    }
    bool GrammarContinues() const {
      return !(ntptr.empty() && tptr.empty());
    }
    bool IsRoot() const {
      return is_root;
    }
    // these are the features associated with the rule from the start
    // node up to this point.  If you use these features, you must
    // not Extend() this rule.
    const SparseVector<double>& GetCFGProductionFeatures() const {
      return input_features;
    }
  
    const EGrammarNode* Extend(const WordID& t) const {
      if (t < 0) {
        map<WordID, EGrammarNode>::const_iterator it = ntptr.find(t);
        if (it == ntptr.end()) return NULL;
        return &it->second;
      } else {
        map<WordID, EGrammarNode>::const_iterator it = tptr.find(t);
        if (it == tptr.end()) return NULL;
        return &it->second;
      }
    }
  
   private:
    map<WordID, EGrammarNode> tptr;
    map<WordID, EGrammarNode> ntptr;
    SparseVector<double> input_features;
    bool is_some_rule_complete;
    bool is_root;
  };
  typedef map<WordID, EGrammarNode> EGrammar;    // indexed by the rule LHS
  
  // edges are immutable once created
  struct Edge {
  #ifdef DEBUG_CHART_PARSER
    static int id_count;
    const int id;
  #endif
    const WordID cat;                   // lhs side of rule proved/being proved
    const EGrammarNode* const dot;      // dot position
    const FSTNode* const q;             // start of span
    const FSTNode* const r;             // end of span
    const Edge* const active_parent;    // back pointer, NULL for PREDICT items
    const Edge* const passive_parent;   // back pointer, NULL for SCAN and PREDICT items
    const TargetPhraseSet* const tps;   // translations
    boost::shared_ptr<SparseVector<double> > features; // features from CFG rule
  
    bool IsPassive() const {
      // when a rule is completed, this value will be set
      return static_cast<bool>(features);
    }
    bool IsActive() const { return !IsPassive(); }
    bool IsInitial() const {
      return !(active_parent || passive_parent);
    }
    bool IsCreatedByScan() const {
      return active_parent && !passive_parent && !dot->IsRoot();
    }
    bool IsCreatedByPredict() const {
      return dot->IsRoot();
    }
    bool IsCreatedByComplete() const {
      return active_parent && passive_parent;
    }
  
    // constructor for PREDICT
    Edge(WordID c, const EGrammarNode* d, const FSTNode* q_and_r) :
  #ifdef DEBUG_CHART_PARSER
      id(++id_count),
  #endif
      cat(c), dot(d), q(q_and_r), r(q_and_r), active_parent(NULL), passive_parent(NULL), tps(NULL) {}
    Edge(WordID c, const EGrammarNode* d, const FSTNode* q_and_r, const Edge* act_parent) :
  #ifdef DEBUG_CHART_PARSER
      id(++id_count),
  #endif
      cat(c), dot(d), q(q_and_r), r(q_and_r), active_parent(act_parent), passive_parent(NULL), tps(NULL) {}
  
    // constructors for SCAN
    Edge(WordID c, const EGrammarNode* d, const FSTNode* i, const FSTNode* j,
         const Edge* act_par, const TargetPhraseSet* translations) :
  #ifdef DEBUG_CHART_PARSER
      id(++id_count),
  #endif
      cat(c), dot(d), q(i), r(j), active_parent(act_par), passive_parent(NULL), tps(translations) {}
  
    Edge(WordID c, const EGrammarNode* d, const FSTNode* i, const FSTNode* j,
         const Edge* act_par, const TargetPhraseSet* translations,
         const SparseVector<double>& feats) :
  #ifdef DEBUG_CHART_PARSER
      id(++id_count),
  #endif
      cat(c), dot(d), q(i), r(j), active_parent(act_par), passive_parent(NULL), tps(translations),
      features(new SparseVector<double>(feats)) {}
  
    // constructors for COMPLETE
    Edge(WordID c, const EGrammarNode* d, const FSTNode* i, const FSTNode* j,
         const Edge* act_par, const Edge *pas_par) :
  #ifdef DEBUG_CHART_PARSER
      id(++id_count),
  #endif
      cat(c), dot(d), q(i), r(j), active_parent(act_par), passive_parent(pas_par), tps(NULL) {
        assert(pas_par->IsPassive());
        assert(act_par->IsActive());
      }
  
    Edge(WordID c, const EGrammarNode* d, const FSTNode* i, const FSTNode* j,
         const Edge* act_par, const Edge *pas_par, const SparseVector<double>& feats) :
  #ifdef DEBUG_CHART_PARSER
      id(++id_count),
  #endif
      cat(c), dot(d), q(i), r(j), active_parent(act_par), passive_parent(pas_par), tps(NULL),
      features(new SparseVector<double>(feats)) {
        assert(pas_par->IsPassive());
        assert(act_par->IsActive());
      }
  
    // constructor for COMPLETE query
    Edge(const FSTNode* _r) :
  #ifdef DEBUG_CHART_PARSER
      id(0),
  #endif
      cat(0), dot(NULL), q(NULL),
      r(_r), active_parent(NULL), passive_parent(NULL), tps(NULL) {}
    // constructor for MERGE quere
    Edge(const FSTNode* _q, int) :
  #ifdef DEBUG_CHART_PARSER
      id(0),
  #endif
      cat(0), dot(NULL), q(_q),
      r(NULL), active_parent(NULL), passive_parent(NULL), tps(NULL) {}
  };
  #ifdef DEBUG_CHART_PARSER
  int Edge::id_count = 0;
  #endif
  
  ostream& operator<<(ostream& os, const Edge& e) {
    string type = "PREDICT";
    if (e.IsCreatedByScan())
      type = "SCAN";
    else if (e.IsCreatedByComplete())
      type = "COMPLETE";
    os << "["
  #ifdef DEBUG_CHART_PARSER
       << '(' << e.id << ") "
  #else
       << '(' << &e << ") "
  #endif
       << "q=" << e.q << ", r=" << e.r
       << ", cat="<< TD::Convert(e.cat*-1) << ", dot="
       << e.dot
  #ifdef DEBUG_CHART_PARSER
       << e.dot->hint
  #endif
       << (e.IsActive() ? ", Active" : ", Passive")
       << ", " << type;
  #ifdef DEBUG_CHART_PARSER
    if (e.active_parent) { os << ", act.parent=(" << e.active_parent->id << ')'; }
    if (e.passive_parent) { os << ", psv.parent=(" << e.passive_parent->id << ')'; }
  #endif
    if (e.tps) { os << ", tps=" << e.tps; }
    return os << ']';
  }
  
  struct Traversal {
    const Edge* const edge;      // result from the active / passive combination
    const Edge* const active;
    const Edge* const passive;
    Traversal(const Edge* me, const Edge* a, const Edge* p) : edge(me), active(a), passive(p) {}
  };
  
  struct UniqueTraversalHash {
    size_t operator()(const Traversal* t) const {
      size_t x = 5381;
      x = ((x << 5) + x) ^ reinterpret_cast<size_t>(t->active);
      x = ((x << 5) + x) ^ reinterpret_cast<size_t>(t->passive);
      x = ((x << 5) + x) ^ t->edge->IsActive();
      return x;
    }
  };
  
  struct UniqueTraversalEquals {
    size_t operator()(const Traversal* a, const Traversal* b) const {
      return (a->passive == b->passive && a->active == b->active && a->edge->IsActive() == b->edge->IsActive());
    }
  };
  
  struct UniqueEdgeHash {
    size_t operator()(const Edge* e) const {
      size_t x = 5381;
      if (e->IsActive()) {
        x = ((x << 5) + x) ^ reinterpret_cast<size_t>(e->dot);
        x = ((x << 5) + x) ^ reinterpret_cast<size_t>(e->q);
        x = ((x << 5) + x) ^ reinterpret_cast<size_t>(e->r);
        x = ((x << 5) + x) ^ static_cast<size_t>(e->cat);
        x += 13;
      } else {  // with passive edges, we don't care about the dot
        x = ((x << 5) + x) ^ reinterpret_cast<size_t>(e->q);
        x = ((x << 5) + x) ^ reinterpret_cast<size_t>(e->r);
        x = ((x << 5) + x) ^ static_cast<size_t>(e->cat);
      }
      return x;
    }
  };
  
  struct UniqueEdgeEquals {
    bool operator()(const Edge* a, const Edge* b) const {
      if (a->IsActive() != b->IsActive()) return false;
      if (a->IsActive()) {
        return (a->cat == b->cat) && (a->dot == b->dot) && (a->q == b->q) && (a->r == b->r);
      } else {
        return (a->cat == b->cat) && (a->q == b->q) && (a->r == b->r);
      }
    }
  };
  
  struct REdgeHash {
    size_t operator()(const Edge* e) const {
      size_t x = 5381;
      x = ((x << 5) + x) ^ reinterpret_cast<size_t>(e->r);
      return x;
    }
  };
  
  struct REdgeEquals {
    bool operator()(const Edge* a, const Edge* b) const {
      return (a->r == b->r);
    }
  };
  
  struct QEdgeHash {
    size_t operator()(const Edge* e) const {
      size_t x = 5381;
      x = ((x << 5) + x) ^ reinterpret_cast<size_t>(e->q);
      return x;
    }
  };
  
  struct QEdgeEquals {
    bool operator()(const Edge* a, const Edge* b) const {
      return (a->q == b->q);
    }
  };
  
  struct EdgeQueue {
    queue<const Edge*> q;
    EdgeQueue() {}
    void clear() { while(!q.empty()) q.pop(); }
    bool HasWork() const { return !q.empty(); }
    const Edge* Next() { const Edge* res = q.front(); q.pop(); return res; }
    void AddEdge(const Edge* s) { q.push(s); }
  };
  
  class EarleyComposerImpl {
   public:
    EarleyComposerImpl(WordID start_cat, const FSTNode& q_0) : start_cat_(start_cat), q_0_(&q_0) {}
  
    // returns false if the intersection is empty
    bool Compose(const EGrammar& g, Hypergraph* forest) {
      goal_node = NULL;
      EGrammar::const_iterator sit = g.find(start_cat_);
      forest->ReserveNodes(kMAX_NODES);
      assert(sit != g.end());
      Edge* init = new Edge(start_cat_, &sit->second, q_0_);
      if (!IncorporateNewEdge(init)) {
        cerr << "Failed to create initial edge!\n";
        abort();
      }
      while (exp_agenda.HasWork() || agenda.HasWork()) {
        while(exp_agenda.HasWork()) {
          const Edge* edge = exp_agenda.Next();
          FinishEdge(edge, forest);
        }
        if (agenda.HasWork()) {
          const Edge* edge = agenda.Next();
  #ifdef DEBUG_CHART_PARSER
          cerr << "processing (" << edge->id << ')' << endl;
  #endif
          if (edge->IsActive()) {
            if (edge->dot->HasTerminals())
              DoScan(edge);
            if (edge->dot->HasNonTerminals()) {
              DoMergeWithPassives(edge);
              DoPredict(edge, g);
            }
          } else {
            DoComplete(edge);
          }
        }
      }
      if (goal_node) {
        forest->PruneUnreachable(goal_node->id_);
        RemoveEpsilons(forest, kEPS);
      }
      FreeAll();
      return goal_node;
    }
  
    void FreeAll() {
      for (int i = 0; i < free_list_.size(); ++i)
        delete free_list_[i];
      free_list_.clear();
      for (int i = 0; i < traversal_free_list_.size(); ++i)
        delete traversal_free_list_[i];
      traversal_free_list_.clear();
      all_traversals.clear();
      exp_agenda.clear();
      agenda.clear();
      tps2node.clear();
      edge2node.clear();
      all_edges.clear();
      passive_edges.clear();
      active_edges.clear();
    }
  
    ~EarleyComposerImpl() {
      FreeAll();
    }
  
    // returns the total number of edges created during composition
    int EdgesCreated() const {
      return free_list_.size();
    }
  
   private:
    void DoScan(const Edge* edge) {
      // here, we assume that the FST will potentially have many more outgoing
      // edges than the grammar, which will be just a couple.  If you want to
      // efficiently handle the case where both are relatively large, this code
      // will need to change how the intersection is done.  The best general
      // solution would probably be the Baeza-Yates double binary search.
  
      const EGrammarNode* dot = edge->dot;
      const FSTNode* r = edge->r;
      const map<WordID, EGrammarNode>& terms = dot->GetTerminals();
      for (map<WordID, EGrammarNode>::const_iterator git = terms.begin();
           git != terms.end(); ++git) {
        const FSTNode* next_r = r->Extend(git->first);
        if (!next_r) continue;
        const EGrammarNode* next_dot = &git->second;
        const bool grammar_continues = next_dot->GrammarContinues();
        const bool rule_completes    = next_dot->RuleCompletes();
        assert(grammar_continues || rule_completes);
        const SparseVector<double>& input_features = next_dot->GetCFGProductionFeatures();
        // create up to 4 new edges!
        if (next_r->HasOutgoingNonEpsilonEdges()) {     // are there further symbols in the FST?
          const TargetPhraseSet* translations = NULL;
          if (rule_completes)
            IncorporateNewEdge(new Edge(edge->cat, next_dot, edge->q, next_r, edge, translations, input_features));
          if (grammar_continues)
            IncorporateNewEdge(new Edge(edge->cat, next_dot, edge->q, next_r, edge, translations));
        }
        if (next_r->HasData()) {   // indicates a loop back to q_0 in the FST
          const TargetPhraseSet* translations = next_r->GetTranslations();
          if (rule_completes)
            IncorporateNewEdge(new Edge(edge->cat, next_dot, edge->q, q_0_, edge, translations, input_features));
          if (grammar_continues)
            IncorporateNewEdge(new Edge(edge->cat, next_dot, edge->q, q_0_, edge, translations));
        }
      }
    }
  
    void DoPredict(const Edge* edge, const EGrammar& g) {
      const EGrammarNode* dot = edge->dot;
      const map<WordID, EGrammarNode>& non_terms = dot->GetNonTerminals();
      for (map<WordID, EGrammarNode>::const_iterator git = non_terms.begin();
           git != non_terms.end(); ++git) {
        const WordID nt_to_predict = git->first;
        //cerr << edge->id << " -- " << TD::Convert(nt_to_predict*-1) << endl;
        EGrammar::const_iterator egi = g.find(nt_to_predict);
        if (egi == g.end()) {
          cerr << "[ERROR] Can't find any grammar rules with a LHS of type "
               << TD::Convert(-1*nt_to_predict) << '!' << endl;
          continue;
        }
        assert(edge->IsActive());
        const EGrammarNode* new_dot = &egi->second;
        Edge* new_edge = new Edge(nt_to_predict, new_dot, edge->r, edge);
        IncorporateNewEdge(new_edge);
      }
    }
  
    void DoComplete(const Edge* passive) {
  #ifdef DEBUG_CHART_PARSER
      cerr << "  complete: " << *passive << endl;
  #endif
      const WordID completed_nt = passive->cat;
      const FSTNode* q = passive->q;
      const FSTNode* next_r = passive->r;
      const Edge query(q);
      const pair<unordered_multiset<const Edge*, REdgeHash, REdgeEquals>::iterator,
           unordered_multiset<const Edge*, REdgeHash, REdgeEquals>::iterator > p =
        active_edges.equal_range(&query);
      for (unordered_multiset<const Edge*, REdgeHash, REdgeEquals>::iterator it = p.first;
           it != p.second; ++it) {
        const Edge* active = *it;
  #ifdef DEBUG_CHART_PARSER
        cerr << "    pos: " << *active << endl;
  #endif
        const EGrammarNode* next_dot = active->dot->Extend(completed_nt);
        if (!next_dot) continue;
        const SparseVector<double>& input_features = next_dot->GetCFGProductionFeatures();
        // add up to 2 rules
        if (next_dot->RuleCompletes())
          IncorporateNewEdge(new Edge(active->cat, next_dot, active->q, next_r, active, passive, input_features));
        if (next_dot->GrammarContinues())
          IncorporateNewEdge(new Edge(active->cat, next_dot, active->q, next_r, active, passive));
      }
    }
  
    void DoMergeWithPassives(const Edge* active) {
      // edge is active, has non-terminals, we need to find the passives that can extend it
      assert(active->IsActive());
      assert(active->dot->HasNonTerminals());
  #ifdef DEBUG_CHART_PARSER
      cerr << "  merge active with passives: ACT=" << *active << endl;
  #endif
      const Edge query(active->r, 1);
      const pair<unordered_multiset<const Edge*, QEdgeHash, QEdgeEquals>::iterator,
           unordered_multiset<const Edge*, QEdgeHash, QEdgeEquals>::iterator > p =
        passive_edges.equal_range(&query);
      for (unordered_multiset<const Edge*, QEdgeHash, QEdgeEquals>::iterator it = p.first;
           it != p.second; ++it) {
        const Edge* passive = *it;
        const EGrammarNode* next_dot = active->dot->Extend(passive->cat);
        if (!next_dot) continue;
        const FSTNode* next_r = passive->r;
        const SparseVector<double>& input_features = next_dot->GetCFGProductionFeatures();
        if (next_dot->RuleCompletes())
          IncorporateNewEdge(new Edge(active->cat, next_dot, active->q, next_r, active, passive, input_features));
        if (next_dot->GrammarContinues())
          IncorporateNewEdge(new Edge(active->cat, next_dot, active->q, next_r, active, passive));
      }
    }
  
    // take ownership of edge memory, add to various indexes, etc
    // returns true if this edge is new
    bool IncorporateNewEdge(Edge* edge) {
      free_list_.push_back(edge);
      if (edge->passive_parent && edge->active_parent) {
        Traversal* t = new Traversal(edge, edge->active_parent, edge->passive_parent);
        traversal_free_list_.push_back(t);
        if (all_traversals.find(t) != all_traversals.end()) {
          return false;
        } else {
          all_traversals.insert(t);
        }
      }
      exp_agenda.AddEdge(edge);
      return true;
    }
  
    bool FinishEdge(const Edge* edge, Hypergraph* hg) {
      bool is_new = false;
      if (all_edges.find(edge) == all_edges.end()) {
  #ifdef DEBUG_CHART_PARSER
        cerr << *edge << " is NEW\n";
  #endif
        all_edges.insert(edge);
        is_new = true;
        if (edge->IsPassive()) passive_edges.insert(edge);
        if (edge->IsActive()) active_edges.insert(edge);
        agenda.AddEdge(edge);
      } else {
  #ifdef DEBUG_CHART_PARSER
        cerr << *edge << " is NOT NEW.\n";
  #endif
      }
      AddEdgeToTranslationForest(edge, hg);
      return is_new;
    }
  
    // build the translation forest
    void AddEdgeToTranslationForest(const Edge* edge, Hypergraph* hg) {
      assert(hg->nodes_.size() < kMAX_NODES);
      Hypergraph::Node* tps = NULL;
      // first add any target language rules
      if (edge->tps) {
        Hypergraph::Node*& node = tps2node[(size_t)edge->tps];
        if (!node) {
          // cerr << "Creating phrases for " << edge->tps << endl;
          const vector<TRulePtr>& rules = edge->tps->GetRules();
          node = hg->AddNode(kPHRASE);
          for (int i = 0; i < rules.size(); ++i) {
            Hypergraph::Edge* hg_edge = hg->AddEdge(rules[i], Hypergraph::TailNodeVector());
            hg_edge->feature_values_ += rules[i]->GetFeatureValues();
            hg->ConnectEdgeToHeadNode(hg_edge, node);
          }
        }
        tps = node;
      }
      Hypergraph::Node*& head_node = edge2node[edge];
      if (!head_node)
        head_node = hg->AddNode(edge->cat);
      if (edge->cat == start_cat_ && edge->q == q_0_ && edge->r == q_0_ && edge->IsPassive()) {
        assert(goal_node == NULL || goal_node == head_node);
        goal_node = head_node;
      }
      int rhs1 = 0;
      int rhs2 = 0;
      Hypergraph::TailNodeVector tail;
      SparseVector<double> extra;
      if (edge->IsCreatedByPredict()) {
        // extra.set_value(FD::Convert("predict"), 1);
      } else if (edge->IsCreatedByScan()) {
        tail.push_back(edge2node[edge->active_parent]->id_);
        rhs1 = edge->active_parent->cat;
        if (tps) {
          tail.push_back(tps->id_);
          rhs2 = kPHRASE;
        }
        //extra.set_value(FD::Convert("scan"), 1);
      } else if (edge->IsCreatedByComplete()) {
        tail.push_back(edge2node[edge->active_parent]->id_);
        rhs1 = edge->active_parent->cat;
        tail.push_back(edge2node[edge->passive_parent]->id_);
        rhs2 = edge->passive_parent->cat;
        //extra.set_value(FD::Convert("complete"), 1);
      } else {
        assert(!"unexpected edge type!");
      }
      //cerr << head_node->id_ << "<--" << *edge << endl;
  
  #ifdef DEBUG_CHART_PARSER
        for (int i = 0; i < tail.size(); ++i)
          if (tail[i] == head_node->id_) {
            cerr << "ERROR: " << *edge << "\n   i=" << i << endl;
            if (i == 1) { cerr << "\tP: " << *edge->passive_parent << endl; }
            if (i == 0) { cerr << "\tA: " << *edge->active_parent << endl; }
            assert(!"self-loop found!");
          }
  #endif
      Hypergraph::Edge* hg_edge = NULL;
      if (tail.size() == 0) {
        hg_edge = hg->AddEdge(CreateEpsilonRule(edge->cat), tail);
      } else if (tail.size() == 1) {
        hg_edge = hg->AddEdge(CreateUnaryRule(edge->cat, rhs1), tail);
      } else if (tail.size() == 2) {
        hg_edge = hg->AddEdge(CreateBinaryRule(edge->cat, rhs1, rhs2), tail);
      }
      if (edge->features)
        hg_edge->feature_values_ += *edge->features;
      hg_edge->feature_values_ += extra;
      hg->ConnectEdgeToHeadNode(hg_edge, head_node);
    }
  
    Hypergraph::Node* goal_node;
    EdgeQueue exp_agenda;
    EdgeQueue agenda;
    unordered_map<size_t, Hypergraph::Node*> tps2node;
    unordered_map<const Edge*, Hypergraph::Node*, UniqueEdgeHash, UniqueEdgeEquals> edge2node;
    unordered_set<const Traversal*, UniqueTraversalHash, UniqueTraversalEquals> all_traversals;
    unordered_set<const Edge*, UniqueEdgeHash, UniqueEdgeEquals> all_edges;
    unordered_multiset<const Edge*, QEdgeHash, QEdgeEquals> passive_edges;
    unordered_multiset<const Edge*, REdgeHash, REdgeEquals> active_edges;
    vector<Edge*> free_list_;
    vector<Traversal*> traversal_free_list_;
    const WordID start_cat_;
    const FSTNode* const q_0_;
  };
  
  #ifdef DEBUG_CHART_PARSER
  static string TrimRule(const string& r) {
    size_t start = r.find(" |||") + 5;
    size_t end = r.rfind(" |||");
    return r.substr(start, end - start);
  }
  #endif
  
  void AddGrammarRule(const string& r, EGrammar* g) {
    const size_t pos = r.find(" ||| ");
    if (pos == string::npos || r[0] != '[') {
      cerr << "Bad rule: " << r << endl;
      return;
    }
    const size_t rpos = r.rfind(" ||| ");
    string feats;
    string rs = r;
    if (rpos != pos) {
      feats = r.substr(rpos + 5);
      rs = r.substr(0, rpos);
    }
    string rhs = rs.substr(pos + 5);
    string trule = rs + " ||| " + rhs + " ||| " + feats;
    TRule tr(trule);
  #ifdef DEBUG_CHART_PARSER
    string hint_last_rule;
  #endif
    EGrammarNode* cur = &(*g)[tr.GetLHS()];
    cur->is_root = true;
    for (int i = 0; i < tr.FLength(); ++i) {
      WordID sym = tr.f()[i];
  #ifdef DEBUG_CHART_PARSER
      hint_last_rule = TD::Convert(sym < 0 ? -sym : sym);
      cur->hint += " <@@> (*" + hint_last_rule + ") " + TrimRule(tr.AsString());
  #endif
      if (sym < 0)
        cur = &cur->ntptr[sym];
      else
        cur = &cur->tptr[sym];
    }
  #ifdef DEBUG_CHART_PARSER
    cur->hint += " <@@> (" + hint_last_rule + "*) " + TrimRule(tr.AsString());
  #endif
    cur->is_some_rule_complete = true;
    cur->input_features = tr.GetFeatureValues();
  }
  
  EarleyComposer::~EarleyComposer() {
    delete pimpl_;
  }
  
  EarleyComposer::EarleyComposer(const FSTNode* fst) {
    InitializeConstants();
    pimpl_ = new EarleyComposerImpl(kUNIQUE_START, *fst);
  }
  
  bool EarleyComposer::Compose(const Hypergraph& src_forest, Hypergraph* trg_forest) {
    // first, convert the src forest into an EGrammar
    EGrammar g;
    const int nedges = src_forest.edges_.size();
    const int nnodes = src_forest.nodes_.size();
    vector<int> cats(nnodes);
    bool assign_cats = false;
    for (int i = 0; i < nnodes; ++i)
      if (assign_cats) {
        cats[i] = TD::Convert("CAT_" + boost::lexical_cast<string>(i)) * -1;
      } else {
        cats[i] = src_forest.nodes_[i].cat_;
      }
    // construct the grammar
    for (int i = 0; i < nedges; ++i) {
      const Hypergraph::Edge& edge = src_forest.edges_[i];
      const vector<WordID>& src = edge.rule_->f();
      EGrammarNode* cur = &g[cats[edge.head_node_]];
      cur->is_root = true;
      int ntc = 0;
      for (int j = 0; j < src.size(); ++j) {
        WordID sym = src[j];
        if (sym <= 0) {
          sym = cats[edge.tail_nodes_[ntc]];
          ++ntc;
          cur = &cur->ntptr[sym];
        } else {
          cur = &cur->tptr[sym];
        }
      }
      cur->is_some_rule_complete = true;
      cur->input_features = edge.feature_values_;
    }
    EGrammarNode& goal_rule = g[kUNIQUE_START];
    assert((goal_rule.ntptr.size() == 1 && goal_rule.tptr.size() == 0) ||
           (goal_rule.ntptr.size() == 0 && goal_rule.tptr.size() == 1));
  
    return pimpl_->Compose(g, trg_forest);
  }
  
  bool EarleyComposer::Compose(istream* in, Hypergraph* trg_forest) {
    EGrammar g;
    while(*in) {
      string line;
      getline(*in, line);
      if (line.empty()) continue;
      AddGrammarRule(line, &g);
    }
  
    return pimpl_->Compose(g, trg_forest);
  }
  