list.h

/*************************************************************************/
/*  list.h                                                               */
/*************************************************************************/
/*                       This file is part of:                           */
/*                           GODOT ENGINE                                */
/*                    http://www.godotengine.org                         */
/*************************************************************************/
/* Copyright (c) 2007-2016 Juan Linietsky, Ariel Manzur.                 */
/*                                                                       */
/* Permission is hereby granted, free of charge, to any person obtaining */
/* a copy of this software and associated documentation files (the       */
/* "Software"), to deal in the Software without restriction, including   */
/* without limitation the rights to use, copy, modify, merge, publish,   */
/* distribute, sublicense, and/or sell copies of the Software, and to    */
/* permit persons to whom the Software is furnished to do so, subject to */
/* the following conditions:                                             */
/*                                                                       */
/* The above copyright notice and this permission notice shall be        */
/* included in all copies or substantial portions of the Software.       */
/*                                                                       */
/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,       */
/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF    */
/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY  */
/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,  */
/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE     */
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                */
/*************************************************************************/
#ifndef GLOBALS_LIST_H
#define GLOBALS_LIST_H

#include "os/memory.h"
#include "sort.h"

template <class T,class A=DefaultAllocator>
class List {
    struct _Data;
public:


    class Element {

    private:
        friend class List<T,A>;

        T value;
        Element* next_ptr;
        Element* prev_ptr;
        _Data *data;
    public:

        _FORCE_INLINE_ const Element* next() const {

            return next_ptr;
        };
        _FORCE_INLINE_ Element* next() {

            return next_ptr;
        };

        _FORCE_INLINE_ const Element* prev() const {

            return prev_ptr;
        };
        _FORCE_INLINE_ Element* prev() {

            return prev_ptr;
        };

        _FORCE_INLINE_ const T& operator *() const {
            return value;
        };
        _FORCE_INLINE_ const T* operator->() const {

            return &value;
        };
        _FORCE_INLINE_ T& operator *() {
            return value;
        };
        _FORCE_INLINE_ T* operator->() {
            return &value;
        };

        _FORCE_INLINE_ T& get() {
            return value;
        };
        _FORCE_INLINE_ const T& get() const {
            return value;
        };
        _FORCE_INLINE_ void set(const T& p_value) {
            value = (T&)p_value;
        };

        void erase() {

            data->erase(this);
        }

        _FORCE_INLINE_ Element() {
            next_ptr = 0;
            prev_ptr = 0;
            data=NULL;
        };
    };

private:

    struct _Data {

        Element* first;
        Element* last;
        int size_cache;


        bool erase(const Element* p_I) {

            ERR_FAIL_COND_V(!p_I,false);
            ERR_FAIL_COND_V(p_I->data!=this,false);

            if (first==p_I) {
                first=p_I->next_ptr;
            };

            if (last==p_I)
                last=p_I->prev_ptr;

            if (p_I->prev_ptr)
                p_I->prev_ptr->next_ptr=p_I->next_ptr;

            if (p_I->next_ptr)
                p_I->next_ptr->prev_ptr=p_I->prev_ptr;

            memdelete_allocator<Element,A>( const_cast<Element*>(p_I) );
            size_cache--;

            return true;
        }
    };

    _Data *_data;


public:

    _FORCE_INLINE_ const Element* front() const {

        return _data?_data->first:0;
    };

    _FORCE_INLINE_ Element* front() {
        return _data?_data->first:0;
    };

    _FORCE_INLINE_ const Element* back() const {

        return _data?_data->last:0;
    };

    _FORCE_INLINE_ Element* back() {

        return _data?_data->last:0;
    };

    Element* push_back(const T& value) {

        if (!_data) {

            _data=memnew_allocator(_Data,A);
            _data->first=NULL;
            _data->last=NULL;
            _data->size_cache=0;
        }

        Element* n = memnew_allocator(Element,A);
        n->value = (T&)value;

        n->prev_ptr=_data->last;
        n->next_ptr=0;
        n->data=_data;

        if (_data->last) {

            _data->last->next_ptr=n;
        }

        _data->last = n;

        if (!_data->first)
            _data->first=n;

        _data->size_cache++;

        return n;
    };

    void pop_back() {

        if (_data && _data->last)
            erase(_data->last);
    }

    Element* push_front(const T& value) {

        if (!_data) {

            _data=memnew_allocator(_Data,A);
            _data->first=NULL;
            _data->last=NULL;
            _data->size_cache=0;
        }

        Element* n = memnew_allocator(Element,A);
        n->value = (T&)value;
        n->prev_ptr = 0;
        n->next_ptr = _data->first;
        n->data=_data;

        if (_data->first) {

            _data->first->prev_ptr=n;
        }

        _data->first = n;

        if (!_data->last)
            _data->last=n;

        _data->size_cache++;

        return n;
    };

    void pop_front() {

        if (_data && _data->first)
            erase(_data->first);
    }

    template<class T_v>
    Element* find(const T_v& p_val) {

        Element* it = front();
        while (it) {
            if (it->value == p_val) return it;
            it = it->next();
        };

        return NULL;
    };

    bool erase(const Element* p_I) {

        if (_data) {
            bool ret =  _data->erase(p_I);

            if (_data->size_cache==0) {
                memdelete_allocator<_Data,A>(_data);
                _data=NULL;
            }

            return ret;
        }

        return false;
    };

    bool erase(const T& value) {

        Element* I = find(value);
        return erase(I);
    };

    _FORCE_INLINE_ bool empty() const {

        return (!_data || !_data->size_cache);
    }

    void clear() {

        while (front()) {
            erase(front());
        };
    };

    _FORCE_INLINE_ int size() const {

        return _data?_data->size_cache:0;

    }

    void swap(Element* p_A, Element *p_B) {

        ERR_FAIL_COND(!p_A || !p_B);
        ERR_FAIL_COND(p_A->data!=_data);
        ERR_FAIL_COND(p_B->data!=_data);

        Element* A_prev=p_A->prev_ptr;
        Element* A_next=p_A->next_ptr;

        p_A->next_ptr=p_B->next_ptr;
        p_A->prev_ptr=p_B->prev_ptr;

        p_B->next_ptr=A_next;
        p_B->prev_ptr=A_prev;

        if (p_A->prev_ptr)
            p_A->prev_ptr->next_ptr=p_A;
        if (p_A->next_ptr)
            p_A->next_ptr->prev_ptr=p_A;

        if (p_B->prev_ptr)
            p_B->prev_ptr->next_ptr=p_B;
        if (p_B->next_ptr)
            p_B->next_ptr->prev_ptr=p_B;

    }
    void operator=(const List& p_list) {

        clear();
        const Element *it=p_list.front();
        while (it) {

            push_back( it->get() );
            it=it->next();
        }

    }

    T& operator[](int p_index) {

        if (p_index<0 || p_index>=size()) {
            T& aux=*((T*)0); //nullreturn
            ERR_FAIL_COND_V(p_index<0 || p_index>=size(),aux);
        }

        Element *I=front();
        int c=0;
        while(I) {

            if (c==p_index) {

                return I->get();
            }
            I=I->next();
            c++;
        }

        ERR_FAIL_V( *((T*)0) ); // bug!!
    }

    const T& operator[](int p_index) const {

        if (p_index<0 || p_index>=size()) {
            T& aux=*((T*)0); //nullreturn
            ERR_FAIL_COND_V(p_index<0 || p_index>=size(),aux);
        }

        const Element *I=front();
        int c=0;
        while(I) {

            if (c==p_index) {

                return I->get();
            }
            I=I->next();
            c++;
        }

        ERR_FAIL_V( *((T*)0) );  // bug!
    }


    void move_to_back(Element* p_I) {

        ERR_FAIL_COND(p_I->data!=_data);
        if (!p_I->next_ptr)
            return;

        if (_data->first==p_I) {
            _data->first=p_I->next_ptr;
        };

        if (_data->last==p_I)
            _data->last=p_I->prev_ptr;

        if (p_I->prev_ptr)
            p_I->prev_ptr->next_ptr=p_I->next_ptr;

        if (p_I->next_ptr)
            p_I->next_ptr->prev_ptr=p_I->prev_ptr;


        _data->last->next_ptr=p_I;
        p_I->prev_ptr=_data->last;
        p_I->next_ptr=NULL;
        _data->last=p_I;

    }

    void invert() {

        int s = size() / 2;
        Element *F = front();
        Element *B = back();
        for(int i=0;i<s;i++) {

            SWAP( F->value, B->value );
            F=F->next();
            B=B->prev();
        }
    }

    void move_to_front(Element* p_I) {

        ERR_FAIL_COND(p_I->data!=_data);
        if (!p_I->prev_ptr)
            return;

        if (_data->first==p_I) {
            _data->first=p_I->next_ptr;
        };

        if (_data->last==p_I)
            _data->last=p_I->prev_ptr;

        if (p_I->prev_ptr)
            p_I->prev_ptr->next_ptr=p_I->next_ptr;

        if (p_I->next_ptr)
            p_I->next_ptr->prev_ptr=p_I->prev_ptr;

        _data->first->prev_ptr=p_I;
        p_I->next_ptr=_data->first;
        p_I->prev_ptr=NULL;
        _data->first=p_I;

    }

    void move_before(Element* value, Element* where) {

        if (value->prev_ptr) {
            value->prev_ptr->next_ptr = value->next_ptr;
        }
        else {
            _data->first = value->next_ptr;
        }
        if (value->next_ptr) {
            value->next_ptr->prev_ptr = value->prev_ptr;
        }
        else {
            _data->last = value->prev_ptr;
        }

        value->next_ptr = where;
        if (!where) {
            value->prev_ptr = _data->last;
            _data->last = value;
            return;
        };

        value->prev_ptr = where->prev_ptr;

        if (where->prev_ptr) {
            where->prev_ptr->next_ptr = value;
        } else {
            _data->first = value;
        };

        where->prev_ptr = value;
    };

    void sort() {

        sort_custom< Comparator<T> >();
    }

    template<class C>
    void sort_custom_inplace() {

        if(size()<2)
            return;

        Element *from=front();
        Element *current=from;
        Element *to=from;

        while(current) {

            Element *next=current->next_ptr;

            //disconnect
            current->next_ptr=NULL;

            if (from!=current) {

                current->prev_ptr=NULL;
                current->next_ptr=from;

                Element *find=from;
                C less;
                while( find && less(find->value,current->value) ) {

                    current->prev_ptr=find;
                    current->next_ptr=find->next_ptr;
                    find=find->next_ptr;
                }

                if (current->prev_ptr)
                    current->prev_ptr->next_ptr=current;
                else
                    from=current;

                if (current->next_ptr)
                    current->next_ptr->prev_ptr=current;
                else
                    to=current;
            } else {

                current->prev_ptr=NULL;
                current->next_ptr=NULL;

            }

            current=next;
        }
        _data->first=from;
        _data->last=to;
    }

    template<class C>
    struct AuxiliaryComparator {

        C compare;
        _FORCE_INLINE_ bool operator()(const Element *a,const Element* b) const {

            return compare(a->value,b->value);
        }
    };

    template<class C>
    void sort_custom() {

        //this version uses auxiliary memory for speed.
        //if you don't want to use auxiliary memory, use the in_place version

        int s = size();
        if(s<2)
            return;


        Element **aux_buffer = memnew_arr(Element*,s);

        int idx=0;
        for(Element *E=front();E;E=E->next_ptr) {

            aux_buffer[idx]=E;
            idx++;
        }

        SortArray<Element*,AuxiliaryComparator<C> > sort;
        sort.sort(aux_buffer,s);

        _data->first=aux_buffer[0];
        aux_buffer[0]->prev_ptr=NULL;
        aux_buffer[0]->next_ptr=aux_buffer[1];

        _data->last=aux_buffer[s-1];
        aux_buffer[s-1]->prev_ptr=aux_buffer[s-2];
        aux_buffer[s-1]->next_ptr=NULL;

        for(int i=1;i<s-1;i++) {

            aux_buffer[i]->prev_ptr=aux_buffer[i-1];
            aux_buffer[i]->next_ptr=aux_buffer[i+1];

        }

        memdelete_arr(aux_buffer);
    }


    List(const List& p_list) {

        _data=NULL;
        const Element *it=p_list.front();
        while (it) {

            push_back( it->get() );
            it=it->next();
        }

    }

    List() {
        _data=NULL;
    };
    ~List() {
        clear();
        if (_data) {

            ERR_FAIL_COND(_data->size_cache);
            memdelete_allocator<_Data,A>(_data);
        }
    };
};

#endif