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