1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pdf/SkTSet.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,356 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#ifndef SkTSet_DEFINED
1.12 +#define SkTSet_DEFINED
1.13 +
1.14 +#include "SkTSort.h"
1.15 +#include "SkTDArray.h"
1.16 +#include "SkTypes.h"
1.17 +
1.18 +/** \class SkTSet<T>
1.19 +
1.20 + The SkTSet template class defines a set. Elements are additionally
1.21 + guaranteed to be sorted by their insertion order.
1.22 + Main operations supported now are: add, merge, find and contains.
1.23 +
1.24 + TSet<T> is mutable.
1.25 +*/
1.26 +
1.27 +// TODO: Add remove, intersect and difference operations.
1.28 +// TODO: Add bench tests.
1.29 +template <typename T> class SkTSet {
1.30 +public:
1.31 + SkTSet() {
1.32 + fSetArray = SkNEW(SkTDArray<T>);
1.33 + fOrderedArray = SkNEW(SkTDArray<T>);
1.34 + }
1.35 +
1.36 + ~SkTSet() {
1.37 + SkASSERT(fSetArray);
1.38 + SkDELETE(fSetArray);
1.39 + SkASSERT(fOrderedArray);
1.40 + SkDELETE(fOrderedArray);
1.41 + }
1.42 +
1.43 + SkTSet(const SkTSet<T>& src) {
1.44 + this->fSetArray = SkNEW_ARGS(SkTDArray<T>, (*src.fSetArray));
1.45 + this->fOrderedArray = SkNEW_ARGS(SkTDArray<T>, (*src.fOrderedArray));
1.46 +#ifdef SK_DEBUG
1.47 + validate();
1.48 +#endif
1.49 + }
1.50 +
1.51 + SkTSet<T>& operator=(const SkTSet<T>& src) {
1.52 + *this->fSetArray = *src.fSetArray;
1.53 + *this->fOrderedArray = *src.fOrderedArray;
1.54 +#ifdef SK_DEBUG
1.55 + validate();
1.56 +#endif
1.57 + return *this;
1.58 + }
1.59 +
1.60 + /** Merges src elements into this, and returns the number of duplicates
1.61 + * found. Elements from src will retain their ordering and will be ordered
1.62 + * after the elements currently in this set.
1.63 + *
1.64 + * Implementation note: this uses a 2-stage merge to obtain O(n log n) time.
1.65 + * The first stage goes through src.fOrderedArray, checking if
1.66 + * this->contains() is false before adding to this.fOrderedArray.
1.67 + * The second stage does a standard sorted list merge on the fSetArrays.
1.68 + */
1.69 + int mergeInto(const SkTSet<T>& src) {
1.70 + SkASSERT(fSetArray);
1.71 + SkASSERT(fOrderedArray);
1.72 +
1.73 + // Do fOrderedArray merge.
1.74 + for (int i = 0; i < src.count(); ++i) {
1.75 + if (!contains((*src.fOrderedArray)[i])) {
1.76 + fOrderedArray->push((*src.fOrderedArray)[i]);
1.77 + }
1.78 + }
1.79 +
1.80 + // Do fSetArray merge.
1.81 + int duplicates = 0;
1.82 +
1.83 + SkTDArray<T>* fArrayNew = new SkTDArray<T>();
1.84 + fArrayNew->setReserve(fOrderedArray->count());
1.85 + int i = 0;
1.86 + int j = 0;
1.87 +
1.88 + while (i < fSetArray->count() && j < src.count()) {
1.89 + if ((*fSetArray)[i] < (*src.fSetArray)[j]) {
1.90 + fArrayNew->push((*fSetArray)[i]);
1.91 + i++;
1.92 + } else if ((*fSetArray)[i] > (*src.fSetArray)[j]) {
1.93 + fArrayNew->push((*src.fSetArray)[j]);
1.94 + j++;
1.95 + } else {
1.96 + duplicates++;
1.97 + j++; // Skip one of the duplicates.
1.98 + }
1.99 + }
1.100 +
1.101 + while (i < fSetArray->count()) {
1.102 + fArrayNew->push((*fSetArray)[i]);
1.103 + i++;
1.104 + }
1.105 +
1.106 + while (j < src.count()) {
1.107 + fArrayNew->push((*src.fSetArray)[j]);
1.108 + j++;
1.109 + }
1.110 + SkDELETE(fSetArray);
1.111 + fSetArray = fArrayNew;
1.112 + fArrayNew = NULL;
1.113 +
1.114 +#ifdef SK_DEBUG
1.115 + validate();
1.116 +#endif
1.117 + return duplicates;
1.118 + }
1.119 +
1.120 + /** Adds a new element into set and returns false if the element is already
1.121 + * in this set.
1.122 + */
1.123 + bool add(const T& elem) {
1.124 + SkASSERT(fSetArray);
1.125 + SkASSERT(fOrderedArray);
1.126 +
1.127 + int pos = 0;
1.128 + int i = find(elem, &pos);
1.129 + if (i >= 0) {
1.130 + return false;
1.131 + }
1.132 + *fSetArray->insert(pos) = elem;
1.133 + fOrderedArray->push(elem);
1.134 +#ifdef SK_DEBUG
1.135 + validate();
1.136 +#endif
1.137 + return true;
1.138 + }
1.139 +
1.140 + /** Returns true if this set is empty.
1.141 + */
1.142 + bool isEmpty() const {
1.143 + SkASSERT(fOrderedArray);
1.144 + SkASSERT(fSetArray);
1.145 + SkASSERT(fSetArray->isEmpty() == fOrderedArray->isEmpty());
1.146 + return fOrderedArray->isEmpty();
1.147 + }
1.148 +
1.149 + /** Return the number of elements in the set.
1.150 + */
1.151 + int count() const {
1.152 + SkASSERT(fOrderedArray);
1.153 + SkASSERT(fSetArray);
1.154 + SkASSERT(fSetArray->count() == fOrderedArray->count());
1.155 + return fOrderedArray->count();
1.156 + }
1.157 +
1.158 + /** Return the number of bytes in the set: count * sizeof(T).
1.159 + */
1.160 + size_t bytes() const {
1.161 + SkASSERT(fOrderedArray);
1.162 + return fOrderedArray->bytes();
1.163 + }
1.164 +
1.165 + /** Return the beginning of a set iterator.
1.166 + * Elements in the iterator will be sorted ascending.
1.167 + */
1.168 + const T* begin() const {
1.169 + SkASSERT(fOrderedArray);
1.170 + return fOrderedArray->begin();
1.171 + }
1.172 +
1.173 + /** Return the end of a set iterator.
1.174 + */
1.175 + const T* end() const {
1.176 + SkASSERT(fOrderedArray);
1.177 + return fOrderedArray->end();
1.178 + }
1.179 +
1.180 + const T& operator[](int index) const {
1.181 + SkASSERT(fOrderedArray);
1.182 + return (*fOrderedArray)[index];
1.183 + }
1.184 +
1.185 + /** Resets the set (deletes memory and initiates an empty set).
1.186 + */
1.187 + void reset() {
1.188 + SkASSERT(fSetArray);
1.189 + SkASSERT(fOrderedArray);
1.190 + fSetArray->reset();
1.191 + fOrderedArray->reset();
1.192 + }
1.193 +
1.194 + /** Rewinds the set (preserves memory and initiates an empty set).
1.195 + */
1.196 + void rewind() {
1.197 + SkASSERT(fSetArray);
1.198 + SkASSERT(fOrderedArray);
1.199 + fSetArray->rewind();
1.200 + fOrderedArray->rewind();
1.201 + }
1.202 +
1.203 + /** Reserves memory for the set.
1.204 + */
1.205 + void setReserve(int reserve) {
1.206 + SkASSERT(fSetArray);
1.207 + SkASSERT(fOrderedArray);
1.208 + fSetArray->setReserve(reserve);
1.209 + fOrderedArray->setReserve(reserve);
1.210 + }
1.211 +
1.212 + /** Returns true if the array contains this element.
1.213 + */
1.214 + bool contains(const T& elem) const {
1.215 + SkASSERT(fSetArray);
1.216 + return (this->find(elem) >= 0);
1.217 + }
1.218 +
1.219 + /** Copies internal array to destination.
1.220 + */
1.221 + void copy(T* dst) const {
1.222 + SkASSERT(fOrderedArray);
1.223 + fOrderedArray->copyRange(dst, 0, fOrderedArray->count());
1.224 + }
1.225 +
1.226 + /** Returns a const reference to the internal vector.
1.227 + */
1.228 + const SkTDArray<T>& toArray() {
1.229 + SkASSERT(fOrderedArray);
1.230 + return *fOrderedArray;
1.231 + }
1.232 +
1.233 + /** Unref all elements in the set.
1.234 + */
1.235 + void unrefAll() {
1.236 + SkASSERT(fSetArray);
1.237 + SkASSERT(fOrderedArray);
1.238 + fOrderedArray->unrefAll();
1.239 + // Also reset the other array, as SkTDArray::unrefAll does an
1.240 + // implcit reset
1.241 + fSetArray->reset();
1.242 + }
1.243 +
1.244 + /** safeUnref all elements in the set.
1.245 + */
1.246 + void safeUnrefAll() {
1.247 + SkASSERT(fSetArray);
1.248 + SkASSERT(fOrderedArray);
1.249 + fOrderedArray->safeUnrefAll();
1.250 + // Also reset the other array, as SkTDArray::safeUnrefAll does an
1.251 + // implcit reset
1.252 + fSetArray->reset();
1.253 + }
1.254 +
1.255 +#ifdef SK_DEBUG
1.256 + void validate() const {
1.257 + SkASSERT(fSetArray);
1.258 + SkASSERT(fOrderedArray);
1.259 + fSetArray->validate();
1.260 + fOrderedArray->validate();
1.261 + SkASSERT(isSorted() && !hasDuplicates() && arraysConsistent());
1.262 + }
1.263 +
1.264 + bool hasDuplicates() const {
1.265 + for (int i = 0; i < fSetArray->count() - 1; ++i) {
1.266 + if ((*fSetArray)[i] == (*fSetArray)[i + 1]) {
1.267 + return true;
1.268 + }
1.269 + }
1.270 + return false;
1.271 + }
1.272 +
1.273 + bool isSorted() const {
1.274 + for (int i = 0; i < fSetArray->count() - 1; ++i) {
1.275 + // Use only < operator
1.276 + if (!((*fSetArray)[i] < (*fSetArray)[i + 1])) {
1.277 + return false;
1.278 + }
1.279 + }
1.280 + return true;
1.281 + }
1.282 +
1.283 + /** Checks if fSetArray is consistent with fOrderedArray
1.284 + */
1.285 + bool arraysConsistent() const {
1.286 + if (fSetArray->count() != fOrderedArray->count()) {
1.287 + return false;
1.288 + }
1.289 + if (fOrderedArray->count() == 0) {
1.290 + return true;
1.291 + }
1.292 +
1.293 + // Copy and sort fOrderedArray, then compare to fSetArray.
1.294 + // A O(n log n) algorithm is necessary as O(n^2) will choke some GMs.
1.295 + SkAutoMalloc sortedArray(fOrderedArray->bytes());
1.296 + T* sortedBase = reinterpret_cast<T*>(sortedArray.get());
1.297 + int count = fOrderedArray->count();
1.298 + fOrderedArray->copyRange(sortedBase, 0, count);
1.299 +
1.300 + SkTQSort<T>(sortedBase, sortedBase + count - 1);
1.301 +
1.302 + for (int i = 0; i < count; ++i) {
1.303 + if (sortedBase[i] != (*fSetArray)[i]) {
1.304 + return false;
1.305 + }
1.306 + }
1.307 +
1.308 + return true;
1.309 + }
1.310 +#endif
1.311 +
1.312 +private:
1.313 + SkTDArray<T>* fSetArray; // Sorted by pointer address for fast
1.314 + // lookup.
1.315 + SkTDArray<T>* fOrderedArray; // Sorted by insertion order for
1.316 + // deterministic output.
1.317 +
1.318 + /** Returns the index in fSetArray where an element was found.
1.319 + * Returns -1 if the element was not found, and it fills *posToInsertSorted
1.320 + * with the index of the place where elem should be inserted to preserve the
1.321 + * internal array sorted.
1.322 + * If element was found, *posToInsertSorted is undefined.
1.323 + */
1.324 + int find(const T& elem, int* posToInsertSorted = NULL) const {
1.325 + SkASSERT(fSetArray);
1.326 +
1.327 + if (fSetArray->count() == 0) {
1.328 + if (posToInsertSorted) {
1.329 + *posToInsertSorted = 0;
1.330 + }
1.331 + return -1;
1.332 + }
1.333 + int iMin = 0;
1.334 + int iMax = fSetArray->count();
1.335 +
1.336 + while (iMin < iMax - 1) {
1.337 + int iMid = (iMin + iMax) / 2;
1.338 + if (elem < (*fSetArray)[iMid]) {
1.339 + iMax = iMid;
1.340 + } else {
1.341 + iMin = iMid;
1.342 + }
1.343 + }
1.344 + if (elem == (*fSetArray)[iMin]) {
1.345 + return iMin;
1.346 + }
1.347 + if (posToInsertSorted) {
1.348 + if (elem < (*fSetArray)[iMin]) {
1.349 + *posToInsertSorted = iMin;
1.350 + } else {
1.351 + *posToInsertSorted = iMin + 1;
1.352 + }
1.353 + }
1.354 +
1.355 + return -1;
1.356 + }
1.357 +};
1.358 +
1.359 +#endif
