ext/scintilla/src/Partitioning.h

   1 // Scintilla source code edit control
   2 /** @file Partitioning.h
   3  ** Data structure used to partition an interval. Used for holding line start/end positions.
   4  **/
   5 // Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
   6 // The License.txt file describes the conditions under which this software may be distributed.
   7
   8 #ifndef PARTITIONING_H
   9 #define PARTITIONING_H
  10
  11 /// A split vector of integers with a method for adding a value to all elements
  12 /// in a range.
  13 /// Used by the Partitioning class.
  14
  15 class SplitVectorWithRangeAdd : public SplitVector<int> {
  16 public:
  17         SplitVectorWithRangeAdd(int growSize_) {
  18                 SetGrowSize(growSize_);
  19                 ReAllocate(growSize_);
  20         }
  21         ~SplitVectorWithRangeAdd() {
  22         }
  23         void RangeAddDelta(int start, int end, int delta) {
  24                 // end is 1 past end, so end-start is number of elements to change
  25                 int i = 0;
  26                 int rangeLength = end - start;
  27                 int range1Length = rangeLength;
  28                 int part1Left = part1Length - start;
  29                 if (range1Length > part1Left)
  30                         range1Length = part1Left;
  31                 while (i < range1Length) {
  32                         body[start++] += delta;
  33                         i++;
  34                 }
  35                 start += gapLength;
  36                 while (i < rangeLength) {
  37                         body[start++] += delta;
  38                         i++;
  39                 }
  40         }
  41 };
  42
  43 /// Divide an interval into multiple partitions.
  44 /// Useful for breaking a document down into sections such as lines.
  45 /// A 0 length interval has a single 0 length partition, numbered 0
  46 /// If interval not 0 length then each partition non-zero length
  47 /// When needed, positions after the interval are considered part of the last partition
  48 /// but the end of the last partition can be found with PositionFromPartition(last+1).
  49
  50 class Partitioning {
  51 private:
  52         // To avoid calculating all the partition positions whenever any text is inserted
  53         // there may be a step somewhere in the list.
  54         int stepPartition;
  55         int stepLength;
  56         SplitVectorWithRangeAdd *body;
  57
  58         // Move step forward
  59         void ApplyStep(int partitionUpTo) {
  60                 if (stepLength != 0) {
  61                         body->RangeAddDelta(stepPartition+1, partitionUpTo + 1, stepLength);
  62                 }
  63                 stepPartition = partitionUpTo;
  64                 if (stepPartition >= body->Length()-1) {
  65                         stepPartition = body->Length()-1;
  66                         stepLength = 0;
  67                 }
  68         }
  69
  70         // Move step backward
  71         void BackStep(int partitionDownTo) {
  72                 if (stepLength != 0) {
  73                         body->RangeAddDelta(partitionDownTo+1, stepPartition+1, -stepLength);
  74                 }
  75                 stepPartition = partitionDownTo;
  76         }
  77
  78         void Allocate(int growSize) {
  79                 body = new SplitVectorWithRangeAdd(growSize);
  80                 stepPartition = 0;
  81                 stepLength = 0;
  82                 body->Insert(0, 0);     // This value stays 0 for ever
  83                 body->Insert(1, 0);     // This is the end of the first partition and will be the start of the second
  84         }
  85
  86 public:
  87         Partitioning(int growSize) {
  88                 Allocate(growSize);
  89         }
  90
  91         ~Partitioning() {
  92                 delete body;
  93                 body = 0;
  94         }
  95
  96         int Partitions() const {
  97                 return body->Length()-1;
  98         }
  99
 100         void InsertPartition(int partition, int pos) {
 101                 if (stepPartition < partition) {
 102                         ApplyStep(partition);
 103                 }
 104                 body->Insert(partition, pos);
 105                 stepPartition++;
 106         }
 107
 108         void SetPartitionStartPosition(int partition, int pos) {
 109                 ApplyStep(partition+1);
 110                 if ((partition < 0) || (partition > body->Length())) {
 111                         return;
 112                 }
 113                 body->SetValueAt(partition, pos);
 114         }
 115
 116         void InsertText(int partitionInsert, int delta) {
 117                 // Point all the partitions after the insertion point further along in the buffer
 118                 if (stepLength != 0) {
 119                         if (partitionInsert >= stepPartition) {
 120                                 // Fill in up to the new insertion point
 121                                 ApplyStep(partitionInsert);
 122                                 stepLength += delta;
 123                         } else if (partitionInsert >= (stepPartition - body->Length() / 10)) {
 124                                 // Close to step but before so move step back
 125                                 BackStep(partitionInsert);
 126                                 stepLength += delta;
 127                         } else {
 128                                 ApplyStep(body->Length()-1);
 129                                 stepPartition = partitionInsert;
 130                                 stepLength = delta;
 131                         }
 132                 } else {
 133                         stepPartition = partitionInsert;
 134                         stepLength = delta;
 135                 }
 136         }
 137
 138         void RemovePartition(int partition) {
 139                 if (partition > stepPartition) {
 140                         ApplyStep(partition);
 141                         stepPartition--;
 142                 } else {
 143                         stepPartition--;
 144                 }
 145                 body->Delete(partition);
 146         }
 147
 148         int PositionFromPartition(int partition) const {
 149                 PLATFORM_ASSERT(partition >= 0);
 150                 PLATFORM_ASSERT(partition < body->Length());
 151                 if ((partition < 0) || (partition >= body->Length())) {
 152                         return 0;
 153                 }
 154                 int pos = body->ValueAt(partition);
 155                 if (partition > stepPartition)
 156                         pos += stepLength;
 157                 return pos;
 158         }
 159
 160         /// Return value in range [0 .. Partitions() - 1] even for arguments outside interval
 161         int PartitionFromPosition(int pos) const {
 162                 if (body->Length() <= 1)
 163                         return 0;
 164                 if (pos >= (PositionFromPartition(body->Length()-1)))
 165                         return body->Length() - 1 - 1;
 166                 int lower = 0;
 167                 int upper = body->Length()-1;
 168                 do {
 169                         int middle = (upper + lower + 1) / 2;   // Round high
 170                         int posMiddle = body->ValueAt(middle);
 171                         if (middle > stepPartition)
 172                                 posMiddle += stepLength;
 173                         if (pos < posMiddle) {
 174                                 upper = middle - 1;
 175                         } else {
 176                                 lower = middle;
 177                         }
 178                 } while (lower < upper);
 179                 return lower;
 180         }
 181
 182         void DeleteAll() {
 183                 int growSize = body->GetGrowSize();
 184                 delete body;
 185                 Allocate(growSize);
 186         }
 187 };
 188
 189 #endif