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