#ifndef DLIST_H
#define DLIST_H

#include <iostream>

#include "types.h"

using namespace std;

// namespace utils{

// Listitem with pointer to data. Implements a doubly linked list.
template <typename T>
struct ListItem
{
    ListItem ()
    {
        // data = (Data)0;
        next = prev = NULL;
    }

    ListItem (T &e)
    {
        data = e;
        next = prev = NULL;
    }

    ~ListItem ()
    {
        next = prev = NULL;
    }


    ListItem *operator ++(int)
    {
        return this->next;
    }

    ListItem *operator --()
    {
        return this->prev;
    }

    //  Pointer to user's data
    T data;

    // Doubly linked
    struct ListItem *next;
    struct ListItem *prev;
};

// ----------------------------------------------------------------------

// List structure itself
template <typename T>
class DList
{
public:
    typedef int  (*CompareFunction)(T &e1, T &e2);
    typedef void (*DeleteFunction)(T &e);

    DList()
    {
        init(NULL, NULL);
    }

    DList(CompareFunction _compare_f, DeleteFunction _delete_f)
    {
        init(_compare_f, _delete_f);
    }

    ~DList()
    {
        wipe();
    }

    void init(CompareFunction _compare_f, DeleteFunction _delete_f)
    {
        numitems = 0;
        lhead = ltail = NULL;
        compare_f = _compare_f;
        delete_f  = _delete_f;

        // NULLitem
        memset(&nullItem, '\0', sizeof(T));
    }

    u32 size()
    {
        return numitems;
    }

    u32 length()
    {
        return size();
    }

    ListItem<T> *head()
    {
        return lhead;
    }

    inline ListItem<T> *front()
    {
        return head();
    }

    inline ListItem<T> *begin()
    {
        return head();
    }

    ListItem<T> *tail()
    {
        return ltail;
    }

    T &at(u32 _idx)
    {
        if (_idx > numitems)
            throw "at: Index out of range";

        return get_nth_item(_idx).data;
    }

    T &operator [] (u32 _idx)
    {
        return this->at(_idx);
    }

    DList &operator +(T &e)
    {
        add(e);
        return *this;
    }

    DList &operator -(T &e)
    {
        remove(e);
        return *this;
    }

    DList &operator +=(T &e)
    {
        add(e);
        return *this;
    }

    int clear()
    {
        return wipe();
    }

    ListItem<T> &push_back(T &e)
    {
        return add(e);
    }

    ListItem<T> &push_front(T &e)
    {
        // @e: Reference to data
        //
        // Returns reference to a new list item
        //
        int found;
        ListItem<T> *item;
        ListItem<T> *item_pos;

        item = new_item(e);

        // Sorted list ?
        // Find insert position ('found' flag is not important here)
        if (compare_f)
            found = find_item(e, &item_pos);
        else
            item_pos = NULL; // Add after last item, in the tail.

        numitems++;

        // Insert new 'item' after 'item_pos'.
        return insert_after(item_pos, item);
    }

    int delete_first()
    {
        return delete_item(lhead, 1);
    }

    int delete_last()
    {
        return delete_item(ltail, 1);
    }


    // Add data (pointer e) as last. If list is sorted, insert in sorted position.
    ListItem<T> &add(T &e)
    {
        // @e: Reference to data
        //
        // Returns reference to a new list item
        //
        int found;
        ListItem<T> *item;
        ListItem<T> *item_pos;

        item = new_item(e);

        // Find insert position ('found' flag is not important here)
        // Sorted list ?
        if (compare_f)
            found = find_item(e, &item_pos);
        else
            item_pos = ltail; // Add after last item, in the tail.

        numitems++;

        // Insert new 'item' after 'item_pos'.
        return insert_after(item_pos, item);
    }


    int find_item(T &e, ListItem<T> **item_pos)
    {
        // @li: The list
        // @e: Pointer to data. Search for this.
        // @item_pos: Found item (or insert new items after this)
        //
        // Returns 1(true) if e was found (in ordered, sorted list).
        // Sets *item_pos (=found item).
        //
        // Returns 0(false) if e was not found (or the list is UNordered).
        // Sets *item_pos  (insert new item _after_ this)
        //
        ListItem<T> *item, *prev;
        int test;

        *item_pos = NULL;

        // Is sorted ?
        if (!compare_f)
        {
            *item_pos = ltail;
            return 0;
        }
        else if (!lhead)
        {
            *item_pos = lhead;
            return 0;
        }

        prev = NULL;
        for (item=lhead; item; item=item->next)
        {
            test = compare_f(e, item->data);
            if (test == 0)
            {
                *item_pos = item;
                return 1;
            }
            else if (test < 0)
            {
                *item_pos = prev;
                return 0;
            }
            prev = item;
        }
        *item_pos = prev;
        return 0;
    }


    // Insert 'item' after 'item_pos'
    ListItem<T> &insert_after(ListItem<T> *item_pos, ListItem<T> *item)
    {
        // @item_pos: Insert new 'item' after this.
        // @item: insert this node.
        //
        // Returns item
        //
        ListItem<T> *temp;

        // If item_pos is NULL, insert first.
        if (!item_pos)
        {
            if (!lhead)
            {
                ltail = item;
            }
            else
            {
                lhead->prev = item;
                item->next = lhead;
            }
            lhead = item;
        }
        else
        {
            // Insert new item after item_pos.
            temp = item_pos->next;

            item->next = temp;
            item->prev = item_pos;

            item_pos->next = item;

            if (temp)
                temp->prev = item;

            if (item_pos == ltail)
                ltail = item;
        }

        return *item;
    }

    // Search and delete item that contains data e.
    int remove(T &e)
    {
        // @e : e is data to be deleted
        //
        // Return 1 (true) if item was found and deleted, otherwise NULL.
        //
        int found;
        ListItem<T> *item_pos;

        // Find e
        found = find_item(e, &item_pos);

        if (found)
            return delete_item(item_pos, 1/* Free mem*/);
    }

    int wipe()
    {
    // Returns 1 (true) if all items (the entire list) was deleted, otherwise 0(false).
    //
        while (size()) delete_first();

        // Re-init
        init(compare_f, delete_f);

        return 1;
    }


private:
    // Number of items in the list
    u32 numitems;

    // First item in the list
    ListItem<T> *lhead;

    // Last item in the list
    ListItem<T> *ltail;

    // User's compare and delete data functions
    CompareFunction compare_f;
    DeleteFunction  delete_f;

    ListItem<T> nullItem;


    // Create new (list)item node.
    ListItem<T> *new_item(T &e)
    {
        //
        // Returns pointer to new plitem_t*
        //
        ListItem<T> *item;
        try
        {
            item = new ListItem<T>(e);

            if (!item) throw "new_item: Cannot allocate memory";
        }
        catch (char *msg)
        {
            cerr << msg << endl;
            throw;
        }

        return item;
    }

    // Remove item from the list. Possibly free memory.
    int delete_item(ListItem<T> *item, u8 _freemem)
    {
        // @item: Remove this list item
        // @_freemem: if 1(true) then deallocate user's data and the item.
        //
        // Returns 1(true) if the item was removed from the list, otherwise 0(false).
        //
        ListItem<T> *temp;
        if (!item) return 0;

        // Call user's delete_f
        //if (delete_f && item->data && _freemem)
        if (delete_f && _freemem)
        {
            delete_f(item->data);
        }

        temp = item->prev;
        if (temp)
            temp->next = item->next;

        temp = item->next;
        if (temp)
            temp->prev = item->prev;

        if (item == lhead)
        {
            lhead = item->next;
        }

        if (item == ltail)
        {
            ltail = item->prev;
        }

        numitems--;

        // Deallocate memory
        if (_freemem)
            delete item;

        return 1;
    }

    ListItem<T> &get_nth_item(u32 _idx)
    {
        ListItem<T> *item;

        u32 i = 0;
        for (item=head(); item; item = item->next)
        {
            if (i == _idx) return *item;
            i++;
        }

        return nullItem;
    }

};


#endif