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
13 template <typename T, typename C = GrLess<T> >
14 class GrOrderedSet : SkNoncopyable {
15 public:
16 /**
17 * Creates an empty set
18 */
GrOrderedSet()19 GrOrderedSet() : fComp() {}
~GrOrderedSet()20 ~GrOrderedSet() {}
21
22 class Iter;
23
24 /**
25 * @return true if there are no items in the set, false otherwise.
26 */
empty()27 bool empty() const { return fRBTree.empty(); }
28
29 /**
30 * @return the number of items in the set.
31 */
count()32 int count() const { return fRBTree.count(); }
33
34 /**
35 * Removes all items in the set
36 */
reset()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
78 private:
79 GrRedBlackTree<T, C> fRBTree;
80
81 const C fComp;
82 };
83
84 template <typename T, typename C>
85 class GrOrderedSet<T,C>::Iter {
86 public:
Iter()87 Iter() {}
Iter(const Iter & i)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 }
getTreeIter()106 const typename GrRedBlackTree<T,C>::Iter& getTreeIter() const {
107 return fTreeIter;
108 }
109
110 private:
111 friend class GrOrderedSet;
Iter(typename GrRedBlackTree<T,C>::Iter iter)112 explicit Iter(typename GrRedBlackTree<T, C>::Iter iter) {
113 fTreeIter = iter;
114 }
115 typename GrRedBlackTree<T,C>::Iter fTreeIter;
116 };
117
118 template <typename T, typename C>
begin()119 typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::begin() {
120 return Iter(fRBTree.begin());
121 }
122
123 template <typename T, typename C>
end()124 typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::end() {
125 return Iter(fRBTree.end());
126 }
127
128 template <typename T, typename C>
last()129 typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::last() {
130 return Iter(fRBTree.last());
131 }
132
133 template <typename T, typename C>
find(const T & t)134 typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::find(const T& t) {
135 return Iter(fRBTree.find(t));
136 }
137
138 template <typename T, typename C>
insert(const T & t)139 typename 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
147 template <typename T, typename C>
remove(const typename GrOrderedSet<T,C>::Iter & iter)148 void 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