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
11namespace 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
17template <typename T>
18class SplitVectorWithRangeAdd : public SplitVector<T> {
19public:
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
58template <typename T>
59class Partitioning {
60private:
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
95public:
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