OLD | NEW |
| (Empty) |
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 */ | |
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 | |
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: | |
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 | |
110 private: | |
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 | |
118 template <typename T, typename C> | |
119 typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::begin() { | |
120 return Iter(fRBTree.begin()); | |
121 } | |
122 | |
123 template <typename T, typename C> | |
124 typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::end() { | |
125 return Iter(fRBTree.end()); | |
126 } | |
127 | |
128 template <typename T, typename C> | |
129 typename GrOrderedSet<T,C>::Iter GrOrderedSet<T,C>::last() { | |
130 return Iter(fRBTree.last()); | |
131 } | |
132 | |
133 template <typename T, typename C> | |
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> | |
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> | |
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 | |
OLD | NEW |