/*
 * CS5600 University of Utah
 * Charles McGarvey
 * mcgarvey@eng.utah.edu
 */

#ifndef _ARRAY_H_
#define _ARRAY_H_

#include "assert.h"
#include "common.h"


#define ARRAY_CAPACITY_DEFAULT  (128)
#define ARRAY_CAPACITY_MIN      (4)


/*
 * A random-access dynamically-expandable array class.
 */
struct array
{
    void*   arr;
    size_t  cap;
    size_t  len;
    size_t  siz;
};
typedef struct array array_t;

/*
 * Allocate a new array with the element size and initial capacity.
 */
array_t* array_alloc2(size_t size, size_t capacity);

/*
 * Allocate a new array with the element size.
 */
INLINE_MAYBE
array_t* array_alloc(size_t size)
{
    return array_alloc2(size, ARRAY_CAPACITY_DEFAULT);
}

#define array_alloc_type(T)        array_alloc(sizeof(T))
#define array_alloc_type2(T, C)    array_alloc2(sizeof(T), C)

/*
 * Destroy an array, freeing up its memory.
 */
INLINE_MAYBE
void array_destroy(array_t* v)
{
    assert(v && v->arr);
    mem_free(v->arr);
    mem_free(v);
}


/*
 * An iterator class for the array.
 */
struct array_it
{
    const array_t*  arr;
    size_t          pos;
    int             dir;
};
typedef struct array_it array_it_t;

/*
 * Initialize an array iterator.
 */
INLINE_MAYBE
void array_it_init(array_it_t* it, const array_t* v, size_t position, int direction)
{
    assert(it);
    it->arr = v;
    it->pos = position;
    it->dir = direction;
}


/*
 * Index into a random position into the array.
 */
INLINE_MAYBE
void* array_index(const array_t* v, size_t i)
{
    assert(v && v->arr);
    return (char*)v->arr + i * v->siz;
}

/*
 * Get the first item in the array.
 */
INLINE_MAYBE
void* array_front(const array_t* v)
{
    return array_index(v, 0);
}

/*
 * Get the last item in the array.
 */
INLINE_MAYBE
void* array_back(const array_t* v)
{
    return array_index(v, v->len - 1);
}


/*
 * Get a forward iterator at the first item in the array.
 */
INLINE_MAYBE
array_it_t array_begin(const array_t* v)
{
    assert(v && v->arr);
    array_it_t it;
    array_it_init(&it, v, 0, 1);
    return it;
}

/*
 * Get a forward iterator after the last item in the array.
 */
INLINE_MAYBE
array_it_t array_end(const array_t* v)
{
    assert(v && v->arr);
    array_it_t it;
    array_it_init(&it, v, v->len, 1);
    return it;
}

/*
 * Get a backward iterator at the last item in the array.
 */
INLINE_MAYBE
array_it_t array_rbegin(const array_t* v)
{
    assert(v && v->arr);
    array_it_t it;
    array_it_init(&it, v, v->len - 1, -1);
    return it;
}

/*
 * Get a backward iterator before the first item in the array.
 */
INLINE_MAYBE
array_it_t array_rend(const array_t* v)
{
    assert(v && v->arr);
    array_it_t it;
    array_it_init(&it, v, -1, -1);
    return it;
}


/*
 * Get the current capacity of the array.  The capacity is how many elements
 * could be inserted into the array without reallocating more memory.
 */
INLINE_MAYBE
size_t array_capacity(const array_t* v)
{
    assert(v && v->arr);
    return v->cap;
}

/*
 * Make sure there is at least enough memory for a certain number of elements.
 */
void array_reserve(array_t* v, size_t s);

/*
 * Shrink the amount of memory used to fit what is currently inserted into the
 * array and no more.  Of course more memory can be reallocated later.
 */
void array_done(array_t* v);


/*
 * Get the current number of items in the array.  This is less than or equal
 * to the capacity of the array.
 */
INLINE_MAYBE
size_t array_size(const array_t* v)
{
    assert(v && v->arr);
    return v->len;
}

/*
 * Get whether or not the array is empty.
 */
INLINE_MAYBE
bool array_empty(const array_t* v)
{
    return array_size(v) == 0;
}

/*
 * Resize the array, either truncating or expanding the size.
 */
INLINE_MAYBE
void array_resize(array_t* v, size_t s)
{
    array_reserve(v, s);
    v->len = s;
}

/*
 * Remove all items from the array.
 */
INLINE_MAYBE
void array_clear(array_t* v)
{
    assert(v && v->arr);
    v->len = 0;
}


/*
 * Push an item onto the end of the array.
 */
INLINE_MAYBE
void array_push(array_t* v, void* e)
{
    assert(v && v->arr);
    size_t len = v->len + 1;
    if (v->cap < len) {
        array_reserve(v, len);
    }
    memcpy(array_index(v, v->len), e, v->siz);
    v->len = len;
}


/*
 * Pop the item off of the end of the array.  The item is returned, but its
 * memory could be overwritten with addition array calls, so it must be copied
 * if it needs to be kept.
 */
INLINE_MAYBE
void* array_pop(array_t* v)
{
    assert(v && v->arr);
    return array_index(v, --v->len);
}


/*
 * The type of function used when calling elements of the array.
 */
typedef void (*array_call_fn_t)(size_t i, void* e);

/*
 * Call a function once for each element of the array.
 */
void array_call(const array_t* v, array_call_fn_t fn);


/*
 * Get the element pointed to by an iterator and increment the iterator.
 */
INLINE_MAYBE
void* array_it_next(array_it_t* it)
{
    assert(it->arr);
    if (it->pos < it->arr->len) {
        void* e = array_index(it->arr, it->pos);
        it->pos += it->dir;
        return e;
    }
    return NULL;
}

/*
 * Decrement the iterator and get the element pointed to by the iterator.
 */
INLINE_MAYBE
void* array_it_prev(array_it_t* it)
{
    assert(it->arr);
    if (it->pos - it->dir < it->arr->len) {
        it->pos -= it->dir;
        void* e = array_index(it->arr, it->pos);
        return e;
    }
    return NULL;
}


#define DEFINE_ARRAY_TYPE(T) DEFINE_ARRAY_TYPE2(T##_t, T)
#define DEFINE_ARRAY_TYPE2(T, N) \
INLINE_MAYBE array_t* array_##N##_alloc() \
{ \
    return array_alloc(sizeof(T)); \
} \
INLINE_MAYBE array_t* array_##N##_alloc2(size_t capacity) \
{ \
    return array_alloc2(sizeof(T), capacity); \
} \
INLINE_MAYBE T* array_##N##_index(const array_t* v, size_t i) \
{ \
    return (T*)array_index(v, i); \
} \
INLINE_MAYBE T* array_##N##_front(array_t* v) \
{ \
    return (T*)array_front(v); \
} \
INLINE_MAYBE T* array_##N##_back(array_t* v) \
{ \
    return (T*)array_back(v); \
} \
INLINE_MAYBE void array_##N##_push(array_t* v, T e) \
{ \
    assert(v && v->arr); \
    size_t len = v->len + 1; \
    if (v->cap < len) { \
        array_reserve(v, len); \
    } \
    T* t = array_##N##_back(v); \
    *(t + 1) = e; \
    /* specialize with assignment copying rather than memcpy */ \
    v->len = len; \
} \
INLINE_MAYBE T* array_##N##_pop(array_t* v) \
{ \
    return (T*)array_pop(v); \
} \
typedef void (*array_##N##_call_fn_t)(size_t i, T* e); \
INLINE_MAYBE void \
array_##N##_call(array_t* v, array_##N##_call_fn_t fn) \
{ \
    array_call(v, (array_call_fn_t)fn); \
} \
INLINE_MAYBE T* array_it_##N##_next(array_it_t* it) \
{ \
    return (T*)array_it_next(it); \
} \
INLINE_MAYBE T* array_it_##N##_prev(array_it_t* it) \
{ \
    return (T*)array_it_prev(it); \
}


#endif // _ARRAY_H_