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 {
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 template <typename T>
16 class SparseVector {
17 private:
18 	std::unique_ptr<Partitioning<Sci::Position>> starts;
19 	std::unique_ptr<SplitVector<T>> values;
20 	T empty;
ClearValue(Sci::Position partition)21 	void ClearValue(Sci::Position partition) {
22 		values->SetValueAt(partition, T());
23 	}
24 public:
SparseVector()25 	SparseVector() : empty() {
26 		starts = std::unique_ptr<Partitioning<Sci::Position>>(new Partitioning<Sci::Position>(8));
27 		values = std::unique_ptr<SplitVector<T>>(new SplitVector<T>());
28 		values->InsertEmpty(0, 2);
29 	}
30 	// Deleted so SparseVector objects can not be copied.
31 	SparseVector(const SparseVector &) = delete;
32 	SparseVector(SparseVector &&) = delete;
33 	void operator=(const SparseVector &) = delete;
34 	void operator=(SparseVector &&) = delete;
~SparseVector()35 	~SparseVector() {
36 		starts.reset();
37 		// starts dead here but not used by ClearValue.
38 		for (Sci::Position part = 0; part < values->Length(); part++) {
39 			ClearValue(part);
40 		}
41 		values.reset();
42 	}
Length()43 	Sci::Position Length() const {
44 		return starts->PositionFromPartition(starts->Partitions());
45 	}
Elements()46 	Sci::Position Elements() const {
47 		return starts->Partitions();
48 	}
PositionOfElement(int element)49 	Sci::Position PositionOfElement(int element) const {
50 		return starts->PositionFromPartition(element);
51 	}
ValueAt(Sci::Position position)52 	const T& ValueAt(Sci::Position position) const {
53 		assert(position < Length());
54 		const Sci::Position partition = starts->PartitionFromPosition(position);
55 		const Sci::Position 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(Sci::Position position,ParamType && value)63 	void SetValueAt(Sci::Position position, ParamType &&value) {
64 		assert(position < Length());
65 		const Sci::Position partition = starts->PartitionFromPosition(position);
66 		const Sci::Position 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::forward<ParamType>(value));
83 			} else {
84 				// Insert a new element
85 				starts->InsertPartition(partition + 1, position);
86 				values->Insert(partition + 1, std::forward<ParamType>(value));
87 			}
88 		}
89 	}
InsertSpace(Sci::Position position,Sci::Position insertLength)90 	void InsertSpace(Sci::Position position, Sci::Position insertLength) {
91 		assert(position <= Length());	// Only operation that works at end.
92 		const Sci::Position partition = starts->PartitionFromPosition(position);
93 		const Sci::Position 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(Sci::Position position)116 	void DeletePosition(Sci::Position position) {
117 		assert(position < Length());
118 		Sci::Position partition = starts->PartitionFromPosition(position);
119 		const Sci::Position 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 }
155 
156 #endif
157