ROSE  0.11.2.0
WorkLists.h
1 // FIXME[Robb Matzke 2020-03-08]: this is generic support stuff and should be moved to roseSupport directory.
2 
3 #ifndef ROSE_WorkLists_H
4 #define ROSE_WorkLists_H
5 
6 #include <boost/logic/tribool.hpp>
7 #include <cassert>
8 #include <list>
9 #include <map>
10 
59 template<typename T, class Compare = std::less<T> >
60 class WorkList {
61 public:
62  typedef T value_type;
63  typedef Compare key_compare;
64 
65  explicit WorkList(bool check_uniqueness=false): nitems_(0), use_map_(check_uniqueness) {}
66 
68  bool empty() const { return 0 == nitems_; }
69 
71  size_t size() const { return nitems_; }
72 
74  void clear() { list_.clear(); map_.clear(); }
75 
77  bool exists(const T &item) const {
78  return use_map_ ? map_.find(item)!=map_.end() : std::find(list_.begin(), list_.end(), item)!=list_.end();
79  }
80 
83  bool unshift(const T&, boost::tribool check_uniqueness=boost::indeterminate);
84 
88  template<class Iterator>
89  size_t unshift(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness=boost::indeterminate);
90 
92  T shift();
93 
96  bool push(const T&, boost::tribool check_uniqueness=boost::logic::indeterminate);
97 
101  template<class Iterator>
102  size_t push(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness=boost::indeterminate);
103 
105  T pop();
106 
111  const T& front() const;
112  const T& back() const;
115  // These are here for compatibility with another WorkList API
118 
122  void add(const T& item) { push(item); }
123  void add(const std::vector<T> &items) { push(items.begin(), items.end()); }
124  void add(const std::set<T> &items) { push(items.begin(), items.end()); }
128  T take() { return shift(); }
129 
130 private:
131  void removed(const T&);
132  std::list<T> list_;
133  std::map<T, size_t, key_compare> map_;
134  size_t nitems_;
135  bool use_map_;
136 };
137 
142 template<typename T, class Compare = std::less<T> >
143 class WorkListUnique: public WorkList<T, Compare> {
144 public:
146 };
147 
152 template<typename T, class Compare = std::less<T> >
153 class WorkListNonUnique: public WorkList<T, Compare> {
154 public:
156 };
157 
158 /*******************************************************************************************************************************
159  * Template member functions
160  *******************************************************************************************************************************/
161 
162 template<typename T, class Compare>
163 bool
164 WorkList<T, Compare>::unshift(const T &item, boost::tribool check_uniqueness)
165 {
166  if (indeterminate(check_uniqueness))
167  check_uniqueness = use_map_;
168  if (use_map_) {
169  std::pair<typename std::map<T, size_t, Compare>::iterator, bool> found = map_.insert(std::pair<T, size_t>(item, 1));
170  if (check_uniqueness && !found.second)
171  return false;
172  if (!found.second)
173  ++found.first->second;
174  } else if (check_uniqueness) {
175  if (std::find(list_.begin(), list_.end(), item)!=list_.end())
176  return false;
177  }
178  list_.push_front(item);
179  ++nitems_;
180  return true;
181 }
182 
183 template<typename T, class Compare>
184 template<class Iterator>
185 size_t
186 WorkList<T, Compare>::unshift(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness)
187 {
188  size_t retval = 0;
189  for (Iterator i=begin; i!=end; ++i) {
190  if (unshift(*i, check_uniqueness))
191  ++retval;
192  }
193  return retval;
194 }
195 
196 template<typename T, class Compare>
197 bool
198 WorkList<T, Compare>::push(const T &item, boost::tribool check_uniqueness)
199 {
200  if (indeterminate(check_uniqueness))
201  check_uniqueness = use_map_;
202  if (use_map_) {
203  std::pair<typename std::map<T, size_t, Compare>::iterator, bool> found = map_.insert(std::make_pair(item, 1));
204  if (check_uniqueness && !found.second)
205  return false;
206  if (!found.second)
207  ++found.first->second;
208  } else if (check_uniqueness) {
209  if (std::find(list_.begin(), list_.end(), item)!=list_.end())
210  return false;
211  }
212  list_.push_back(item);
213  ++nitems_;
214  return true;
215 }
216 
217 template<typename T, class Compare>
218 template<class Iterator>
219 size_t
220 WorkList<T, Compare>::push(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness)
221 {
222  size_t retval = 0;
223  for (Iterator i=begin; i!=end; ++i) {
224  if (push(*i, check_uniqueness))
225  ++retval;
226  }
227  return retval;
228 }
229 
230 template<typename T, class Compare>
231 T
233 {
234  assert(!empty());
235  T item = list_.front();
236  list_.pop_front();
237  removed(item);
238  return item;
239 }
240 
241 template<typename T, class Compare>
242 T
244 {
245  assert(!empty());
246  T item = list_.back();
247  list_.pop_back();
248  removed(item);
249  return item;
250 }
251 
252 template<typename T, class Compare>
253 const T&
255 {
256  assert(!empty());
257  return list_.front();
258 }
259 
260 template<typename T, class Compare>
261 const T&
263 {
264  assert(!empty());
265  return list_.back();
266 }
267 
268 template<typename T, class Compare>
269 void
270 WorkList<T, Compare>::removed(const T &item)
271 {
272  if (use_map_) {
273  typename std::map<T, size_t>::iterator found = map_.find(item);
274  assert(found!=map_.end());
275  if (found->second > 1) {
276  --found->second;
277  } else {
278  map_.erase(found);
279  }
280  }
281  --nitems_;
282 }
283 
284 #endif
bool exists(const T &item) const
Return true if the specified item is already on the work list.
Definition: WorkLists.h:77
List of things to work on.
Definition: WorkLists.h:60
void add(const T &item)
Adds an item(s) to the end of the queue.
Definition: WorkLists.h:122
void clear()
Reset the list to an empty state.
Definition: WorkLists.h:74
T shift()
Remove and return the item from the front of the work list.
Definition: WorkLists.h:232
A version of WorkList that does not check for uniqueness by default.
Definition: WorkLists.h:153
A version of WorkList that checks for uniqueness by default.
Definition: WorkLists.h:143
void add(const std::set< T > &items)
Adds an item(s) to the end of the queue.
Definition: WorkLists.h:124
const T & back() const
Returns the object at the front/back of the list without removing it.
Definition: WorkLists.h:262
T take()
Remove and return an item from the front of the work list.
Definition: WorkLists.h:128
T pop()
Remove an item from the back of the work list.
Definition: WorkLists.h:243
bool push(const T &, boost::tribool check_uniqueness=boost::logic::indeterminate)
Add an item to the back of the work list.
Definition: WorkLists.h:198
const T & front() const
Returns the object at the front/back of the list without removing it.
Definition: WorkLists.h:254
bool unshift(const T &, boost::tribool check_uniqueness=boost::indeterminate)
Add an item to the front of the work list.
Definition: WorkLists.h:164
bool empty() const
Returns true if this work list is empty.
Definition: WorkLists.h:68
size_t size() const
Returns the number of items in the work list.
Definition: WorkLists.h:71
void add(const std::vector< T > &items)
Adds an item(s) to the end of the queue.
Definition: WorkLists.h:123