Deterministic SkTSet and PDF Output

src/pdf/SkTSet.h

 /*
  * 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.
+    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() {
-        fArray = SkNEW(SkTDArray<T>);
+        fSetArray = SkNEW(SkTDArray<T>);
+        fOrderedArray = SkNEW(SkTDArray<T>);
     }
 
     ~SkTSet() {
-        SkASSERT(fArray);
-        SkDELETE(fArray);
+        SkASSERT(fSetArray);
+        SkDELETE(fSetArray);
+        SkASSERT(fOrderedArray);
+        SkDELETE(fOrderedArray);
     }
 
     SkTSet(const SkTSet<T>& src) {
-        this->fArray = SkNEW_ARGS(SkTDArray<T>, (*src.fArray));
+        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->fArray = *src.fArray;
+        *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.
-    */
+     * 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(fArray);
+        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(count() + src.count());
+        fArrayNew->setReserve(fOrderedArray->count());
         int i = 0;
         int j = 0;
 
-        while (i < count() && j < src.count()) {
-            if ((*fArray)[i] < (*src.fArray)[j]) {
-                fArrayNew->push((*fArray)[i]);
+        while (i < fSetArray->count() && j < src.count()) {
+            if ((*fSetArray)[i] < (*src.fSetArray)[j]) {
+                fArrayNew->push((*fSetArray)[i]);
                 i++;
-            } else if ((*fArray)[i] > (*src.fArray)[j]) {
-                fArrayNew->push((*src.fArray)[j]);
+            } else if ((*fSetArray)[i] > (*src.fSetArray)[j]) {
+                fArrayNew->push((*src.fSetArray)[j]);
                 j++;
             } else {
                 duplicates++;
                 j++; // Skip one of the duplicates.
             }
         }
 
-        while (i < count()) {
-            fArrayNew->push((*fArray)[i]);
+        while (i < fSetArray->count()) {
+            fArrayNew->push((*fSetArray)[i]);
             i++;
         }
 
         while (j < src.count()) {
-            fArrayNew->push((*src.fArray)[j]);
+            fArrayNew->push((*src.fSetArray)[j]);
             j++;
         }
-        SkDELETE(fArray);
-        fArray = fArrayNew;
+        SkDELETE(fSetArray);
+        fSetArray = fArrayNew;
         fArrayNew = NULL;
 
 #ifdef SK_DEBUG
         validate();
 #endif
         return duplicates;
     }
 
-    /** Adds a new element into set and returns true if the element is already
+    /** Adds a new element into set and returns false if the element is already
      * in this set.
     */
     bool add(const T& elem) {
-        SkASSERT(fArray);
+        SkASSERT(fSetArray);
+        SkASSERT(fOrderedArray);
 
         int pos = 0;
         int i = find(elem, &pos);
         if (i >= 0) {
             return false;
         }
-        *fArray->insert(pos) = elem;
+        *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(fArray);
-        return fArray->isEmpty();
+        SkASSERT(fOrderedArray);
+        SkASSERT(fSetArray);
+        SkASSERT(fSetArray->isEmpty() == fOrderedArray->isEmpty());
+        return fOrderedArray->isEmpty();
     }
 
     /** Return the number of elements in the set.
      */
     int count() const {
-        SkASSERT(fArray);
-        return fArray->count();
+        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 {

[edisonn, 2013/07/17 20:03:28]

if this function is not used anywhere, please remove it. If used, make sure the
previous contract is still respected.

-        SkASSERT(fArray);
-        return fArray->bytes();
+        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(fArray);
-        return fArray->begin();
+        SkASSERT(fOrderedArray);
+        return fOrderedArray->begin();
     }
 
     /** Return the end of a set iterator.
      */
     const T*  end() const {
-        SkASSERT(fArray);
-        return fArray->end();
+        SkASSERT(fOrderedArray);
+        return fOrderedArray->end();
     }
 
     const T&  operator[](int index) const {
-        SkASSERT(fArray);
-        return (*fArray)[index];
+        SkASSERT(fOrderedArray);
+        return (*fOrderedArray)[index];
     }
 
     /** Resets the set (deletes memory and initiates an empty set).
      */
     void reset() {
-        SkASSERT(fArray);
-        fArray->reset();
+        SkASSERT(fSetArray);
+        SkASSERT(fOrderedArray);
+        fSetArray->reset();
+        fOrderedArray->reset();
     }
 
     /** Rewinds the set (preserves memory and initiates an empty set).
      */
     void rewind() {
-        SkASSERT(fArray);
-        fArray->rewind();
+        SkASSERT(fSetArray);
+        SkASSERT(fOrderedArray);
+        fSetArray->rewind();
+        fOrderedArray->rewind();
     }
 
     /** Reserves memory for the set.
      */
     void setReserve(size_t reserve) {
-        SkASSERT(fArray);
-        fArray->setReserve(reserve);
-    }
-
-    /** Returns the index 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(fArray);
-
-        if (fArray->count() == 0) {
-            if (posToInsertSorted) {
-                *posToInsertSorted = 0;
-            }
-            return -1;
-        }
-        int iMin = 0;
-        int iMax = fArray->count();
-
-        while (iMin < iMax - 1) {
-            int iMid = (iMin + iMax) / 2;
-            if (elem < (*fArray)[iMid]) {
-                iMax = iMid;
-            } else {
-                iMin = iMid;
-            }
-        }
-        if (elem == (*fArray)[iMin]) {
-            return iMin;
-        }
-        if (posToInsertSorted) {
-            if (elem < (*fArray)[iMin]) {
-                *posToInsertSorted = iMin;
-            } else {
-                *posToInsertSorted = iMin + 1;
-            }
-        }
-
-        return -1;
+        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(fArray);
+        SkASSERT(fSetArray);
         return (this->find(elem) >= 0);
     }
 
     /** Copies internal array to destination.
      */
     void copy(T* dst) const {
-        SkASSERT(fArray);
-        fArray->copyRange(0, fArray->count(), dst);
+        SkASSERT(fOrderedArray);
+        fOrderedArray->copyRange(dst, 0, fOrderedArray->count());
     }
 
     /** Returns a const reference to the internal vector.
      */
     const SkTDArray<T>& toArray() {
-        SkASSERT(fArray);
-        return *fArray;
+        SkASSERT(fOrderedArray);
+        return *fOrderedArray;
     }
 
     /** Unref all elements in the set.
      */
     void unrefAll() {
-        SkASSERT(fArray);
-        fArray->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(fArray);
-        fArray->safeUnrefAll();
+    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(fArray);
-        fArray->validate();
-        SkASSERT(isSorted() && !hasDuplicates());
+        SkASSERT(fSetArray);
+        SkASSERT(fOrderedArray);
+        fSetArray->validate();
+        fOrderedArray->validate();
+        SkASSERT(isSorted() && !hasDuplicates() && arraysConsistent());
     }
 
     bool hasDuplicates() const {
-        for (int i = 0; i < fArray->count() - 1; ++i) {
-            if ((*fArray)[i] == (*fArray)[i + 1]) {
+        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 < fArray->count() - 1; ++i) {
+        for (int i = 0; i < fSetArray->count() - 1; ++i) {
             // Use only < operator
-            if (!((*fArray)[i] < (*fArray)[i + 1])) {
+            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());
+        size_t count = fOrderedArray->count();
+        fOrderedArray->copyRange(sortedBase, 0, count);
+
+        SkTQSort<T>(sortedBase, sortedBase + count - 1);
+
+        for (size_t i = 0; i < count; ++i) {
+            if (sortedBase[i] != (*fSetArray)[i]) {
+                return false;
+            }
+        }
+
+        return true;
+    }
 #endif
 
 private:
-    SkTDArray<T>* fArray;
+    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