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