ROSE  0.10.0.0
Tracker.h
1 // WARNING: Changes to this file must be contributed back to Sawyer or else they will
2 // be clobbered by the next update from Sawyer. The Sawyer repository is at
3 // https://github.com/matzke1/sawyer.
4 
5 
6 
7 
8 #ifndef Sawyer_Container_Tracker_H
9 #define Sawyer_Container_Tracker_H
10 
11 #include <Sawyer/Set.h>
12 #include <Sawyer/Synchronization.h>
13 
14 namespace Sawyer {
15 namespace Container {
16 
21 template<class Key>
23  Set<Key> set;
24 public:
25  void clear() {
26  set.clear();
27  }
28  bool exists(const Key &key) const {
29  return set.exists(key);
30  }
31  bool insert(const Key &key) {
32  return set.insert(key);
33  }
34 };
35 
40 template<class Key>
42  std::vector<bool> bvec;
43 public:
44  void clear() {
45  bvec.clear();
46  }
47  bool exists(const Key &key) const {
48  return key < bvec.size() && bvec[key];
49  }
50  bool insert(const Key &key) {
51  bool retval = !exists(key);
52  if (key >= bvec.size())
53  bvec.resize(key+1, false);
54  bvec[key] = true;
55  return retval;
56  }
57 };
58 
63 template<class Key>
65  boost::unordered_set<Key> set;
66 public:
67  void clear() {
68  set.clear();
69  }
70  bool exists(const Key &key) const {
71  return set.find(key) != set.end();
72  }
73  bool insert(const Key &key) {
74  return set.insert(key).second;
75  }
76 };
77 
79 template<class Key>
80 struct TrackerTraits {
88 };
89 
164 template<class T, class K = T, class Traits = TrackerTraits<K> >
165 class Tracker {
166 public:
168  typedef T Value;
169 
173  typedef K Key;
174 
175 private:
176  mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects the following data members.
177  typename Traits::Index index_;
178 
179 public:
183  void clear() {
184  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
185  index_.clear();
186  }
187 
193  bool testAndSet(const Value &value) {
194  Key key(value);
195  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
196  return !index_.insert(key);
197  }
198 
200  bool operator()(const Value &value) {
201  return testAndSet(value);
202  }
203 
209  bool wasSeen(const Value &value) const {
210  Key key(value);
211  SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
212  return index_.exists(key);
213  }
214 
221  bool insert(const Value &value) {
222  return !testAndSet(value);
223  }
224 
245  void removeIfSeen(std::vector<Value> &vector) {
246  size_t nSaved = 0;
247  for (size_t i = 0; i < vector.size(); ++i) {
248  if (insert(vector[i]))
249  vector[nSaved++] = vector[i];
250  }
251  vector.resize(nSaved);
252  }
253 };
254 
255 } // namespace
256 } // namespace
257 
258 #endif
T Value
Type of values represented by the tracker.
Definition: Tracker.h:168
void removeIfSeen(std::vector< Value > &vector)
Remove and track items from a vector.
Definition: Tracker.h:245
Traits for Tracker.
Definition: Tracker.h:80
void clear()
Erase all values.
Definition: Set.h:262
bool insert(const Value &value)
Insert a value.
Definition: Set.h:222
bool operator()(const Value &value)
Unary operator is the same as testAndSet.
Definition: Tracker.h:200
bool insert(const Value &value)
Cause this tracker to see a value.
Definition: Tracker.h:221
K Key
Key type for the values represented by the tracker.
Definition: Tracker.h:173
bool exists(const Value &value) const
Whether a value exists.
Definition: Set.h:139
Set-based index referenced by TrackerTraits.
Definition: Tracker.h:22
Name space for the entire library.
bool wasSeen(const Value &value) const
Test whether a value has been encountered previously.
Definition: Tracker.h:209
Hash-based index referenced by TrackerTraits.
Definition: Tracker.h:64
Tracks whether something has been seen before.
Definition: Tracker.h:165
Vector-based index referenced by TrackerTraits.
Definition: Tracker.h:41
bool testAndSet(const Value &value)
Test and then insert the value.
Definition: Tracker.h:193
TrackerSetIndex< Key > Index
Type of index for storing member keys.
Definition: Tracker.h:87
void clear()
Make this tracker forget everything it has seen.
Definition: Tracker.h:183