10 #ifndef INCLUDED_SC_INC_FSTALGORITHM_HXX
11 #define INCLUDED_SC_INC_FSTALGORITHM_HXX
13 #include <mdds/flat_segment_tree.hpp>
18 template<
typename Key,
typename Span>
20 std::vector<Span>& rSpans,
21 typename mdds::flat_segment_tree<Key,bool>::const_iterator it,
22 typename mdds::flat_segment_tree<Key,bool>::const_iterator itEnd,
const Key* pStart )
24 Key nLastPos = it->first;
25 bool bLastVal = it->second;
26 for (++it; it != itEnd; ++it)
28 Key nThisPos = it->first;
29 bool bThisVal = it->second;
33 Key nIndex1 = nLastPos;
34 Key nIndex2 = nThisPos-1;
36 if (!pStart || *pStart < nIndex1)
37 rSpans.push_back(
Span(nIndex1, nIndex2));
38 else if (*pStart <= nIndex2)
39 rSpans.push_back(
Span(*pStart, nIndex2));
47 template<
typename Key,
typename Val,
typename Span>
49 std::vector<Span>& rSpans,
50 typename mdds::flat_segment_tree<Key,Val>::const_iterator it,
51 typename mdds::flat_segment_tree<Key,Val>::const_iterator itEnd )
53 Key nLastPos = it->first;
54 Val nLastVal = it->second;
55 for (++it; it != itEnd; ++it)
57 Key nThisPos = it->first;
58 Val nThisVal = it->second;
62 Key nIndex1 = nLastPos;
63 Key nIndex2 = nThisPos-1;
64 rSpans.push_back(
Span(nIndex1, nIndex2, nLastVal));
77 template<
typename Key,
typename Span>
78 std::vector<Span>
toSpanArray(
const mdds::flat_segment_tree<Key,bool>& rTree )
80 typedef mdds::flat_segment_tree<Key,bool> FstType;
82 std::vector<Span> aSpans;
84 typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end();
85 buildSpan<Key,Span>(aSpans, it, itEnd,
nullptr);
96 template<
typename Key,
typename Val,
typename Span>
99 typedef mdds::flat_segment_tree<Key,Val> FstType;
101 std::vector<Span> aSpans;
103 typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end();
104 buildSpanWithValue<Key,Val,Span>(aSpans, it, itEnd);
108 template<
typename Key,
typename Span>
109 std::vector<Span>
toSpanArray(
const mdds::flat_segment_tree<Key,bool>& rTree,
Key nStartPos )
111 typedef mdds::flat_segment_tree<Key,bool> FstType;
113 std::vector<Span> aSpans;
114 if (!rTree.is_tree_valid())
117 bool bThisVal =
false;
118 std::pair<typename FstType::const_iterator, bool> r =
119 rTree.search_tree(nStartPos, bThisVal);
125 typename FstType::const_iterator it = r.first, itEnd = rTree.end();
126 buildSpan<Key,Span>(aSpans, it, itEnd, &nStartPos);
void buildSpanWithValue(std::vector< Span > &rSpans, typename mdds::flat_segment_tree< Key, Val >::const_iterator it, typename mdds::flat_segment_tree< Key, Val >::const_iterator itEnd)
void buildSpan(std::vector< Span > &rSpans, typename mdds::flat_segment_tree< Key, bool >::const_iterator it, typename mdds::flat_segment_tree< Key, bool >::const_iterator itEnd, const Key *pStart)
std::vector< Span > toSpanArray(const mdds::flat_segment_tree< Key, bool > &rTree)
Convert a flat_segment_tree structure whose value type is boolean, into an array of ranges that corre...
std::vector< Span > toSpanArrayWithValue(const mdds::flat_segment_tree< Key, Val > &rTree)
Convert a flat_segment_tree structure into an array of ranges with values.