1 /** @file RunStyles.cxx
2 ** Data structure used to store sparse styles.
3 **/
4 // Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
5 // The License.txt file describes the conditions under which this software may be distributed.
6
7 #include <stdlib.h>
8 #include <string.h>
9 #include <stdio.h>
10 #include <stdarg.h>
11
12 #include <stdexcept>
13 #include <algorithm>
14
15 #include "Platform.h"
16
17 #include "Scintilla.h"
18 #include "SplitVector.h"
19 #include "Partitioning.h"
20 #include "RunStyles.h"
21
22 #ifdef SCI_NAMESPACE
23 using namespace Scintilla;
24 #endif
25
26 // Find the first run at a position
RunFromPosition(int position) const27 int RunStyles::RunFromPosition(int position) const {
28 int run = starts->PartitionFromPosition(position);
29 // Go to first element with this position
30 while ((run > 0) && (position == starts->PositionFromPartition(run-1))) {
31 run--;
32 }
33 return run;
34 }
35
36 // If there is no run boundary at position, insert one continuing style.
SplitRun(int position)37 int RunStyles::SplitRun(int position) {
38 int run = RunFromPosition(position);
39 int posRun = starts->PositionFromPartition(run);
40 if (posRun < position) {
41 int runStyle = ValueAt(position);
42 run++;
43 starts->InsertPartition(run, position);
44 styles->InsertValue(run, 1, runStyle);
45 }
46 return run;
47 }
48
RemoveRun(int run)49 void RunStyles::RemoveRun(int run) {
50 starts->RemovePartition(run);
51 styles->DeleteRange(run, 1);
52 }
53
RemoveRunIfEmpty(int run)54 void RunStyles::RemoveRunIfEmpty(int run) {
55 if ((run < starts->Partitions()) && (starts->Partitions() > 1)) {
56 if (starts->PositionFromPartition(run) == starts->PositionFromPartition(run+1)) {
57 RemoveRun(run);
58 }
59 }
60 }
61
RemoveRunIfSameAsPrevious(int run)62 void RunStyles::RemoveRunIfSameAsPrevious(int run) {
63 if ((run > 0) && (run < starts->Partitions())) {
64 if (styles->ValueAt(run-1) == styles->ValueAt(run)) {
65 RemoveRun(run);
66 }
67 }
68 }
69
RunStyles()70 RunStyles::RunStyles() {
71 starts = new Partitioning(8);
72 styles = new SplitVector<int>();
73 styles->InsertValue(0, 2, 0);
74 }
75
~RunStyles()76 RunStyles::~RunStyles() {
77 delete starts;
78 starts = NULL;
79 delete styles;
80 styles = NULL;
81 }
82
Length() const83 int RunStyles::Length() const {
84 return starts->PositionFromPartition(starts->Partitions());
85 }
86
ValueAt(int position) const87 int RunStyles::ValueAt(int position) const {
88 return styles->ValueAt(starts->PartitionFromPosition(position));
89 }
90
FindNextChange(int position,int end) const91 int RunStyles::FindNextChange(int position, int end) const {
92 int run = starts->PartitionFromPosition(position);
93 if (run < starts->Partitions()) {
94 int runChange = starts->PositionFromPartition(run);
95 if (runChange > position)
96 return runChange;
97 int nextChange = starts->PositionFromPartition(run + 1);
98 if (nextChange > position) {
99 return nextChange;
100 } else if (position < end) {
101 return end;
102 } else {
103 return end + 1;
104 }
105 } else {
106 return end + 1;
107 }
108 }
109
StartRun(int position) const110 int RunStyles::StartRun(int position) const {
111 return starts->PositionFromPartition(starts->PartitionFromPosition(position));
112 }
113
EndRun(int position) const114 int RunStyles::EndRun(int position) const {
115 return starts->PositionFromPartition(starts->PartitionFromPosition(position) + 1);
116 }
117
FillRange(int & position,int value,int & fillLength)118 bool RunStyles::FillRange(int &position, int value, int &fillLength) {
119 if (fillLength <= 0) {
120 return false;
121 }
122 int end = position + fillLength;
123 if (end > Length()) {
124 return false;
125 }
126 int runEnd = RunFromPosition(end);
127 if (styles->ValueAt(runEnd) == value) {
128 // End already has value so trim range.
129 end = starts->PositionFromPartition(runEnd);
130 if (position >= end) {
131 // Whole range is already same as value so no action
132 return false;
133 }
134 fillLength = end - position;
135 } else {
136 runEnd = SplitRun(end);
137 }
138 int runStart = RunFromPosition(position);
139 if (styles->ValueAt(runStart) == value) {
140 // Start is in expected value so trim range.
141 runStart++;
142 position = starts->PositionFromPartition(runStart);
143 fillLength = end - position;
144 } else {
145 if (starts->PositionFromPartition(runStart) < position) {
146 runStart = SplitRun(position);
147 runEnd++;
148 }
149 }
150 if (runStart < runEnd) {
151 styles->SetValueAt(runStart, value);
152 // Remove each old run over the range
153 for (int run=runStart+1; run<runEnd; run++) {
154 RemoveRun(runStart+1);
155 }
156 runEnd = RunFromPosition(end);
157 RemoveRunIfSameAsPrevious(runEnd);
158 RemoveRunIfSameAsPrevious(runStart);
159 runEnd = RunFromPosition(end);
160 RemoveRunIfEmpty(runEnd);
161 return true;
162 } else {
163 return false;
164 }
165 }
166
SetValueAt(int position,int value)167 void RunStyles::SetValueAt(int position, int value) {
168 int len = 1;
169 FillRange(position, value, len);
170 }
171
InsertSpace(int position,int insertLength)172 void RunStyles::InsertSpace(int position, int insertLength) {
173 int runStart = RunFromPosition(position);
174 if (starts->PositionFromPartition(runStart) == position) {
175 int runStyle = ValueAt(position);
176 // Inserting at start of run so make previous longer
177 if (runStart == 0) {
178 // Inserting at start of document so ensure 0
179 if (runStyle) {
180 styles->SetValueAt(0, 0);
181 starts->InsertPartition(1, 0);
182 styles->InsertValue(1, 1, runStyle);
183 starts->InsertText(0, insertLength);
184 } else {
185 starts->InsertText(runStart, insertLength);
186 }
187 } else {
188 if (runStyle) {
189 starts->InsertText(runStart-1, insertLength);
190 } else {
191 // Insert at end of run so do not extend style
192 starts->InsertText(runStart, insertLength);
193 }
194 }
195 } else {
196 starts->InsertText(runStart, insertLength);
197 }
198 }
199
DeleteAll()200 void RunStyles::DeleteAll() {
201 delete starts;
202 starts = NULL;
203 delete styles;
204 styles = NULL;
205 starts = new Partitioning(8);
206 styles = new SplitVector<int>();
207 styles->InsertValue(0, 2, 0);
208 }
209
DeleteRange(int position,int deleteLength)210 void RunStyles::DeleteRange(int position, int deleteLength) {
211 int end = position + deleteLength;
212 int runStart = RunFromPosition(position);
213 int runEnd = RunFromPosition(end);
214 if (runStart == runEnd) {
215 // Deleting from inside one run
216 starts->InsertText(runStart, -deleteLength);
217 RemoveRunIfEmpty(runStart);
218 } else {
219 runStart = SplitRun(position);
220 runEnd = SplitRun(end);
221 starts->InsertText(runStart, -deleteLength);
222 // Remove each old run over the range
223 for (int run=runStart; run<runEnd; run++) {
224 RemoveRun(runStart);
225 }
226 RemoveRunIfEmpty(runStart);
227 RemoveRunIfSameAsPrevious(runStart);
228 }
229 }
230
Runs() const231 int RunStyles::Runs() const {
232 return starts->Partitions();
233 }
234
AllSame() const235 bool RunStyles::AllSame() const {
236 for (int run = 1; run < starts->Partitions(); run++) {
237 if (styles->ValueAt(run) != styles->ValueAt(run - 1))
238 return false;
239 }
240 return true;
241 }
242
AllSameAs(int value) const243 bool RunStyles::AllSameAs(int value) const {
244 return AllSame() && (styles->ValueAt(0) == value);
245 }
246
Find(int value,int start) const247 int RunStyles::Find(int value, int start) const {
248 if (start < Length()) {
249 int run = start ? RunFromPosition(start) : 0;
250 if (styles->ValueAt(run) == value)
251 return start;
252 run++;
253 while (run < starts->Partitions()) {
254 if (styles->ValueAt(run) == value)
255 return starts->PositionFromPartition(run);
256 run++;
257 }
258 }
259 return -1;
260 }
261
Check() const262 void RunStyles::Check() const {
263 if (Length() < 0) {
264 throw std::runtime_error("RunStyles: Length can not be negative.");
265 }
266 if (starts->Partitions() < 1) {
267 throw std::runtime_error("RunStyles: Must always have 1 or more partitions.");
268 }
269 if (starts->Partitions() != styles->Length()-1) {
270 throw std::runtime_error("RunStyles: Partitions and styles different lengths.");
271 }
272 int start=0;
273 while (start < Length()) {
274 int end = EndRun(start);
275 if (start >= end) {
276 throw std::runtime_error("RunStyles: Partition is 0 length.");
277 }
278 start = end;
279 }
280 if (styles->ValueAt(styles->Length()-1) != 0) {
281 throw std::runtime_error("RunStyles: Unused style at end changed.");
282 }
283 for (int j=1; j<styles->Length()-1; j++) {
284 if (styles->ValueAt(j) == styles->ValueAt(j-1)) {
285 throw std::runtime_error("RunStyles: Style of a partition same as previous.");
286 }
287 }
288 }
289