scintilla/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
  46 class Partitioning {
  47 private:
  48         // To avoid calculating all the partition positions whenever any text is inserted
  49         // there may be a step somewhere in the list.
  50         int stepPartition;
  51         int stepLength;
  52         SplitVectorWithRangeAdd *body;
  53
  54         // Move step forward
  55         void ApplyStep(int partitionUpTo) {
  56                 if (stepLength != 0) {
  57                         body->RangeAddDelta(stepPartition+1, partitionUpTo + 1, stepLength);
  58                 }
  59                 stepPartition = partitionUpTo;
  60                 if (stepPartition >= body->Length()-1) {
  61                         stepPartition = body->Length()-1;
  62                         stepLength = 0;
  63                 }
  64         }
  65
  66         // Move step backward
  67         void BackStep(int partitionDownTo) {
  68                 if (stepLength != 0) {
  69                         body->RangeAddDelta(partitionDownTo+1, stepPartition+1, -stepLength);
  70                 }
  71                 stepPartition = partitionDownTo;
  72         }
  73
  74         void Allocate(int growSize) {
  75                 body = new SplitVectorWithRangeAdd(growSize);
  76                 stepPartition = 0;
  77                 stepLength = 0;
  78                 body->Insert(0, 0);     // This value stays 0 for ever
  79                 body->Insert(1, 0);     // This is the end of the first partition and will be the start of the second
  80         }
  81
  82 public:
  83         Partitioning(int growSize) {
  84                 Allocate(growSize);
  85         }
  86
  87         ~Partitioning() {
  88                 delete body;
  89                 body = 0;
  90         }
  91
  92         int Partitions() const {
  93                 return body->Length()-1;
  94         }
  95
  96         void InsertPartition(int partition, int pos) {
  97                 if (stepPartition < partition) {
  98                         ApplyStep(partition);
  99                 }
 100                 body->Insert(partition, pos);
 101                 stepPartition++;
 102         }
 103
 104         void SetPartitionStartPosition(int partition, int pos) {
 105                 ApplyStep(partition+1);
 106                 if ((partition < 0) || (partition > body->Length())) {
 107                         return;
 108                 }
 109                 body->SetValueAt(partition, pos);
 110         }
 111
 112         void InsertText(int partitionInsert, int delta) {
 113                 // Point all the partitions after the insertion point further along in the buffer
 114                 if (stepLength != 0) {
 115                         if (partitionInsert >= stepPartition) {
 116                                 // Fill in up to the new insertion point
 117                                 ApplyStep(partitionInsert);
 118                                 stepLength += delta;
 119                         } else if (partitionInsert >= (stepPartition - body->Length() / 10)) {
 120                                 // Close to step but before so move step back
 121                                 BackStep(partitionInsert);
 122                                 stepLength += delta;
 123                         } else {
 124                                 ApplyStep(body->Length()-1);
 125                                 stepPartition = partitionInsert;
 126                                 stepLength = delta;
 127                         }
 128                 } else {
 129                         stepPartition = partitionInsert;
 130                         stepLength = delta;
 131                 }
 132         }
 133
 134         void RemovePartition(int partition) {
 135                 if (partition > stepPartition) {
 136                         ApplyStep(partition);
 137                         stepPartition--;
 138                 } else {
 139                         stepPartition--;
 140                 }
 141                 body->Delete(partition);
 142         }
 143
 144         int PositionFromPartition(int partition) const {
 145                 PLATFORM_ASSERT(partition >= 0);
 146                 PLATFORM_ASSERT(partition < body->Length());
 147                 if ((partition < 0) || (partition >= body->Length())) {
 148                         return 0;
 149                 }
 150                 int pos = body->ValueAt(partition);
 151                 if (partition > stepPartition)
 152                         pos += stepLength;
 153                 return pos;
 154         }
 155
 156         int PartitionFromPosition(int pos) const {
 157                 if (body->Length() <= 1)
 158                         return 0;
 159                 if (pos >= (PositionFromPartition(body->Length()-1)))
 160                         return body->Length() - 1 - 1;
 161                 int lower = 0;
 162                 int upper = body->Length()-1;
 163                 do {
 164                         int middle = (upper + lower + 1) / 2;   // Round high
 165                         int posMiddle = body->ValueAt(middle);
 166                         if (middle > stepPartition)
 167                                 posMiddle += stepLength;
 168                         if (pos < posMiddle) {
 169                                 upper = middle - 1;
 170                         } else {
 171                                 lower = middle;
 172                         }
 173                 } while (lower < upper);
 174                 return lower;
 175         }
 176
 177         void DeleteAll() {
 178                 int growSize = body->GetGrowSize();
 179                 delete body;
 180                 Allocate(growSize);
 181         }
 182 };
 183
 184 #endif