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 {
  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 template <typename T>
  16 class SparseVector {
  17 private:
  18         std::unique_ptr<Partitioning<int>> starts;
  19         std::unique_ptr<SplitVector<T>> values;
  20         T empty;
  21         // Deleted so SparseVector objects can not be copied.
  22         SparseVector(const SparseVector &) = delete;
  23         void operator=(const SparseVector &) = delete;
  24         void ClearValue(int partition) {
  25                 values->SetValueAt(partition, T());
  26         }
  27 public:
  28         SparseVector() : empty() {
  29                 starts.reset(new Partitioning<int>(8));
  30                 values.reset(new SplitVector<T>());
  31                 values->InsertEmpty(0, 2);
  32         }
  33         ~SparseVector() {
  34                 starts.reset();
  35                 // starts dead here but not used by ClearValue.
  36                 for (int part = 0; part < values->Length(); part++) {
  37                         ClearValue(part);
  38                 }
  39                 values.reset();
  40         }
  41         int Length() const {
  42                 return starts->PositionFromPartition(starts->Partitions());
  43         }
  44         int Elements() const {
  45                 return starts->Partitions();
  46         }
  47         int PositionOfElement(int element) const {
  48                 return starts->PositionFromPartition(element);
  49         }
  50         const T& ValueAt(int position) const {
  51                 assert(position < Length());
  52                 const int partition = starts->PartitionFromPosition(position);
  53                 const int startPartition = starts->PositionFromPartition(partition);
  54                 if (startPartition == position) {
  55                         return values->ValueAt(partition);
  56                 } else {
  57                         return empty;
  58                 }
  59         }
  60         template <typename ParamType>
  61         void SetValueAt(int position, ParamType &&value) {
  62                 assert(position < Length());
  63                 const int partition = starts->PartitionFromPosition(position);
  64                 const int startPartition = starts->PositionFromPartition(partition);
  65                 if (value == T()) {
  66                         // Setting the empty value is equivalent to deleting the position
  67                         if (position == 0) {
  68                                 ClearValue(partition);
  69                         } else if (position == startPartition) {
  70                                 // Currently an element at this position, so remove
  71                                 ClearValue(partition);
  72                                 starts->RemovePartition(partition);
  73                                 values->Delete(partition);
  74                         }
  75                         // Else element remains empty
  76                 } else {
  77                         if (position == startPartition) {
  78                                 // Already a value at this position, so replace
  79                                 ClearValue(partition);
  80                                 values->SetValueAt(partition, std::move(value));
  81                         } else {
  82                                 // Insert a new element
  83                                 starts->InsertPartition(partition + 1, position);
  84                                 values->Insert(partition + 1, std::move(value));
  85                         }
  86                 }
  87         }
  88         void InsertSpace(int position, int insertLength) {
  89                 assert(position <= Length());   // Only operation that works at end.
  90                 const int partition = starts->PartitionFromPosition(position);
  91                 const int startPartition = starts->PositionFromPartition(partition);
  92                 if (startPartition == position) {
  93                         const bool positionOccupied = values->ValueAt(partition) != T();
  94                         // Inserting at start of run so make previous longer
  95                         if (partition == 0) {
  96                                 // Inserting at start of document so ensure start empty
  97                                 if (positionOccupied) {
  98                                         starts->InsertPartition(1, 0);
  99                                         values->InsertEmpty(0, 1);
 100                                 }
 101                                 starts->InsertText(partition, insertLength);
 102                         } else {
 103                                 if (positionOccupied) {
 104                                         starts->InsertText(partition - 1, insertLength);
 105                                 } else {
 106                                         // Insert at end of run so do not extend style
 107                                         starts->InsertText(partition, insertLength);
 108                                 }
 109                         }
 110                 } else {
 111                         starts->InsertText(partition, insertLength);
 112                 }
 113         }
 114         void DeletePosition(int position) {
 115                 assert(position < Length());
 116                 int partition = starts->PartitionFromPosition(position);
 117                 const int startPartition = starts->PositionFromPartition(partition);
 118                 if (startPartition == position) {
 119                         if (partition == 0) {
 120                                 ClearValue(0);
 121                         } else if (partition == starts->Partitions()) {
 122                                 // This should not be possible
 123                                 ClearValue(partition);
 124                                 throw std::runtime_error("SparseVector: deleting end partition.");
 125                         } else {
 126                                 ClearValue(partition);
 127                                 starts->RemovePartition(partition);
 128                                 values->Delete(partition);
 129                                 // Its the previous partition now that gets smaller
 130                                 partition--;
 131                         }
 132                 }
 133                 starts->InsertText(partition, -1);
 134         }
 135         void Check() const {
 136                 if (Length() < 0) {
 137                         throw std::runtime_error("SparseVector: Length can not be negative.");
 138                 }
 139                 if (starts->Partitions() < 1) {
 140                         throw std::runtime_error("SparseVector: Must always have 1 or more partitions.");
 141                 }
 142                 if (starts->Partitions() != values->Length() - 1) {
 143                         throw std::runtime_error("SparseVector: Partitions and values different lengths.");
 144                 }
 145                 // The final element can not be set
 146                 if (values->ValueAt(values->Length() - 1) != T()) {
 147                         throw std::runtime_error("SparseVector: Unused style at end changed.");
 148                 }
 149         }
 150 };
 151
 152 }
 153
 154 #endif