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