ROSE  0.9.9.139
WorkLists.h
1 #ifndef ROSE_WorkLists_H
2 #define ROSE_WorkLists_H
3 
4 #include <boost/logic/tribool.hpp>
5 #include <cassert>
6 #include <list>
7 #include <map>
8 
57 template<typename T, class Compare = std::less<T> >
58 class WorkList {
59 public:
60  typedef T value_type;
61  typedef Compare key_compare;
62 
63  explicit WorkList(bool check_uniqueness=false): nitems_(0), use_map_(check_uniqueness) {}
64 
66  bool empty() const { return 0 == nitems_; }
67 
69  size_t size() const { return nitems_; }
70 
72  void clear() { list_.clear(); map_.clear(); }
73 
75  bool exists(const T &item) const {
76  return use_map_ ? map_.find(item)!=map_.end() : std::find(list_.begin(), list_.end(), item)!=list_.end();
77  }
78 
81  bool unshift(const T&, boost::tribool check_uniqueness=boost::indeterminate);
82 
86  template<class Iterator>
87  size_t unshift(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness=boost::indeterminate);
88 
90  T shift();
91 
94  bool push(const T&, boost::tribool check_uniqueness=boost::logic::indeterminate);
95 
99  template<class Iterator>
100  size_t push(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness=boost::indeterminate);
101 
103  T pop();
104 
109  const T& front() const;
110  const T& back() const;
113  // These are here for compatibility with another WorkList API
116 
118  bool isEmpty() const ROSE_DEPRECATED("use empty instead");
119 
123  void add(const T& item) { push(item); }
124  void add(const std::vector<T> &items) { push(items.begin(), items.end()); }
125  void add(const std::set<T> &items) { push(items.begin(), items.end()); }
129  T take() { return shift(); }
130 
132  const T& examine() const ROSE_DEPRECATED("use front instead");
133 
134 private:
135  void removed(const T&);
136  std::list<T> list_;
137  std::map<T, size_t, key_compare> map_;
138  size_t nitems_;
139  bool use_map_;
140 };
141 
146 template<typename T, class Compare = std::less<T> >
147 class WorkListUnique: public WorkList<T, Compare> {
148 public:
150 };
151 
156 template<typename T, class Compare = std::less<T> >
157 class WorkListNonUnique: public WorkList<T, Compare> {
158 public:
160 };
161 
162 /*******************************************************************************************************************************
163  * Template member functions
164  *******************************************************************************************************************************/
165 
166 template<typename T, class Compare>
167 bool
168 WorkList<T, Compare>::unshift(const T &item, boost::tribool check_uniqueness)
169 {
170  if (indeterminate(check_uniqueness))
171  check_uniqueness = use_map_;
172  if (use_map_) {
173  std::pair<typename std::map<T, size_t, Compare>::iterator, bool> found = map_.insert(std::pair<T, size_t>(item, 1));
174  if (check_uniqueness && !found.second)
175  return false;
176  if (!found.second)
177  ++found.first->second;
178  } else if (check_uniqueness) {
179  if (std::find(list_.begin(), list_.end(), item)!=list_.end())
180  return false;
181  }
182  list_.push_front(item);
183  ++nitems_;
184  return true;
185 }
186 
187 template<typename T, class Compare>
188 template<class Iterator>
189 size_t
190 WorkList<T, Compare>::unshift(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness)
191 {
192  size_t retval = 0;
193  for (Iterator i=begin; i!=end; ++i) {
194  if (unshift(*i, check_uniqueness))
195  ++retval;
196  }
197  return retval;
198 }
199 
200 template<typename T, class Compare>
201 bool
202 WorkList<T, Compare>::push(const T &item, boost::tribool check_uniqueness)
203 {
204  if (indeterminate(check_uniqueness))
205  check_uniqueness = use_map_;
206  if (use_map_) {
207  std::pair<typename std::map<T, size_t, Compare>::iterator, bool> found = map_.insert(std::make_pair(item, 1));
208  if (check_uniqueness && !found.second)
209  return false;
210  if (!found.second)
211  ++found.first->second;
212  } else if (check_uniqueness) {
213  if (std::find(list_.begin(), list_.end(), item)!=list_.end())
214  return false;
215  }
216  list_.push_back(item);
217  ++nitems_;
218  return true;
219 }
220 
221 template<typename T, class Compare>
222 template<class Iterator>
223 size_t
224 WorkList<T, Compare>::push(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness)
225 {
226  size_t retval = 0;
227  for (Iterator i=begin; i!=end; ++i) {
228  if (push(*i, check_uniqueness))
229  ++retval;
230  }
231  return retval;
232 }
233 
234 template<typename T, class Compare>
235 T
237 {
238  assert(!empty());
239  T item = list_.front();
240  list_.pop_front();
241  removed(item);
242  return item;
243 }
244 
245 template<typename T, class Compare>
246 T
248 {
249  assert(!empty());
250  T item = list_.back();
251  list_.pop_back();
252  removed(item);
253  return item;
254 }
255 
256 template<typename T, class Compare>
257 const T&
259 {
260  assert(!empty());
261  return list_.front();
262 }
263 
264 template<typename T, class Compare>
265 const T&
267 {
268  assert(!empty());
269  return list_.back();
270 }
271 
272 template<typename T, class Compare>
273 void
274 WorkList<T, Compare>::removed(const T &item)
275 {
276  if (use_map_) {
277  typename std::map<T, size_t>::iterator found = map_.find(item);
278  assert(found!=map_.end());
279  if (found->second > 1) {
280  --found->second;
281  } else {
282  map_.erase(found);
283  }
284  }
285  --nitems_;
286 }
287 
288 // deprecated
289 template<typename T, class Compare>
290 bool
292 {
293  return empty();
294 }
295 
296 // deprecated
297 template<typename T, class Compare>
298 const T&
300 {
301  return front();
302 }
303 
304 #endif
bool exists(const T &item) const
Return true if the specified item is already on the work list.
Definition: WorkLists.h:75
List of things to work on.
Definition: WorkLists.h:58
STL namespace.
void add(const T &item)
Adds an item(s) to the end of the queue.
Definition: WorkLists.h:123
void clear()
Reset the list to an empty state.
Definition: WorkLists.h:72
T shift()
Remove and return the item from the front of the work list.
Definition: WorkLists.h:236
A version of WorkList that does not check for uniqueness by default.
Definition: WorkLists.h:157
A version of WorkList that checks for uniqueness by default.
Definition: WorkLists.h:147
void add(const std::set< T > &items)
Adds an item(s) to the end of the queue.
Definition: WorkLists.h:125
const T & back() const
Returns the object at the front/back of the list without removing it.
Definition: WorkLists.h:266
T take()
Remove and return an item from the front of the work list.
Definition: WorkLists.h:129
T pop()
Remove an item from the back of the work list.
Definition: WorkLists.h:247
bool push(const T &, boost::tribool check_uniqueness=boost::logic::indeterminate)
Add an item to the back of the work list.
Definition: WorkLists.h:202
const T & front() const
Returns the object at the front/back of the list without removing it.
Definition: WorkLists.h:258
bool unshift(const T &, boost::tribool check_uniqueness=boost::indeterminate)
Add an item to the front of the work list.
Definition: WorkLists.h:168
bool empty() const
Returns true if this work list is empty.
Definition: WorkLists.h:66
bool isEmpty() const ROSE_DEPRECATED("use empty instead")
An alias for empty().
Definition: WorkLists.h:291
const T & examine() const ROSE_DEPRECATED("use front instead")
Alias for front().
Definition: WorkLists.h:299
size_t size() const
Returns the number of items in the work list.
Definition: WorkLists.h:69
void add(const std::vector< T > &items)
Adds an item(s) to the end of the queue.
Definition: WorkLists.h:124