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