Start arbitrary arity. Currently incorrect.

14 files changed, 250 insertions, 166 deletions

diff --git a/search/Jamfile b/search/Jamfile
index e8b14363d..dcf55558c 100644
--- a/search/Jamfile
+++ b/search/Jamfile
@@ -1,4 +1,4 @@
-lib search : weights.cc vertex.cc vertex_generator.cc edge_queue.cc edge_generator.cc rule.cc ../lm//kenlm ../util//kenutil /top//boost_system : : : <include>.. ;
+lib search : weights.cc vertex.cc vertex_generator.cc pool.cc edge_generator.cc rule.cc ../lm//kenlm ../util//kenutil /top//boost_system : : : <include>.. ;
 
 import testing ;
 
diff --git a/search/edge.hh b/search/edge.hh
index 77ab0ade6..98085c416 100644
--- a/search/edge.hh
+++ b/search/edge.hh
@@ -2,30 +2,76 @@
 #define SEARCH_EDGE__
 
 #include "lm/state.hh"
-#include "search/arity.hh"
-#include "search/rule.hh"
+#include "search/pool.hh"
 #include "search/types.hh"
 #include "search/vertex.hh"
 
-#include <queue>
+#include <functional>
+
+#include <stdint.h>
 
 namespace search {
 
-struct PartialEdge {
-  Score score;
-  // Terminals
-  lm::ngram::ChartState between[kMaxArity + 1];
-  // Non-terminals
-  PartialVertex nt[kMaxArity];
+// Copyable, but the copy will be shallow.
+class PartialEdge {
+  public:
+    // Allow default construction for STL.  
+    PartialEdge() : base_(NULL) {}
+    bool Valid() const { return base_; }
+
+    Score GetScore() const {
+      return *reinterpret_cast<const float*>(base_);
+    }
+    void SetScore(Score to) {
+      *reinterpret_cast<float*>(base_) = to;
+    }
+    bool operator<(const PartialEdge &other) const {
+      return GetScore() < other.GetScore();
+    }
+
+    Arity GetArity() const {
+      return *reinterpret_cast<const Arity*>(base_ + sizeof(Score));
+    }
+
+    // Non-terminals
+    const PartialVertex *NT() const {
+      return reinterpret_cast<const PartialVertex*>(base_ + sizeof(Score) + sizeof(Arity));
+    }
+    PartialVertex *NT() {
+      return reinterpret_cast<PartialVertex*>(base_ + sizeof(Score) + sizeof(Arity));
+    }
+
+    const lm::ngram::ChartState &CompletedState() const {
+      return *Between();
+    }
+    const lm::ngram::ChartState *Between() const {
+      return reinterpret_cast<const lm::ngram::ChartState*>(base_ + sizeof(Score) + sizeof(Arity) + GetArity() * sizeof(PartialVertex));
+    }
+    lm::ngram::ChartState *Between() {
+      return reinterpret_cast<lm::ngram::ChartState*>(base_ + sizeof(Score) + sizeof(Arity) + GetArity() * sizeof(PartialVertex));
+    }
 
-  const lm::ngram::ChartState &CompletedState() const {
-    return between[0];
-  }
+  private:
+    friend class PartialEdgePool;
+    PartialEdge(void *base, Arity arity) : base_(static_cast<uint8_t*>(base)) {
+      *reinterpret_cast<Arity*>(base_ + sizeof(Score)) = arity;
+    }
 
-  bool operator<(const PartialEdge &other) const {
-    return score < other.score;
-  }
+    uint8_t *base_;
 };
 
+class PartialEdgePool {
+  public:
+    PartialEdge Allocate(Arity arity) {
+      return PartialEdge(
+          pool_.Allocate(sizeof(Score) + sizeof(Arity) + arity * sizeof(PartialVertex) + (arity + 1) * sizeof(lm::ngram::ChartState)),
+          arity);
+    }
+
+  private:
+    Pool pool_;
+};
+
+
 } // namespace search
 #endif // SEARCH_EDGE__
diff --git a/search/edge_generator.cc b/search/edge_generator.cc
index 56239dfbb..654f9e36f 100644
--- a/search/edge_generator.cc
+++ b/search/edge_generator.cc
@@ -10,111 +10,111 @@
 
 namespace search {
 
-EdgeGenerator::EdgeGenerator(PartialEdge &root, unsigned char arity, Note note) : arity_(arity), note_(note) {
-/*  for (unsigned char i = 0; i < edge.Arity(); ++i) {
-    root.nt[i] = edge.GetVertex(i).RootPartial();
-  }
-  for (unsigned char i = edge.Arity(); i < 2; ++i) {
-    root.nt[i] = kBlankPartialVertex;
-  }*/
-  generate_.push(&root);
-  top_score_ = root.score;
+EdgeGenerator::EdgeGenerator(PartialEdge root, Note note) : top_score_(root.GetScore()), arity_(root.GetArity()), note_(note) {
+  generate_.push(root);
 }
 
 namespace {
 
-template <class Model> float FastScore(const Context<Model> &context, unsigned char victim, unsigned char arity, const PartialEdge &previous, PartialEdge &update) {
-  memcpy(update.between, previous.between, sizeof(lm::ngram::ChartState) * (arity + 1));
+template <class Model> void FastScore(const Context<Model> &context, Arity victim, Arity before_idx, Arity incomplete, const PartialEdge previous, PartialEdge update) {
+  lm::ngram::ChartState *between = update.Between();
+  const lm::ngram::ChartState *previous_between = previous.Between();
+  const search::PartialVertex &previous_vertex = previous.NT()[victim];
 
-  float ret = 0.0;
-  lm::ngram::ChartState *before, *after;
-  if (victim == 0) {
-    before = &update.between[0];
-    after = &update.between[(arity == 2 && previous.nt[1].Complete()) ? 2 : 1];
-  } else {
-    assert(victim == 1);
-    assert(arity == 2);
-    before = &update.between[previous.nt[0].Complete() ? 0 : 1];
-    after = &update.between[2];
-  }
-  const lm::ngram::ChartState &previous_reveal = previous.nt[victim].State();
-  const PartialVertex &update_nt = update.nt[victim];
+  lm::ngram::ChartState *before = &between[before_idx], *after = &between[before_idx + 1];
+  // copy [0, after] 
+  memcpy(between, previous_between, sizeof(lm::ngram::ChartState) * (before_idx + 2));
+
+  float adjustment = 0.0;
+  const lm::ngram::ChartState &previous_reveal = previous_vertex.State();
+  const PartialVertex &update_nt = update.NT()[victim];
   const lm::ngram::ChartState &update_reveal = update_nt.State();
-  float just_after = 0.0;
   if ((update_reveal.left.length > previous_reveal.left.length) || (update_reveal.left.full && !previous_reveal.left.full)) {
-    just_after += lm::ngram::RevealAfter(context.LanguageModel(), before->left, before->right, update_reveal.left, previous_reveal.left.length);
+    adjustment += lm::ngram::RevealAfter(context.LanguageModel(), before->left, before->right, update_reveal.left, previous_reveal.left.length);
   }
-  if ((update_reveal.right.length > previous_reveal.right.length) || (update_nt.RightFull() && !previous.nt[victim].RightFull())) {
-    ret += lm::ngram::RevealBefore(context.LanguageModel(), update_reveal.right, previous_reveal.right.length, update_nt.RightFull(), after->left, after->right);
+  if ((update_reveal.right.length > previous_reveal.right.length) || (update_nt.RightFull() && !previous_vertex.RightFull())) {
+    adjustment += lm::ngram::RevealBefore(context.LanguageModel(), update_reveal.right, previous_reveal.right.length, update_nt.RightFull(), after->left, after->right);
   }
   if (update_nt.Complete()) {
     if (update_reveal.left.full) {
       before->left.full = true;
     } else {
       assert(update_reveal.left.length == update_reveal.right.length);
-      ret += lm::ngram::Subsume(context.LanguageModel(), before->left, before->right, after->left, after->right, update_reveal.left.length);
-    }
-    if (victim == 0) {
-      update.between[0].right = after->right;
-    } else {
-      update.between[2].left = before->left;
+      adjustment += lm::ngram::Subsume(context.LanguageModel(), before->left, before->right, after->left, after->right, update_reveal.left.length);
     }
+    before->right = after->right;
+    // Copy the others shifted one down, covering after.  
+    memcpy(after, previous_between + before_idx + 2, sizeof(lm::ngram::ChartState) * (incomplete + 1 - before_idx - 2));
+  } else {
+    // Copy [after + 1, incomplete]
+    memcpy(after + 1, previous_between + before_idx + 2, sizeof(lm::ngram::ChartState) * (incomplete + 1 - before_idx - 2));
   }
-  return previous.score + (ret + just_after) * context.GetWeights().LM();
+  update.SetScore(previous.GetScore() + adjustment * context.GetWeights().LM());
 }
 
 } // namespace
 
-template <class Model> PartialEdge *EdgeGenerator::Pop(Context<Model> &context, boost::pool<> &partial_edge_pool) {
+template <class Model> PartialEdge EdgeGenerator::Pop(Context<Model> &context, PartialEdgePool &partial_edge_pool) {
   assert(!generate_.empty());
-  PartialEdge &top = *generate_.top();
+  PartialEdge top = generate_.top();
   generate_.pop();
-  unsigned int victim = 0;
-  unsigned char lowest_length = 255;
-  for (unsigned char i = 0; i != arity_; ++i) {
-    if (!top.nt[i].Complete() && top.nt[i].Length() < lowest_length) {
-      lowest_length = top.nt[i].Length();
-      victim = i;
+  PartialVertex *top_nt = top.NT();
+
+  Arity victim = 0;
+  Arity victim_completed;
+  Arity completed = 0;
+  // Select victim or return if complete.   
+  {
+    unsigned char lowest_length = 255;
+    for (Arity i = 0; i != arity_; ++i) {
+      if (top_nt[i].Complete()) {
+        ++completed;
+      } else if (top_nt[i].Length() < lowest_length) {
+        lowest_length = top_nt[i].Length();
+        victim = i;
+        victim_completed = completed;
+      }
+    }
+    if (lowest_length == 255) {
+      // Now top.between[0] is the full edge state.  
+      top_score_ = generate_.empty() ? -kScoreInf : generate_.top().GetScore();
+      return top;
     }
-  }
-  if (lowest_length == 255) {
-    // All states report complete.  
-    top.between[0].right = top.between[arity_].right;
-    // Now top.between[0] is the full edge state.  
-    top_score_ = generate_.empty() ? -kScoreInf : generate_.top()->score;
-    return &top;
   }
 
-  unsigned int stay = !victim;
-  PartialEdge &continuation = *static_cast<PartialEdge*>(partial_edge_pool.malloc());
-  float old_bound = top.nt[victim].Bound();
-  // The alternate's score will change because alternate.nt[victim] changes.  
-  bool split = top.nt[victim].Split(continuation.nt[victim]);
+  float old_bound = top_nt[victim].Bound();
+  PartialEdge continuation = partial_edge_pool.Allocate(arity_);
+  PartialVertex *continuation_nt = continuation.NT();
+  // The alternate's score will change because the nt changes.
+  bool split = top_nt[victim].Split(continuation_nt[victim]);
   // top is now the alternate.  
 
-  continuation.nt[stay] = top.nt[stay];
-  continuation.score = FastScore(context, victim, arity_, top, continuation);
+  for (Arity i = 0; i < victim; ++i) continuation_nt[i] = top_nt[i];
+  for (Arity i = victim + 1; i < arity_; ++i) continuation_nt[i] = top_nt[i];
+  FastScore(context, victim, victim - victim_completed, arity_ - completed, top, continuation);
   // TODO: dedupe?  
-  generate_.push(&continuation);
+  generate_.push(continuation);
 
   if (split) {
     // We have an alternate.  
-    top.score += top.nt[victim].Bound() - old_bound;
+    top.SetScore(top_nt[victim].Bound() - old_bound);
     // TODO: dedupe?  
-    generate_.push(&top);
+    generate_.push(top);
   } else {
-    partial_edge_pool.free(&top);
+    // TODO should free top here. 
+    // Better would be changing Split.  
   }
 
-  top_score_ = generate_.top()->score;
-  return NULL;
+  top_score_ = generate_.top().GetScore();
+  // Invalid indicates no new hypothesis generated.  
+  return PartialEdge();
 }
 
-template PartialEdge *EdgeGenerator::Pop(Context<lm::ngram::RestProbingModel> &context, boost::pool<> &partial_edge_pool);
-template PartialEdge *EdgeGenerator::Pop(Context<lm::ngram::ProbingModel> &context, boost::pool<> &partial_edge_pool);
-template PartialEdge *EdgeGenerator::Pop(Context<lm::ngram::TrieModel> &context, boost::pool<> &partial_edge_pool);
-template PartialEdge *EdgeGenerator::Pop(Context<lm::ngram::QuantTrieModel> &context, boost::pool<> &partial_edge_pool);
-template PartialEdge *EdgeGenerator::Pop(Context<lm::ngram::ArrayTrieModel> &context, boost::pool<> &partial_edge_pool);
-template PartialEdge *EdgeGenerator::Pop(Context<lm::ngram::QuantArrayTrieModel> &context, boost::pool<> &partial_edge_pool);
+template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::RestProbingModel> &context, PartialEdgePool &partial_edge_pool);
+template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::ProbingModel> &context, PartialEdgePool &partial_edge_pool);
+template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::TrieModel> &context, PartialEdgePool &partial_edge_pool);
+template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::QuantTrieModel> &context, PartialEdgePool &partial_edge_pool);
+template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::ArrayTrieModel> &context, PartialEdgePool &partial_edge_pool);
+template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::QuantArrayTrieModel> &context, PartialEdgePool &partial_edge_pool);
 
 } // namespace search
diff --git a/search/edge_generator.hh b/search/edge_generator.hh
index 875ccc5ea..734993cab 100644
--- a/search/edge_generator.hh
+++ b/search/edge_generator.hh
@@ -3,11 +3,8 @@
 
 #include "search/edge.hh"
 #include "search/note.hh"
+#include "search/types.hh"
 
-#include <boost/pool/pool.hpp>
-#include <boost/unordered_map.hpp>
-
-#include <functional>
 #include <queue>
 
 namespace lm {
@@ -19,18 +16,11 @@ class ChartState;
 namespace search {
 
 template <class Model> class Context;
-
-class VertexGenerator;
-
-struct PartialEdgePointerLess : std::binary_function<const PartialEdge *, const PartialEdge *, bool> {
-  bool operator()(const PartialEdge *first, const PartialEdge *second) const {
-    return *first < *second;
-  }
-};
+class PartialEdgePool;
 
 class EdgeGenerator {
   public:
-    EdgeGenerator(PartialEdge &root, unsigned char arity, Note note);
+    EdgeGenerator(PartialEdge root, Note note);
 
     Score TopScore() const {
       return top_score_;
@@ -41,16 +31,16 @@ class EdgeGenerator {
     }
 
     // Pop.  If there's a complete hypothesis, return it.  Otherwise return NULL.  
-    template <class Model> PartialEdge *Pop(Context<Model> &context, boost::pool<> &partial_edge_pool);
+    template <class Model> PartialEdge Pop(Context<Model> &context, PartialEdgePool &partial_edge_pool);
 
   private:
     Score top_score_;
 
-    unsigned char arity_;
-
-    typedef std::priority_queue<PartialEdge*, std::vector<PartialEdge*>, PartialEdgePointerLess> Generate;
+    typedef std::priority_queue<PartialEdge> Generate;
     Generate generate_;
 
+    Arity arity_;
+
     Note note_;
 };
 
diff --git a/search/edge_queue.cc b/search/edge_queue.cc
deleted file mode 100644
index e3ae6ebf7..000000000
--- a/search/edge_queue.cc
+++ /dev/null
@@ -1,25 +0,0 @@
-#include "search/edge_queue.hh"
-
-#include "lm/left.hh"
-#include "search/context.hh"
-
-#include <stdint.h>
-
-namespace search {
-
-EdgeQueue::EdgeQueue(unsigned int pop_limit_hint) : partial_edge_pool_(sizeof(PartialEdge), pop_limit_hint * 2) {
-  take_ = static_cast<PartialEdge*>(partial_edge_pool_.malloc());
-}
-
-/*void EdgeQueue::AddEdge(PartialEdge &root, unsigned char arity, Note note) {
-  // Ignore empty edges.  
-  for (unsigned char i = 0; i < edge.Arity(); ++i) {
-    PartialVertex root(edge.GetVertex(i).RootPartial());
-    if (root.Empty()) return;
-    total_score += root.Bound();
-  }
-  PartialEdge &allocated = *static_cast<PartialEdge*>(partial_edge_pool_.malloc());
-  allocated.score = total_score;
-}*/
-
-} // namespace search
diff --git a/search/edge_queue.hh b/search/edge_queue.hh
index 187eaed71..fae70562f 100644
--- a/search/edge_queue.hh
+++ b/search/edge_queue.hh
@@ -16,15 +16,14 @@ template <class Model> class Context;
 
 class EdgeQueue {
   public:
-    explicit EdgeQueue(unsigned int pop_limit_hint);
+    EdgeQueue() {}
 
-    PartialEdge &InitializeEdge() {
-      return *take_;
+    PartialEdge AllocateEdge(Arity arity) {
+      return partial_edge_pool_.Allocate(arity);
     }
 
-    void AddEdge(unsigned char arity, Note note) {
-      generate_.push(edge_pool_.construct(*take_, arity, note));
-      take_ = static_cast<PartialEdge*>(partial_edge_pool_.malloc());
+    void AddEdge(PartialEdge edge, Note note) {
+      generate_.push(edge_pool_.construct(edge, note));
     }
 
     bool Empty() const { return generate_.empty(); }
@@ -38,9 +37,9 @@ class EdgeQueue {
       while (to_pop > 0 && !generate_.empty()) {
         EdgeGenerator *top = generate_.top();
         generate_.pop();
-        PartialEdge *ret = top->Pop(context, partial_edge_pool_);
-        if (ret) {
-          output.NewHypothesis(*ret, top->GetNote());
+        PartialEdge ret(top->Pop(context, partial_edge_pool_));
+        if (ret.Valid()) {
+          output.NewHypothesis(ret, top->GetNote());
           --to_pop;
           if (top->TopScore() != -kScoreInf) {
             generate_.push(top);
@@ -64,9 +63,7 @@ class EdgeQueue {
     typedef std::priority_queue<EdgeGenerator*, std::vector<EdgeGenerator*>, LessByTopScore> Generate;
     Generate generate_;
 
-    boost::pool<> partial_edge_pool_;
-
-    PartialEdge *take_;
+    PartialEdgePool partial_edge_pool_;
 };
 
 } // namespace search
diff --git a/search/final.hh b/search/final.hh
index 1b3092ac4..fc86e0f98 100644
--- a/search/final.hh
+++ b/search/final.hh
@@ -11,16 +11,13 @@ namespace search {
 
 class Final {
   public:
-    typedef boost::array<const Final*, search::kMaxArity> ChildArray;
-
-    void Reset(Score bound, Note note, const Final &left, const Final &right) {
+    const Final **Reset(Score bound, Note note) {
       bound_ = bound;
       note_ = note;
-      children_[0] = &left;
-      children_[1] = &right;
+      return children_;
     }
 
-    const ChildArray &Children() const { return children_; }
+    const Final *const *Children() const { return children_; }
 
     Note GetNote() const { return note_; }
 
@@ -31,7 +28,7 @@ class Final {
 
     Note note_;
 
-    ChildArray children_;
+    const Final *children_[2];
 };
 
 } // namespace search
diff --git a/search/pool.cc b/search/pool.cc
new file mode 100644
index 000000000..13ec867cf
--- /dev/null
+++ b/search/pool.cc
@@ -0,0 +1,35 @@
+#include "search/pool.hh"
+
+#include <stdlib.h>
+
+namespace search {
+
+Pool::Pool() {
+  current_ = NULL;
+  current_end_ = NULL;
+}
+
+Pool::~Pool() {
+  FreeAll();
+}
+
+void Pool::FreeAll() {
+  for (std::vector<void *>::const_iterator i(free_list_.begin()); i != free_list_.end(); ++i) {
+    free(*i);
+  }
+  free_list_.clear();
+  current_ = NULL;
+  current_end_ = NULL;
+}
+
+void *Pool::More(std::size_t size) {
+  std::size_t amount = std::max(static_cast<size_t>(32) << free_list_.size(), size);
+  uint8_t *ret = static_cast<uint8_t*>(malloc(amount));
+  if (!ret) throw std::bad_alloc();
+  free_list_.push_back(ret);
+  current_ = ret + size;
+  current_end_ = ret + amount;
+  return ret;
+}
+
+} // namespace search
diff --git a/search/pool.hh b/search/pool.hh
new file mode 100644
index 000000000..d8a1cdd6b
--- /dev/null
+++ b/search/pool.hh
@@ -0,0 +1,43 @@
+// Very simple pool.  It can only allocate memory.  And all of the memory it
+// allocates must be freed at the same time.  
+
+#ifndef SEARCH_POOL__
+#define SEARCH_POOL__
+
+#include <boost/noncopyable.hpp>
+
+#include <vector>
+
+#include <stdint.h>
+
+namespace search {
+
+class Pool : boost::noncopyable {
+  public:
+    Pool();
+
+    ~Pool();
+
+    void *Allocate(size_t size) {
+      void *ret = current_;
+      current_ += size;
+      if (current_ < current_end_) {
+        return ret;
+      } else {
+        return More(size);
+      }
+    }
+
+    void FreeAll();
+
+  private:
+    void *More(size_t size);
+
+    std::vector<void *> free_list_;
+
+    uint8_t *current_, *current_end_;
+}; 
+
+} // namespace lm
+
+#endif // SEARCH_POOL__
diff --git a/search/types.hh b/search/types.hh
index 9726379fb..46bc95288 100644
--- a/search/types.hh
+++ b/search/types.hh
@@ -3,15 +3,14 @@
 
 #include <cmath>
 
+#include <stdint.h>
+
 namespace search {
 
 typedef float Score;
 const Score kScoreInf = INFINITY;
 
-// This could have been an enum but gcc wants 4 bytes.  
-typedef bool ExtendDirection;
-const ExtendDirection kExtendLeft = 0;
-const ExtendDirection kExtendRight = 1;
+typedef uint32_t Arity;
 
 } // namespace search
 
diff --git a/search/vertex.cc b/search/vertex.cc
index cc53c0dd5..ed3631352 100644
--- a/search/vertex.cc
+++ b/search/vertex.cc
@@ -39,10 +39,4 @@ void VertexNode::SortAndSet(ContextBase &context, VertexNode **parent_ptr) {
   bound_ = extend_.front()->Bound();
 }
 
-namespace {
-VertexNode kBlankVertexNode;
-} // namespace
-
-PartialVertex kBlankPartialVertex(kBlankVertexNode);
-
 } // namespace search
diff --git a/search/vertex.hh b/search/vertex.hh
index e1a9ad113..4ccb24713 100644
--- a/search/vertex.hh
+++ b/search/vertex.hh
@@ -126,8 +126,6 @@ class PartialVertex {
     unsigned int index_;
 };
 
-extern PartialVertex kBlankPartialVertex;
-
 class Vertex {
   public:
     Vertex() {}
diff --git a/search/vertex_generator.cc b/search/vertex_generator.cc
index d94e6e06e..392cf8e5e 100644
--- a/search/vertex_generator.cc
+++ b/search/vertex_generator.cc
@@ -14,18 +14,28 @@ VertexGenerator::VertexGenerator(ContextBase &context, Vertex &gen) : context_(c
 }
 
 namespace {
+
 const uint64_t kCompleteAdd = static_cast<uint64_t>(-1);
+
+void FillFinal(PartialEdge partial, Note note, Final &out) {
+  const Final **final_out = out.Reset(partial.GetScore(), note);
+  const PartialVertex *part = partial.NT();
+  const PartialVertex *const part_end_loop = part + partial.GetArity();
+  for (; part != part_end_loop; ++part, ++final_out) {
+    *final_out = &part->End();
+  }
+}
+
 } // namespace
 
-void VertexGenerator::NewHypothesis(const PartialEdge &partial, Note note) {
+void VertexGenerator::NewHypothesis(PartialEdge partial, Note note) {
   const lm::ngram::ChartState &state = partial.CompletedState();
   std::pair<Existing::iterator, bool> got(existing_.insert(std::pair<uint64_t, Final*>(hash_value(state), NULL)));
   if (!got.second) {
     // Found it already.  
     Final &exists = *got.first->second;
-    if (exists.Bound() < partial.score) {
-      exists.Reset(partial.score, note, partial.nt[0].End(), partial.nt[1].End());
-    }
+    if (exists.Bound() < partial.GetScore())
+      FillFinal(partial, note, exists);
     return;
   }
   unsigned char left = 0, right = 0;
@@ -70,12 +80,12 @@ VertexGenerator::Trie &VertexGenerator::FindOrInsert(VertexGenerator::Trie &node
   return next;
 }
 
-Final *VertexGenerator::CompleteTransition(VertexGenerator::Trie &starter, const lm::ngram::ChartState &state, Note note, const PartialEdge &partial) {
+Final *VertexGenerator::CompleteTransition(VertexGenerator::Trie &starter, const lm::ngram::ChartState &state, Note note, PartialEdge partial) {
   VertexNode &node = *starter.under;
   assert(node.State().left.full == state.left.full);
   assert(!node.End());
   Final *final = context_.NewFinal();
-  final->Reset(partial.score, note, partial.nt[0].End(), partial.nt[1].End());
+  FillFinal(partial, note, *final);
   node.SetEnd(final);
   return final;
 }
diff --git a/search/vertex_generator.hh b/search/vertex_generator.hh
index 6b98da3e3..bb04573f8 100644
--- a/search/vertex_generator.hh
+++ b/search/vertex_generator.hh
@@ -24,7 +24,7 @@ class VertexGenerator {
   public:
     VertexGenerator(ContextBase &context, Vertex &gen);
 
-    void NewHypothesis(const PartialEdge &partial, Note note);
+    void NewHypothesis(PartialEdge partial, Note note);
 
     void FinishedSearch() {
       root_.under->SortAndSet(context_, NULL);
@@ -43,7 +43,7 @@ class VertexGenerator {
 
     Trie &FindOrInsert(Trie &node, uint64_t added, const lm::ngram::ChartState &state, unsigned char left, bool left_full, unsigned char right, bool right_full);
 
-    Final *CompleteTransition(Trie &node, const lm::ngram::ChartState &state, Note note, const PartialEdge &partial);
+    Final *CompleteTransition(Trie &node, const lm::ngram::ChartState &state, Note note, PartialEdge partial);
 
     ContextBase &context_;