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 */
CountRanges(const sal_uInt16 * pRanges)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)
MergeRange(const sal_uInt16 * pWhichRanges,sal_uInt16 nFrom,sal_uInt16 nTo)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: */
127