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 
15 namespace sc {
16 
17 template<typename Key, typename Span>
18 void buildSpan(
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 
46 template<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 
76 template<typename Key, typename Span>
77 std::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 
95 template<typename Key, typename Val, typename Span>
96 std::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 
107 template<typename Key, typename Span>
108 std::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: */
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.
struct _ADOKey Key