The Tor Browser: comparison gfx/skia/trunk/src/pdf/SkTSet.h

--1:000000000000
+:cd13bdd6e845
+/*
+* 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

The Tor Browser / file comparison

comparison: gfx/skia/trunk/src/pdf/SkTSet.h

gfx/skia/trunk/src/pdf/SkTSet.h