aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/pdf/SkTSet.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/pdf/SkTSet.h')
-rw-r--r--src/pdf/SkTSet.h356
1 files changed, 0 insertions, 356 deletions
diff --git a/src/pdf/SkTSet.h b/src/pdf/SkTSet.h
deleted file mode 100644
index f57d30eccb..0000000000
--- a/src/pdf/SkTSet.h
+++ /dev/null
@@ -1,356 +0,0 @@
-/*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#ifndef SkTSet_DEFINED
-#define SkTSet_DEFINED
-
-#include "SkTSort.h"
-#include "SkTDArray.h"
-#include "SkTypes.h"
-
-/** \class SkTSet<T>
-
- The SkTSet template class defines a set. Elements are additionally
- guaranteed to be sorted by their insertion order.
- Main operations supported now are: add, merge, find and contains.
-
- TSet<T> is mutable.
-*/
-
-// TODO: Add remove, intersect and difference operations.
-// TODO: Add bench tests.
-template <typename T> class SkTSet {
-public:
- SkTSet() {
- fSetArray = SkNEW(SkTDArray<T>);
- fOrderedArray = SkNEW(SkTDArray<T>);
- }
-
- ~SkTSet() {
- SkASSERT(fSetArray);
- SkDELETE(fSetArray);
- SkASSERT(fOrderedArray);
- SkDELETE(fOrderedArray);
- }
-
- SkTSet(const SkTSet<T>& src) {
- this->fSetArray = SkNEW_ARGS(SkTDArray<T>, (*src.fSetArray));
- this->fOrderedArray = SkNEW_ARGS(SkTDArray<T>, (*src.fOrderedArray));
-#ifdef SK_DEBUG
- validate();
-#endif
- }
-
- SkTSet<T>& operator=(const SkTSet<T>& src) {
- *this->fSetArray = *src.fSetArray;
- *this->fOrderedArray = *src.fOrderedArray;
-#ifdef SK_DEBUG
- validate();
-#endif
- return *this;
- }
-
- /** Merges src elements into this, and returns the number of duplicates
- * found. Elements from src will retain their ordering and will be ordered
- * after the elements currently in this set.
- *
- * Implementation note: this uses a 2-stage merge to obtain O(n log n) time.
- * The first stage goes through src.fOrderedArray, checking if
- * this->contains() is false before adding to this.fOrderedArray.
- * The second stage does a standard sorted list merge on the fSetArrays.
- */
- int mergeInto(const SkTSet<T>& src) {
- SkASSERT(fSetArray);
- SkASSERT(fOrderedArray);
-
- // Do fOrderedArray merge.
- for (int i = 0; i < src.count(); ++i) {
- if (!contains((*src.fOrderedArray)[i])) {
- fOrderedArray->push((*src.fOrderedArray)[i]);
- }
- }
-
- // Do fSetArray merge.
- int duplicates = 0;
-
- SkTDArray<T>* fArrayNew = new SkTDArray<T>();
- fArrayNew->setReserve(fOrderedArray->count());
- int i = 0;
- int j = 0;
-
- while (i < fSetArray->count() && j < src.count()) {
- if ((*fSetArray)[i] < (*src.fSetArray)[j]) {
- fArrayNew->push((*fSetArray)[i]);
- i++;
- } else if ((*fSetArray)[i] > (*src.fSetArray)[j]) {
- fArrayNew->push((*src.fSetArray)[j]);
- j++;
- } else {
- duplicates++;
- j++; // Skip one of the duplicates.
- }
- }
-
- while (i < fSetArray->count()) {
- fArrayNew->push((*fSetArray)[i]);
- i++;
- }
-
- while (j < src.count()) {
- fArrayNew->push((*src.fSetArray)[j]);
- j++;
- }
- SkDELETE(fSetArray);
- fSetArray = fArrayNew;
- fArrayNew = NULL;
-
-#ifdef SK_DEBUG
- validate();
-#endif
- return duplicates;
- }
-
- /** Adds a new element into set and returns false if the element is already
- * in this set.
- */
- bool add(const T& elem) {
- SkASSERT(fSetArray);
- SkASSERT(fOrderedArray);
-
- int pos = 0;
- int i = find(elem, &pos);
- if (i >= 0) {
- return false;
- }
- *fSetArray->insert(pos) = elem;
- fOrderedArray->push(elem);
-#ifdef SK_DEBUG
- validate();
-#endif
- return true;
- }
-
- /** Returns true if this set is empty.
- */
- bool isEmpty() const {
- SkASSERT(fOrderedArray);
- SkASSERT(fSetArray);
- SkASSERT(fSetArray->isEmpty() == fOrderedArray->isEmpty());
- return fOrderedArray->isEmpty();
- }
-
- /** Return the number of elements in the set.
- */
- int count() const {
- SkASSERT(fOrderedArray);
- SkASSERT(fSetArray);
- SkASSERT(fSetArray->count() == fOrderedArray->count());
- return fOrderedArray->count();
- }
-
- /** Return the number of bytes in the set: count * sizeof(T).
- */
- size_t bytes() const {
- SkASSERT(fOrderedArray);
- return fOrderedArray->bytes();
- }
-
- /** Return the beginning of a set iterator.
- * Elements in the iterator will be sorted ascending.
- */
- const T* begin() const {
- SkASSERT(fOrderedArray);
- return fOrderedArray->begin();
- }
-
- /** Return the end of a set iterator.
- */
- const T* end() const {
- SkASSERT(fOrderedArray);
- return fOrderedArray->end();
- }
-
- const T& operator[](int index) const {
- SkASSERT(fOrderedArray);
- return (*fOrderedArray)[index];
- }
-
- /** Resets the set (deletes memory and initiates an empty set).
- */
- void reset() {
- SkASSERT(fSetArray);
- SkASSERT(fOrderedArray);
- fSetArray->reset();
- fOrderedArray->reset();
- }
-
- /** Rewinds the set (preserves memory and initiates an empty set).
- */
- void rewind() {
- SkASSERT(fSetArray);
- SkASSERT(fOrderedArray);
- fSetArray->rewind();
- fOrderedArray->rewind();
- }
-
- /** Reserves memory for the set.
- */
- void setReserve(int reserve) {
- SkASSERT(fSetArray);
- SkASSERT(fOrderedArray);
- fSetArray->setReserve(reserve);
- fOrderedArray->setReserve(reserve);
- }
-
- /** Returns true if the array contains this element.
- */
- bool contains(const T& elem) const {
- SkASSERT(fSetArray);
- return (this->find(elem) >= 0);
- }
-
- /** Copies internal array to destination.
- */
- void copy(T* dst) const {
- SkASSERT(fOrderedArray);
- fOrderedArray->copyRange(dst, 0, fOrderedArray->count());
- }
-
- /** Returns a const reference to the internal vector.
- */
- const SkTDArray<T>& toArray() {
- SkASSERT(fOrderedArray);
- return *fOrderedArray;
- }
-
- /** Unref all elements in the set.
- */
- void unrefAll() {
- SkASSERT(fSetArray);
- SkASSERT(fOrderedArray);
- fOrderedArray->unrefAll();
- // Also reset the other array, as SkTDArray::unrefAll does an
- // implcit reset
- fSetArray->reset();
- }
-
- /** safeUnref all elements in the set.
- */
- void safeUnrefAll() {
- SkASSERT(fSetArray);
- SkASSERT(fOrderedArray);
- fOrderedArray->safeUnrefAll();
- // Also reset the other array, as SkTDArray::safeUnrefAll does an
- // implcit reset
- fSetArray->reset();
- }
-
-#ifdef SK_DEBUG
- void validate() const {
- SkASSERT(fSetArray);
- SkASSERT(fOrderedArray);
- fSetArray->validate();
- fOrderedArray->validate();
- SkASSERT(isSorted() && !hasDuplicates() && arraysConsistent());
- }
-
- bool hasDuplicates() const {
- for (int i = 0; i < fSetArray->count() - 1; ++i) {
- if ((*fSetArray)[i] == (*fSetArray)[i + 1]) {
- return true;
- }
- }
- return false;
- }
-
- bool isSorted() const {
- for (int i = 0; i < fSetArray->count() - 1; ++i) {
- // Use only < operator
- if (!((*fSetArray)[i] < (*fSetArray)[i + 1])) {
- return false;
- }
- }
- return true;
- }
-
- /** Checks if fSetArray is consistent with fOrderedArray
- */
- bool arraysConsistent() const {
- if (fSetArray->count() != fOrderedArray->count()) {
- return false;
- }
- if (fOrderedArray->count() == 0) {
- return true;
- }
-
- // Copy and sort fOrderedArray, then compare to fSetArray.
- // A O(n log n) algorithm is necessary as O(n^2) will choke some GMs.
- SkAutoMalloc sortedArray(fOrderedArray->bytes());
- T* sortedBase = reinterpret_cast<T*>(sortedArray.get());
- int count = fOrderedArray->count();
- fOrderedArray->copyRange(sortedBase, 0, count);
-
- SkTQSort<T>(sortedBase, sortedBase + count - 1);
-
- for (int i = 0; i < count; ++i) {
- if (sortedBase[i] != (*fSetArray)[i]) {
- return false;
- }
- }
-
- return true;
- }
-#endif
-
-private:
- SkTDArray<T>* fSetArray; // Sorted by pointer address for fast
- // lookup.
- SkTDArray<T>* fOrderedArray; // Sorted by insertion order for
- // deterministic output.
-
- /** Returns the index in fSetArray where an element was found.
- * Returns -1 if the element was not found, and it fills *posToInsertSorted
- * with the index of the place where elem should be inserted to preserve the
- * internal array sorted.
- * If element was found, *posToInsertSorted is undefined.
- */
- int find(const T& elem, int* posToInsertSorted = NULL) const {
- SkASSERT(fSetArray);
-
- if (fSetArray->count() == 0) {
- if (posToInsertSorted) {
- *posToInsertSorted = 0;
- }
- return -1;
- }
- int iMin = 0;
- int iMax = fSetArray->count();
-
- while (iMin < iMax - 1) {
- int iMid = (iMin + iMax) / 2;
- if (elem < (*fSetArray)[iMid]) {
- iMax = iMid;
- } else {
- iMin = iMid;
- }
- }
- if (elem == (*fSetArray)[iMin]) {
- return iMin;
- }
- if (posToInsertSorted) {
- if (elem < (*fSetArray)[iMin]) {
- *posToInsertSorted = iMin;
- } else {
- *posToInsertSorted = iMin + 1;
- }
- }
-
- return -1;
- }
-};
-
-#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-06 08:47:22 +0000