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