List.h

/*
 * $Id: List.h 3250 2012-04-15 15:26:53Z karijes $
 *
 * STL-like list class
 * Copyright (c) 2005-2007 edelib authors
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library. If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef __EDELIB_LIST_H__
#define __EDELIB_LIST_H__

#include "Debug.h"

EDELIB_NS_BEGIN

#ifndef SKIP_DOCS

struct ListNode {
        void* value;
        ListNode* next;
        ListNode* prev;
        ListNode() : value(0), next(0), prev(0) { }
};

template <typename T>
struct ListIterator {
        typedef ListNode NodeType;
        NodeType* node;

        ListIterator(NodeType* n) : node(n) { }
        ListIterator() : node(0) { }

        T& operator*(void) const { 
                E_ASSERT(node != 0 && "Bad code! Access to zero node!!!"); 
                E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!"); 
                return *(T*)node->value;
        }

        T* operator->(void) const {
                E_ASSERT(node != 0 && "Bad code! Access to zero node!!!"); 
                E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!"); 
                return (T*)node->value;
        }

        bool operator!=(const ListIterator& other) const { return node != other.node; }
        bool operator==(const ListIterator& other) const { return node == other.node; }
        ListIterator& operator++(void) { node = node->next; return *this; }
        ListIterator& operator--(void) { node = node->prev; return *this; }
};

#ifndef USE_SMALL_LIST
template <typename T>
struct ListConstIterator {
        typedef ListNode NodeType;
        NodeType* node;

        ListConstIterator(NodeType* n) : node(n) { }
        ListConstIterator() : node(0) { }

        // stupid language constructs !!!
        ListConstIterator(const ListIterator<T>& i) : node(i.node) { }

        const T& operator*(void) const { 
                E_ASSERT(node != 0 && "Bad code! Access to zero node!!!"); 
                E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!"); 
                return *(T*)node->value;
        }

        const T* operator->(void) const { 
                E_ASSERT(node != 0 && "Bad code! Access to zero node!!!"); 
                E_ASSERT(node->value != 0 && "Bad code! Dereferencing NULL value!!!"); 
                return (T*)node->value;
        }

        bool operator!=(const ListConstIterator& other) const { return node != other.node; }
        bool operator==(const ListConstIterator& other) const { return node == other.node; }
        ListConstIterator& operator++(void) { node = node->next; return *this; }
        ListConstIterator& operator--(void) { node = node->prev; return *this; }
};
#endif

#endif

template <typename T>
class list {
public:
#ifndef SKIP_DOCS
        typedef unsigned int size_type;
#endif
private:
        typedef ListNode Node;
        typedef bool (SortCmp)(const T& val1, const T& val2);

        size_type sz;
        Node* tail;

        E_DISABLE_CLASS_COPY(list)

        static bool default_sort_cmp(const T& val1, const T& val2) { return val1 < val2; }

        Node* merge_nodes(Node* a, Node* b, SortCmp* cmp) {
                Node head;
                Node* c = &head;
                Node* cprev = 0;

                while(a != 0 && b != 0) {
                        // compare values
                        if(cmp(*(T*)a->value, *(T*)b->value)) {
                                c->next = a;
                                a = a->next;
                        } else {
                                c->next = b;
                                b = b->next;
                        }

                        c = c->next;
                        c->prev = cprev;
                        cprev = c;
                }

                if(a == 0)
                        c->next = b;
                else
                        c->next = a;

                c->next->prev = c;
                return head.next;
        }

        Node* mergesort(Node* c, SortCmp* cmp) {
                Node* a, *b;
                if(c->next == 0)
                        return c;
                a = c;
                b = c->next;

                while((b != 0) && (b->next != 0)) {
                        c = c->next;
                        b = b->next->next;
                }

                b = c->next;
                c->next = 0;
                return merge_nodes(mergesort(a, cmp), mergesort(b, cmp), cmp);
        }

public:
        /*
         * This comment is not part of documentation, and in short explains
         * implementation details.
         *
         * List is implemented as circular doubly linked list, which means
         * that last node is pointing back to the first one (and reverse). 
         * Due the nature of traversing in circular lists, additional node 
         * (dummy node) is created so traversal (first != last) can be done.
         *
         * As you can see, only one node (tail) is used; it always pointing
         * to dummy node (which is always latest node). To get first element node, 
         * tail->first is used, and to get last (user visible), tail->prev is used. 
         * This implementation is needed so cases like --end() can return valid 
         * iterator to last element in the list.
         *
         * I tried to avoid dummy node creation, but implementing circular list
         * will be pain in the ass. Also, contrary popular std::list implementations I could
         * find, this node will be created only when insert()/push_back()/push_front()
         * are called; without those calls, list will not allocate it.
         */
#ifndef SKIP_DOCS
        typedef ListIterator<T> iterator;
#ifndef USE_SMALL_LIST
        typedef ListConstIterator<T> const_iterator;
#else
        typedef ListIterator<T> const_iterator;
#endif
#endif

        list() : sz(0), tail(0) { }

        ~list() { clear(); } 

        void clear(void) { 
                if(!tail) {
                        E_ASSERT(sz == 0 && "Internal error! size() != 0, but list is empty !?!!");
                        return;
                }

                Node* p = tail->next;
                Node* t;
                while(p != tail) {
                        t = p->next;
                        delete (T*)p->value;
                        delete p;
                        p = t;
                }

                // delete dummy node
                delete tail;

                tail = 0;
                sz = 0;
        }

        iterator insert(iterator it, const T& val) {
                // [23.2.2.3] insert() does not affect validity of iterators
                Node* tmp = new Node;
                tmp->value = new T(val); 

                if(!tail) {
                        // dummy node first
                        tail = new Node;
                        tail->next = tail->prev = tmp;
                        tmp->next = tmp->prev = tail;
                } else {
                        tmp->next = it.node;
                        tmp->prev = it.node->prev;
                        it.node->prev->next = tmp;
                        it.node->prev = tmp;
                }

                sz++;
                return iterator(tmp);
        }

        iterator erase(iterator it) {
                // do not allow erase(l.end())
                E_ASSERT(it.node != tail && "Bad code! erase() on end()!!!");

                // [23.2.2.3] erase() invalidates only the iterators
                it.node->prev->next = it.node->next;
                it.node->next->prev = it.node->prev;

                iterator ret(it.node);
                ++ret;
                sz--;

                delete (T*)it.node->value;
                delete it.node;

                return ret;
        }

        void push_back(const T& val) { insert(end(), val); }

        void push_front(const T& val) { insert(begin(), val); }

        iterator begin(void) { return iterator(tail ? tail->next : 0); }

        const_iterator begin(void) const { return const_iterator(tail ? tail->next : 0); }

        iterator end(void) { return iterator(tail); }

        const_iterator end(void) const { return const_iterator(tail); }

        T& front(void) { return *(begin()); }

        const T& front(void) const { return *(begin()); }

        T& back(void) { return *(--end()); }

        const T& back(void) const { return *(--end()); }

        size_type size(void) const { return sz; }

        bool empty(void) const { return sz == 0; }

        bool operator==(list<T>& other) {
                if(size() != other.size())
                        return false;

                iterator it = begin(), it_end = end(), it2 = other.begin();
                for(; it != it_end; ++it, ++it2) {
                        if((*it) != (*it2))
                                return false;
                }

                return true;
        }

        bool operator!=(list<T>& other) { return !operator==(other); }

        void sort(SortCmp* cmp = default_sort_cmp) {
                if(size() <= 1)
                        return;

                // unlink nodes first making first->prev and last->next zero
                tail->prev->next = 0;

                Node* nn = mergesort(tail->next, cmp);

                tail->next = nn;
                nn->prev = tail;

                /* 
                 * Search last node and let tail points to it. 
                 * Althought this looks like overhead, this sort is still twice faster that std::list sort.
                 * Alternative optimization would be that __mergesort() returns end node.
                 */
                while(1) {
                        if(nn->next)
                                nn = nn->next;
                        else {
                                nn->next = tail;
                                tail->prev = nn;
                                break;
                        }
                }
        }
};

#if 0
// list specialization for pointers
#ifndef SKIP_DOCS
#ifndef NO_LIST_SPECIALIZATION

// explicit instantation
template class list<void*>;
template class ListIterator<void*>;

template <typename T>
struct ListIterator<T*> {
private:
        ListIterator<void*> impl;

public:
        // implicit conversion; some magic. Yuck !
        operator ListIterator<void*> () { return impl; }

        ListIterator(const ListIterator<void*>& b) : impl(b) { } 
        typedef ListNode NodeType;

        ListIterator() { }
        ListIterator(NodeType* n) : impl(n) { }

        T* operator*(void) const { return (T*)*impl; }

        bool operator!=(const ListIterator& other) const { return impl != other.impl; }
        bool operator==(const ListIterator& other) const { return impl == other.impl; }

        ListIterator& operator++(void) { ++impl; return *this; }
        ListIterator& operator--(void) { --impl; return *this; }
};

template <typename T>
class list<T*> {
private:
        list<void*> impl;
        static bool default_sort_cmp(const T* val1, const T* val2) { return *val1 < *val2; }

public:
        typedef unsigned int size_type;

        typedef T* value_type;
        typedef const value_type& const_reference;
        typedef value_type&       reference;
        typedef value_type*       pointer;
        typedef const value_type* const_pointer;

        typedef bool (SortCmp)(const_reference val1, const_reference val2);
        
        typedef ListIterator<T*> iterator;
        typedef ListIterator<T*> const_iterator;

        void clear(void) { impl.clear(); }

        iterator insert(iterator it, const_reference val) { return impl.insert(it, val); }
        iterator erase(iterator it) { return impl.erase(it); }

        void push_back(const_reference val) { impl.push_back((void*)val); }
        void push_front(const_reference val) { impl.push_front((void*)val); }

        iterator begin(void) { return impl.begin(); }
        const_iterator begin(void) const { return impl.begin(); }

        iterator end(void) { return impl.end(); }
        const_iterator end(void) const { return impl.end(); }

        pointer front(void) { return impl.front(); }
        const_pointer front(void) const { return impl.front(); }

        pointer back(void) { return impl.back(); }
        const_pointer back(void) const { return impl.back(); }

        size_type size(void) const { return impl.size(); }
        bool empty(void) const { return impl.empty(); }

        bool operator==(list<T*>& other) { return impl.operator==(other); }
        bool operator!=(list<T*>& other) { return impl.operator!=(other); }

        //void sort(SortCmp* cmp = default_sort_cmp) { impl.sort( (bool (*)(void* const&, void* const&)) cmp); }
        void sort(SortCmp* cmp) { impl.sort((bool (*)(void* const&, void* const&)) cmp); }
};

#endif // NO_LIST_SPECIALIZATION
#endif // SKIP_DOCS
#endif

EDELIB_NS_END
#endif