svl/source/inc/items_helper.hxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4; fill-column: 100 -*- */
   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  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #pragma once
  21
  22 #include <sal/config.h>
  23
  24 #include <sal/types.h>
  25 #include <svl/itemset.hxx>
  26
  27 #include <memory>
  28 #include <utility>
  29 #include <vector>
  30
  31 namespace svl::detail
  32 {
  33 /**
  34  * Determines the number of sal_uInt16s in a 0-terminated array of pairs of
  35  * sal_uInt16s, each representing a range of sal_uInt16s, and total capacity of the ranges.
  36  * The terminating 0 is included in the count.
  37  */
  38 inline std::pair<sal_uInt16, sal_uInt16> CountRanges(const sal_uInt16* pRanges)
  39 {
  40     sal_uInt16 nCount = 0;
  41     sal_uInt16 nCapacity = 0;
  42     if (pRanges)
  43     {
  44         nCount = 1;
  45         while (*pRanges)
  46         {
  47             nCount += 2;
  48             nCapacity += rangeSize(pRanges[0], pRanges[1]);
  49             pRanges += 2;
  50         }
  51     }
  52     return { nCount, nCapacity };
  53 }
  54
  55 // Adds a range to which ranges, keeping the ranges in valid state (sorted, non-overlapping)
  56 inline std::unique_ptr<sal_uInt16[]> MergeRange(const sal_uInt16* pWhichRanges, sal_uInt16 nFrom,
  57                                                 sal_uInt16 nTo)
  58 {
  59     assert(validRange(nFrom, nTo));
  60
  61     if (!pWhichRanges)
  62     {
  63         auto pNewRanges = std::make_unique<sal_uInt16[]>(3);
  64         pNewRanges[0] = nFrom;
  65         pNewRanges[1] = nTo;
  66         pNewRanges[2] = 0;
  67         return pNewRanges;
  68     }
  69
  70     assert(validRanges(pWhichRanges));
  71
  72     // create vector of ranges (sal_uInt16 pairs of lower and upper bound)
  73     const size_t nOldCount = CountRanges(pWhichRanges).first;
  74     std::vector<std::pair<sal_uInt16, sal_uInt16>> aRangesTable;
  75     aRangesTable.reserve(nOldCount / 2 + 1);
  76     bool bAdded = false;
  77     for (size_t i = 0; i + 1 < nOldCount; i += 2)
  78     {
  79         if (!bAdded && pWhichRanges[i] >= nFrom)
  80         { // insert new range, keep ranges sorted
  81             aRangesTable.emplace_back(std::pair<sal_uInt16, sal_uInt16>(nFrom, nTo));
  82             bAdded = true;
  83         }
  84         // insert current range
  85         aRangesTable.emplace_back(
  86             std::pair<sal_uInt16, sal_uInt16>(pWhichRanges[i], pWhichRanges[i + 1]));
  87     }
  88     if (!bAdded)
  89         aRangesTable.emplace_back(std::pair<sal_uInt16, sal_uInt16>(nFrom, nTo));
  90
  91     // true if ranges overlap or adjoin, false if ranges are separate
  92     auto needMerge
  93         = [](std::pair<sal_uInt16, sal_uInt16> lhs, std::pair<sal_uInt16, sal_uInt16> rhs) {
  94               return (lhs.first - 1) <= rhs.second && (rhs.first - 1) <= lhs.second;
  95           };
  96
  97     auto it = aRangesTable.begin();
  98     // we got at least one range
  99     for (;;)
 100     {
 101         auto itNext = std::next(it);
 102         if (itNext == aRangesTable.end())
 103             break;
 104         // check neighbouring ranges, find first range which overlaps or adjoins a previous range
 105         if (needMerge(*it, *itNext))
 106         {
 107             // lower bounds are sorted, implies: it->first = min(it[0].first, it[1].first)
 108             it->second = std::max(it->second, itNext->second);
 109             aRangesTable.erase(itNext);
 110         }
 111         else
 112             ++it;
 113     }
 114
 115     // construct range array
 116     const size_t nNewSize = 2 * aRangesTable.size() + 1;
 117     auto pNewRanges = std::make_unique<sal_uInt16[]>(nNewSize);
 118     for (size_t i = 0; i < (nNewSize - 1); i += 2)
 119         std::tie(pNewRanges[i], pNewRanges[i + 1]) = aRangesTable[i / 2];
 120
 121     pNewRanges[nNewSize - 1] = 0;
 122     return pNewRanges;
 123 }
 124 }
 125
 126 /* vim:set shiftwidth=4 softtabstop=4 expandtab cinoptions=b1,g0,N-s cinkeys+=0=break: */