// http://www.fredosaurus.com/notes-cpp/strings/header-string.html

#ifndef DARRAY_H
#define DARRAY_H

#include <iostream>
#include "types.h"

using namespace std;

// namespace utils{

// Default array increment (uses here a number divisible by 4)
#define LA_ARRAY_INCR 4

// Tolerable waste of space
#define LA_ARRAY_MAX_WASTE (3*LA_ARRAY_INCR-1)


template <typename T>
class DArray
{
public:
    typedef int  (*CompareFunction)(T &e1, T &e2);
    typedef void (*DeleteFunction)(T &e);

    T nullItem;

    DArray()
    {
        init(0, NULL, NULL);
    }

    DArray(u32 _size)
    {
        init(_size, NULL, NULL);
    }


    DArray(CompareFunction _compare_f, DeleteFunction _delete_f)
    {
        init(0, _compare_f, _delete_f);
    }

    DArray(u32 _size, CompareFunction _compare_f, DeleteFunction _delete_f)
    {
        init(_size, _compare_f, _delete_f);
    }

    // Set compare (sort) function. Call this before you add data.
    void setSortFunction(CompareFunction _compare_f)
    {
        compare_f = _compare_f;
    }

    // Set delete function. Call this before you add data.
    void setDeleteFunction(DeleteFunction _delete_f)
    {
        delete_f = _delete_f;
    }

    u32 size()
    {
        return length;
    }

    u32 alloc_size()
    {
        return alloc_length;
    }


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

        return data[_idx];
    }

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

    DArray &operator +(T &e)
    {
        insert(e);
        return *this;
    }

    DArray &operator -(T &e)
    {
        u32 idx;
        int found;

        idx = find_idx(e, &found);

        if (found) this->delete_at(idx);

        return *this;
    }


    DArray &operator +=(T &e)
    {
        insert(e);
        return *this;
    }

    // Insert data e in sorted position or in tail if compare_f == NULL. Expand array and move data.
    int insert(T &e)
    {
        // @a: The array
        // @e: Insert this data element (pointer to data)
        //
        // Returns 1(true) if OK, otherwise 0(false).

        u32 idx;
        int found;

        // Find position (sorted order)
        idx = find_idx(e, &found);

        return insert_at(e, idx);
    }

    // Insert data pointed by e at idx. Create space, expand array and move data.
    int insert_at(T &e, u32 idx /* 0,1,2,...*/)
    {
        u32 len;

        if (idx+1 > length)
            len = idx+1;
        else
            len = length+1;

        allocate(len);

        // Create an empty slot. Move array elements.
        if (idx < length)
            move_data(idx, idx+1, length - idx);
        // memmove(a->data + idx+1, a->data+idx, (a->length - idx)*sizeof(void*));

        data[idx] = e;
        length = len;

        return idx;
    }

    inline int push_back(T &e)
    {
        return add(e);
    }

    // Add item e at the tail, (or in sorted position if sorted array). Expand array.
    int add(T &e)
    {
        // @a: The array
        // @e: Add this data element (pointer to data)
        //
        // Returns 1(true) if OK, otherwise 0(false).

        return insert(e);
    }


    // Put item e at the index idx. Just replace the existing slot. Do NOT move data.
    // Equivalent to: x[idx] = e.
    int set_at(T &e, u32 idx /* 0,1,2,...*/)
    {
        // @a: The array
        // @e: Put this data element (pointer to data)
        // @idx: Put at this index.
        //
        // Returns 1(true) if OK, otherwise 0(false).

        u32 len;

        if (idx+1 > length)
            len = idx+1;
        else
            len = length;

        // Make sure we have space
        allocate(len);

        // TODO FIX: Should we delete the old item?
        if (delete_f) delete_f(data[idx]);

        data[idx] = e;
        length = len;
        return 1;
    }

    // Delete the item at idx. Move data,compress array.
    int delete_at(u32 idx)
    {
        // @a: The array
        // @idx: Delete this index
        //
        // Returns 1(true) if OK, otherwise 0(false).

        if (idx >= length) return 0;

        if (delete_f)
        {
            delete_f(data[idx]);
            // data[idx] = NULL;
            memset(&data[idx], '\0', sizeof(T));
        }

        // Remove, sequeeze one slot. Move array elements to the left.
        if (length > 1)
            move_data(idx+1, idx, length - idx -1);

        memset(&data[length], '\0', sizeof(T));

        length--;

        return squeeze();
    }

    // int add(T &e)
    s32 find_item(T e, int *found)
    {
        u32 idx;

        // Find position (sorted order)
        idx = find_idx(e, found);

        if (*found)
            return idx;
        else
            return -1;
    }

    // Squeeze array. Deallocate unused space.
    int squeeze()
    {
        // @a: The array
        //
        // Returns 1(true) if OK, otherwise 0(false).
        u32 siz;
        T *p;

        try
        {

            if (alloc_length > length + LA_ARRAY_MAX_WASTE)
            {
                // Set new (minimized) size to multiple of LA_ARRAY_INCR.
                siz = (((length - 1)/ LA_ARRAY_INCR)* LA_ARRAY_INCR) + LA_ARRAY_INCR;

                p = new T[siz * sizeof(T)];

                // Enough memory?
                if (!p) throw "Squeeze: Cannot reallocate memory";

                memmove(p, data, length *sizeof(T));

                data = p;
                alloc_length = siz;
            }

        }
        catch ( char *e)
        {
            cerr << e << endl;
            throw;
        }

        return 1;
    }

    // Remove, wipe the entire array
    int clear()
    {
        return wipe();
    }

    // Remove, wipe the entire array
    int wipe()
    {
        // @a: The array
        //
        // Returns 1(true) if OK, otherwise 0(false).
        u32 i;

        if (!data) return 1;

        // Deallocate user's data
        if (delete_f)
        {
            for (i=0; i < length; i++)
            {
                // if (&data[i])
                {
                    delete_f(data[i]);
                    memset(&data[i], '\0', sizeof(T));
                }
            }
        }

        // Deallocate array
        // delete [] data;  // Calls destrcutor in each object
        delete data;
        data = NULL;
        length = 0;
        alloc_length = 0;

        return 1;
    }



    void setSize(u32 _length)
    {
        u32 i;

        if (_length == 0)
        {
            wipe();
            return;
        }

        for (i=_length; i < length; i++)
        {
            if (delete_f)
            {
                delete_f(data[i]);
            }
            memset(&data[i], '\0', sizeof(T));
        }

        allocate(_length);
    }


private:
    T *data;
    u32 length;
    u32 alloc_length;

    CompareFunction compare_f;
    DeleteFunction   delete_f;


    void init(u32 _len, CompareFunction _compare_f, DeleteFunction _delete_f)
    {
        length = _len;
        alloc_length = 0;
        compare_f = _compare_f;
        delete_f = _delete_f;
        data = NULL;

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

    // Find data pointed by *e. Returns index and sets found_flag.
    u32 find_idx(T &e, int *found_flag)
    {
        u32 first, last, mid;
        int test; // must be a signed int

        *found_flag = 0;

        // Has a compare function?
        if (!compare_f)
            return length;
        else if (length == 0)
            return 0;

        // Do binary search. O(log2)
        first = mid = 0;
        last = length - 1;

        while (first <= last)
        {
            mid = first + (last - first)/2;  // Read next line.
            // mid = (first + last)/2; <-- Can cause a MAX_UINT overflow!
            test = compare_f(e, data[mid]);
            if (test == 0)
            {
                // Found!
                *found_flag = 1;
                return mid;
            }
            else if (test < 0)
            {
                // Note: "last" is u32, it cannot be < 0.
                if (mid == 0)
                    return 0;
                else
                    last = mid - 1;
            }
            else
            {
                first = mid + 1;
            }
        }

        if (test < 0)
            return mid;
        else
            return last+1;
    }

    // Move array elements _from _to
    inline int move_data(u32 _from, u32 _to, u32 _num_items)
    {
        // @a: The array
        // @_from: Move from this index
        // @_to: To this index
        // @_num_items: Number of items (slots)
        //
        // Returns 1(true) if OK, otherwise 0(false).

        // Move memory. Memmove can handle overlapping data. (that's important)
        if (memmove(data + _to, data + _from, _num_items*sizeof(T)))
            return 1;
        else
            return 0;
    }



    void allocate(u32 _length=3)
    {
        u32 siz;

        try
        {

            // Expand?
            if (_length > alloc_length)
            {
                T *p;

                // Calculate new size
                siz = (((_length - 1)/ LA_ARRAY_INCR)* LA_ARRAY_INCR) + LA_ARRAY_INCR;

                p = new T[siz * sizeof(T)];

                // Enough memory?
                if (!p) throw "allocate: Cannot allocate memory";

                memmove(p, data, length *sizeof(T));

                if (data) delete data;
                // delete [] data;

                data = p;

                // Set new slots to NULL
                memset(data + length, '\0', (siz - length)*sizeof(T));

                alloc_length = siz;
            }

        }
        catch ( char *e)
        {
            cerr << e << endl;
            throw;
        }

    }


};

// }

#endif