/*
* 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