Line data    Source code

       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             : #ifndef INCLUDED_SC_INC_FSTALGORITHM_HXX
      11             : #define INCLUDED_SC_INC_FSTALGORITHM_HXX
      12             : 
      13             : #include <mdds/flat_segment_tree.hpp>
      14             : #include <vector>
      15             : 
      16             : namespace sc {
      17             : 
      18             : template<typename _Key, typename _Span>
      19     1148124 : void buildSpan(
      20             :     std::vector<_Span>& rSpans,
      21             :     typename mdds::flat_segment_tree<_Key,bool>::const_iterator it,
      22             :     typename mdds::flat_segment_tree<_Key,bool>::const_iterator itEnd, const _Key* pStart )
      23             : {
      24     1148124 :     _Key nLastPos = it->first;
      25     1148124 :     bool bLastVal = it->second;
      26     2305857 :     for (++it; it != itEnd; ++it)
      27             :     {
      28     1157733 :         _Key nThisPos = it->first;
      29     1157733 :         bool bThisVal = it->second;
      30             : 
      31     1157733 :         if (bLastVal)
      32             :         {
      33        5825 :             _Key nIndex1 = nLastPos;
      34        5825 :             _Key nIndex2 = nThisPos-1;
      35             : 
      36        5825 :             if (!pStart || *pStart < nIndex1)
      37        5825 :                 rSpans.push_back(_Span(nIndex1, nIndex2));
      38           0 :             else if (*pStart <= nIndex2)
      39           0 :                 rSpans.push_back(_Span(*pStart, nIndex2));
      40             :         }
      41             : 
      42     1157733 :         nLastPos = nThisPos;
      43     1157733 :         bLastVal = bThisVal;
      44             :     }
      45     1148124 : }
      46             : 
      47             : template<typename _Key, typename _Val, typename _Span>
      48         113 : void buildSpanWithValue(
      49             :     std::vector<_Span>& rSpans,
      50             :     typename mdds::flat_segment_tree<_Key,_Val>::const_iterator it,
      51             :     typename mdds::flat_segment_tree<_Key,_Val>::const_iterator itEnd, const _Key* pStart )
      52             : {
      53         113 :     _Key nLastPos = it->first;
      54         113 :     _Val nLastVal = it->second;
      55         230 :     for (++it; it != itEnd; ++it)
      56             :     {
      57         117 :         _Key nThisPos = it->first;
      58         117 :         _Val nThisVal = it->second;
      59             : 
      60         117 :         if (nLastVal)
      61             :         {
      62           3 :             _Key nIndex1 = nLastPos;
      63           3 :             _Key nIndex2 = nThisPos-1;
      64             : 
      65           3 :             if (!pStart || *pStart < nIndex1)
      66           3 :                 rSpans.push_back(_Span(nIndex1, nIndex2, nLastVal));
      67           0 :             else if (*pStart <= nIndex2)
      68           0 :                 rSpans.push_back(_Span(*pStart, nIndex2, nLastVal));
      69             :         }
      70             : 
      71         117 :         nLastPos = nThisPos;
      72         117 :         nLastVal = nThisVal;
      73             :     }
      74         113 : }
      75             : 
      76             : /**
      77             :  * Convert a flat_segment_tree structure whose value type is boolean, into
      78             :  * an array of ranges that corresponds with the segments that have a 'true'
      79             :  * value.
      80             :  */
      81             : template<typename _Key, typename _Span>
      82     1148124 : std::vector<_Span> toSpanArray( const mdds::flat_segment_tree<_Key,bool>& rTree )
      83             : {
      84             :     typedef mdds::flat_segment_tree<_Key,bool> FstType;
      85             : 
      86     1148124 :     std::vector<_Span> aSpans;
      87             : 
      88     1148124 :     typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end();
      89     1148124 :     buildSpan<_Key,_Span>(aSpans, it, itEnd, NULL);
      90     1148124 :     return aSpans;
      91             : }
      92             : 
      93             : /**
      94             :  * Convert a flat_segment_tree structure into an array of ranges with
      95             :  * values.  Only those ranges whose value is evaluated to be true will be
      96             :  * included.  The value type must be something that supports bool operator.
      97             :  * The span type must support a constructor that takes a start key, an end
      98             :  * key and a value in this order.
      99             :  */
     100             : template<typename _Key, typename _Val, typename _Span>
     101         113 : std::vector<_Span> toSpanArrayWithValue( const mdds::flat_segment_tree<_Key,_Val>& rTree )
     102             : {
     103             :     typedef mdds::flat_segment_tree<_Key,_Val> FstType;
     104             : 
     105         113 :     std::vector<_Span> aSpans;
     106             : 
     107         113 :     typename FstType::const_iterator it = rTree.begin(), itEnd = rTree.end();
     108         113 :     buildSpanWithValue<_Key,_Val,_Span>(aSpans, it, itEnd, NULL);
     109         113 :     return aSpans;
     110             : }
     111             : 
     112             : template<typename _Key, typename _Span>
     113           0 : std::vector<_Span> toSpanArray( const mdds::flat_segment_tree<_Key,bool>& rTree, _Key nStartPos )
     114             : {
     115             :     typedef mdds::flat_segment_tree<_Key,bool> FstType;
     116             : 
     117           0 :     std::vector<_Span> aSpans;
     118           0 :     if (!rTree.is_tree_valid())
     119           0 :         return aSpans;
     120             : 
     121           0 :     bool bThisVal = false;
     122             :     std::pair<typename FstType::const_iterator, bool> r =
     123           0 :         rTree.search_tree(nStartPos, bThisVal);
     124             : 
     125           0 :     if (!r.second)
     126             :         // Tree search failed.
     127           0 :         return aSpans;
     128             : 
     129           0 :     typename FstType::const_iterator it = r.first, itEnd = rTree.end();
     130           0 :     buildSpan<_Key,_Span>(aSpans, it, itEnd, &nStartPos);
     131           0 :     return aSpans;
     132             : }
     133             : 
     134             : }
     135             : 
     136             : #endif
     137             : 
     138             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */