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 /// A split vector of integers with a method for adding a value to all elements
13 /// Used by the Partitioning class.
15 class SplitVectorWithRangeAdd
: public SplitVector
<int> {
17 SplitVectorWithRangeAdd(int growSize_
) {
18 SetGrowSize(growSize_
);
19 ReAllocate(growSize_
);
21 ~SplitVectorWithRangeAdd() {
23 void RangeAddDelta(int start
, int end
, int delta
) {
24 // end is 1 past end, so end-start is number of elements to change
26 int rangeLength
= end
- start
;
27 int range1Length
= rangeLength
;
28 int part1Left
= part1Length
- start
;
29 if (range1Length
> part1Left
)
30 range1Length
= part1Left
;
31 while (i
< range1Length
) {
32 body
[start
++] += delta
;
36 while (i
< rangeLength
) {
37 body
[start
++] += delta
;
43 /// Divide an interval into multiple partitions.
44 /// Useful for breaking a document down into sections such as lines.
45 /// A 0 length interval has a single 0 length partition, numbered 0
46 /// If interval not 0 length then each partition non-zero length
47 /// When needed, positions after the interval are considered part of the last partition
48 /// but the end of the last partition can be found with PositionFromPartition(last+1).
52 // To avoid calculating all the partition positions whenever any text is inserted
53 // there may be a step somewhere in the list.
56 SplitVectorWithRangeAdd
*body
;
59 void ApplyStep(int partitionUpTo
) {
60 if (stepLength
!= 0) {
61 body
->RangeAddDelta(stepPartition
+1, partitionUpTo
+ 1, stepLength
);
63 stepPartition
= partitionUpTo
;
64 if (stepPartition
>= body
->Length()-1) {
65 stepPartition
= body
->Length()-1;
71 void BackStep(int partitionDownTo
) {
72 if (stepLength
!= 0) {
73 body
->RangeAddDelta(partitionDownTo
+1, stepPartition
+1, -stepLength
);
75 stepPartition
= partitionDownTo
;
78 void Allocate(int growSize
) {
79 body
= new SplitVectorWithRangeAdd(growSize
);
82 body
->Insert(0, 0); // This value stays 0 for ever
83 body
->Insert(1, 0); // This is the end of the first partition and will be the start of the second
87 Partitioning(int growSize
) {
96 int Partitions() const {
97 return body
->Length()-1;
100 void InsertPartition(int partition
, int pos
) {
101 if (stepPartition
< partition
) {
102 ApplyStep(partition
);
104 body
->Insert(partition
, pos
);
108 void SetPartitionStartPosition(int partition
, int pos
) {
109 ApplyStep(partition
+1);
110 if ((partition
< 0) || (partition
> body
->Length())) {
113 body
->SetValueAt(partition
, pos
);
116 void InsertText(int partitionInsert
, int delta
) {
117 // Point all the partitions after the insertion point further along in the buffer
118 if (stepLength
!= 0) {
119 if (partitionInsert
>= stepPartition
) {
120 // Fill in up to the new insertion point
121 ApplyStep(partitionInsert
);
123 } else if (partitionInsert
>= (stepPartition
- body
->Length() / 10)) {
124 // Close to step but before so move step back
125 BackStep(partitionInsert
);
128 ApplyStep(body
->Length()-1);
129 stepPartition
= partitionInsert
;
133 stepPartition
= partitionInsert
;
138 void RemovePartition(int partition
) {
139 if (partition
> stepPartition
) {
140 ApplyStep(partition
);
145 body
->Delete(partition
);
148 int PositionFromPartition(int partition
) const {
149 PLATFORM_ASSERT(partition
>= 0);
150 PLATFORM_ASSERT(partition
< body
->Length());
151 if ((partition
< 0) || (partition
>= body
->Length())) {
154 int pos
= body
->ValueAt(partition
);
155 if (partition
> stepPartition
)
160 /// Return value in range [0 .. Partitions() - 1] even for arguments outside interval
161 int PartitionFromPosition(int pos
) const {
162 if (body
->Length() <= 1)
164 if (pos
>= (PositionFromPartition(body
->Length()-1)))
165 return body
->Length() - 1 - 1;
167 int upper
= body
->Length()-1;
169 int middle
= (upper
+ lower
+ 1) / 2; // Round high
170 int posMiddle
= body
->ValueAt(middle
);
171 if (middle
> stepPartition
)
172 posMiddle
+= stepLength
;
173 if (pos
< posMiddle
) {
178 } while (lower
< upper
);
183 int growSize
= body
->GetGrowSize();