WorkLists.h

Go to the documentation of this file.

#ifndef ROSE_WorkLists_H
#define ROSE_WorkLists_H

#include <boost/logic/tribool.hpp>
#include <cassert>
#include <list>
#include <map>

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::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

    bool isEmpty() const __attribute__((deprecated));

    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(); }

    const T& examine() const __attribute__((deprecated));

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_;
}

// deprecated
template<typename T, class Compare>
bool
WorkList<T, Compare>::isEmpty() const
{
    return empty();
}

// deprecated
template<typename T, class Compare>
const T&
WorkList<T, Compare>::examine() const
{
    return front();
}

#endif