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