1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#ifndef SkTSet_DEFINED
9#define SkTSet_DEFINED
10
11#include "SkTSort.h"
12#include "SkTDArray.h"
13#include "SkTypes.h"
14
15/** \class SkTSet<T>
16
17    The SkTSet template class defines a set. Elements are additionally
18    guaranteed to be sorted by their insertion order.
19    Main operations supported now are: add, merge, find and contains.
20
21    TSet<T> is mutable.
22*/
23
24// TODO: Add remove, intersect and difference operations.
25// TODO: Add bench tests.
26template <typename T> class SkTSet {
27public:
28    SkTSet() {
29        fSetArray = SkNEW(SkTDArray<T>);
30        fOrderedArray = SkNEW(SkTDArray<T>);
31    }
32
33    ~SkTSet() {
34        SkASSERT(fSetArray);
35        SkDELETE(fSetArray);
36        SkASSERT(fOrderedArray);
37        SkDELETE(fOrderedArray);
38    }
39
40    SkTSet(const SkTSet<T>& src) {
41        this->fSetArray = SkNEW_ARGS(SkTDArray<T>, (*src.fSetArray));
42        this->fOrderedArray = SkNEW_ARGS(SkTDArray<T>, (*src.fOrderedArray));
43#ifdef SK_DEBUG
44        validate();
45#endif
46    }
47
48    SkTSet<T>& operator=(const SkTSet<T>& src) {
49        *this->fSetArray = *src.fSetArray;
50        *this->fOrderedArray = *src.fOrderedArray;
51#ifdef SK_DEBUG
52        validate();
53#endif
54        return *this;
55    }
56
57    /** Merges src elements into this, and returns the number of duplicates
58     * found. Elements from src will retain their ordering and will be ordered
59     * after the elements currently in this set.
60     *
61     * Implementation note: this uses a 2-stage merge to obtain O(n log n) time.
62     * The first stage goes through src.fOrderedArray, checking if
63     * this->contains() is false before adding to this.fOrderedArray.
64     * The second stage does a standard sorted list merge on the fSetArrays.
65     */
66    int mergeInto(const SkTSet<T>& src) {
67        SkASSERT(fSetArray);
68        SkASSERT(fOrderedArray);
69
70        // Do fOrderedArray merge.
71        for (int i = 0; i < src.count(); ++i) {
72            if (!contains((*src.fOrderedArray)[i])) {
73                fOrderedArray->push((*src.fOrderedArray)[i]);
74            }
75        }
76
77        // Do fSetArray merge.
78        int duplicates = 0;
79
80        SkTDArray<T>* fArrayNew = new SkTDArray<T>();
81        fArrayNew->setReserve(fOrderedArray->count());
82        int i = 0;
83        int j = 0;
84
85        while (i < fSetArray->count() && j < src.count()) {
86            if ((*fSetArray)[i] < (*src.fSetArray)[j]) {
87                fArrayNew->push((*fSetArray)[i]);
88                i++;
89            } else if ((*fSetArray)[i] > (*src.fSetArray)[j]) {
90                fArrayNew->push((*src.fSetArray)[j]);
91                j++;
92            } else {
93                duplicates++;
94                j++; // Skip one of the duplicates.
95            }
96        }
97
98        while (i < fSetArray->count()) {
99            fArrayNew->push((*fSetArray)[i]);
100            i++;
101        }
102
103        while (j < src.count()) {
104            fArrayNew->push((*src.fSetArray)[j]);
105            j++;
106        }
107        SkDELETE(fSetArray);
108        fSetArray = fArrayNew;
109        fArrayNew = NULL;
110
111#ifdef SK_DEBUG
112        validate();
113#endif
114        return duplicates;
115    }
116
117    /** Adds a new element into set and returns false if the element is already
118     * in this set.
119    */
120    bool add(const T& elem) {
121        SkASSERT(fSetArray);
122        SkASSERT(fOrderedArray);
123
124        int pos = 0;
125        int i = find(elem, &pos);
126        if (i >= 0) {
127            return false;
128        }
129        *fSetArray->insert(pos) = elem;
130        fOrderedArray->push(elem);
131#ifdef SK_DEBUG
132        validate();
133#endif
134        return true;
135    }
136
137    /** Returns true if this set is empty.
138    */
139    bool isEmpty() const {
140        SkASSERT(fOrderedArray);
141        SkASSERT(fSetArray);
142        SkASSERT(fSetArray->isEmpty() == fOrderedArray->isEmpty());
143        return fOrderedArray->isEmpty();
144    }
145
146    /** Return the number of elements in the set.
147     */
148    int count() const {
149        SkASSERT(fOrderedArray);
150        SkASSERT(fSetArray);
151        SkASSERT(fSetArray->count() == fOrderedArray->count());
152        return fOrderedArray->count();
153    }
154
155    /** Return the number of bytes in the set: count * sizeof(T).
156     */
157    size_t bytes() const {
158        SkASSERT(fOrderedArray);
159        return fOrderedArray->bytes();
160    }
161
162    /** Return the beginning of a set iterator.
163     * Elements in the iterator will be sorted ascending.
164     */
165    const T*  begin() const {
166        SkASSERT(fOrderedArray);
167        return fOrderedArray->begin();
168    }
169
170    /** Return the end of a set iterator.
171     */
172    const T*  end() const {
173        SkASSERT(fOrderedArray);
174        return fOrderedArray->end();
175    }
176
177    const T&  operator[](int index) const {
178        SkASSERT(fOrderedArray);
179        return (*fOrderedArray)[index];
180    }
181
182    /** Resets the set (deletes memory and initiates an empty set).
183     */
184    void reset() {
185        SkASSERT(fSetArray);
186        SkASSERT(fOrderedArray);
187        fSetArray->reset();
188        fOrderedArray->reset();
189    }
190
191    /** Rewinds the set (preserves memory and initiates an empty set).
192     */
193    void rewind() {
194        SkASSERT(fSetArray);
195        SkASSERT(fOrderedArray);
196        fSetArray->rewind();
197        fOrderedArray->rewind();
198    }
199
200    /** Reserves memory for the set.
201     */
202    void setReserve(int reserve) {
203        SkASSERT(fSetArray);
204        SkASSERT(fOrderedArray);
205        fSetArray->setReserve(reserve);
206        fOrderedArray->setReserve(reserve);
207    }
208
209    /** Returns true if the array contains this element.
210     */
211    bool contains(const T& elem) const {
212        SkASSERT(fSetArray);
213        return (this->find(elem) >= 0);
214    }
215
216    /** Copies internal array to destination.
217     */
218    void copy(T* dst) const {
219        SkASSERT(fOrderedArray);
220        fOrderedArray->copyRange(dst, 0, fOrderedArray->count());
221    }
222
223    /** Returns a const reference to the internal vector.
224     */
225    const SkTDArray<T>& toArray() {
226        SkASSERT(fOrderedArray);
227        return *fOrderedArray;
228    }
229
230    /** Unref all elements in the set.
231     */
232    void unrefAll() {
233        SkASSERT(fSetArray);
234        SkASSERT(fOrderedArray);
235        fOrderedArray->unrefAll();
236        // Also reset the other array, as SkTDArray::unrefAll does an
237        // implcit reset
238        fSetArray->reset();
239    }
240
241    /** safeUnref all elements in the set.
242     */
243    void safeUnrefAll() {
244        SkASSERT(fSetArray);
245        SkASSERT(fOrderedArray);
246        fOrderedArray->safeUnrefAll();
247        // Also reset the other array, as SkTDArray::safeUnrefAll does an
248        // implcit reset
249        fSetArray->reset();
250    }
251
252#ifdef SK_DEBUG
253    void validate() const {
254        SkASSERT(fSetArray);
255        SkASSERT(fOrderedArray);
256        fSetArray->validate();
257        fOrderedArray->validate();
258        SkASSERT(isSorted() && !hasDuplicates() && arraysConsistent());
259    }
260
261    bool hasDuplicates() const {
262        for (int i = 0; i < fSetArray->count() - 1; ++i) {
263            if ((*fSetArray)[i] == (*fSetArray)[i + 1]) {
264                return true;
265            }
266        }
267        return false;
268    }
269
270    bool isSorted() const {
271        for (int i = 0; i < fSetArray->count() - 1; ++i) {
272            // Use only < operator
273            if (!((*fSetArray)[i] < (*fSetArray)[i + 1])) {
274                return false;
275            }
276        }
277        return true;
278    }
279
280    /** Checks if fSetArray is consistent with fOrderedArray
281     */
282    bool arraysConsistent() const {
283        if (fSetArray->count() != fOrderedArray->count()) {
284            return false;
285        }
286        if (fOrderedArray->count() == 0) {
287            return true;
288        }
289
290        // Copy and sort fOrderedArray, then compare to fSetArray.
291        // A O(n log n) algorithm is necessary as O(n^2) will choke some GMs.
292        SkAutoMalloc sortedArray(fOrderedArray->bytes());
293        T* sortedBase = reinterpret_cast<T*>(sortedArray.get());
294        int count = fOrderedArray->count();
295        fOrderedArray->copyRange(sortedBase, 0, count);
296
297        SkTQSort<T>(sortedBase, sortedBase + count - 1);
298
299        for (int i = 0; i < count; ++i) {
300            if (sortedBase[i] != (*fSetArray)[i]) {
301                return false;
302            }
303        }
304
305        return true;
306    }
307#endif
308
309private:
310    SkTDArray<T>* fSetArray;        // Sorted by pointer address for fast
311                                    // lookup.
312    SkTDArray<T>* fOrderedArray;    // Sorted by insertion order for
313                                    // deterministic output.
314
315    /** Returns the index in fSetArray where an element was found.
316     * Returns -1 if the element was not found, and it fills *posToInsertSorted
317     * with the index of the place where elem should be inserted to preserve the
318     * internal array sorted.
319     * If element was found, *posToInsertSorted is undefined.
320     */
321    int find(const T& elem, int* posToInsertSorted = NULL) const {
322        SkASSERT(fSetArray);
323
324        if (fSetArray->count() == 0) {
325            if (posToInsertSorted) {
326                *posToInsertSorted = 0;
327            }
328            return -1;
329        }
330        int iMin = 0;
331        int iMax = fSetArray->count();
332
333        while (iMin < iMax - 1) {
334            int iMid = (iMin + iMax) / 2;
335            if (elem < (*fSetArray)[iMid]) {
336                iMax = iMid;
337            } else {
338                iMin = iMid;
339            }
340        }
341        if (elem == (*fSetArray)[iMin]) {
342            return iMin;
343        }
344        if (posToInsertSorted) {
345            if (elem < (*fSetArray)[iMin]) {
346                *posToInsertSorted = iMin;
347            } else {
348                *posToInsertSorted = iMin + 1;
349            }
350        }
351
352        return -1;
353    }
354};
355
356#endif
357