diff -r 000000000000 -r 6474c204b198 gfx/skia/trunk/src/pdf/SkTSet.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gfx/skia/trunk/src/pdf/SkTSet.h	Wed Dec 31 06:09:35 2014 +0100
@@ -0,0 +1,356 @@
+/*
+ * 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