WorkLists.h

// FIXME[Robb Matzke 2020-03-08]: this is generic support stuff and should be moved to roseSupport directory.
 
#ifndef ROSE_WorkLists_H
#define ROSE_WorkLists_H
 
#include <boost/logic/tribool.hpp>
 
#include <algorithm>
#include <cassert>
#include <list>
#include <map>
#include <set>
#include <vector>
 
template<typename T, class Compare = std::less<T> >
class WorkList {
public:
    typedef T value_type;
    typedef Compare key_compare;
 
    explicit WorkList(bool check_uniqueness=false): nitems_(0), use_map_(check_uniqueness) {}
 
    bool empty() const { return 0 == nitems_; }
 
    size_t size() const { return nitems_; }
 
    void clear() { list_.clear(); map_.clear(); }
 
    bool exists(const T &item) const {
        return use_map_ ? map_.find(item)!=map_.end() : std::find(list_.begin(), list_.end(), item)!=list_.end();
    }
 
    bool unshift(const T&, boost::tribool check_uniqueness=boost::indeterminate);
 
    template<class Iterator>
    size_t unshift(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness=boost::indeterminate);
 
    T shift();
 
    bool push(const T&, boost::tribool check_uniqueness=boost::logic::indeterminate);
    
    template<class Iterator>
    size_t push(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness=boost::indeterminate);
 
    T pop();
 
    const T& front() const;
    const T& back() const;
    // These are here for compatibility with another WorkList API
 
    void add(const T& item) { push(item); }
    void add(const std::vector<T> &items) { push(items.begin(), items.end()); }
    void add(const std::set<T> &items) { push(items.begin(), items.end()); }
    T take() { return shift(); }
 
private:
    void removed(const T&);
    std::list<T> list_;
    std::map<T, size_t, key_compare> map_;
    size_t nitems_;
    bool use_map_;
};
 
template<typename T, class Compare = std::less<T> >
class WorkListUnique: public WorkList<T, Compare> {
public:
    WorkListUnique(): WorkList<T, Compare>(true) {}
};
 
template<typename T, class Compare = std::less<T> >
class WorkListNonUnique: public WorkList<T, Compare> {
public:
    WorkListNonUnique(): WorkList<T, Compare>(false) {}
};
 
/*******************************************************************************************************************************
 * Template member functions
 *******************************************************************************************************************************/
 
template<typename T, class Compare>
bool
WorkList<T, Compare>::unshift(const T &item, boost::tribool check_uniqueness)
{
    if (indeterminate(check_uniqueness))
        check_uniqueness = use_map_;
    if (use_map_) {
        std::pair<typename std::map<T, size_t, Compare>::iterator, bool> found = map_.insert(std::pair<T, size_t>(item, 1));
        if (check_uniqueness && !found.second)
            return false;
        if (!found.second)
            ++found.first->second;
    } else if (check_uniqueness) {
        if (std::find(list_.begin(), list_.end(), item)!=list_.end())
            return false;
    }
    list_.push_front(item);
    ++nitems_;
    return true;
}
 
template<typename T, class Compare>
template<class Iterator>
size_t
WorkList<T, Compare>::unshift(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness)
{
    size_t retval = 0;
    for (Iterator i=begin; i!=end; ++i) {
        if (unshift(*i, check_uniqueness))
            ++retval;
    }
    return retval;
}
 
template<typename T, class Compare>
bool
WorkList<T, Compare>::push(const T &item, boost::tribool check_uniqueness)
{
    if (indeterminate(check_uniqueness))
        check_uniqueness = use_map_;
    if (use_map_) {
        std::pair<typename std::map<T, size_t, Compare>::iterator, bool> found = map_.insert(std::make_pair(item, 1));
        if (check_uniqueness && !found.second)
            return false;
        if (!found.second)
            ++found.first->second;
    } else if (check_uniqueness) {
        if (std::find(list_.begin(), list_.end(), item)!=list_.end())
            return false;
    }
    list_.push_back(item);
    ++nitems_;
    return true;
}
 
template<typename T, class Compare>
template<class Iterator>
size_t
WorkList<T, Compare>::push(const Iterator &begin, const Iterator &end, boost::tribool check_uniqueness)
{
    size_t retval = 0;
    for (Iterator i=begin; i!=end; ++i) {
        if (push(*i, check_uniqueness))
            ++retval;
    }
    return retval;
}
 
template<typename T, class Compare>
T
WorkList<T, Compare>::shift()
{
    assert(!empty());
    T item = list_.front();
    list_.pop_front();
    removed(item);
    return item;
}
 
template<typename T, class Compare>
T
WorkList<T, Compare>::pop()
{
    assert(!empty());
    T item = list_.back();
    list_.pop_back();
    removed(item);
    return item;
}
 
template<typename T, class Compare>
const T&
WorkList<T, Compare>::front() const
{
    assert(!empty());
    return list_.front();
}
 
template<typename T, class Compare>
const T&
WorkList<T, Compare>::back() const
{
    assert(!empty());
    return list_.back();
}
 
template<typename T, class Compare>
void
WorkList<T, Compare>::removed(const T &item)
{
    if (use_map_) {
        typename std::map<T, size_t>::iterator found = map_.find(item);
        assert(found!=map_.end());
        if (found->second > 1) {
            --found->second;
        } else {
            map_.erase(found);
        }
    }
    --nitems_;
}
 
#endif