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.
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.
11 namespace Scintilla::Internal
{
13 /// Divide an interval into multiple partitions.
14 /// Useful for breaking a document down into sections such as lines.
15 /// A 0 length interval has a single 0 length partition, numbered 0
16 /// If interval not 0 length then each partition non-zero length
17 /// When needed, positions after the interval are considered part of the last partition
18 /// but the end of the last partition can be found with PositionFromPartition(last+1).
23 // To avoid calculating all the partition positions whenever any text is inserted
24 // there may be a step somewhere in the list.
29 // Deleted so SplitVectorWithRangeAdd objects can not be copied.
30 void RangeAddDelta(T start
, T end
, T delta
) noexcept
{
31 // end is 1 past end, so end-start is number of elements to change
32 const ptrdiff_t position
= start
;
34 const ptrdiff_t rangeLength
= end
- position
;
35 ptrdiff_t range1Length
= rangeLength
;
36 const ptrdiff_t part1Left
= body
.GapPosition() - position
;
37 if (range1Length
> part1Left
)
38 range1Length
= part1Left
;
39 T
*writer
= &body
[position
];
40 while (i
< range1Length
) {
45 if (i
< rangeLength
) {
46 T
*writer2
= &body
[position
+ i
];
47 while (i
< rangeLength
) {
56 void ApplyStep(T partitionUpTo
) noexcept
{
57 if (stepLength
!= 0) {
58 RangeAddDelta(stepPartition
+1, partitionUpTo
+ 1, stepLength
);
60 stepPartition
= partitionUpTo
;
61 if (stepPartition
>= Partitions()) {
62 stepPartition
= Partitions();
68 void BackStep(T partitionDownTo
) noexcept
{
69 if (stepLength
!= 0) {
70 RangeAddDelta(partitionDownTo
+1, stepPartition
+1, -stepLength
);
72 stepPartition
= partitionDownTo
;
76 explicit Partitioning(size_t growSize
=8) : stepPartition(0), stepLength(0), body(growSize
) {
77 body
.Insert(0, 0); // This value stays 0 for ever
78 body
.Insert(1, 0); // This is the end of the first partition and will be the start of the second
81 T
Partitions() const noexcept
{
82 return static_cast<T
>(body
.Length())-1;
85 void ReAllocate(ptrdiff_t newSize
) {
86 // + 1 accounts for initial element that is always 0.
87 body
.ReAllocate(newSize
+ 1);
90 T
Length() const noexcept
{
91 return PositionFromPartition(Partitions());
94 void InsertPartition(T partition
, T pos
) {
95 if (stepPartition
< partition
) {
98 body
.Insert(partition
, pos
);
102 void InsertPartitions(T partition
, const T
*positions
, size_t length
) {
103 if (stepPartition
< partition
) {
104 ApplyStep(partition
);
106 body
.InsertFromArray(partition
, positions
, 0, length
);
107 stepPartition
+= static_cast<T
>(length
);
110 void InsertPartitionsWithCast(T partition
, const ptrdiff_t *positions
, size_t length
) {
111 // Used for 64-bit builds when T is 32-bits
112 if (stepPartition
< partition
) {
113 ApplyStep(partition
);
115 T
*pInsertion
= body
.InsertEmpty(partition
, length
);
116 for (size_t i
= 0; i
< length
; i
++) {
117 pInsertion
[i
] = static_cast<T
>(positions
[i
]);
119 stepPartition
+= static_cast<T
>(length
);
122 void SetPartitionStartPosition(T partition
, T pos
) noexcept
{
123 ApplyStep(partition
+1);
124 if ((partition
< 0) || (partition
>= body
.Length())) {
127 body
.SetValueAt(partition
, pos
);
130 void InsertText(T partitionInsert
, T delta
) noexcept
{
131 // Point all the partitions after the insertion point further along in the buffer
132 if (stepLength
!= 0) {
133 if (partitionInsert
>= stepPartition
) {
134 // Fill in up to the new insertion point
135 ApplyStep(partitionInsert
);
137 } else if (partitionInsert
>= (stepPartition
- body
.Length() / 10)) {
138 // Close to step but before so move step back
139 BackStep(partitionInsert
);
142 ApplyStep(Partitions());
143 stepPartition
= partitionInsert
;
147 stepPartition
= partitionInsert
;
152 void RemovePartition(T partition
) {
153 if (partition
> stepPartition
) {
154 ApplyStep(partition
);
159 body
.Delete(partition
);
162 T
PositionFromPartition(T partition
) const noexcept
{
163 PLATFORM_ASSERT(partition
>= 0);
164 PLATFORM_ASSERT(partition
< body
.Length());
165 const ptrdiff_t lengthBody
= body
.Length();
166 if ((partition
< 0) || (partition
>= lengthBody
)) {
169 T pos
= body
.ValueAt(partition
);
170 if (partition
> stepPartition
)
175 /// Return value in range [0 .. Partitions() - 1] even for arguments outside interval
176 T
PartitionFromPosition(T pos
) const noexcept
{
177 if (body
.Length() <= 1)
179 if (pos
>= (PositionFromPartition(Partitions())))
180 return Partitions() - 1;
182 T upper
= Partitions();
184 const T middle
= (upper
+ lower
+ 1) / 2; // Round high
185 T posMiddle
= body
.ValueAt(middle
);
186 if (middle
> stepPartition
)
187 posMiddle
+= stepLength
;
188 if (pos
< posMiddle
) {
193 } while (lower
< upper
);
201 body
.Insert(0, 0); // This value stays 0 for ever
202 body
.Insert(1, 0); // This is the end of the first partition and will be the start of the second
206 #ifdef CHECK_CORRECTNESS
208 throw std::runtime_error("Partitioning: Length can not be negative.");
210 if (Partitions() < 1) {
211 throw std::runtime_error("Partitioning: Must always have 1 or more partitions.");
214 if ((PositionFromPartition(0) != 0) || (PositionFromPartition(1) != 0)) {
215 throw std::runtime_error("Partitioning: Invalid empty partitioning.");
218 // Positions should be a strictly ascending sequence
219 for (T i
= 0; i
< Partitions(); i
++) {
220 const T pos
= PositionFromPartition(i
);
221 const T posNext
= PositionFromPartition(i
+1);
223 throw std::runtime_error("Partitioning: Negative partition.");
224 } else if (pos
== posNext
) {
225 throw std::runtime_error("Partitioning: Empty partition.");