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
11namespace 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.
19template <typename T>
20class SparseVector {
21private:
22 std::unique_ptr<Partitioning<Sci::Position>> starts;
23 std::unique_ptr<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 }
28public:
29 SparseVector() : empty() {
30 starts = std::make_unique<Partitioning<Sci::Position>>(8);
31 values = std::make_unique<SplitVector<T>>();
32 values->InsertEmpty(0, 2);
33 }
34 // Deleted so SparseVector objects can not be copied.
35 SparseVector(const SparseVector &) = delete;
36 SparseVector(SparseVector &&) = delete;
37 void operator=(const SparseVector &) = delete;
38 void operator=(SparseVector &&) = delete;
39 ~SparseVector() {
40 starts.reset();
41 // starts dead here but not used by ClearValue.
42 for (Sci::Position part = 0; part < values->Length(); part++) {
43 ClearValue(part);
44 }
45 values.reset();
46 }
47 Sci::Position Length() const noexcept {
48 return starts->Length();
49 }
50 Sci::Position Elements() const noexcept {
51 return starts->Partitions();
52 }
53 Sci::Position PositionOfElement(Sci::Position element) const noexcept {
54 return starts->PositionFromPartition(element);
55 }
56 Sci::Position ElementFromPosition(Sci::Position position) const noexcept {
57 if (position < Length()) {
58 return starts->PartitionFromPosition(position);
59 } else {
60 return starts->Partitions();
61 }
62 }
63 const T& ValueAt(Sci::Position position) const noexcept {
64 assert(position <= Length());
65 const Sci::Position partition = ElementFromPosition(position);
66 const Sci::Position startPartition = starts->PositionFromPartition(partition);
67 if (startPartition == position) {
68 return values->ValueAt(partition);
69 } else {
70 return empty;
71 }
72 }
73 template <typename ParamType>
74 void SetValueAt(Sci::Position position, ParamType &&value) {
75 assert(position <= Length());
76 const Sci::Position partition = ElementFromPosition(position);
77 const Sci::Position startPartition = starts->PositionFromPartition(partition);
78 if (value == T()) {
79 // Setting the empty value is equivalent to deleting the position
80 if (position == 0) {
81 ClearValue(partition);
82 } else if (position == startPartition) {
83 // Currently an element at this position, so remove
84 ClearValue(partition);
85 starts->RemovePartition(partition);
86 values->Delete(partition);
87 }
88 // Else element remains empty
89 } else {
90 if (position == startPartition) {
91 // Already a value at this position, so replace
92 ClearValue(partition);
93 values->SetValueAt(partition, std::forward<ParamType>(value));
94 } else {
95 // Insert a new element
96 starts->InsertPartition(partition + 1, position);
97 values->Insert(partition + 1, std::forward<ParamType>(value));
98 }
99 }
100 }
101 void InsertSpace(Sci::Position position, Sci::Position insertLength) {
102 assert(position <= Length());
103 const Sci::Position partition = starts->PartitionFromPosition(position);
104 const Sci::Position startPartition = starts->PositionFromPartition(partition);
105 if (startPartition == position) {
106 const bool positionOccupied = values->ValueAt(partition) != T();
107 // Inserting at start of run so make previous longer
108 if (partition == 0) {
109 // Inserting at start of document so ensure start empty
110 if (positionOccupied) {
111 starts->InsertPartition(1, 0);
112 values->InsertEmpty(0, 1);
113 }
114 starts->InsertText(partition, insertLength);
115 } else {
116 if (positionOccupied) {
117 starts->InsertText(partition - 1, insertLength);
118 } else {
119 // Insert at end of run so do not extend style
120 starts->InsertText(partition, insertLength);
121 }
122 }
123 } else {
124 starts->InsertText(partition, insertLength);
125 }
126 }
127 void DeletePosition(Sci::Position position) {
128 assert(position < Length());
129 Sci::Position partition = starts->PartitionFromPosition(position);
130 const Sci::Position startPartition = starts->PositionFromPartition(partition);
131 if (startPartition == position) {
132 if (partition == 0) {
133 ClearValue(0);
134 if (starts->PositionFromPartition(1) == 1) {
135 // Removing all space of first partition, so remove next partition
136 // and move value if not last
137 if (Elements() > 1) {
138 starts->RemovePartition(partition + 1);
139 values->Delete(partition);
140 }
141 }
142 } else if (partition == starts->Partitions()) {
143 // This should not be possible
144 ClearValue(partition);
145 throw std::runtime_error("SparseVector: deleting end partition.");
146 } else {
147 ClearValue(partition);
148 starts->RemovePartition(partition);
149 values->Delete(partition);
150 // Its the previous partition now that gets smaller
151 partition--;
152 }
153 }
154 starts->InsertText(partition, -1);
155 Check();
156 }
157 void DeleteRange(Sci::Position position, Sci::Position deleteLength) {
158 // For now, delete elements in range - may want to leave value at start
159 // or combine onto position.
160 if (position > Length() || (deleteLength == 0)) {
161 return;
162 }
163 const Sci::Position positionEnd = position + deleteLength;
164 assert(positionEnd <= Length());
165 if (position == 0) {
166 // Remove all partitions in range, moving values to start
167 while ((Elements() > 1) && (starts->PositionFromPartition(1) <= deleteLength)) {
168 starts->RemovePartition(1);
169 values->Delete(0);
170 }
171 starts->InsertText(0, -deleteLength);
172 if (Length() == 0) {
173 ClearValue(0);
174 }
175 } else {
176 const Sci::Position partition = starts->PartitionFromPosition(position);
177 const bool atPartitionStart = position == starts->PositionFromPartition(partition);
178 const Sci::Position partitionDelete = partition + (atPartitionStart ? 0 : 1);
179 assert(partitionDelete > 0);
180 for (;;) {
181 const Sci::Position positionAtIndex = starts->PositionFromPartition(partitionDelete);
182 assert(position <= positionAtIndex);
183 if (positionAtIndex >= positionEnd) {
184 break;
185 }
186 assert(partitionDelete <= Elements());
187 starts->RemovePartition(partitionDelete);
188 values->Delete(partitionDelete);
189 }
190 starts->InsertText(partition - (atPartitionStart ? 1 : 0), -deleteLength);
191 }
192 Check();
193 }
194 Sci::Position IndexAfter(Sci::Position position) const noexcept {
195 assert(position < Length());
196 if (position < 0)
197 return 0;
198 const Sci::Position partition = starts->PartitionFromPosition(position);
199 return partition + 1;
200 }
201 void Check() const {
202#ifdef CHECK_CORRECTNESS
203 starts->Check();
204 if (starts->Partitions() != values->Length() - 1) {
205 throw std::runtime_error("SparseVector: Partitions and values different lengths.");
206 }
207#endif
208 }
209};
210
211}
212
213#endif
214