ROSE  0.9.11.56
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 
120  void add(const T& item) { push(item); }
121  void add(const std::vector<T> &items) { push(items.begin(), items.end()); }
122  void add(const std::set<T> &items) { push(items.begin(), items.end()); }
126  T take() { return shift(); }
127 
128 private:
129  void removed(const T&);
130  std::list<T> list_;
131  std::map<T, size_t, key_compare> map_;
132  size_t nitems_;
133  bool use_map_;
134 };
135 
140 template<typename T, class Compare = std::less<T> >
141 class WorkListUnique: public WorkList<T, Compare> {
142 public:
144 };
145 
150 template<typename T, class Compare = std::less<T> >
151 class WorkListNonUnique: public WorkList<T, Compare> {
152 public:
154 };
155 
156 /*******************************************************************************************************************************
157  * Template member functions
158  *******************************************************************************************************************************/
159 
160 template<typename T, class Compare>
161 bool
162 WorkList<T, Compare>::unshift(const T &item, boost::tribool check_uniqueness)
163 {
164  if (indeterminate(check_uniqueness))
165  check_uniqueness = use_map_;
166  if (use_map_) {
167  std::pair<typename std::map<T, size_t, Compare>::iterator, bool> found = map_.insert(std::pair<T, size_t>(item, 1));
168  if (check_uniqueness && !found.second)
169  return false;
170  if (!found.second)
171  ++found.first->second;
172  } else if (check_uniqueness) {
173  if (std::find(list_.begin(), list_.end(), item)!=list_.end())
174  return false;
175  }
176  list_.push_front(item);
177  ++nitems_;
178  return true;
179 }
180 
181 template<typename T, class Compare>
182 template<class Iterator>
183 size_t
184 WorkList<T, Compare>::unshift(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness)
185 {
186  size_t retval = 0;
187  for (Iterator i=begin; i!=end; ++i) {
188  if (unshift(*i, check_uniqueness))
189  ++retval;
190  }
191  return retval;
192 }
193 
194 template<typename T, class Compare>
195 bool
196 WorkList<T, Compare>::push(const T &item, boost::tribool check_uniqueness)
197 {
198  if (indeterminate(check_uniqueness))
199  check_uniqueness = use_map_;
200  if (use_map_) {
201  std::pair<typename std::map<T, size_t, Compare>::iterator, bool> found = map_.insert(std::make_pair(item, 1));
202  if (check_uniqueness && !found.second)
203  return false;
204  if (!found.second)
205  ++found.first->second;
206  } else if (check_uniqueness) {
207  if (std::find(list_.begin(), list_.end(), item)!=list_.end())
208  return false;
209  }
210  list_.push_back(item);
211  ++nitems_;
212  return true;
213 }
214 
215 template<typename T, class Compare>
216 template<class Iterator>
217 size_t
218 WorkList<T, Compare>::push(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness)
219 {
220  size_t retval = 0;
221  for (Iterator i=begin; i!=end; ++i) {
222  if (push(*i, check_uniqueness))
223  ++retval;
224  }
225  return retval;
226 }
227 
228 template<typename T, class Compare>
229 T
231 {
232  assert(!empty());
233  T item = list_.front();
234  list_.pop_front();
235  removed(item);
236  return item;
237 }
238 
239 template<typename T, class Compare>
240 T
242 {
243  assert(!empty());
244  T item = list_.back();
245  list_.pop_back();
246  removed(item);
247  return item;
248 }
249 
250 template<typename T, class Compare>
251 const T&
253 {
254  assert(!empty());
255  return list_.front();
256 }
257 
258 template<typename T, class Compare>
259 const T&
261 {
262  assert(!empty());
263  return list_.back();
264 }
265 
266 template<typename T, class Compare>
267 void
268 WorkList<T, Compare>::removed(const T &item)
269 {
270  if (use_map_) {
271  typename std::map<T, size_t>::iterator found = map_.find(item);
272  assert(found!=map_.end());
273  if (found->second > 1) {
274  --found->second;
275  } else {
276  map_.erase(found);
277  }
278  }
279  --nitems_;
280 }
281 
282 #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
void add(const T &item)
Adds an item(s) to the end of the queue.
Definition: WorkLists.h:120
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:230
A version of WorkList that does not check for uniqueness by default.
Definition: WorkLists.h:151
A version of WorkList that checks for uniqueness by default.
Definition: WorkLists.h:141
void add(const std::set< T > &items)
Adds an item(s) to the end of the queue.
Definition: WorkLists.h:122
const T & back() const
Returns the object at the front/back of the list without removing it.
Definition: WorkLists.h:260
T take()
Remove and return an item from the front of the work list.
Definition: WorkLists.h:126
T pop()
Remove an item from the back of the work list.
Definition: WorkLists.h:241
bool push(const T &, boost::tribool check_uniqueness=boost::logic::indeterminate)
Add an item to the back of the work list.
Definition: WorkLists.h:196
const T & front() const
Returns the object at the front/back of the list without removing it.
Definition: WorkLists.h:252
bool unshift(const T &, boost::tribool check_uniqueness=boost::indeterminate)
Add an item to the front of the work list.
Definition: WorkLists.h:162
bool empty() const
Returns true if this work list is empty.
Definition: WorkLists.h:66
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:121