00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #pragma once
00021
00022 #include "IntermediateVarSpanNode.h"
00023 #include "moses/Range.h"
00024
00025 #include <boost/array.hpp>
00026
00027 #include <map>
00028
00029 #include <vector>
00030
00031 namespace Moses
00032 {
00033
00036 struct VarSpanNode {
00037 public:
00038 struct NonTermRange {
00039 size_t s1;
00040 size_t s2;
00041 size_t e1;
00042 size_t e2;
00043 };
00044 typedef std::vector<IntermediateVarSpanNode> NodeVec;
00045 typedef boost::array<int, 5> KeyType;
00046 typedef std::map<KeyType, VarSpanNode> MapType;
00047
00048 VarSpanNode() : m_parent(0), m_label(0), m_rank(0) {}
00049
00050 VarSpanNode &Insert(const NodeVec &vec) {
00051 if (vec.empty()) {
00052 return *this;
00053 }
00054 return Insert(vec.begin(), vec.end());
00055 }
00056
00057
00058
00059 void CalculateRanges(int start, int end,
00060 std::vector<NonTermRange> &ranges) const {
00061 ranges.resize(m_rank);
00062 const VarSpanNode *n = this;
00063 size_t firstIndex = m_rank;
00064 while (n->m_parent) {
00065 const KeyType &key = *(n->m_label);
00066 assert(key[0] == 0 || key[0] == key[1]);
00067 assert(key[3] == -1 || key[2] == key[3]);
00068 const int numSplitPoints = key[4];
00069 firstIndex -= numSplitPoints+1;
00070 const int vsn_start = key[0] == 0 ? start : key[0];
00071 const int vsn_end = key[3] == -1 ? end : key[3];
00072
00073 ranges[firstIndex].s1 = ranges[firstIndex].s2 = vsn_start - start;
00074
00075
00076 if (numSplitPoints) {
00077 ranges[firstIndex].e1 = vsn_start - start;
00078 ranges[firstIndex].e2 = vsn_end - start - numSplitPoints;
00079 } else {
00080 ranges[firstIndex].e1 = ranges[firstIndex].e2 = vsn_end - start;
00081 }
00082
00083
00084 for (int i = 1; i <= numSplitPoints; ++i) {
00085 ranges[firstIndex+i].s1 = ranges[firstIndex].s1+i;
00086 ranges[firstIndex+i].s2 = ranges[firstIndex].e2+i;
00087 ranges[firstIndex+i].e1 = ranges[firstIndex].s1+i;
00088 ranges[firstIndex+i].e2 = ranges[firstIndex].e2+i;
00089 }
00090
00091 ranges[firstIndex+numSplitPoints].e1 = vsn_end - start;
00092 ranges[firstIndex+numSplitPoints].e2 = vsn_end - start;
00093 n = n->m_parent;
00094 }
00095 assert(firstIndex == 0);
00096 }
00097
00098 const VarSpanNode *m_parent;
00099 const KeyType *m_label;
00100 size_t m_rank;
00101 MapType m_children;
00102
00103 private:
00104 VarSpanNode &Insert(NodeVec::const_iterator first,
00105 NodeVec::const_iterator last) {
00106 assert(first != last);
00107
00108 KeyType key;
00109 key[0] = first->m_start.first;
00110 key[1] = first->m_start.second;
00111 key[2] = first->m_end.first;
00112 key[3] = first->m_end.second;
00113 key[4] = first->m_numSplitPoints;
00114
00115 std::pair<MapType::iterator, bool> result = m_children.insert(
00116 std::make_pair(key, VarSpanNode()));
00117 VarSpanNode &child = result.first->second;
00118 if (result.second) {
00119 child.m_parent = this;
00120 child.m_label = &(result.first->first);
00121 child.m_rank = m_rank + first->m_numSplitPoints + 1;
00122 }
00123 if (++first == last) {
00124 return child;
00125 }
00126 return child.Insert(first, last);
00127 }
00128 };
00129
00130 }