From 940b4d1848e8c70ab7642901a68594e8016caffc Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 27 Apr 2024 18:51:28 +0200 Subject: Adding upstream version 1:7.0.4. Signed-off-by: Daniel Baumann --- sc/inc/fstalgorithm.hxx | 134 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 134 insertions(+) create mode 100644 sc/inc/fstalgorithm.hxx (limited to 'sc/inc/fstalgorithm.hxx') diff --git a/sc/inc/fstalgorithm.hxx b/sc/inc/fstalgorithm.hxx new file mode 100644 index 000000000..2a6ec14dd --- /dev/null +++ b/sc/inc/fstalgorithm.hxx @@ -0,0 +1,134 @@ +/* -*- 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 +#include + +namespace sc { + +template +void buildSpan( + std::vector& rSpans, + typename mdds::flat_segment_tree::const_iterator it, + typename mdds::flat_segment_tree::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 +void buildSpanWithValue( + std::vector& rSpans, + typename mdds::flat_segment_tree::const_iterator it, + typename mdds::flat_segment_tree::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 +std::vector toSpanArray( const mdds::flat_segment_tree& rTree ) +{ + typedef mdds::flat_segment_tree FstType; + + std::vector aSpans; + + typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end(); + buildSpan(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 +std::vector toSpanArrayWithValue( const mdds::flat_segment_tree& rTree ) +{ + typedef mdds::flat_segment_tree FstType; + + std::vector aSpans; + + typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end(); + buildSpanWithValue(aSpans, it, itEnd); + return aSpans; +} + +template +std::vector toSpanArray( const mdds::flat_segment_tree& rTree, Key nStartPos ) +{ + typedef mdds::flat_segment_tree FstType; + + std::vector aSpans; + if (!rTree.is_tree_valid()) + return aSpans; + + bool bThisVal = false; + std::pair 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(aSpans, it, itEnd, &nStartPos); + return aSpans; +} + +} + +#endif + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ -- cgit v1.2.3