| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * Copyright 2012 Google Inc. | |
| 3 * | |
| 4 * Use of this source code is governed by a BSD-style license that can be | |
| 5 * found in the LICENSE file. | |
| 6 */ | |
| 7 | |
| 8 #ifndef SkTSet_DEFINED | |
| 9 #define SkTSet_DEFINED | |
| 10 | |
| 11 #include "SkTSort.h" | |
| 12 #include "SkTDArray.h" | |
| 13 #include "SkTypes.h" | |
| 14 | |
| 15 /** \class SkTSet<T> | |
| 16 | |
| 17 The SkTSet template class defines a set. Elements are additionally | |
| 18 guaranteed to be sorted by their insertion order. | |
| 19 Main operations supported now are: add, merge, find and contains. | |
| 20 | |
| 21 TSet<T> is mutable. | |
| 22 */ | |
| 23 | |
| 24 // TODO: Add remove, intersect and difference operations. | |
| 25 // TODO: Add bench tests. | |
| 26 template <typename T> class SkTSet { | |
| 27 public: | |
| 28 SkTSet() { | |
| 29 fSetArray = SkNEW(SkTDArray<T>); | |
| 30 fOrderedArray = SkNEW(SkTDArray<T>); | |
| 31 } | |
| 32 | |
| 33 ~SkTSet() { | |
| 34 SkASSERT(fSetArray); | |
| 35 SkDELETE(fSetArray); | |
| 36 SkASSERT(fOrderedArray); | |
| 37 SkDELETE(fOrderedArray); | |
| 38 } | |
| 39 | |
| 40 SkTSet(const SkTSet<T>& src) { | |
| 41 this->fSetArray = SkNEW_ARGS(SkTDArray<T>, (*src.fSetArray)); | |
| 42 this->fOrderedArray = SkNEW_ARGS(SkTDArray<T>, (*src.fOrderedArray)); | |
| 43 #ifdef SK_DEBUG | |
| 44 validate(); | |
| 45 #endif | |
| 46 } | |
| 47 | |
| 48 SkTSet<T>& operator=(const SkTSet<T>& src) { | |
| 49 *this->fSetArray = *src.fSetArray; | |
| 50 *this->fOrderedArray = *src.fOrderedArray; | |
| 51 #ifdef SK_DEBUG | |
| 52 validate(); | |
| 53 #endif | |
| 54 return *this; | |
| 55 } | |
| 56 | |
| 57 /** Merges src elements into this, and returns the number of duplicates | |
| 58 * found. Elements from src will retain their ordering and will be ordered | |
| 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 */ | |
| 66 int mergeInto(const SkTSet<T>& src) { | |
| 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. | |
| 78 int duplicates = 0; | |
| 79 | |
| 80 SkTDArray<T>* fArrayNew = new SkTDArray<T>(); | |
| 81 fArrayNew->setReserve(fOrderedArray->count()); | |
| 82 int i = 0; | |
| 83 int j = 0; | |
| 84 | |
| 85 while (i < fSetArray->count() && j < src.count()) { | |
| 86 if ((*fSetArray)[i] < (*src.fSetArray)[j]) { | |
| 87 fArrayNew->push((*fSetArray)[i]); | |
| 88 i++; | |
| 89 } else if ((*fSetArray)[i] > (*src.fSetArray)[j]) { | |
| 90 fArrayNew->push((*src.fSetArray)[j]); | |
| 91 j++; | |
| 92 } else { | |
| 93 duplicates++; | |
| 94 j++; // Skip one of the duplicates. | |
| 95 } | |
| 96 } | |
| 97 | |
| 98 while (i < fSetArray->count()) { | |
| 99 fArrayNew->push((*fSetArray)[i]); | |
| 100 i++; | |
| 101 } | |
| 102 | |
| 103 while (j < src.count()) { | |
| 104 fArrayNew->push((*src.fSetArray)[j]); | |
| 105 j++; | |
| 106 } | |
| 107 SkDELETE(fSetArray); | |
| 108 fSetArray = fArrayNew; | |
| 109 fArrayNew = NULL; | |
| 110 | |
| 111 #ifdef SK_DEBUG | |
| 112 validate(); | |
| 113 #endif | |
| 114 return duplicates; | |
| 115 } | |
| 116 | |
| 117 /** Adds a new element into set and returns false if the element is already | |
| 118 * in this set. | |
| 119 */ | |
| 120 bool add(const T& elem) { | |
| 121 SkASSERT(fSetArray); | |
| 122 SkASSERT(fOrderedArray); | |
| 123 | |
| 124 int pos = 0; | |
| 125 int i = find(elem, &pos); | |
| 126 if (i >= 0) { | |
| 127 return false; | |
| 128 } | |
| 129 *fSetArray->insert(pos) = elem; | |
| 130 fOrderedArray->push(elem); | |
| 131 #ifdef SK_DEBUG | |
| 132 validate(); | |
| 133 #endif | |
| 134 return true; | |
| 135 } | |
| 136 | |
| 137 /** Returns true if this set is empty. | |
| 138 */ | |
| 139 bool isEmpty() const { | |
| 140 SkASSERT(fOrderedArray); | |
| 141 SkASSERT(fSetArray); | |
| 142 SkASSERT(fSetArray->isEmpty() == fOrderedArray->isEmpty()); | |
| 143 return fOrderedArray->isEmpty(); | |
| 144 } | |
| 145 | |
| 146 /** Return the number of elements in the set. | |
| 147 */ | |
| 148 int count() const { | |
| 149 SkASSERT(fOrderedArray); | |
| 150 SkASSERT(fSetArray); | |
| 151 SkASSERT(fSetArray->count() == fOrderedArray->count()); | |
| 152 return fOrderedArray->count(); | |
| 153 } | |
| 154 | |
| 155 /** Return the number of bytes in the set: count * sizeof(T). | |
| 156 */ | |
| 157 size_t bytes() const { | |
| 158 SkASSERT(fOrderedArray); | |
| 159 return fOrderedArray->bytes(); | |
| 160 } | |
| 161 | |
| 162 /** Return the beginning of a set iterator. | |
| 163 * Elements in the iterator will be sorted ascending. | |
| 164 */ | |
| 165 const T* begin() const { | |
| 166 SkASSERT(fOrderedArray); | |
| 167 return fOrderedArray->begin(); | |
| 168 } | |
| 169 | |
| 170 /** Return the end of a set iterator. | |
| 171 */ | |
| 172 const T* end() const { | |
| 173 SkASSERT(fOrderedArray); | |
| 174 return fOrderedArray->end(); | |
| 175 } | |
| 176 | |
| 177 const T& operator[](int index) const { | |
| 178 SkASSERT(fOrderedArray); | |
| 179 return (*fOrderedArray)[index]; | |
| 180 } | |
| 181 | |
| 182 /** Resets the set (deletes memory and initiates an empty set). | |
| 183 */ | |
| 184 void reset() { | |
| 185 SkASSERT(fSetArray); | |
| 186 SkASSERT(fOrderedArray); | |
| 187 fSetArray->reset(); | |
| 188 fOrderedArray->reset(); | |
| 189 } | |
| 190 | |
| 191 /** Rewinds the set (preserves memory and initiates an empty set). | |
| 192 */ | |
| 193 void rewind() { | |
| 194 SkASSERT(fSetArray); | |
| 195 SkASSERT(fOrderedArray); | |
| 196 fSetArray->rewind(); | |
| 197 fOrderedArray->rewind(); | |
| 198 } | |
| 199 | |
| 200 /** Reserves memory for the set. | |
| 201 */ | |
| 202 void setReserve(int reserve) { | |
| 203 SkASSERT(fSetArray); | |
| 204 SkASSERT(fOrderedArray); | |
| 205 fSetArray->setReserve(reserve); | |
| 206 fOrderedArray->setReserve(reserve); | |
| 207 } | |
| 208 | |
| 209 /** Returns true if the array contains this element. | |
| 210 */ | |
| 211 bool contains(const T& elem) const { | |
| 212 SkASSERT(fSetArray); | |
| 213 return (this->find(elem) >= 0); | |
| 214 } | |
| 215 | |
| 216 /** Copies internal array to destination. | |
| 217 */ | |
| 218 void copy(T* dst) const { | |
| 219 SkASSERT(fOrderedArray); | |
| 220 fOrderedArray->copyRange(dst, 0, fOrderedArray->count()); | |
| 221 } | |
| 222 | |
| 223 /** Returns a const reference to the internal vector. | |
| 224 */ | |
| 225 const SkTDArray<T>& toArray() { | |
| 226 SkASSERT(fOrderedArray); | |
| 227 return *fOrderedArray; | |
| 228 } | |
| 229 | |
| 230 /** Unref all elements in the set. | |
| 231 */ | |
| 232 void unrefAll() { | |
| 233 SkASSERT(fSetArray); | |
| 234 SkASSERT(fOrderedArray); | |
| 235 fOrderedArray->unrefAll(); | |
| 236 // Also reset the other array, as SkTDArray::unrefAll does an | |
| 237 // implcit reset | |
| 238 fSetArray->reset(); | |
| 239 } | |
| 240 | |
| 241 /** safeUnref all elements in the set. | |
| 242 */ | |
| 243 void safeUnrefAll() { | |
| 244 SkASSERT(fSetArray); | |
| 245 SkASSERT(fOrderedArray); | |
| 246 fOrderedArray->safeUnrefAll(); | |
| 247 // Also reset the other array, as SkTDArray::safeUnrefAll does an | |
| 248 // implcit reset | |
| 249 fSetArray->reset(); | |
| 250 } | |
| 251 | |
| 252 #ifdef SK_DEBUG | |
| 253 void validate() const { | |
| 254 SkASSERT(fSetArray); | |
| 255 SkASSERT(fOrderedArray); | |
| 256 fSetArray->validate(); | |
| 257 fOrderedArray->validate(); | |
| 258 SkASSERT(isSorted() && !hasDuplicates() && arraysConsistent()); | |
| 259 } | |
| 260 | |
| 261 bool hasDuplicates() const { | |
| 262 for (int i = 0; i < fSetArray->count() - 1; ++i) { | |
| 263 if ((*fSetArray)[i] == (*fSetArray)[i + 1]) { | |
| 264 return true; | |
| 265 } | |
| 266 } | |
| 267 return false; | |
| 268 } | |
| 269 | |
| 270 bool isSorted() const { | |
| 271 for (int i = 0; i < fSetArray->count() - 1; ++i) { | |
| 272 // Use only < operator | |
| 273 if (!((*fSetArray)[i] < (*fSetArray)[i + 1])) { | |
| 274 return false; | |
| 275 } | |
| 276 } | |
| 277 return true; | |
| 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 int count = fOrderedArray->count(); | |
| 295 fOrderedArray->copyRange(sortedBase, 0, count); | |
| 296 | |
| 297 SkTQSort<T>(sortedBase, sortedBase + count - 1); | |
| 298 | |
| 299 for (int i = 0; i < count; ++i) { | |
| 300 if (sortedBase[i] != (*fSetArray)[i]) { | |
| 301 return false; | |
| 302 } | |
| 303 } | |
| 304 | |
| 305 return true; | |
| 306 } | |
| 307 #endif | |
| 308 | |
| 309 private: | |
| 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 } | |
| 354 }; | |
| 355 | |
| 356 #endif | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1038523004:
SkPDF SkPDFObject::addResources signature simplified (Closed)
Base URL: https://skia.googlesource.com/skia.git@master