1 | // Scintilla source code edit control |
2 | /** @file Partitioning.h |
3 | ** Data structure used to partition an interval. Used for holding line start/end positions. |
4 | **/ |
5 | // Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org> |
6 | // The License.txt file describes the conditions under which this software may be distributed. |
7 | |
8 | #ifndef PARTITIONING_H |
9 | #define PARTITIONING_H |
10 | |
11 | namespace Scintilla::Internal { |
12 | |
13 | /// A split vector of integers with a method for adding a value to all elements |
14 | /// in a range. |
15 | /// Used by the Partitioning class. |
16 | |
17 | template <typename T> |
18 | class SplitVectorWithRangeAdd : public SplitVector<T> { |
19 | public: |
20 | explicit SplitVectorWithRangeAdd(ptrdiff_t growSize_) { |
21 | this->SetGrowSize(growSize_); |
22 | this->ReAllocate(growSize_); |
23 | } |
24 | // Deleted so SplitVectorWithRangeAdd objects can not be copied. |
25 | SplitVectorWithRangeAdd(const SplitVectorWithRangeAdd &) = delete; |
26 | SplitVectorWithRangeAdd(SplitVectorWithRangeAdd &&) = delete; |
27 | void operator=(const SplitVectorWithRangeAdd &) = delete; |
28 | void operator=(SplitVectorWithRangeAdd &&) = delete; |
29 | ~SplitVectorWithRangeAdd() { |
30 | } |
31 | void RangeAddDelta(ptrdiff_t start, ptrdiff_t end, T delta) noexcept { |
32 | // end is 1 past end, so end-start is number of elements to change |
33 | ptrdiff_t i = 0; |
34 | const ptrdiff_t rangeLength = end - start; |
35 | ptrdiff_t range1Length = rangeLength; |
36 | const ptrdiff_t part1Left = this->part1Length - start; |
37 | if (range1Length > part1Left) |
38 | range1Length = part1Left; |
39 | while (i < range1Length) { |
40 | this->body[start++] += delta; |
41 | i++; |
42 | } |
43 | start += this->gapLength; |
44 | while (i < rangeLength) { |
45 | this->body[start++] += delta; |
46 | i++; |
47 | } |
48 | } |
49 | }; |
50 | |
51 | /// Divide an interval into multiple partitions. |
52 | /// Useful for breaking a document down into sections such as lines. |
53 | /// A 0 length interval has a single 0 length partition, numbered 0 |
54 | /// If interval not 0 length then each partition non-zero length |
55 | /// When needed, positions after the interval are considered part of the last partition |
56 | /// but the end of the last partition can be found with PositionFromPartition(last+1). |
57 | |
58 | template <typename T> |
59 | class Partitioning { |
60 | private: |
61 | // To avoid calculating all the partition positions whenever any text is inserted |
62 | // there may be a step somewhere in the list. |
63 | T stepPartition; |
64 | T stepLength; |
65 | std::unique_ptr<SplitVectorWithRangeAdd<T>> body; |
66 | |
67 | // Move step forward |
68 | void ApplyStep(T partitionUpTo) noexcept { |
69 | if (stepLength != 0) { |
70 | body->RangeAddDelta(stepPartition+1, partitionUpTo + 1, stepLength); |
71 | } |
72 | stepPartition = partitionUpTo; |
73 | if (stepPartition >= body->Length()-1) { |
74 | stepPartition = Partitions(); |
75 | stepLength = 0; |
76 | } |
77 | } |
78 | |
79 | // Move step backward |
80 | void BackStep(T partitionDownTo) noexcept { |
81 | if (stepLength != 0) { |
82 | body->RangeAddDelta(partitionDownTo+1, stepPartition+1, -stepLength); |
83 | } |
84 | stepPartition = partitionDownTo; |
85 | } |
86 | |
87 | void Allocate(ptrdiff_t growSize) { |
88 | body = std::make_unique<SplitVectorWithRangeAdd<T>>(growSize); |
89 | stepPartition = 0; |
90 | stepLength = 0; |
91 | body->Insert(0, 0); // This value stays 0 for ever |
92 | body->Insert(1, 0); // This is the end of the first partition and will be the start of the second |
93 | } |
94 | |
95 | public: |
96 | explicit Partitioning(int growSize) : stepPartition(0), stepLength(0) { |
97 | Allocate(growSize); |
98 | } |
99 | |
100 | // Deleted so Partitioning objects can not be copied. |
101 | Partitioning(const Partitioning &) = delete; |
102 | Partitioning(Partitioning &&) = delete; |
103 | void operator=(const Partitioning &) = delete; |
104 | void operator=(Partitioning &&) = delete; |
105 | |
106 | ~Partitioning() { |
107 | } |
108 | |
109 | T Partitions() const noexcept { |
110 | return static_cast<T>(body->Length())-1; |
111 | } |
112 | |
113 | void ReAllocate(ptrdiff_t newSize) { |
114 | // + 1 accounts for initial element that is always 0. |
115 | body->ReAllocate(newSize + 1); |
116 | } |
117 | |
118 | T Length() const noexcept { |
119 | return PositionFromPartition(Partitions()); |
120 | } |
121 | |
122 | void InsertPartition(T partition, T pos) { |
123 | if (stepPartition < partition) { |
124 | ApplyStep(partition); |
125 | } |
126 | body->Insert(partition, pos); |
127 | stepPartition++; |
128 | } |
129 | |
130 | void InsertPartitions(T partition, const T *positions, size_t length) { |
131 | if (stepPartition < partition) { |
132 | ApplyStep(partition); |
133 | } |
134 | body->InsertFromArray(partition, positions, 0, length); |
135 | stepPartition += static_cast<T>(length); |
136 | } |
137 | |
138 | void InsertPartitionsWithCast(T partition, const ptrdiff_t *positions, size_t length) { |
139 | // Used for 64-bit builds when T is 32-bits |
140 | if (stepPartition < partition) { |
141 | ApplyStep(partition); |
142 | } |
143 | T *pInsertion = body->InsertEmpty(partition, length); |
144 | for (size_t i = 0; i < length; i++) { |
145 | pInsertion[i] = static_cast<T>(positions[i]); |
146 | } |
147 | stepPartition += static_cast<T>(length); |
148 | } |
149 | |
150 | void SetPartitionStartPosition(T partition, T pos) noexcept { |
151 | ApplyStep(partition+1); |
152 | if ((partition < 0) || (partition > body->Length())) { |
153 | return; |
154 | } |
155 | body->SetValueAt(partition, pos); |
156 | } |
157 | |
158 | void InsertText(T partitionInsert, T delta) noexcept { |
159 | // Point all the partitions after the insertion point further along in the buffer |
160 | if (stepLength != 0) { |
161 | if (partitionInsert >= stepPartition) { |
162 | // Fill in up to the new insertion point |
163 | ApplyStep(partitionInsert); |
164 | stepLength += delta; |
165 | } else if (partitionInsert >= (stepPartition - body->Length() / 10)) { |
166 | // Close to step but before so move step back |
167 | BackStep(partitionInsert); |
168 | stepLength += delta; |
169 | } else { |
170 | ApplyStep(Partitions()); |
171 | stepPartition = partitionInsert; |
172 | stepLength = delta; |
173 | } |
174 | } else { |
175 | stepPartition = partitionInsert; |
176 | stepLength = delta; |
177 | } |
178 | } |
179 | |
180 | void RemovePartition(T partition) { |
181 | if (partition > stepPartition) { |
182 | ApplyStep(partition); |
183 | stepPartition--; |
184 | } else { |
185 | stepPartition--; |
186 | } |
187 | body->Delete(partition); |
188 | } |
189 | |
190 | T PositionFromPartition(T partition) const noexcept { |
191 | PLATFORM_ASSERT(partition >= 0); |
192 | PLATFORM_ASSERT(partition < body->Length()); |
193 | const ptrdiff_t lengthBody = body->Length(); |
194 | if ((partition < 0) || (partition >= lengthBody)) { |
195 | return 0; |
196 | } |
197 | T pos = body->ValueAt(partition); |
198 | if (partition > stepPartition) |
199 | pos += stepLength; |
200 | return pos; |
201 | } |
202 | |
203 | /// Return value in range [0 .. Partitions() - 1] even for arguments outside interval |
204 | T PartitionFromPosition(T pos) const noexcept { |
205 | if (body->Length() <= 1) |
206 | return 0; |
207 | if (pos >= (PositionFromPartition(Partitions()))) |
208 | return Partitions() - 1; |
209 | T lower = 0; |
210 | T upper = Partitions(); |
211 | do { |
212 | const T middle = (upper + lower + 1) / 2; // Round high |
213 | T posMiddle = body->ValueAt(middle); |
214 | if (middle > stepPartition) |
215 | posMiddle += stepLength; |
216 | if (pos < posMiddle) { |
217 | upper = middle - 1; |
218 | } else { |
219 | lower = middle; |
220 | } |
221 | } while (lower < upper); |
222 | return lower; |
223 | } |
224 | |
225 | void DeleteAll() { |
226 | Allocate(body->GetGrowSize()); |
227 | } |
228 | |
229 | void Check() const { |
230 | #ifdef CHECK_CORRECTNESS |
231 | if (Length() < 0) { |
232 | throw std::runtime_error("Partitioning: Length can not be negative." ); |
233 | } |
234 | if (Partitions() < 1) { |
235 | throw std::runtime_error("Partitioning: Must always have 1 or more partitions." ); |
236 | } |
237 | if (Length() == 0) { |
238 | if ((PositionFromPartition(0) != 0) || (PositionFromPartition(1) != 0)) { |
239 | throw std::runtime_error("Partitioning: Invalid empty partitioning." ); |
240 | } |
241 | } else { |
242 | // Positions should be a strictly ascending sequence |
243 | for (T i = 0; i < Partitions(); i++) { |
244 | const T pos = PositionFromPartition(i); |
245 | const T posNext = PositionFromPartition(i+1); |
246 | if (pos > posNext) { |
247 | throw std::runtime_error("Partitioning: Negative partition." ); |
248 | } else if (pos == posNext) { |
249 | throw std::runtime_error("Partitioning: Empty partition." ); |
250 | } |
251 | } |
252 | } |
253 | #endif |
254 | } |
255 | |
256 | }; |
257 | |
258 | |
259 | } |
260 | |
261 | #endif |
262 | |