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