1096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger/* 2096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * Copyright 2012 Google Inc. 3096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * 4096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * Use of this source code is governed by a BSD-style license that can be 5096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * found in the LICENSE file. 6096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 7096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 8096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#ifndef SkTSet_DEFINED 9096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#define SkTSet_DEFINED 10096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 1158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger#include "SkTSort.h" 12096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#include "SkTDArray.h" 13096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#include "SkTypes.h" 14096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 15096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger/** \class SkTSet<T> 16096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 1758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger The SkTSet template class defines a set. Elements are additionally 1858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger guaranteed to be sorted by their insertion order. 19096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger Main operations supported now are: add, merge, find and contains. 20096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 21096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger TSet<T> is mutable. 22096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger*/ 23096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 24096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger// TODO: Add remove, intersect and difference operations. 25096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger// TODO: Add bench tests. 2658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenbergertemplate <typename T> class SkTSet { 27096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenbergerpublic: 28096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger SkTSet() { 2958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fSetArray = SkNEW(SkTDArray<T>); 3058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fOrderedArray = SkNEW(SkTDArray<T>); 31096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 32096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 33096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger ~SkTSet() { 3458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 3558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkDELETE(fSetArray); 3658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 3758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkDELETE(fOrderedArray); 38096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 39096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 40096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger SkTSet(const SkTSet<T>& src) { 4158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger this->fSetArray = SkNEW_ARGS(SkTDArray<T>, (*src.fSetArray)); 4258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger this->fOrderedArray = SkNEW_ARGS(SkTDArray<T>, (*src.fOrderedArray)); 43096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#ifdef SK_DEBUG 44096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger validate(); 45096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#endif 46096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 47096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 48096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger SkTSet<T>& operator=(const SkTSet<T>& src) { 4958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger *this->fSetArray = *src.fSetArray; 5058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger *this->fOrderedArray = *src.fOrderedArray; 51096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#ifdef SK_DEBUG 52096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger validate(); 53096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#endif 54096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger return *this; 55096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 56096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 57096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Merges src elements into this, and returns the number of duplicates 5858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger * found. Elements from src will retain their ordering and will be ordered 5958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger * after the elements currently in this set. 6058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger * 6158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger * Implementation note: this uses a 2-stage merge to obtain O(n log n) time. 6258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger * The first stage goes through src.fOrderedArray, checking if 6358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger * this->contains() is false before adding to this.fOrderedArray. 6458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger * The second stage does a standard sorted list merge on the fSetArrays. 6558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger */ 66096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger int mergeInto(const SkTSet<T>& src) { 6758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 6858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 6958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 7058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // Do fOrderedArray merge. 7158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger for (int i = 0; i < src.count(); ++i) { 7258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (!contains((*src.fOrderedArray)[i])) { 7358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fOrderedArray->push((*src.fOrderedArray)[i]); 7458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 7558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 7658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 7758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // Do fSetArray merge. 78096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger int duplicates = 0; 79096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 80096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger SkTDArray<T>* fArrayNew = new SkTDArray<T>(); 8158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fArrayNew->setReserve(fOrderedArray->count()); 82096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger int i = 0; 83096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger int j = 0; 84096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 8558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger while (i < fSetArray->count() && j < src.count()) { 8658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((*fSetArray)[i] < (*src.fSetArray)[j]) { 8758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fArrayNew->push((*fSetArray)[i]); 88096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger i++; 8958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } else if ((*fSetArray)[i] > (*src.fSetArray)[j]) { 9058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fArrayNew->push((*src.fSetArray)[j]); 91096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger j++; 92096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } else { 93096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger duplicates++; 94096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger j++; // Skip one of the duplicates. 95096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 96096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 97096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 9858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger while (i < fSetArray->count()) { 9958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fArrayNew->push((*fSetArray)[i]); 100096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger i++; 101096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 102096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 103096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger while (j < src.count()) { 10458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fArrayNew->push((*src.fSetArray)[j]); 105096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger j++; 106096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 10758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkDELETE(fSetArray); 10858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fSetArray = fArrayNew; 109096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger fArrayNew = NULL; 110096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 111096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#ifdef SK_DEBUG 112096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger validate(); 113096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#endif 114096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger return duplicates; 115096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 116096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 11758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger /** Adds a new element into set and returns false if the element is already 118096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * in this set. 119096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 120096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger bool add(const T& elem) { 12158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 12258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 123096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 124096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger int pos = 0; 125096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger int i = find(elem, &pos); 126096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger if (i >= 0) { 127096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger return false; 128096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 12958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger *fSetArray->insert(pos) = elem; 13058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fOrderedArray->push(elem); 131096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#ifdef SK_DEBUG 132096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger validate(); 133096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#endif 134096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger return true; 135096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 136096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 137096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Returns true if this set is empty. 138096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 139096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger bool isEmpty() const { 14058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 14158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 14258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray->isEmpty() == fOrderedArray->isEmpty()); 14358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return fOrderedArray->isEmpty(); 144096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 145096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 146096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Return the number of elements in the set. 147096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 148096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger int count() const { 14958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 15058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 15158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray->count() == fOrderedArray->count()); 15258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return fOrderedArray->count(); 153096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 154096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 155096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Return the number of bytes in the set: count * sizeof(T). 156096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 157096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger size_t bytes() const { 15858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 15958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return fOrderedArray->bytes(); 160096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 161096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 162096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Return the beginning of a set iterator. 163096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * Elements in the iterator will be sorted ascending. 164096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 165096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger const T* begin() const { 16658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 16758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return fOrderedArray->begin(); 168096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 169096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 170096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Return the end of a set iterator. 171096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 172096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger const T* end() const { 17358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 17458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return fOrderedArray->end(); 175096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 176096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 177096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger const T& operator[](int index) const { 17858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 17958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return (*fOrderedArray)[index]; 180096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 181096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 182096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Resets the set (deletes memory and initiates an empty set). 183096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 184096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger void reset() { 18558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 18658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 18758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fSetArray->reset(); 18858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fOrderedArray->reset(); 189096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 190096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 191096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Rewinds the set (preserves memory and initiates an empty set). 192096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 193096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger void rewind() { 19458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 19558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 19658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fSetArray->rewind(); 19758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fOrderedArray->rewind(); 198096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 199096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 200096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Reserves memory for the set. 201096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 2020a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger void setReserve(int reserve) { 20358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 20458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 20558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fSetArray->setReserve(reserve); 20658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fOrderedArray->setReserve(reserve); 207096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 208096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 209096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Returns true if the array contains this element. 210096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 211096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger bool contains(const T& elem) const { 21258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 213096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger return (this->find(elem) >= 0); 214096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 215096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 216096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Copies internal array to destination. 217096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 218096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger void copy(T* dst) const { 21958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 22058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fOrderedArray->copyRange(dst, 0, fOrderedArray->count()); 221096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 222096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 223096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Returns a const reference to the internal vector. 224096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 225096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger const SkTDArray<T>& toArray() { 22658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 22758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return *fOrderedArray; 228096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 229096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 230096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** Unref all elements in the set. 231096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 232096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger void unrefAll() { 23358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 23458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 23558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fOrderedArray->unrefAll(); 23658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // Also reset the other array, as SkTDArray::unrefAll does an 23758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // implcit reset 23858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fSetArray->reset(); 239096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 240096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 241096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger /** safeUnref all elements in the set. 242096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger */ 24358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger void safeUnrefAll() { 24458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 24558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 24658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fOrderedArray->safeUnrefAll(); 24758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // Also reset the other array, as SkTDArray::safeUnrefAll does an 24858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // implcit reset 24958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fSetArray->reset(); 250096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 251096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 252096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#ifdef SK_DEBUG 253096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger void validate() const { 25458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 25558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fOrderedArray); 25658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fSetArray->validate(); 25758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fOrderedArray->validate(); 25858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(isSorted() && !hasDuplicates() && arraysConsistent()); 259096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 260096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 261096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger bool hasDuplicates() const { 26258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger for (int i = 0; i < fSetArray->count() - 1; ++i) { 26358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if ((*fSetArray)[i] == (*fSetArray)[i + 1]) { 264096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger return true; 265096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 266096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 267096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger return false; 268096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 269096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 270096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger bool isSorted() const { 27158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger for (int i = 0; i < fSetArray->count() - 1; ++i) { 272096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger // Use only < operator 27358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (!((*fSetArray)[i] < (*fSetArray)[i + 1])) { 27458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return false; 27558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 27658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 27758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return true; 27858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 27958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 28058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger /** Checks if fSetArray is consistent with fOrderedArray 28158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger */ 28258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger bool arraysConsistent() const { 28358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fSetArray->count() != fOrderedArray->count()) { 28458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return false; 28558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 28658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fOrderedArray->count() == 0) { 28758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return true; 28858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 28958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 29058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // Copy and sort fOrderedArray, then compare to fSetArray. 29158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // A O(n log n) algorithm is necessary as O(n^2) will choke some GMs. 29258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkAutoMalloc sortedArray(fOrderedArray->bytes()); 29358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger T* sortedBase = reinterpret_cast<T*>(sortedArray.get()); 2940a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger int count = fOrderedArray->count(); 29558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger fOrderedArray->copyRange(sortedBase, 0, count); 29658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 29758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkTQSort<T>(sortedBase, sortedBase + count - 1); 29858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 2990a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger for (int i = 0; i < count; ++i) { 30058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (sortedBase[i] != (*fSetArray)[i]) { 301096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger return false; 302096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 303096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 30458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 305096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger return true; 306096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 307096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#endif 308096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 309096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenbergerprivate: 31058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkTDArray<T>* fSetArray; // Sorted by pointer address for fast 31158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // lookup. 31258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkTDArray<T>* fOrderedArray; // Sorted by insertion order for 31358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger // deterministic output. 31458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 31558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger /** Returns the index in fSetArray where an element was found. 31658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger * Returns -1 if the element was not found, and it fills *posToInsertSorted 31758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger * with the index of the place where elem should be inserted to preserve the 31858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger * internal array sorted. 31958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger * If element was found, *posToInsertSorted is undefined. 32058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger */ 32158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int find(const T& elem, int* posToInsertSorted = NULL) const { 32258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger SkASSERT(fSetArray); 32358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 32458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (fSetArray->count() == 0) { 32558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (posToInsertSorted) { 32658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger *posToInsertSorted = 0; 32758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 32858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return -1; 32958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 33058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int iMin = 0; 33158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int iMax = fSetArray->count(); 33258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 33358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger while (iMin < iMax - 1) { 33458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger int iMid = (iMin + iMax) / 2; 33558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (elem < (*fSetArray)[iMid]) { 33658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger iMax = iMid; 33758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } else { 33858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger iMin = iMid; 33958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 34058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 34158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (elem == (*fSetArray)[iMin]) { 34258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return iMin; 34358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 34458190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (posToInsertSorted) { 34558190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger if (elem < (*fSetArray)[iMin]) { 34658190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger *posToInsertSorted = iMin; 34758190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } else { 34858190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger *posToInsertSorted = iMin + 1; 34958190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 35058190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 35158190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger 35258190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger return -1; 35358190644c30e1c4aa8e527f3503c58f841e0fcf3Derek Sollenberger } 354096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger}; 355096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 356096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger#endif 357