DistinctList.h

// WARNING: Changes to this file must be contributed back to Sawyer or else they will
//          be clobbered by the next update from Sawyer.  The Sawyer repository is at
//          https://github.com/matzke1/sawyer.




#ifndef Sawyer_DistinctList_H
#define Sawyer_DistinctList_H

#include <boost/foreach.hpp>
#include <list>
#include <Sawyer/Map.h>
#include <Sawyer/Sawyer.h>
#include <stdexcept>

namespace Sawyer {
namespace Container {

template<class T, class Cmp = std::less<T> >
class DistinctList {
public:
    typedef T Item;
    typedef Cmp Comparator;
    typedef std::list<Item> Items;                      // iterators must be insert- and erase-stable

private:
    typedef Sawyer::Container::Map<Item, typename Items::iterator, Comparator> Map;
    Items items_;
    Map position_;

public:
    DistinctList() {}

    template<class T2, class Cmp2>
    DistinctList(const DistinctList<T2, Cmp2> &other) {
        BOOST_FOREACH (const T2 &item, other.items())
            pushBack(item);
    }

    template<class T2, class Cmp2>
    DistinctList& operator=(const DistinctList<T2, Cmp2> &other) {
        clear();
        BOOST_FOREACH (const T2 &item, other.items())
            pushBack(item);
        return *this;
    }

    void clear() {
        items_.clear();
        position_.clear();
    }
    
    bool isEmpty() const {
        return position_.isEmpty();
    }

    size_t size() const {
        return position_.size();
    }

    bool exists(const Item &item) const {
        return position_.exists(item);
    }
    
    size_t position(const Item &item) const {
        if (!position_.exists(item))
            return size();
        size_t retval = 0;
        BOOST_FOREACH (const Item &x, items_) {
            if (x == item)
                return retval;
            ++retval;
        }
        return retval;
    }
    
    const Item& front() const {
        if (isEmpty())
            throw std::runtime_error("front called on empty list");
        return items_.front();
    }
    
    const Item& back() const {
        if (isEmpty())
            throw std::runtime_error("back called on empty list");
        return items_.back();
    }
    
    void pushFront(const Item &item) {
        typename Map::NodeIterator found = position_.find(item);
        if (found == position_.nodes().end()) {
            items_.push_front(item);
            position_.insert(item, items_.begin());
        }
    }

    void pushBack(const Item &item) {
        typename Map::NodeIterator found = position_.find(item);
        if (found == position_.nodes().end()) {
            items_.push_back(item);
            position_.insert(item, --items_.end());
        }
    }

    Item popFront() {
        if (isEmpty())
            throw std::runtime_error("popFront called on empty list");
        Item item = items_.front();
        items_.pop_front();
        position_.erase(item);
        return item;
    }

    Item popBack() {
        if (isEmpty())
            throw std::runtime_error("popBack called on empty list");
        Item item = items_.back();
        items_.pop_back();
        position_.erase(item);
        return item;
    }

    void erase(const Item &item) {
        typename Map::NodeIterator found = position_.find(item);
        if (found != position_.nodes().end()) {
            items_.erase(found->value());
            position_.eraseAt(found);
        }
    }

    const Items& items() const {
        return items_;
    }
};

} // namespace
} // namespace

#endif