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 | 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 | } |
28 | public: |
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 | |