ext/scintilla/src/SparseVector.h

   1 // Scintilla source code edit control
   2 /** @file SparseVector.h
   3  ** Hold data sparsely associated with elements in a range.
   4  **/
   5 // Copyright 2016 by Neil Hodgson <neilh@scintilla.org>
   6 // The License.txt file describes the conditions under which this software may be distributed.
   7
   8 #ifndef SPARSEVECTOR_H
   9 #define SPARSEVECTOR_H
  10
  11 namespace Scintilla::Internal {
  12
  13 // SparseVector is similar to RunStyles but is more efficient for cases where values occur
  14 // for one position instead of over a range of positions.
  15 // There are always elements at the start and end, so the element type should have
  16 // a reasonable empty value that will cause no problems.
  17 // The element type should have a noexcept default constructor as that allows methods to
  18 // be noexcept.
  19 template <typename T>
  20 class SparseVector {
  21 private:
  22         Partitioning<Sci::Position> starts;
  23         SplitVector<T> values;
  24         T empty;        // Return from ValueAt when no element at a position.
  25         void ClearValue(Sci::Position partition) noexcept {
  26                 values.SetValueAt(partition, T());
  27         }
  28 public:
  29         SparseVector() : empty() {
  30                 starts = Partitioning<Sci::Position>(8);
  31                 values = SplitVector<T>();
  32                 values.InsertEmpty(0, 2);
  33         }
  34         Sci::Position Length() const noexcept {
  35                 return starts.Length();
  36         }
  37         Sci::Position Elements() const noexcept {
  38                 return starts.Partitions();
  39         }
  40         Sci::Position PositionOfElement(Sci::Position element) const noexcept {
  41                 return starts.PositionFromPartition(element);
  42         }
  43         Sci::Position ElementFromPosition(Sci::Position position) const noexcept {
  44                 if (position < Length()) {
  45                         return starts.PartitionFromPosition(position);
  46                 } else {
  47                         return starts.Partitions();
  48                 }
  49         }
  50         const T& ValueAt(Sci::Position position) const noexcept {
  51                 assert(position <= Length());
  52                 const Sci::Position partition = ElementFromPosition(position);
  53                 const Sci::Position startPartition = starts.PositionFromPartition(partition);
  54                 if (startPartition == position) {
  55                         return values.ValueAt(partition);
  56                 } else {
  57                         return empty;
  58                 }
  59         }
  60         T Extract(Sci::Position position) {
  61                 // Move value currently at position; clear and remove position; return value.
  62                 // Doesn't remove position at start or end.
  63                 assert(position <= Length());
  64                 const Sci::Position partition = ElementFromPosition(position);
  65                 assert(partition >= 0);
  66                 assert(partition <= starts.Partitions());
  67                 assert(starts.PositionFromPartition(partition) == position);
  68                 T value = std::move(values.operator[](partition));
  69                 if ((partition > 0) && (partition < starts.Partitions())) {
  70                         starts.RemovePartition(partition);
  71                         values.Delete(partition);
  72                 }
  73                 Check();
  74                 return value;
  75         }
  76         template <typename ParamType>
  77         void SetValueAt(Sci::Position position, ParamType &&value) {
  78                 assert(position <= Length());
  79                 const Sci::Position partition = ElementFromPosition(position);
  80                 const Sci::Position startPartition = starts.PositionFromPartition(partition);
  81                 if (value == T()) {
  82                         // Setting the empty value is equivalent to deleting the position
  83                         if (position == 0 || position == Length()) {
  84                                 ClearValue(partition);
  85                         } else if (position == startPartition) {
  86                                 // Currently an element at this position, so remove
  87                                 ClearValue(partition);
  88                                 starts.RemovePartition(partition);
  89                                 values.Delete(partition);
  90                         }
  91                         // Else element remains empty
  92                 } else {
  93                         if (position == startPartition) {
  94                                 // Already a value at this position, so replace
  95                                 ClearValue(partition);
  96                                 values.SetValueAt(partition, std::forward<ParamType>(value));
  97                         } else {
  98                                 // Insert a new element
  99                                 starts.InsertPartition(partition + 1, position);
 100                                 values.Insert(partition + 1, std::forward<ParamType>(value));
 101                         }
 102                 }
 103         }
 104         void InsertSpace(Sci::Position position, Sci::Position insertLength) {
 105                 assert(position <= Length());
 106                 const Sci::Position partition = starts.PartitionFromPosition(position);
 107                 const Sci::Position startPartition = starts.PositionFromPartition(partition);
 108                 if (startPartition == position) {
 109                         const bool positionOccupied = values.ValueAt(partition) != T();
 110                         // Inserting at start of run so make previous longer
 111                         if (partition == 0) {
 112                                 // Inserting at start of document so ensure start empty
 113                                 if (positionOccupied) {
 114                                         starts.InsertPartition(1, 0);
 115                                         values.InsertEmpty(0, 1);
 116                                 }
 117                                 starts.InsertText(partition, insertLength);
 118                         } else {
 119                                 if (positionOccupied) {
 120                                         starts.InsertText(partition - 1, insertLength);
 121                                 } else {
 122                                         // Insert at end of run so do not extend style
 123                                         starts.InsertText(partition, insertLength);
 124                                 }
 125                         }
 126                 } else {
 127                         starts.InsertText(partition, insertLength);
 128                 }
 129         }
 130         void DeletePosition(Sci::Position position) {
 131                 assert(position < Length());
 132                 Sci::Position partition = starts.PartitionFromPosition(position);
 133                 const Sci::Position startPartition = starts.PositionFromPartition(partition);
 134                 if (startPartition == position) {
 135                         if (partition == 0) {
 136                                 ClearValue(0);
 137                                 if (starts.PositionFromPartition(1) == 1) {
 138                                         // Removing all space of first partition, so remove next partition
 139                                         // and move value if not last
 140                                         if (Elements() > 1) {
 141                                                 starts.RemovePartition(partition + 1);
 142                                                 values.Delete(partition);
 143                                         }
 144                                 }
 145                         } else if (partition == starts.Partitions()) {
 146                                 // This should not be possible
 147                                 ClearValue(partition);
 148                                 throw std::runtime_error("SparseVector: deleting end partition.");
 149                         } else {
 150                                 ClearValue(partition);
 151                                 starts.RemovePartition(partition);
 152                                 values.Delete(partition);
 153                                 // Its the previous partition now that gets smaller
 154                                 partition--;
 155                         }
 156                 }
 157                 starts.InsertText(partition, -1);
 158                 Check();
 159         }
 160         void DeleteAll() {
 161                 starts = Partitioning<Sci::Position>(8);
 162                 values = SplitVector<T>();
 163                 values.InsertEmpty(0, 2);
 164         }
 165         void DeleteRange(Sci::Position position, Sci::Position deleteLength) {
 166                 // For now, delete elements in range - may want to leave value at start
 167                 // or combine onto position.
 168                 if (position > Length() || (deleteLength == 0)) {
 169                         return;
 170                 }
 171                 const Sci::Position positionEnd = position + deleteLength;
 172                 assert(positionEnd <= Length());
 173                 if (position == 0) {
 174                         // Remove all partitions in range, moving values to start
 175                         while ((Elements() > 1) && (starts.PositionFromPartition(1) <= deleteLength)) {
 176                                 starts.RemovePartition(1);
 177                                 values.Delete(0);
 178                         }
 179                         starts.InsertText(0, -deleteLength);
 180                         if (Length() == 0) {
 181                                 ClearValue(0);
 182                         }
 183                 } else {
 184                         const Sci::Position partition = starts.PartitionFromPosition(position);
 185                         const bool atPartitionStart = position == starts.PositionFromPartition(partition);
 186                         const Sci::Position partitionDelete = partition + (atPartitionStart ? 0 : 1);
 187                         assert(partitionDelete > 0);
 188                         for (;;) {
 189                                 const Sci::Position positionAtIndex = starts.PositionFromPartition(partitionDelete);
 190                                 assert(position <= positionAtIndex);
 191                                 if (positionAtIndex >= positionEnd) {
 192                                         break;
 193                                 }
 194                                 assert(partitionDelete <= Elements());
 195                                 starts.RemovePartition(partitionDelete);
 196                                 values.Delete(partitionDelete);
 197                         }
 198                         starts.InsertText(partition - (atPartitionStart ? 1 : 0), -deleteLength);
 199                 }
 200                 Check();
 201         }
 202         Sci::Position PositionNext(Sci::Position start) const noexcept {
 203                 const Sci::Position element = ElementFromPosition(start);
 204                 if (element < Elements()) {
 205                         return PositionOfElement(element + 1);
 206                 }
 207                 return Length() + 1;    // Out of bounds to terminate
 208         }
 209         Sci::Position IndexAfter(Sci::Position position) const noexcept {
 210                 assert(position < Length());
 211                 if (position < 0)
 212                         return 0;
 213                 const Sci::Position partition = starts.PartitionFromPosition(position);
 214                 return partition + 1;
 215         }
 216         void Check() const {
 217 #ifdef CHECK_CORRECTNESS
 218                 starts.Check();
 219                 if (starts.Partitions() != values.Length() - 1) {
 220                         throw std::runtime_error("SparseVector: Partitions and values different lengths.");
 221                 }
 222 #endif
 223         }
 224 };
 225
 226 }
 227
 228 #endif