Skip to content
Newer
Older
100644 185 lines (165 sloc) 4.7 KB
f858c4b @djs Import Scintilla 2.11
authored
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 /// A split vector of integers with a method for adding a value to all elements
12 /// in a range.
13 /// Used by the Partitioning class.
14
15 class SplitVectorWithRangeAdd : public SplitVector<int> {
16 public:
17 SplitVectorWithRangeAdd(int growSize_) {
18 SetGrowSize(growSize_);
19 ReAllocate(growSize_);
20 }
21 ~SplitVectorWithRangeAdd() {
22 }
23 void RangeAddDelta(int start, int end, int delta) {
24 // end is 1 past end, so end-start is number of elements to change
25 int i = 0;
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;
33 i++;
34 }
35 start += gapLength;
36 while (i < rangeLength) {
37 body[start++] += delta;
38 i++;
39 }
40 }
41 };
42
43 /// Divide an interval into multiple partitions.
44 /// Useful for breaking a document down into sections such as lines.
45
46 class Partitioning {
47 private:
48 // To avoid calculating all the partition positions whenever any text is inserted
49 // there may be a step somewhere in the list.
50 int stepPartition;
51 int stepLength;
52 SplitVectorWithRangeAdd *body;
53
54 // Move step forward
55 void ApplyStep(int partitionUpTo) {
56 if (stepLength != 0) {
57 body->RangeAddDelta(stepPartition+1, partitionUpTo + 1, stepLength);
58 }
59 stepPartition = partitionUpTo;
60 if (stepPartition >= body->Length()-1) {
61 stepPartition = body->Length()-1;
62 stepLength = 0;
63 }
64 }
65
66 // Move step backward
67 void BackStep(int partitionDownTo) {
68 if (stepLength != 0) {
69 body->RangeAddDelta(partitionDownTo+1, stepPartition+1, -stepLength);
70 }
71 stepPartition = partitionDownTo;
72 }
73
74 void Allocate(int growSize) {
75 body = new SplitVectorWithRangeAdd(growSize);
76 stepPartition = 0;
77 stepLength = 0;
78 body->Insert(0, 0); // This value stays 0 for ever
79 body->Insert(1, 0); // This is the end of the first partition and will be the start of the second
80 }
81
82 public:
83 Partitioning(int growSize) {
84 Allocate(growSize);
85 }
86
87 ~Partitioning() {
88 delete body;
89 body = 0;
90 }
91
92 int Partitions() const {
93 return body->Length()-1;
94 }
95
96 void InsertPartition(int partition, int pos) {
97 if (stepPartition < partition) {
98 ApplyStep(partition);
99 }
100 body->Insert(partition, pos);
101 stepPartition++;
102 }
103
104 void SetPartitionStartPosition(int partition, int pos) {
105 ApplyStep(partition+1);
106 if ((partition < 0) || (partition > body->Length())) {
107 return;
108 }
109 body->SetValueAt(partition, pos);
110 }
111
112 void InsertText(int partitionInsert, int delta) {
113 // Point all the partitions after the insertion point further along in the buffer
114 if (stepLength != 0) {
115 if (partitionInsert >= stepPartition) {
116 // Fill in up to the new insertion point
117 ApplyStep(partitionInsert);
118 stepLength += delta;
119 } else if (partitionInsert >= (stepPartition - body->Length() / 10)) {
120 // Close to step but before so move step back
121 BackStep(partitionInsert);
122 stepLength += delta;
123 } else {
124 ApplyStep(body->Length()-1);
125 stepPartition = partitionInsert;
126 stepLength = delta;
127 }
128 } else {
129 stepPartition = partitionInsert;
130 stepLength = delta;
131 }
132 }
133
134 void RemovePartition(int partition) {
135 if (partition > stepPartition) {
136 ApplyStep(partition);
137 stepPartition--;
138 } else {
139 stepPartition--;
140 }
141 body->Delete(partition);
142 }
143
144 int PositionFromPartition(int partition) const {
145 PLATFORM_ASSERT(partition >= 0);
146 PLATFORM_ASSERT(partition < body->Length());
147 if ((partition < 0) || (partition >= body->Length())) {
148 return 0;
149 }
150 int pos = body->ValueAt(partition);
151 if (partition > stepPartition)
152 pos += stepLength;
153 return pos;
154 }
155
156 int PartitionFromPosition(int pos) const {
157 if (body->Length() <= 1)
158 return 0;
159 if (pos >= (PositionFromPartition(body->Length()-1)))
160 return body->Length() - 1 - 1;
161 int lower = 0;
162 int upper = body->Length()-1;
163 do {
164 int middle = (upper + lower + 1) / 2; // Round high
165 int posMiddle = body->ValueAt(middle);
166 if (middle > stepPartition)
167 posMiddle += stepLength;
168 if (pos < posMiddle) {
169 upper = middle - 1;
170 } else {
171 lower = middle;
172 }
173 } while (lower < upper);
174 return lower;
175 }
176
177 void DeleteAll() {
178 int growSize = body->GetGrowSize();
179 delete body;
180 Allocate(growSize);
181 }
182 };
183
184 #endif
Something went wrong with that request. Please try again.