00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #include "VarSpanTrieBuilder.h"
00021
00022 #include "ApplicableRuleTrie.h"
00023 #include "IntermediateVarSpanNode.h"
00024 #include "VarSpanNode.h"
00025
00026 #include <algorithm>
00027 #include <vector>
00028
00029 namespace Moses
00030 {
00031
00032 std::auto_ptr<VarSpanNode> VarSpanTrieBuilder::Build(
00033 ApplicableRuleTrie &root)
00034 {
00035 std::auto_ptr<VarSpanNode> vstRoot(new VarSpanNode());
00036 NodeVec vec;
00037 const std::vector<ApplicableRuleTrie*> &children = root.m_children;
00038 for (std::vector<ApplicableRuleTrie*>::const_iterator p = children.begin();
00039 p != children.end(); ++p) {
00040 Build(**p, vec, *(vstRoot.get()));
00041 }
00042 return vstRoot;
00043 }
00044
00045 void VarSpanTrieBuilder::Build(ApplicableRuleTrie &artNode,
00046 NodeVec &vec,
00047 VarSpanNode &vstRoot)
00048 {
00049 typedef IntermediateVarSpanNode::Range Range;
00050
00051
00052
00053 NodeVecState state;
00054 RecordState(vec, state);
00055
00056 if (artNode.m_end == -1) {
00057 if (!vec.empty() && vec.back().isOpen()) {
00058 ++(vec.back().m_numSplitPoints);
00059 ++(vec.back().m_end.first);
00060 } else if (artNode.m_start == -1) {
00061 Range start(0, -1);
00062 Range end(0, -1);
00063 vec.push_back(IntermediateVarSpanNode(start, end));
00064 } else {
00065 Range start(artNode.m_start, artNode.m_start);
00066 Range end(artNode.m_start, -1);
00067 vec.push_back(IntermediateVarSpanNode(start, end));
00068 }
00069 } else if (!vec.empty() && vec.back().isOpen()) {
00070 vec.back().m_end = Range(artNode.m_start-1, artNode.m_start-1);
00071 if (vec.back().m_start.second == -1) {
00072 size_t s = artNode.m_start - (vec.back().m_numSplitPoints + 1);
00073 vec.back().m_start.second = s;
00074 }
00075 }
00076
00077 if (artNode.m_node->HasRules()) {
00078 artNode.m_vstNode = &(vstRoot.Insert(vec));
00079 }
00080
00081 const std::vector<ApplicableRuleTrie*> &children = artNode.m_children;
00082 for (std::vector<ApplicableRuleTrie*>::const_iterator p = children.begin();
00083 p != children.end(); ++p) {
00084 Build(**p, vec, vstRoot);
00085 }
00086
00087
00088 RestoreState(state, vec);
00089 }
00090
00091 void VarSpanTrieBuilder::RecordState(const NodeVec &vec, NodeVecState &state)
00092 {
00093 state.m_size = vec.size();
00094 if (!vec.empty()) {
00095 state.m_lastNode = vec.back();
00096 }
00097 }
00098
00099 void VarSpanTrieBuilder::RestoreState(const NodeVecState &state, NodeVec &vec)
00100 {
00101 assert(state.m_size == vec.size() || state.m_size+1 == vec.size());
00102 if (state.m_size < vec.size()) {
00103 vec.resize(state.m_size);
00104 } else if (!vec.empty()) {
00105 vec.back() = state.m_lastNode;
00106 }
00107 }
00108
00109 }