3 #ifndef ROSE_WorkLists_H
4 #define ROSE_WorkLists_H
6 #include <boost/logic/tribool.hpp>
59 template<
typename T,
class Compare = std::less<T> >
63 typedef Compare key_compare;
65 explicit WorkList(
bool check_uniqueness=
false): nitems_(0), use_map_(check_uniqueness) {}
68 bool empty()
const {
return 0 == nitems_; }
71 size_t size()
const {
return nitems_; }
74 void clear() { list_.clear(); map_.clear(); }
78 return use_map_ ? map_.find(item)!=map_.end() : std::find(list_.begin(), list_.end(), item)!=list_.end();
83 bool unshift(
const T&, boost::tribool check_uniqueness=boost::indeterminate);
88 template<
class Iterator>
89 size_t unshift(
const Iterator &begin,
const Iterator &end, boost::tribool check_uniqueness=boost::indeterminate);
96 bool push(
const T&, boost::tribool check_uniqueness=boost::logic::indeterminate);
101 template<
class Iterator>
102 size_t push(
const Iterator &begin,
const Iterator &end, boost::tribool check_uniqueness=boost::indeterminate);
111 const T&
front()
const;
112 const T&
back()
const;
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()); }
131 void removed(
const T&);
133 std::map<T, size_t, key_compare> map_;
142 template<
typename T,
class Compare = std::less<T> >
152 template<
typename T,
class Compare = std::less<T> >
162 template<
typename T,
class Compare>
166 if (indeterminate(check_uniqueness))
167 check_uniqueness = 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)
173 ++found.first->second;
174 }
else if (check_uniqueness) {
175 if (std::find(list_.begin(), list_.end(), item)!=list_.end())
178 list_.push_front(item);
183 template<
typename T,
class Compare>
184 template<
class Iterator>
189 for (Iterator i=begin; i!=end; ++i) {
190 if (unshift(*i, check_uniqueness))
196 template<
typename T,
class Compare>
200 if (indeterminate(check_uniqueness))
201 check_uniqueness = 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)
207 ++found.first->second;
208 }
else if (check_uniqueness) {
209 if (std::find(list_.begin(), list_.end(), item)!=list_.end())
212 list_.push_back(item);
217 template<
typename T,
class Compare>
218 template<
class Iterator>
223 for (Iterator i=begin; i!=end; ++i) {
224 if (push(*i, check_uniqueness))
230 template<
typename T,
class Compare>
235 T item = list_.front();
241 template<
typename T,
class Compare>
246 T item = list_.back();
252 template<
typename T,
class Compare>
257 return list_.front();
260 template<
typename T,
class Compare>
268 template<
typename T,
class Compare>
273 typename std::map<T, size_t>::iterator found = map_.find(item);
274 assert(found!=map_.end());
275 if (found->second > 1) {
bool exists(const T &item) const
Return true if the specified item is already on the work list.
List of things to work on.
void add(const T &item)
Adds an item(s) to the end of the queue.
void clear()
Reset the list to an empty state.
T shift()
Remove and return the item from the front of the work list.
A version of WorkList that does not check for uniqueness by default.
A version of WorkList that checks for uniqueness by default.
void add(const std::set< T > &items)
Adds an item(s) to the end of the queue.
const T & back() const
Returns the object at the front/back of the list without removing it.
T take()
Remove and return an item from the front of the work list.
T pop()
Remove an item from the back of the work list.
bool push(const T &, boost::tribool check_uniqueness=boost::logic::indeterminate)
Add an item to the back of the work list.
const T & front() const
Returns the object at the front/back of the list without removing it.
bool unshift(const T &, boost::tribool check_uniqueness=boost::indeterminate)
Add an item to the front of the work list.
bool empty() const
Returns true if this work list is empty.
size_t size() const
Returns the number of items in the work list.
void add(const std::vector< T > &items)
Adds an item(s) to the end of the queue.