List.h

Go to the documentation of this file.

#pragma once
#ifdef USE_INITIALIZER_LIST
#  include "InitializerList.h" 
#endif
#include <stddef.h>
#include <assert.h>
#include "Allocator.h"
 
namespace audio_tools {
 
template <class T> 
class List {
    public:
        struct Node {
            Node* next = nullptr;
            Node* prior = nullptr;
            T data;
        };
 
        class Iterator {
            public:
                Iterator(Node*node){
                    this->node = node;
                }
                inline Iterator operator++() {
                    if (node->next!=nullptr){
                        node = node->next;
                        is_eof = false;
                    } else is_eof=true;
                    return *this;
                }
                inline Iterator operator++(int) {
                    return ++*this;
                }
                inline Iterator operator--() {
                    if (node->prior!=nullptr){
                        node = node->prior;
                        is_eof = false;
                    } else is_eof=true;
                    return *this;
                }
                inline Iterator operator--(int) {
                    return --*this;
                }
                inline Iterator operator+(int offset) {
                    return getIteratorAtOffset(offset);
                }
                inline Iterator operator-(int offset) {
                    return getIteratorAtOffset(-offset);
                }
                inline bool operator==(Iterator it) {
                    return node == it.get_node();
                }
                inline bool operator!=(Iterator it) {
                    return node != it.get_node();
                }
                inline T &operator*() {
                    return node->data;
                }
                inline T *operator->() {
                    return &(node->data);
                }
                inline Node *get_node() {
                    return node;
                }
                inline operator bool() {
                    return is_eof;
                }
            protected:
                Node* node=nullptr;
                bool is_eof = false;
 
                Iterator getIteratorAtOffset(int offset){
                    Node *tmp = node;
                    if (offset>0){
                        for (int j=0;j<offset;j++){
                            if (tmp->next==nullptr){
                                return Iterator(tmp);
                            }
                            tmp = tmp->next;
                        }
                    } else if (offset<0){
                        for (int j=0;j<-offset;j++){
                            if (tmp->prior==nullptr){
                                return Iterator(tmp);
                            }
                            tmp = tmp->prior;
                        }
                    }
                    Iterator it(tmp);
                    return it;
                }
 
        };
 
        List(Allocator &allocator=DefaultAllocator) { 
            p_allocator = &allocator;
            link(); 
        };
        List(List&ref) = default;
 
        template<size_t N>
        List(const T (&a)[N], Allocator &allocator=DefaultAllocator) {
            p_allocator = &allocator;
            link();
            for(int i = 0; i < N; ++i) 
                push_back(a[i]);
        }
 
         ~List(){
            clear();
        }
 
#ifdef USE_INITIALIZER_LIST
 
        List(std::initializer_list<T> iniList) {
            link();
            for(auto &obj : iniList) 
                push_back(obj);
        } 
#endif        
        bool swap(List<T>&ref){
            List<T> tmp(*this);
            validate();
 
            first = ref.first;
            last = ref.last;
            record_count = ref.record_count;
 
            ref.first = tmp.first;
            ref.last = tmp.last;
            ref.record_count = tmp.record_count;
 
            validate();
            return true;
        }
 
        bool push_back(T data){
            Node *node = createNode();
            if (node==nullptr) return false;
            node->data = data;
 
            // update links
            Node *old_last_prior = last.prior;
            node->next = &last;
            node->prior = old_last_prior;
            old_last_prior->next = node;
            last.prior = node;
 
            record_count++;
            validate();
            return true;
        }
 
        bool push_front(T data){
            Node *node = createNode();
            if (node==nullptr) return false;
            node->data = data;
 
            // update links
            Node *old_begin_next = first.next;
            node->prior = &first;
            node->next = old_begin_next;
            old_begin_next->prior = node;
            first.next = node;
 
            record_count++;
            validate();
            return true;
        }
 
        bool insert(Iterator it, const T& data){
            Node *node = createNode();
            if (node==nullptr) return false;
            node->data = data;
 
            // update links
            Node *current_node = it.get_node();
            Node *prior = current_node->prior;
 
            prior->next = node;
            current_node->prior = node;
            node->prior = prior;
            node->next = current_node;
 
            record_count++;
            validate();
            return true;
        }
 
 
        bool pop_front(){
            T tmp;
            return pop_front(tmp);
        }
 
        bool pop_back(){
            T tmp;
            return pop_back(tmp);
        }
 
        bool pop_front(T &data){
            if (record_count==0) return false;
            // get data
            Node *p_delete = firstDataNode();
            Node *p_prior = p_delete->prior;
            Node *p_next = p_delete->next;
 
            data = p_delete->data;
 
            // remove last node
            p_prior->next = p_next;
            p_next->prior = p_prior;
 
            deleteNode(p_delete);
 
            record_count--;    
 
            validate();
            return true;
        }
 
        bool pop_back(T &data){
            if (record_count==0) return false;
            Node *p_delete = lastDataNode();
            Node *p_prior = p_delete->prior;
            Node *p_next = p_delete->next;
 
            // get data
            data = p_delete->data;
 
            // remove last node
            p_prior->next = p_next;
            p_next->prior = p_prior;
 
            deleteNode(p_delete);
 
            record_count--;
 
            validate();
            return true;
        }
 
        bool erase (Iterator it){
            Node *p_delete = it.get_node();
            // check for valid iterator 
            if (empty() || p_delete==&first || p_delete==&last){
                return false;
            }
            Node *p_prior = p_delete->prior;
            Node *p_next = p_delete->next;
 
            // remove last node
            p_prior->next = p_next;
            p_next->prior = p_prior;
 
            deleteNode(p_delete);
 
            record_count--;    
            return true;
        }
 
 
        Iterator begin() {
            Iterator it(firstDataNode());
            return it;
        }
 
        Iterator end(){
             Iterator it(&last);
             return it;
        }
 
        Iterator rbegin() {
            Iterator it(lastDataNode());
            return it;
        }
 
        Iterator rend(){
            Iterator it(&first);
            return it;
        }
 
        size_t size() {
            return record_count;
        }
 
        bool empty() {
            return size()==0;
        }
 
        bool clear() {
            while(pop_front())
                ;
            validate();
            return true;
        }
 
        inline T &operator[](int index) {
            Node *n = firstDataNode();
            for (int j=0;j<index;j++){
                n = n->next;
                if (n==nullptr){
                    return last.data;
                }
            }
            return n->data;
        }
 
        void setAllocator(Allocator &allocator){
            p_allocator = &allocator;
        }
 
        T& front() {
            return *begin();
        }
 
        T& back() {
            return *rbegin();
        }
 
 
    protected:
        Node first; // empty dummy first node which which is always before the first data node 
        Node last; // empty dummy last node which which is always after the last data node 
        size_t record_count=0;
        Allocator *p_allocator = &DefaultAllocator;
 
        Node* createNode() {
#if USE_ALLOCATOR
            Node *node = (Node*) p_allocator->allocate(sizeof(Node));// new Node();
#else
            Node *node = new Node();
#endif
            return node;
        }
 
        void deleteNode(Node* p_delete){
#if USE_ALLOCATOR
            p_allocator->free(p_delete); //delete p_delete;
#else
            delete p_delete;
#endif
 
        }
 
        void link(){
            first.next = &last;
            last.prior = &first;
        }
 
        Node* lastDataNode(){
            return last.prior;
        }
        Node* firstDataNode(){
            return first.next;
        }
 
        void validate() {
            assert(first.next!=nullptr);
            assert(last.prior!=nullptr);
            if (empty()){
                assert(first.next == &last);
                assert(last.prior == &first);
            }
        }
 
};
 
}