linkedlist.h

Go to the documentation of this file.

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <boost/static_assert.hpp>
#include <boost/type_traits.hpp>
#include <list>

namespace frechet { namespace data {

class BLinkedListElement {
protected:
    BLinkedListElement *link[2];
    friend class BLinkedList;
public:
    BLinkedListElement();

#ifdef LINKED_LIST_VDESTRUCTOR

    virtual ~BLinkedListElement();
#endif
    BLinkedListElement*& prev() { return link[0]; }
    BLinkedListElement*& next() { return link[1]; }
};

template<class T>
class LinkedListElement : public BLinkedListElement {
    //BOOST_STATIC_ASSERT((boost::is_base_of<BLinkedListElement, T>::value));
    //moved to LinkedList<T>
public:
    LinkedListElement() : BLinkedListElement() {}

    T* prev() const         { return (T*)link[0]; }
    T* next() const         { return (T*)link[1]; }

    T* next(bool forward)   { return (T*)link[(int)forward]; }
};

class BLinkedList;

class BLinkedList {
protected:
    BLinkedListElement *_first;
    BLinkedListElement *_last;
    int _size;
    bool _circular;
public:
    BLinkedList(bool circular=false);
    BLinkedList(BLinkedList&& that);
    ~BLinkedList();

    bool empty() const;
    int size() const;

    bool circular() const;
    void setCircular(bool);

    BLinkedList& operator= (BLinkedList&& that);

    void insert_first(BLinkedListElement* el);
    void insert_last(BLinkedListElement* el);

    void insert_before(BLinkedListElement* el, BLinkedListElement* before);
    void insert_after(BLinkedListElement* el, BLinkedListElement* after);

    BLinkedListElement* remove(BLinkedListElement* el);
    void clear();

    int concat(BLinkedList& that);
    int swap(BLinkedList& that);

protected:
    BLinkedListElement* operator[] (int i) const;
private:
    void dispose();
    void releaseAll();
    //  shallow copies are not allowed
    BLinkedList(const BLinkedList&) { throw "illegal"; }
    BLinkedList& operator= (const BLinkedList&) { throw "illegal"; }
};

template<class T>
class LinkedList : public BLinkedList {
    BOOST_STATIC_ASSERT((boost::is_base_of<BLinkedListElement, T>::value));
public:
    LinkedList() : BLinkedList() {}
    LinkedList(LinkedList&& that) : BLinkedList((BLinkedList&&)that) {}

    template<typename Cloner>
    LinkedList(const LinkedList& that, Cloner cloner) : BLinkedList(that.allocator)
    {
        for(T* p = that.first(); p; p = p->next())
            insert_last(cloner(p));
    }

    LinkedList& operator= (LinkedList&& that) {
        BLinkedList::operator= ((BLinkedList&&)that);
        return *this;
    }

    T* first() const { return (T*)_first; }
    T* last() const  { return (T*)_last; }

    T* remove(T* el) { return (T*)BLinkedList::remove(el); }

    T* operator[] (int i) const { return (T*) BLinkedList::operator[] (i); }

    void swap(LinkedList<T>& that)  {
        BLinkedList::swap(that);
    }
};


/*
//namespace std {
    template<typename T>
    void swap(LinkedList<T>& a, LinkedList<T>& b) {
        a.swap(b);
    }
//}

namespace std {
    template<typename T>
    void swap(LinkedList<T>& a, LinkedList<T>& b) {
        a.swap(b);
    }
}
*/

} } // namespace

#endif // LINKEDLIST_H