OLD | NEW |
---|---|
1 /* | 1 /* |
2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #ifndef SkTSet_DEFINED | 8 #ifndef SkTSet_DEFINED |
9 #define SkTSet_DEFINED | 9 #define SkTSet_DEFINED |
10 | 10 |
11 #include "SkTSort.h" | |
11 #include "SkTDArray.h" | 12 #include "SkTDArray.h" |
12 #include "SkTypes.h" | 13 #include "SkTypes.h" |
13 | 14 |
14 /** \class SkTSet<T> | 15 /** \class SkTSet<T> |
15 | 16 |
16 The SkTSet template class defines a set. | 17 The SkTSet template class defines a set. Elements are additionally |
18 guaranteed to be sorted by their insertion order. | |
17 Main operations supported now are: add, merge, find and contains. | 19 Main operations supported now are: add, merge, find and contains. |
18 | 20 |
19 TSet<T> is mutable. | 21 TSet<T> is mutable. |
20 */ | 22 */ |
21 | 23 |
22 // TODO: Add remove, intersect and difference operations. | 24 // TODO: Add remove, intersect and difference operations. |
23 // TODO: Add bench tests. | 25 // TODO: Add bench tests. |
24 template <typename T> class SkTSet { | 26 template <typename T> class SkTSet { |
25 public: | 27 public: |
26 SkTSet() { | 28 SkTSet() { |
27 fArray = SkNEW(SkTDArray<T>); | 29 fSetArray = SkNEW(SkTDArray<T>); |
30 fOrderedArray = SkNEW(SkTDArray<T>); | |
28 } | 31 } |
29 | 32 |
30 ~SkTSet() { | 33 ~SkTSet() { |
31 SkASSERT(fArray); | 34 SkASSERT(fSetArray); |
32 SkDELETE(fArray); | 35 SkDELETE(fSetArray); |
36 SkASSERT(fOrderedArray); | |
37 SkDELETE(fOrderedArray); | |
33 } | 38 } |
34 | 39 |
35 SkTSet(const SkTSet<T>& src) { | 40 SkTSet(const SkTSet<T>& src) { |
36 this->fArray = SkNEW_ARGS(SkTDArray<T>, (*src.fArray)); | 41 this->fSetArray = SkNEW_ARGS(SkTDArray<T>, (*src.fSetArray)); |
42 this->fOrderedArray = SkNEW_ARGS(SkTDArray<T>, (*src.fOrderedArray)); | |
37 #ifdef SK_DEBUG | 43 #ifdef SK_DEBUG |
38 validate(); | 44 validate(); |
39 #endif | 45 #endif |
40 } | 46 } |
41 | 47 |
42 SkTSet<T>& operator=(const SkTSet<T>& src) { | 48 SkTSet<T>& operator=(const SkTSet<T>& src) { |
43 *this->fArray = *src.fArray; | 49 *this->fSetArray = *src.fSetArray; |
50 *this->fOrderedArray = *src.fOrderedArray; | |
44 #ifdef SK_DEBUG | 51 #ifdef SK_DEBUG |
45 validate(); | 52 validate(); |
46 #endif | 53 #endif |
47 return *this; | 54 return *this; |
48 } | 55 } |
49 | 56 |
50 /** Merges src elements into this, and returns the number of duplicates | 57 /** Merges src elements into this, and returns the number of duplicates |
51 * found. | 58 * found. Elements from src will retain their ordering and will be ordered |
52 */ | 59 * after the elements currently in this set. |
60 * | |
61 * Implementation note: this uses a 2-stage merge to obtain O(n log n) time. | |
62 * The first stage goes through src.fOrderedArray, checking if | |
63 * this->contains() is false before adding to this.fOrderedArray. | |
64 * The second stage does a standard sorted list merge on the fSetArrays. | |
65 */ | |
53 int mergeInto(const SkTSet<T>& src) { | 66 int mergeInto(const SkTSet<T>& src) { |
54 SkASSERT(fArray); | 67 SkASSERT(fSetArray); |
68 SkASSERT(fOrderedArray); | |
69 | |
70 // Do fOrderedArray merge. | |
71 for (int i = 0; i < src.count(); ++i) { | |
72 if (!contains((*src.fOrderedArray)[i])) { | |
73 fOrderedArray->push((*src.fOrderedArray)[i]); | |
74 } | |
75 } | |
76 | |
77 // Do fSetArray merge. | |
55 int duplicates = 0; | 78 int duplicates = 0; |
56 | 79 |
57 SkTDArray<T>* fArrayNew = new SkTDArray<T>(); | 80 SkTDArray<T>* fArrayNew = new SkTDArray<T>(); |
58 fArrayNew->setReserve(count() + src.count()); | 81 fArrayNew->setReserve(fOrderedArray->count()); |
59 int i = 0; | 82 int i = 0; |
60 int j = 0; | 83 int j = 0; |
61 | 84 |
62 while (i < count() && j < src.count()) { | 85 while (i < fSetArray->count() && j < src.count()) { |
63 if ((*fArray)[i] < (*src.fArray)[j]) { | 86 if ((*fSetArray)[i] < (*src.fSetArray)[j]) { |
64 fArrayNew->push((*fArray)[i]); | 87 fArrayNew->push((*fSetArray)[i]); |
65 i++; | 88 i++; |
66 } else if ((*fArray)[i] > (*src.fArray)[j]) { | 89 } else if ((*fSetArray)[i] > (*src.fSetArray)[j]) { |
67 fArrayNew->push((*src.fArray)[j]); | 90 fArrayNew->push((*src.fSetArray)[j]); |
68 j++; | 91 j++; |
69 } else { | 92 } else { |
70 duplicates++; | 93 duplicates++; |
71 j++; // Skip one of the duplicates. | 94 j++; // Skip one of the duplicates. |
72 } | 95 } |
73 } | 96 } |
74 | 97 |
75 while (i < count()) { | 98 while (i < fSetArray->count()) { |
76 fArrayNew->push((*fArray)[i]); | 99 fArrayNew->push((*fSetArray)[i]); |
77 i++; | 100 i++; |
78 } | 101 } |
79 | 102 |
80 while (j < src.count()) { | 103 while (j < src.count()) { |
81 fArrayNew->push((*src.fArray)[j]); | 104 fArrayNew->push((*src.fSetArray)[j]); |
82 j++; | 105 j++; |
83 } | 106 } |
84 SkDELETE(fArray); | 107 SkDELETE(fSetArray); |
85 fArray = fArrayNew; | 108 fSetArray = fArrayNew; |
86 fArrayNew = NULL; | 109 fArrayNew = NULL; |
87 | 110 |
88 #ifdef SK_DEBUG | 111 #ifdef SK_DEBUG |
89 validate(); | 112 validate(); |
90 #endif | 113 #endif |
91 return duplicates; | 114 return duplicates; |
92 } | 115 } |
93 | 116 |
94 /** Adds a new element into set and returns true if the element is already | 117 /** Adds a new element into set and returns false if the element is already |
95 * in this set. | 118 * in this set. |
96 */ | 119 */ |
97 bool add(const T& elem) { | 120 bool add(const T& elem) { |
98 SkASSERT(fArray); | 121 SkASSERT(fSetArray); |
122 SkASSERT(fOrderedArray); | |
99 | 123 |
100 int pos = 0; | 124 int pos = 0; |
101 int i = find(elem, &pos); | 125 int i = find(elem, &pos); |
102 if (i >= 0) { | 126 if (i >= 0) { |
103 return false; | 127 return false; |
104 } | 128 } |
105 *fArray->insert(pos) = elem; | 129 *fSetArray->insert(pos) = elem; |
130 fOrderedArray->push(elem); | |
106 #ifdef SK_DEBUG | 131 #ifdef SK_DEBUG |
107 validate(); | 132 validate(); |
108 #endif | 133 #endif |
109 return true; | 134 return true; |
110 } | 135 } |
111 | 136 |
112 /** Returns true if this set is empty. | 137 /** Returns true if this set is empty. |
113 */ | 138 */ |
114 bool isEmpty() const { | 139 bool isEmpty() const { |
115 SkASSERT(fArray); | 140 SkASSERT(fOrderedArray); |
116 return fArray->isEmpty(); | 141 SkASSERT(fSetArray); |
142 SkASSERT(fSetArray->isEmpty() == fOrderedArray->isEmpty()); | |
143 return fOrderedArray->isEmpty(); | |
117 } | 144 } |
118 | 145 |
119 /** Return the number of elements in the set. | 146 /** Return the number of elements in the set. |
120 */ | 147 */ |
121 int count() const { | 148 int count() const { |
122 SkASSERT(fArray); | 149 SkASSERT(fOrderedArray); |
123 return fArray->count(); | 150 SkASSERT(fSetArray); |
151 SkASSERT(fSetArray->count() == fOrderedArray->count()); | |
152 return fOrderedArray->count(); | |
124 } | 153 } |
125 | 154 |
126 /** Return the number of bytes in the set: count * sizeof(T). | 155 /** Return the number of bytes in the set: count * sizeof(T). |
127 */ | 156 */ |
128 size_t bytes() const { | 157 size_t bytes() const { |
edisonn
2013/07/17 20:03:28
if this function is not used anywhere, please remo
| |
129 SkASSERT(fArray); | 158 SkASSERT(fOrderedArray); |
130 return fArray->bytes(); | 159 return fOrderedArray->bytes(); |
131 } | 160 } |
132 | 161 |
133 /** Return the beginning of a set iterator. | 162 /** Return the beginning of a set iterator. |
134 * Elements in the iterator will be sorted ascending. | 163 * Elements in the iterator will be sorted ascending. |
135 */ | 164 */ |
136 const T* begin() const { | 165 const T* begin() const { |
137 SkASSERT(fArray); | 166 SkASSERT(fOrderedArray); |
138 return fArray->begin(); | 167 return fOrderedArray->begin(); |
139 } | 168 } |
140 | 169 |
141 /** Return the end of a set iterator. | 170 /** Return the end of a set iterator. |
142 */ | 171 */ |
143 const T* end() const { | 172 const T* end() const { |
144 SkASSERT(fArray); | 173 SkASSERT(fOrderedArray); |
145 return fArray->end(); | 174 return fOrderedArray->end(); |
146 } | 175 } |
147 | 176 |
148 const T& operator[](int index) const { | 177 const T& operator[](int index) const { |
149 SkASSERT(fArray); | 178 SkASSERT(fOrderedArray); |
150 return (*fArray)[index]; | 179 return (*fOrderedArray)[index]; |
151 } | 180 } |
152 | 181 |
153 /** Resets the set (deletes memory and initiates an empty set). | 182 /** Resets the set (deletes memory and initiates an empty set). |
154 */ | 183 */ |
155 void reset() { | 184 void reset() { |
156 SkASSERT(fArray); | 185 SkASSERT(fSetArray); |
157 fArray->reset(); | 186 SkASSERT(fOrderedArray); |
187 fSetArray->reset(); | |
188 fOrderedArray->reset(); | |
158 } | 189 } |
159 | 190 |
160 /** Rewinds the set (preserves memory and initiates an empty set). | 191 /** Rewinds the set (preserves memory and initiates an empty set). |
161 */ | 192 */ |
162 void rewind() { | 193 void rewind() { |
163 SkASSERT(fArray); | 194 SkASSERT(fSetArray); |
164 fArray->rewind(); | 195 SkASSERT(fOrderedArray); |
196 fSetArray->rewind(); | |
197 fOrderedArray->rewind(); | |
165 } | 198 } |
166 | 199 |
167 /** Reserves memory for the set. | 200 /** Reserves memory for the set. |
168 */ | 201 */ |
169 void setReserve(size_t reserve) { | 202 void setReserve(size_t reserve) { |
170 SkASSERT(fArray); | 203 SkASSERT(fSetArray); |
171 fArray->setReserve(reserve); | 204 SkASSERT(fOrderedArray); |
172 } | 205 fSetArray->setReserve(reserve); |
173 | 206 fOrderedArray->setReserve(reserve); |
174 /** Returns the index where an element was found. | |
175 * Returns -1 if the element was not found, and it fills *posToInsertSorted | |
176 * with the index of the place where elem should be inserted to preserve the | |
177 * internal array sorted. | |
178 * If element was found, *posToInsertSorted is undefined. | |
179 */ | |
180 int find(const T& elem, int* posToInsertSorted = NULL) const { | |
181 SkASSERT(fArray); | |
182 | |
183 if (fArray->count() == 0) { | |
184 if (posToInsertSorted) { | |
185 *posToInsertSorted = 0; | |
186 } | |
187 return -1; | |
188 } | |
189 int iMin = 0; | |
190 int iMax = fArray->count(); | |
191 | |
192 while (iMin < iMax - 1) { | |
193 int iMid = (iMin + iMax) / 2; | |
194 if (elem < (*fArray)[iMid]) { | |
195 iMax = iMid; | |
196 } else { | |
197 iMin = iMid; | |
198 } | |
199 } | |
200 if (elem == (*fArray)[iMin]) { | |
201 return iMin; | |
202 } | |
203 if (posToInsertSorted) { | |
204 if (elem < (*fArray)[iMin]) { | |
205 *posToInsertSorted = iMin; | |
206 } else { | |
207 *posToInsertSorted = iMin + 1; | |
208 } | |
209 } | |
210 | |
211 return -1; | |
212 } | 207 } |
213 | 208 |
214 /** Returns true if the array contains this element. | 209 /** Returns true if the array contains this element. |
215 */ | 210 */ |
216 bool contains(const T& elem) const { | 211 bool contains(const T& elem) const { |
217 SkASSERT(fArray); | 212 SkASSERT(fSetArray); |
218 return (this->find(elem) >= 0); | 213 return (this->find(elem) >= 0); |
219 } | 214 } |
220 | 215 |
221 /** Copies internal array to destination. | 216 /** Copies internal array to destination. |
222 */ | 217 */ |
223 void copy(T* dst) const { | 218 void copy(T* dst) const { |
224 SkASSERT(fArray); | 219 SkASSERT(fOrderedArray); |
225 fArray->copyRange(0, fArray->count(), dst); | 220 fOrderedArray->copyRange(dst, 0, fOrderedArray->count()); |
226 } | 221 } |
227 | 222 |
228 /** Returns a const reference to the internal vector. | 223 /** Returns a const reference to the internal vector. |
229 */ | 224 */ |
230 const SkTDArray<T>& toArray() { | 225 const SkTDArray<T>& toArray() { |
231 SkASSERT(fArray); | 226 SkASSERT(fOrderedArray); |
232 return *fArray; | 227 return *fOrderedArray; |
233 } | 228 } |
234 | 229 |
235 /** Unref all elements in the set. | 230 /** Unref all elements in the set. |
236 */ | 231 */ |
237 void unrefAll() { | 232 void unrefAll() { |
238 SkASSERT(fArray); | 233 SkASSERT(fSetArray); |
239 fArray->unrefAll(); | 234 SkASSERT(fOrderedArray); |
235 fOrderedArray->unrefAll(); | |
236 // Also reset the other array, as SkTDArray::unrefAll does an | |
237 // implcit reset | |
238 fSetArray->reset(); | |
240 } | 239 } |
241 | 240 |
242 /** safeUnref all elements in the set. | 241 /** safeUnref all elements in the set. |
243 */ | 242 */ |
244 void safeUnrefAll() { | 243 void safeUnrefAll() { |
245 SkASSERT(fArray); | 244 SkASSERT(fSetArray); |
246 fArray->safeUnrefAll(); | 245 SkASSERT(fOrderedArray); |
246 fOrderedArray->safeUnrefAll(); | |
247 // Also reset the other array, as SkTDArray::safeUnrefAll does an | |
248 // implcit reset | |
249 fSetArray->reset(); | |
247 } | 250 } |
248 | 251 |
249 #ifdef SK_DEBUG | 252 #ifdef SK_DEBUG |
250 void validate() const { | 253 void validate() const { |
251 SkASSERT(fArray); | 254 SkASSERT(fSetArray); |
252 fArray->validate(); | 255 SkASSERT(fOrderedArray); |
253 SkASSERT(isSorted() && !hasDuplicates()); | 256 fSetArray->validate(); |
257 fOrderedArray->validate(); | |
258 SkASSERT(isSorted() && !hasDuplicates() && arraysConsistent()); | |
254 } | 259 } |
255 | 260 |
256 bool hasDuplicates() const { | 261 bool hasDuplicates() const { |
257 for (int i = 0; i < fArray->count() - 1; ++i) { | 262 for (int i = 0; i < fSetArray->count() - 1; ++i) { |
258 if ((*fArray)[i] == (*fArray)[i + 1]) { | 263 if ((*fSetArray)[i] == (*fSetArray)[i + 1]) { |
259 return true; | 264 return true; |
260 } | 265 } |
261 } | 266 } |
262 return false; | 267 return false; |
263 } | 268 } |
264 | 269 |
265 bool isSorted() const { | 270 bool isSorted() const { |
266 for (int i = 0; i < fArray->count() - 1; ++i) { | 271 for (int i = 0; i < fSetArray->count() - 1; ++i) { |
267 // Use only < operator | 272 // Use only < operator |
268 if (!((*fArray)[i] < (*fArray)[i + 1])) { | 273 if (!((*fSetArray)[i] < (*fSetArray)[i + 1])) { |
269 return false; | 274 return false; |
270 } | 275 } |
271 } | 276 } |
272 return true; | 277 return true; |
273 } | 278 } |
279 | |
280 /** Checks if fSetArray is consistent with fOrderedArray | |
281 */ | |
282 bool arraysConsistent() const { | |
283 if (fSetArray->count() != fOrderedArray->count()) { | |
284 return false; | |
285 } | |
286 if (fOrderedArray->count() == 0) { | |
287 return true; | |
288 } | |
289 | |
290 // Copy and sort fOrderedArray, then compare to fSetArray. | |
291 // A O(n log n) algorithm is necessary as O(n^2) will choke some GMs. | |
292 SkAutoMalloc sortedArray(fOrderedArray->bytes()); | |
293 T* sortedBase = reinterpret_cast<T*>(sortedArray.get()); | |
294 size_t count = fOrderedArray->count(); | |
295 fOrderedArray->copyRange(sortedBase, 0, count); | |
296 | |
297 SkTQSort<T>(sortedBase, sortedBase + count - 1); | |
298 | |
299 for (size_t i = 0; i < count; ++i) { | |
300 if (sortedBase[i] != (*fSetArray)[i]) { | |
301 return false; | |
302 } | |
303 } | |
304 | |
305 return true; | |
306 } | |
274 #endif | 307 #endif |
275 | 308 |
276 private: | 309 private: |
277 SkTDArray<T>* fArray; | 310 SkTDArray<T>* fSetArray; // Sorted by pointer address for fast |
311 // lookup. | |
312 SkTDArray<T>* fOrderedArray; // Sorted by insertion order for | |
313 // deterministic output. | |
314 | |
315 /** Returns the index in fSetArray where an element was found. | |
316 * Returns -1 if the element was not found, and it fills *posToInsertSorted | |
317 * with the index of the place where elem should be inserted to preserve the | |
318 * internal array sorted. | |
319 * If element was found, *posToInsertSorted is undefined. | |
320 */ | |
321 int find(const T& elem, int* posToInsertSorted = NULL) const { | |
322 SkASSERT(fSetArray); | |
323 | |
324 if (fSetArray->count() == 0) { | |
325 if (posToInsertSorted) { | |
326 *posToInsertSorted = 0; | |
327 } | |
328 return -1; | |
329 } | |
330 int iMin = 0; | |
331 int iMax = fSetArray->count(); | |
332 | |
333 while (iMin < iMax - 1) { | |
334 int iMid = (iMin + iMax) / 2; | |
335 if (elem < (*fSetArray)[iMid]) { | |
336 iMax = iMid; | |
337 } else { | |
338 iMin = iMid; | |
339 } | |
340 } | |
341 if (elem == (*fSetArray)[iMin]) { | |
342 return iMin; | |
343 } | |
344 if (posToInsertSorted) { | |
345 if (elem < (*fSetArray)[iMin]) { | |
346 *posToInsertSorted = iMin; | |
347 } else { | |
348 *posToInsertSorted = iMin + 1; | |
349 } | |
350 } | |
351 | |
352 return -1; | |
353 } | |
278 }; | 354 }; |
279 | 355 |
280 #endif | 356 #endif |
OLD | NEW |