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