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 <cstddef>
   8 #include <cstdlib>
   9 #include <cstring>
  10 #include <cstdio>
  11 #include <cstdarg>
  12
  13 #include <stdexcept>
  14 #include <vector>
  15 #include <algorithm>
  16 #include <memory>
  17
  18 #include "Platform.h"
  19
  20 #include "Scintilla.h"
  21 #include "Position.h"
  22 #include "SplitVector.h"
  23 #include "Partitioning.h"
  24 #include "RunStyles.h"
  25
  26 #ifdef SCI_NAMESPACE
  27 using namespace Scintilla;
  28 #endif
  29
  30 // Find the first run at a position
  31 int RunStyles::RunFromPosition(int position) const {
  32         int run = starts->PartitionFromPosition(position);
  33         // Go to first element with this position
  34         while ((run > 0) && (position == starts->PositionFromPartition(run-1))) {
  35                 run--;
  36         }
  37         return run;
  38 }
  39
  40 // If there is no run boundary at position, insert one continuing style.
  41 int RunStyles::SplitRun(int position) {
  42         int run = RunFromPosition(position);
  43         const int posRun = starts->PositionFromPartition(run);
  44         if (posRun < position) {
  45                 int runStyle = ValueAt(position);
  46                 run++;
  47                 starts->InsertPartition(run, position);
  48                 styles->InsertValue(run, 1, runStyle);
  49         }
  50         return run;
  51 }
  52
  53 void RunStyles::RemoveRun(int run) {
  54         starts->RemovePartition(run);
  55         styles->DeleteRange(run, 1);
  56 }
  57
  58 void RunStyles::RemoveRunIfEmpty(int run) {
  59         if ((run < starts->Partitions()) && (starts->Partitions() > 1)) {
  60                 if (starts->PositionFromPartition(run) == starts->PositionFromPartition(run+1)) {
  61                         RemoveRun(run);
  62                 }
  63         }
  64 }
  65
  66 void RunStyles::RemoveRunIfSameAsPrevious(int run) {
  67         if ((run > 0) && (run < starts->Partitions())) {
  68                 if (styles->ValueAt(run-1) == styles->ValueAt(run)) {
  69                         RemoveRun(run);
  70                 }
  71         }
  72 }
  73
  74 RunStyles::RunStyles() {
  75         starts.reset(new Partitioning(8));
  76         styles.reset(new SplitVector<int>());
  77         styles->InsertValue(0, 2, 0);
  78 }
  79
  80 RunStyles::~RunStyles() {
  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         const int run = starts->PartitionFromPosition(position);
  93         if (run < starts->Partitions()) {
  94                 const int runChange = starts->PositionFromPartition(run);
  95                 if (runChange > position)
  96                         return runChange;
  97                 const 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         starts.reset(new Partitioning(8));
 202         styles.reset(new SplitVector<int>());
 203         styles->InsertValue(0, 2, 0);
 204 }
 205
 206 void RunStyles::DeleteRange(int position, int deleteLength) {
 207         int end = position + deleteLength;
 208         int runStart = RunFromPosition(position);
 209         int runEnd = RunFromPosition(end);
 210         if (runStart == runEnd) {
 211                 // Deleting from inside one run
 212                 starts->InsertText(runStart, -deleteLength);
 213                 RemoveRunIfEmpty(runStart);
 214         } else {
 215                 runStart = SplitRun(position);
 216                 runEnd = SplitRun(end);
 217                 starts->InsertText(runStart, -deleteLength);
 218                 // Remove each old run over the range
 219                 for (int run=runStart; run<runEnd; run++) {
 220                         RemoveRun(runStart);
 221                 }
 222                 RemoveRunIfEmpty(runStart);
 223                 RemoveRunIfSameAsPrevious(runStart);
 224         }
 225 }
 226
 227 int RunStyles::Runs() const {
 228         return starts->Partitions();
 229 }
 230
 231 bool RunStyles::AllSame() const {
 232         for (int run = 1; run < starts->Partitions(); run++) {
 233                 if (styles->ValueAt(run) != styles->ValueAt(run - 1))
 234                         return false;
 235         }
 236         return true;
 237 }
 238
 239 bool RunStyles::AllSameAs(int value) const {
 240         return AllSame() && (styles->ValueAt(0) == value);
 241 }
 242
 243 int RunStyles::Find(int value, int start) const {
 244         if (start < Length()) {
 245                 int run = start ? RunFromPosition(start) : 0;
 246                 if (styles->ValueAt(run) == value)
 247                         return start;
 248                 run++;
 249                 while (run < starts->Partitions()) {
 250                         if (styles->ValueAt(run) == value)
 251                                 return starts->PositionFromPartition(run);
 252                         run++;
 253                 }
 254         }
 255         return -1;
 256 }
 257
 258 void RunStyles::Check() const {
 259         if (Length() < 0) {
 260                 throw std::runtime_error("RunStyles: Length can not be negative.");
 261         }
 262         if (starts->Partitions() < 1) {
 263                 throw std::runtime_error("RunStyles: Must always have 1 or more partitions.");
 264         }
 265         if (starts->Partitions() != styles->Length()-1) {
 266                 throw std::runtime_error("RunStyles: Partitions and styles different lengths.");
 267         }
 268         int start=0;
 269         while (start < Length()) {
 270                 const int end = EndRun(start);
 271                 if (start >= end) {
 272                         throw std::runtime_error("RunStyles: Partition is 0 length.");
 273                 }
 274                 start = end;
 275         }
 276         if (styles->ValueAt(styles->Length()-1) != 0) {
 277                 throw std::runtime_error("RunStyles: Unused style at end changed.");
 278         }
 279         for (int j=1; j<styles->Length()-1; j++) {
 280                 if (styles->ValueAt(j) == styles->ValueAt(j-1)) {
 281                         throw std::runtime_error("RunStyles: Style of a partition same as previous.");
 282                 }
 283         }
 284 }