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
132
133
134
135
136
137
138
|
/* -*- 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/.
*/
#ifndef INCLUDED_SC_INC_FSTALGORITHM_HXX
#define INCLUDED_SC_INC_FSTALGORITHM_HXX
#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, const _Key* pStart )
{
_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;
if (!pStart || *pStart < nIndex1)
rSpans.push_back(_Span(nIndex1, nIndex2, nLastVal));
else if (*pStart <= nIndex2)
rSpans.push_back(_Span(*pStart, 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, NULL);
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, NULL);
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;
}
}
#endif
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
