1 // Scintilla source code edit control
2 /** @file SparseVector.h
3 ** Hold data sparsely associated with elements in a range.
5 // Copyright 2016 by Neil Hodgson <neilh@scintilla.org>
6 // The License.txt file describes the conditions under which this software may be distributed.
11 namespace Scintilla::Internal
{
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
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());
29 SparseVector() : empty() {
30 starts
= Partitioning
<Sci::Position
>(8);
31 values
= SplitVector
<T
>();
32 values
.InsertEmpty(0, 2);
34 Sci::Position
Length() const noexcept
{
35 return starts
.Length();
37 Sci::Position
Elements() const noexcept
{
38 return starts
.Partitions();
40 Sci::Position
PositionOfElement(Sci::Position element
) const noexcept
{
41 return starts
.PositionFromPartition(element
);
43 Sci::Position
ElementFromPosition(Sci::Position position
) const noexcept
{
44 if (position
< Length()) {
45 return starts
.PartitionFromPosition(position
);
47 return starts
.Partitions();
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
);
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
);
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
);
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
);
91 // Else element remains empty
93 if (position
== startPartition
) {
94 // Already a value at this position, so replace
95 ClearValue(partition
);
96 values
.SetValueAt(partition
, std::forward
<ParamType
>(value
));
98 // Insert a new element
99 starts
.InsertPartition(partition
+ 1, position
);
100 values
.Insert(partition
+ 1, std::forward
<ParamType
>(value
));
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);
117 starts
.InsertText(partition
, insertLength
);
119 if (positionOccupied
) {
120 starts
.InsertText(partition
- 1, insertLength
);
122 // Insert at end of run so do not extend style
123 starts
.InsertText(partition
, insertLength
);
127 starts
.InsertText(partition
, insertLength
);
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) {
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
);
145 } else if (partition
== starts
.Partitions()) {
146 // This should not be possible
147 ClearValue(partition
);
148 throw std::runtime_error("SparseVector: deleting end partition.");
150 ClearValue(partition
);
151 starts
.RemovePartition(partition
);
152 values
.Delete(partition
);
153 // Its the previous partition now that gets smaller
157 starts
.InsertText(partition
, -1);
161 starts
= Partitioning
<Sci::Position
>(8);
162 values
= SplitVector
<T
>();
163 values
.InsertEmpty(0, 2);
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)) {
171 const Sci::Position positionEnd
= position
+ deleteLength
;
172 assert(positionEnd
<= Length());
174 // Remove all partitions in range, moving values to start
175 while ((Elements() > 1) && (starts
.PositionFromPartition(1) <= deleteLength
)) {
176 starts
.RemovePartition(1);
179 starts
.InsertText(0, -deleteLength
);
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);
189 const Sci::Position positionAtIndex
= starts
.PositionFromPartition(partitionDelete
);
190 assert(position
<= positionAtIndex
);
191 if (positionAtIndex
>= positionEnd
) {
194 assert(partitionDelete
<= Elements());
195 starts
.RemovePartition(partitionDelete
);
196 values
.Delete(partitionDelete
);
198 starts
.InsertText(partition
- (atPartitionStart
? 1 : 0), -deleteLength
);
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);
207 return Length() + 1; // Out of bounds to terminate
209 Sci::Position
IndexAfter(Sci::Position position
) const noexcept
{
210 assert(position
< Length());
213 const Sci::Position partition
= starts
.PartitionFromPosition(position
);
214 return partition
+ 1;
217 #ifdef CHECK_CORRECTNESS
219 if (starts
.Partitions() != values
.Length() - 1) {
220 throw std::runtime_error("SparseVector: Partitions and values different lengths.");