IndexedList.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_IndexedList_H
#define Sawyer_IndexedList_H

#include <Sawyer/Assert.h>
#include <Sawyer/DefaultAllocator.h>
#include <Sawyer/Optional.h>
#include <Sawyer/Sawyer.h>

#include <boost/range/iterator_range.hpp>
#include <boost/serialization/access.hpp>
#include <boost/serialization/nvp.hpp>
#include <boost/serialization/split_member.hpp>
#include <iterator>
#include <vector>

namespace Sawyer {
namespace Container {

template<class T>
struct IndexedListTraits {
    typedef typename T::NodeIterator NodeIterator;
    typedef typename T::ValueIterator ValueIterator;
};

template<class T>
struct IndexedListTraits<const T> {
    typedef typename T::ConstNodeIterator NodeIterator;
    typedef typename T::ConstValueIterator ValueIterator;
};

template<class T, class Alloc = DefaultAllocator>
class IndexedList {
public:
    typedef T Value;                                    
    typedef Alloc Allocator;                            
    class Node;                                         
private:

    static const size_t NO_ID = (size_t)(-1);


    // Forms a circular list. ProtoNode is the first part of a Node so that we can static_cast from ProtoNode to Node.
    class ProtoNode {
    public:
        size_t id;                                      // Unique, small, contiguous ID numbers
        ProtoNode *next, *prev;                         // Linkage to neighoring nodes
        explicit ProtoNode(size_t id=NO_ID): id(id), next(this), prev(this) {}
        bool isHead() const { return id==NO_ID; }       // implies no Node memory is attached; don't static_cast to Node!
        void insert(ProtoNode &newNode) {               // insert newNode before this node
            ASSERT_forbid(newNode.isHead());
            ASSERT_require(newNode.next==&newNode);
            ASSERT_require(newNode.prev==&newNode);
            prev->next = &newNode;
            newNode.prev = prev;
            prev = &newNode;
            newNode.next = this;
        }
        void remove() {                                 // remove this node from the list
            ASSERT_forbid(isHead());
            prev->next = next;
            next->prev = prev;
            next = prev = this;
        }
        Node& dereference() {
            ASSERT_forbid(isHead());
            Node *node = (Node*)this;                   // ProtoNode must be first data member of Node
            ASSERT_require(&node->linkage_ == this);    // it wasn't first
            return *node;
        }
        const Node& dereference() const {
            ASSERT_forbid(isHead());
            const Node *node = (const Node*)this;       // ProtoNode must be first data member of Node
            ASSERT_require(&node->linkage_ == this);    // it wasn't first
            return *node;
        }
    };

public:
    class Node {
        ProtoNode linkage_;                             // This member MUST BE FIRST so ProtoNode::dereference works
        Value value_;                                   // User-supplied data for each node
    private:
        friend class IndexedList;
        Node(size_t id, const Value &value): linkage_(id), value_(value) { ASSERT_forbid(linkage_.isHead()); }
    public:
        const size_t& id() const { return linkage_.id; }

        Value& value() { return value_; }
        const Value& value() const { return value_; }
        Value& operator*() { return value_; }
        const Value& operator*() const { return value_; }
        Value* operator->() { return &value_; }
        const Value* operator->() const { return &value_; }
    };

    //                                  Iterators
private:
    template<class Derived, class Value, class BaseIterator>
    class IteratorBase {
    public:
        // Five standard iterator types
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type = Value;
        using difference_type = std::ptrdiff_t;
        using pointer = Value*;
        using reference = Value&;

    protected:
        BaseIterator base_;
        IteratorBase() { base_ = NULL; }
        IteratorBase(const IteratorBase &other): base_(other.base_) {}
        IteratorBase(const BaseIterator &base): base_(base) {}
    public:
        bool isAtEnd() const { return base_->isHead(); }
        Derived& operator++() { base_ = base_->next; return *derived(); }
        Derived operator++(int) { Derived old(this->base_); base_ = base_->next; return old; }
        Derived& operator--() { base_ = base_->prev; return *derived(); }
        Derived operator--(int) { Derived old(this->base_); base_ = base_->prev; return old; }
        template<class OtherIter> bool operator==(const OtherIter &other) const { return base_ == other.base(); }
        template<class OtherIter> bool operator!=(const OtherIter &other) const { return base_ != other.base(); }
    protected:
        Derived* derived() { return static_cast<Derived*>(this); }
        const Derived* derived() const { return static_cast<const Derived*>(this); }
    public:
        const BaseIterator& base() const { return base_; }
    };

public:
    class NodeIterator: public IteratorBase<NodeIterator, Node, ProtoNode*> {
        typedef                IteratorBase<NodeIterator, Node, ProtoNode*> Super;
    public:
        NodeIterator() {}
        NodeIterator(const NodeIterator &other): Super(other) {}
        Node& operator*() const { return this->base_->dereference(); }
        Node* operator->() const { return &this->base_->dereference(); }
    private:
        friend class IndexedList;
        NodeIterator(ProtoNode *base): Super(base) {}
        NodeIterator(Node *node): Super(&node->linkage_) {}
    };

    class ConstNodeIterator: public IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> {
        typedef                     IteratorBase<ConstNodeIterator, const Node, const ProtoNode*> Super;
    public:
        ConstNodeIterator() {}
        ConstNodeIterator(const ConstNodeIterator &other): Super(other) {}
        ConstNodeIterator(const NodeIterator &other): Super(other.base()) {}
        const Node& operator*() const { return this->base_->dereference(); }
        const Node* operator->() const { return &this->base_->dereference(); }
    private:
        friend class IndexedList;
        ConstNodeIterator(const ProtoNode *base): Super(base) {}
        ConstNodeIterator(const Node *node): Super(&node->linkage_) {}
    };

    class ValueIterator: public IteratorBase<ValueIterator, Value, ProtoNode*> {
        typedef                 IteratorBase<ValueIterator, Value, ProtoNode*> Super;
    public:
        ValueIterator() {}
        ValueIterator(const ValueIterator &other): Super(other) {}
        ValueIterator(const NodeIterator &other): Super(other.base()) {}
        Value& operator*() const { return this->base()->dereference().value(); }
        Value* operator->() const { return &this->base()->dereference().value(); }
    private:
        friend class IndexedList;
        ValueIterator(ProtoNode *base): Super(base) {}
        ValueIterator(Node *node): Super(&node->linkage_) {}
    };

    class ConstValueIterator: public IteratorBase<ConstValueIterator, const Value, const ProtoNode*> {
        typedef                      IteratorBase<ConstValueIterator, const Value, const ProtoNode*> Super;
    public:
        ConstValueIterator() {}
        ConstValueIterator(const ConstValueIterator &other): Super(other) {}
        ConstValueIterator(const NodeIterator &other): Super(other.base()) {}
        ConstValueIterator(const ConstNodeIterator &other): Super(other.base()) {}
        ConstValueIterator(const ValueIterator &other): Super(other.base()) {}
        const Value& operator*() const { return this->base()->dereference().value(); }
        const Value* operator->() const { return &this->base()->dereference().value(); }
    private:
        friend class IndexedList;
        ConstValueIterator(const ProtoNode *base): Super(base) {}
        ConstValueIterator(const Node *node): Super(&node->linkage_) {}
    };
private:
    Allocator allocator_;                               // provided allocator for list nodes
    ProtoNode *head_;                                   // always point to a list head, not a true node (normal allocator)
    typedef std::vector<Node*> Index;                   // allocated with provided allocator
    Index index_;                                       // allocated with normal allocator

    //                                  Serialization
private:
    friend class boost::serialization::access;

    template<class S>
    void save(S &s, const unsigned /*version*/) const {
        size_t n = size();
        s <<BOOST_SERIALIZATION_NVP(n);
        for (const ProtoNode *pnode = head_->next; pnode != head_; pnode = pnode->next) {
            ASSERT_require(n-- > 0);
            size_t id = pnode->dereference().id();
            const Value &value = pnode->dereference().value();
            s <<BOOST_SERIALIZATION_NVP(id);
            s <<BOOST_SERIALIZATION_NVP(value);
        }
    }

    template<class S>
    void load(S &s, const unsigned /*version*/) {
        clear();
        size_t n = 0;
        s >>BOOST_SERIALIZATION_NVP(n);
        ASSERT_require(index_.empty());
        index_.resize(n, NULL);
        for (size_t i=0; i<n; ++i) {
            size_t id = 0;
            s >>BOOST_SERIALIZATION_NVP(id);
            Node *node = new (allocator_.allocate(sizeof(Node))) Node(id, Value());
            s >>boost::serialization::make_nvp("value", node->value());

            ASSERT_require(id < index_.size());
            ASSERT_require(index_[id] == NULL);
            index_[id] = node;

            head_->insert(node->linkage_);              // append to end of node list
        }
    }

    BOOST_SERIALIZATION_SPLIT_MEMBER();

        
    //                                  Initialization
public:

    explicit IndexedList(const Allocator &allocator = Allocator())
        : allocator_(allocator), head_(new ProtoNode) {}

    IndexedList(const IndexedList &other): allocator_(other.allocator_), head_(new ProtoNode) {
        for (ConstValueIterator otherIter=other.values().begin(); otherIter!=other.values().end(); ++otherIter)
            pushBack(*otherIter);
    }

    template<class T2, class Alloc2>
    IndexedList(const IndexedList<T2, Alloc2> &other, const Allocator &/*allocator*/ = Allocator())
        : allocator_(Allocator()), head_(new ProtoNode) {
        typedef typename IndexedList<T2>::ConstValueIterator OtherIter;
        for (OtherIter otherIter=other.values().begin(); otherIter!=other.values().end(); ++otherIter)
            pushBack(Value(*otherIter));
    }

    explicit IndexedList(size_t nElmts, const Value &val = Value(), const Allocator &allocator = Allocator())
        : allocator_(allocator), head_(new ProtoNode) {
        index_.reserve(nElmts);
        for (size_t i=0; i<nElmts; ++i)
            pushBack(val);
    }

    IndexedList& operator=(const IndexedList &other) {
        clear();
        insertMultiple(nodes().begin(), other.values());
        return *this;
    }

    template<class T2>
    IndexedList& operator=(const IndexedList<T2> &other) {
        clear();
        insert(nodes().begin(), other.values());
        return *this;
    }

    ~IndexedList() {
        clear();
        delete head_;
    }

    const Allocator& allocator() const {
        return allocator_;
    }
    
    //                                  Iteration
public:

    boost::iterator_range<NodeIterator> nodes() {
        return boost::iterator_range<NodeIterator>(NodeIterator(head_->next), NodeIterator(head_));
    }
    boost::iterator_range<ConstNodeIterator> nodes() const {
        return boost::iterator_range<ConstNodeIterator>(ConstNodeIterator(head_->next), ConstNodeIterator(head_));
    }
    boost::iterator_range<ValueIterator> values() {
        return boost::iterator_range<ValueIterator>(ValueIterator(head_->next), ValueIterator(head_));
    }
    boost::iterator_range<ConstValueIterator> values() const {
        return boost::iterator_range<ConstValueIterator>(ConstValueIterator(head_->next), ConstValueIterator(head_));
    }
private:
    bool isLocalIterator(const ConstValueIterator &iter) const {
        const ProtoNode *pn = iter.base();
        ASSERT_not_null(pn);
        if (pn == head_)
            return true;                                // local end iterator
        const Node *node = &pn->dereference();
        size_t id = node->id();
        return id<index_.size() && node==index_[id];
    }


    //                                  Size and capacity
public:

    bool isEmpty() const {
        return index_.empty();
    }

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

    size_t capacity() const {
        return index_.capacity();
    }
    void capacity(size_t n) {
        index_.reserve(n);
    }
    //                                  Searching
public:

    NodeIterator find(size_t id) {
        ASSERT_require(id < index_.size());
        ASSERT_not_null(index_[id]);
        return NodeIterator(index_[id]);
    }
    ConstNodeIterator find(size_t id) const {
        ASSERT_require(id < index_.size());
        ASSERT_not_null(index_[id]);
        return ConstNodeIterator(index_[id]);
    }
    //                                  Accessors
public:

    Node& frontNode() {
        ASSERT_forbid(isEmpty());
        return head_->next->dereference();
    }
    const Node& frontNode() const {
        ASSERT_forbid(isEmpty());
        return head_->next->dereference();
    }
    Value& frontValue() {
        return frontNode().value();
    }
    const Value& frontValue() const {
        return frontNode().value();
    }
    Node& backNode() {
        ASSERT_forbid(isEmpty());
        return head_->prev->dereference();
    }
    const Node& backNode() const {
        ASSERT_forbid(isEmpty());
        return head_->prev->dereference();
    }
    Value& backValue() {
        return backNode().value();
    }
    const Value& backValue() const {
        return backNode().value();
    }
    Node& indexedNode(size_t id) {
        ASSERT_require(id < size());
        ASSERT_not_null(index_[id]);
        return *index_[id];
    }
    const Node& indexedNode(size_t id) const {
        ASSERT_require(id < size());
        ASSERT_not_null(index_[id]);
        return *index_[id];
    }
    Value& indexedValue(size_t id) {
        return indexedNode(id).value();
    }
    const Value& indexedValue(size_t id) const {
        return indexedNode(id).value();
    }
    Value& operator[](size_t id) {
        return indexedValue(id);
    }
    const Value& operator[](size_t id) const {
        return indexedValue(id);
    }

    Optional<Value> getOptional(size_t id) const {
        return id < size() ? Optional<Value>(indexedValue(id)) : Optional<Value>();
    }

    Value& getOrElse(size_t id, Value &dflt) {
        return id < size() ? indexedValue(id) : dflt;
    }
    const Value& getOrElse(size_t id, const Value &dflt) const {
        return id < size() ? indexedValue(id) : dflt;
    }

    const Value& getOrDefault(size_t id) const {
        static const Value dflt;
        return id < size() ? indexedValue(id) : dflt;
    }
    //                                  Mutators
public:

    IndexedList& pushFront(const Value &value) {
        insert(nodes().begin(), value);
        return *this;
    }

    IndexedList& pushBack(const Value &value) {
        insert(nodes().end(), value);
        return *this;
    }

    NodeIterator insert(const ValueIterator &position, const Value &value) {
        ProtoNode *pos = position.base();
        Node *node = new (allocator_.allocate(sizeof(Node))) Node(index_.size(), value);
        index_.push_back(node);
        pos->insert(node->linkage_);
        return NodeIterator(node);
    }

    IndexedList& insert(const ValueIterator &position, size_t nElmts, const Value &value) {
        for (size_t i=0; i<nElmts; ++i)
            insert(position, value);
        return *this;
    }

    template<class OtherValueIterator>
    IndexedList& insertMultiple(const ValueIterator &position, const boost::iterator_range<OtherValueIterator> &range) {
        for (OtherValueIterator otherIter=range.begin(); otherIter!=range.end(); ++otherIter)
            insert(position, Value(*otherIter));
        return *this;
    }


    void clear() {
        for (size_t i=0; i<index_.size(); ++i) {
            index_[i]->~Node();
            allocator_.deallocate((void*)index_[i], sizeof(Node));
        }
        index_.clear();
        head_->next = head_->prev = head_;
    }

    NodeIterator erase(size_t id) {
        ASSERT_require(id < size());
        return eraseAt(find(id));
    }

    NodeIterator eraseAt(const ValueIterator &position) {
        ASSERT_require(isLocalIterator(position));
        ProtoNode *pos = position.base();
        ProtoNode *next = pos->next;                    // to build the return value
        pos->remove();                                  // remove node from the doubly linked list w/out deleting
        size_t id = pos->id;
        if (id + 1 < index_.size()) {
            std::swap(index_.back(), index_[id]);
            index_[id]->linkage_.id = id;
        }
        index_.back()->~Node();
        allocator_.deallocate(index_.back(), sizeof(Node));
        index_.pop_back();
        return NodeIterator(next);
    }

    // range must be a range within this container
    NodeIterator eraseAtMultiple(const boost::iterator_range<NodeIterator> &range) {
        boost::iterator_range<ValueIterator> valueRange(range.begin(), range.end());
        return eraseAtMultiple(valueRange);
    }
    NodeIterator eraseAtMultiple(const boost::iterator_range<ValueIterator> &range) {
        ValueIterator otherIter = range.begin();
        while (otherIter!=range.end())
            otherIter = eraseAt(otherIter);
        return NodeIterator(range.end().base());
    }

    // debugging
    void dump(std::ostream &o) const {
        o <<"list contents:\n"
          <<"  index:\n";
        for (size_t i=0; i<index_.size(); ++i)
            o <<"    [" <<i <<"]=" <<index_[i] <<"\n";
        o <<"  list:\n";
        ProtoNode *pn = head_;
        for (size_t i=0; i<index_.size()+1; ++i, pn=pn->next) {
            o <<"    " <<pn <<"\t" <<pn->next <<"\t" <<pn->prev <<"\t" <<pn->id <<"\n";
            ASSERT_require(pn->isHead() || index_[pn->id]==&pn->dereference());
            ASSERT_require(pn->next->prev == pn);
            ASSERT_require(pn->prev->next == pn);
        }
    }
};

} // namespace
} // namespace

#endif