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 "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
  27 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.
  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
  49 void RunStyles::RemoveRun(int run) {
  50         starts->RemovePartition(run);
  51         styles->DeleteRange(run, 1);
  52 }
  53
  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
  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
  70 RunStyles::RunStyles() {
  71         starts = new Partitioning(8);
  72         styles = new SplitVector<int>();
  73         styles->InsertValue(0, 2, 0);
  74 }
  75
  76 RunStyles::~RunStyles() {
  77         delete starts;
  78         starts = NULL;
  79         delete styles;
  80         styles = NULL;
  81 }
  82
  83 int RunStyles::Length() const {
  84         return starts->PositionFromPartition(starts->Partitions());
  85 }
  86
  87 int RunStyles::ValueAt(int position) const {
  88         return styles->ValueAt(starts->PartitionFromPosition(position));
  89 }
  90
  91 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
 110 int RunStyles::StartRun(int position) const {
 111         return starts->PositionFromPartition(starts->PartitionFromPosition(position));
 112 }
 113
 114 int RunStyles::EndRun(int position) const {
 115         return starts->PositionFromPartition(starts->PartitionFromPosition(position) + 1);
 116 }
 117
 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
 167 void RunStyles::SetValueAt(int position, int value) {
 168         int len = 1;
 169         FillRange(position, value, len);
 170 }
 171
 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
 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
 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
 231 int RunStyles::Runs() const {
 232         return starts->Partitions();
 233 }
 234
 235 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
 243 bool RunStyles::AllSameAs(int value) const {
 244         return AllSame() && (styles->ValueAt(0) == value);
 245 }
 246
 247 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
 262 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 }