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. 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