1/*
2 * Copyright 2014 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 GrOrderedSet_DEFINED
9#define GrOrderedSet_DEFINED
10
11#include "GrRedBlackTree.h"
12
13template <typename T, typename C = GrLess<T> >
14class GrOrderedSet : SkNoncopyable {
15public:
16    /**
17     * Creates an empty set
18     */
19    GrOrderedSet() : fComp() {}
20    ~GrOrderedSet() {}
21
22    class Iter;
23
24    /**
25     * @return true if there are no items in the set, false otherwise.
26     */
27    bool empty() const { return fRBTree.empty(); }
28
29    /**
30     * @return the number of items in the set.
31     */
32    int count() const { return fRBTree.count(); }
33
34    /**
35     * Removes all items in the set
36     */
37    void reset() { fRBTree.reset(); }
38
39    /**
40     * Adds an element to set if it does not already exists in the set.
41     * @param t  the item to add
42     * @return an iterator to added element or matching element already in set
43     */
44    Iter insert(const T& t);
45
46    /**
47     * Removes the item indicated by an iterator. The iterator will not be valid
48     * afterwards.
49     * @param iter      iterator of item to remove. Must be valid (not end()).
50     */
51    void remove(const Iter& iter);
52
53    /**
54     * @return  an iterator to the first item in sorted order, or end() if empty
55     */
56    Iter begin();
57
58    /**
59     * Gets the last valid iterator. This is always valid, even on an empty.
60     * However, it can never be dereferenced. Useful as a loop terminator.
61     * @return  an iterator that is just beyond the last item in sorted order.
62     */
63    Iter end();
64
65    /**
66     * @return  an iterator that to the last item in sorted order, or end() if
67     * empty.
68     */
69    Iter last();
70
71    /**
72     * Finds an occurrence of an item.
73     * @param t     the item to find.
74     * @return an iterator to a set element equal to t or end() if none exists.
75     */
76    Iter find(const T& t);
77
78private:
79    GrRedBlackTree<T, C> fRBTree;
80
81    const C fComp;
82};
83
84template <typename T, typename C>
85class GrOrderedSet<T,C>::Iter {
86public:
87    Iter() {}
88    Iter(const Iter& i) { fTreeIter = i.fTreeIter; }
89    Iter& operator =(const Iter& i) {
90        fTreeIter = i.fTreeIter;
91        return *this;
92    }
93    const T& operator *() const { return *fTreeIter; }
94    bool operator ==(const Iter& i) const {
95        return fTreeIter == i.fTreeIter;
96    }
97    bool operator !=(const Iter& i) const { return !(*this == i); }
98    Iter& operator ++() {
99        ++fTreeIter;
100        return *this;
101    }
102    Iter& operator --() {
103        --fTreeIter;
104        return *this;
105    }
106    const typename GrRedBlackTree<T,C>::Iter& getTreeIter() const {
107        return fTreeIter;
108    }
109
110private:
111    friend class GrOrderedSet;
112    explicit Iter(typename GrRedBlackTree<T, C>::Iter iter) {
113        fTreeIter = iter;
114    }
115    typename GrRedBlackTree<T,C>::Iter fTreeIter;
116};
117
118template <typename T, typename C>
119typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::begin() {
120    return Iter(fRBTree.begin());
121}
122
123template <typename T, typename C>
124typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::end() {
125    return Iter(fRBTree.end());
126}
127
128template <typename T, typename C>
129typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::last() {
130    return Iter(fRBTree.last());
131}
132
133template <typename T, typename C>
134typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::find(const T& t) {
135    return Iter(fRBTree.find(t));
136}
137
138template <typename T, typename C>
139typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::insert(const T& t) {
140    if (fRBTree.find(t) == fRBTree.end()) {
141        return Iter(fRBTree.insert(t));
142    } else {
143        return Iter(fRBTree.find(t));
144    }
145}
146
147template <typename T, typename C>
148void GrOrderedSet<T,C>::remove(const typename GrOrderedSet<T,C>::Iter& iter) {
149    if (this->end() != iter) {
150        fRBTree.remove(iter.getTreeIter());
151    }
152}
153
154#endif
155