1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/*
* This file is part of the LibreOffice project.
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
*/
#pragma once
#include <mdds/flat_segment_tree.hpp>
#include <vector>
namespace sc {
template<typename Key, typename Span>
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 )
{
Key nLastPos = it->first;
bool bLastVal = it->second;
for (++it; it != itEnd; ++it)
{
Key nThisPos = it->first;
bool bThisVal = it->second;
if (bLastVal)
{
Key nIndex1 = nLastPos;
Key nIndex2 = nThisPos-1;
if (!pStart || *pStart < nIndex1)
rSpans.push_back(Span(nIndex1, nIndex2));
else if (*pStart <= nIndex2)
rSpans.push_back(Span(*pStart, nIndex2));
}
nLastPos = nThisPos;
bLastVal = bThisVal;
}
}
template<typename Key, typename Val, typename Span>
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 )
{
Key nLastPos = it->first;
Val nLastVal = it->second;
for (++it; it != itEnd; ++it)
{
Key nThisPos = it->first;
Val nThisVal = it->second;
if (nLastVal)
{
Key nIndex1 = nLastPos;
Key nIndex2 = nThisPos-1;
rSpans.push_back(Span(nIndex1, nIndex2, nLastVal));
}
nLastPos = nThisPos;
nLastVal = nThisVal;
}
}
/**
* Convert a flat_segment_tree structure whose value type is boolean, into
* an array of ranges that corresponds with the segments that have a 'true'
* value.
*/
template<typename Key, typename Span>
std::vector<Span> toSpanArray( const mdds::flat_segment_tree<Key,bool>& rTree )
{
typedef mdds::flat_segment_tree<Key,bool> FstType;
std::vector<Span> aSpans;
typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end();
buildSpan<Key,Span>(aSpans, it, itEnd, nullptr);
return aSpans;
}
/**
* Convert a flat_segment_tree structure into an array of ranges with
* values. Only those ranges whose value is evaluated to be true will be
* included. The value type must be something that supports bool operator.
* The span type must support a constructor that takes a start key, an end
* key and a value in this order.
*/
template<typename Key, typename Val, typename Span>
std::vector<Span> toSpanArrayWithValue( const mdds::flat_segment_tree<Key,Val>& rTree )
{
typedef mdds::flat_segment_tree<Key,Val> FstType;
std::vector<Span> aSpans;
typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end();
buildSpanWithValue<Key,Val,Span>(aSpans, it, itEnd);
return aSpans;
}
template<typename Key, typename Span>
std::vector<Span> toSpanArray( const mdds::flat_segment_tree<Key,bool>& rTree, Key nStartPos )
{
typedef mdds::flat_segment_tree<Key,bool> FstType;
std::vector<Span> aSpans;
if (!rTree.is_tree_valid())
return aSpans;
bool bThisVal = false;
std::pair<typename FstType::const_iterator, bool> r =
rTree.search_tree(nStartPos, bThisVal);
if (!r.second)
// Tree search failed.
return aSpans;
typename FstType::const_iterator it = r.first, itEnd = rTree.end();
buildSpan<Key,Span>(aSpans, it, itEnd, &nStartPos);
return aSpans;
}
}
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
