ext/scintilla/src/RunStyles.cxx

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