/* -*- mode: C -*-  */
/*
   IGraph library.
   Copyright (C) 2003-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301 USA

*/

#include "igraph_types.h"
#include "igraph_vector_ptr.h"
#include "igraph_memory.h"
#include "igraph_random.h"
#include "igraph_error.h"
#include "config.h"

#include <assert.h>
#include <string.h>         /* memcpy & co. */
#include <stdlib.h>

/**
 * \section about_igraph_vector_ptr_objects Pointer vectors
 * (<type>igraph_vector_ptr_t</type>)
 *
 * <para>The \type igraph_vector_ptr_t data type is very similar to
 * the \type igraph_vector_t type, but it stores generic pointers instead of
 * real numbers.</para>
 *
 * <para>This type has the same space complexity as \type
 * igraph_vector_t, and most implemented operations work the same way
 * as for \type igraph_vector_t. </para>
 *
 * <para>This type is mostly used to pass to or receive from a set of
 * graphs to some \a igraph functions, such as \ref
 * igraph_decompose(), which decomposes a graph to connected
 * components.</para>
 *
 * <para>The same \ref VECTOR macro used for ordinary vectors can be
 * used for pointer vectors as well, please note that a typeless
 * generic pointer will be provided by this macro and you may need to
 * cast it to a specific pointer before starting to work with it.</para>
 *
 * <para>Pointer vectors may have an associated item destructor function
 * which takes a pointer and returns nothing. The item destructor will
 * be called on each item in the pointer vector when it is destroyed by
 * \ref igraph_vector_ptr_destroy() or \ref igraph_vector_ptr_destroy_all(),
 * or when its elements are freed by \ref igraph_vector_ptr_free_all().
 * Note that the semantics of an item destructor does not coincide with
 * C++ destructors; for instance, when a pointer vector is resized to a
 * smaller size, the extra items will \em not be destroyed automatically!
 * Nevertheless, item destructors may become handy in many cases; for
 * instance, a vector of graphs generated by \ref igraph_decompose() can
 * be destroyed with a single call to \ref igraph_vector_ptr_destroy_all()
 * if the item destructor is set to \ref igraph_destroy().</para>
 */


/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_init
 * \brief Initialize a pointer vector (constructor).
 *
 * </para><para>
 * This is the constructor of the pointer vector data type. All
 * pointer vectors constructed this way should be destroyed via
 * calling \ref igraph_vector_ptr_destroy().
 * \param v Pointer to an uninitialized
 *        <type>igraph_vector_ptr_t</type> object, to be created.
 * \param size Integer, the size of the pointer vector.
 * \return Error code:
 *         \c IGRAPH_ENOMEM if out of memory
 *
 * Time complexity: operating system dependent, the amount of \quote
 * time \endquote required to allocate \p size elements.
 */

int igraph_vector_ptr_init      (igraph_vector_ptr_t* v, int long size) {
    long int alloc_size = size > 0 ? size : 1;
    assert(v != NULL);
    if (size < 0) {
        size = 0;
    }
    v->stor_begin = igraph_Calloc(alloc_size, void*);
    if (v->stor_begin == 0) {
        IGRAPH_ERROR("vector ptr init failed", IGRAPH_ENOMEM);
    }
    v->stor_end = v->stor_begin + alloc_size;
    v->end = v->stor_begin + size;
    v->item_destructor = 0;

    return 0;
}

/**
 */

const igraph_vector_ptr_t *igraph_vector_ptr_view (const igraph_vector_ptr_t *v, void *const *data,
        long int length) {
    igraph_vector_ptr_t *v2 = (igraph_vector_ptr_t*) v;
    v2->stor_begin = (void **)data;
    v2->stor_end = (void**)data + length;
    v2->end = v2->stor_end;
    v2->item_destructor = 0;
    return v;
}

/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_destroy
 * \brief Destroys a pointer vector.
 *
 * </para><para>
 * The destructor for pointer vectors.
 * \param v Pointer to the pointer vector to destroy.
 *
 * Time complexity: operating system dependent, the \quote time
 * \endquote required to deallocate O(n) bytes, n is the number of
 * elements allocated for the pointer vector (not necessarily the
 * number of elements in the vector).
 */

void igraph_vector_ptr_destroy   (igraph_vector_ptr_t* v) {
    assert(v != 0);
    if (v->stor_begin != 0) {
        igraph_Free(v->stor_begin);
        v->stor_begin = NULL;
    }
}

void igraph_i_vector_ptr_call_item_destructor_all(igraph_vector_ptr_t* v) {
    void **ptr;

    if (v->item_destructor != 0) {
        for (ptr = v->stor_begin; ptr < v->end; ptr++) {
            if (*ptr != 0) {
                v->item_destructor(*ptr);
            }
        }
    }
}

/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_free_all
 * \brief Frees all the elements of a pointer vector.
 *
 * If an item destructor is set for this pointer vector, this function will
 * first call the destructor on all elements of the vector and then
 * free all the elements using free(). If an item destructor is not set,
 * the elements will simply be freed.
 *
 * \param v Pointer to the pointer vector whose elements will be freed.
 *
 * Time complexity: operating system dependent, the \quote time
 * \endquote required to call the destructor n times and then
 * deallocate O(n) pointers, each pointing to a memory area of
 * arbitrary size. n is the number of elements in the pointer vector.
 */

void igraph_vector_ptr_free_all   (igraph_vector_ptr_t* v) {
    void **ptr;
    assert(v != 0);
    assert(v->stor_begin != 0);

    igraph_i_vector_ptr_call_item_destructor_all(v);
    for (ptr = v->stor_begin; ptr < v->end; ptr++) {
        igraph_Free(*ptr);
    }
}

/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_destroy_all
 * \brief Frees all the elements and destroys the pointer vector.
 *
 * This function is equivalent to \ref igraph_vector_ptr_free_all()
 * followed by \ref igraph_vector_ptr_destroy().
 *
 * \param v Pointer to the pointer vector to destroy.
 *
 * Time complexity: operating system dependent, the \quote time
 * \endquote required to deallocate O(n) pointers, each pointing to
 * a memory area of arbitrary size, plus the \quote time \endquote
 * required to deallocate O(n) bytes, n being the number of elements
 * allocated for the pointer vector (not necessarily the number of
 * elements in the vector).
 */

void igraph_vector_ptr_destroy_all   (igraph_vector_ptr_t* v) {
    assert(v != 0);
    assert(v->stor_begin != 0);
    igraph_vector_ptr_free_all(v);
    igraph_vector_ptr_set_item_destructor(v, 0);
    igraph_vector_ptr_destroy(v);
}

/**
 * \ingroup vectorptr
 * \brief Reserves memory for a pointer vector for later use.
 *
 * @return Error code:
 *         - <b>IGRAPH_ENOMEM</b>: out of memory
 */

int igraph_vector_ptr_reserve   (igraph_vector_ptr_t* v, long int size) {
    long int actual_size = igraph_vector_ptr_size(v);
    void **tmp;
    assert(v != NULL);
    assert(v->stor_begin != NULL);

    if (size <= igraph_vector_ptr_size(v)) {
        return 0;
    }

    tmp = igraph_Realloc(v->stor_begin, (size_t) size, void*);
    if (tmp == 0) {
        IGRAPH_ERROR("vector ptr reserve failed", IGRAPH_ENOMEM);
    }
    v->stor_begin = tmp;
    v->stor_end = v->stor_begin + size;
    v->end = v->stor_begin + actual_size;

    return 0;
}

/**
 * \ingroup vectorptr
 * \brief Decides whether the pointer vector is empty.
 */

igraph_bool_t igraph_vector_ptr_empty     (const igraph_vector_ptr_t* v) {
    assert(v != NULL);
    assert(v->stor_begin != NULL);
    return v->stor_begin == v->end;
}

/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_size
 * \brief Gives the number of elements in the pointer vector.
 *
 * \param v The pointer vector object.
 * \return The size of the object, ie. the number of pointers stored.
 *
 * Time complexity: O(1).
 */

long int igraph_vector_ptr_size      (const igraph_vector_ptr_t* v) {
    assert(v != NULL);
    /*  assert(v->stor_begin != NULL);       */ /* TODO */
    return v->end - v->stor_begin;
}

/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_clear
 * \brief Removes all elements from a pointer vector.
 *
 * </para><para>
 * This function resizes a pointer to vector to zero length. Note that
 * the pointed objects are \em not deallocated, you should call
 * free() on them, or make sure that their allocated memory is freed
 * in some other way, you'll get memory leaks otherwise. If you have
 * set up an item destructor earlier, the destructor will be called
 * on every element.
 *
 * </para><para>
 * Note that the current implementation of this function does
 * \em not deallocate the memory required for storing the
 * pointers, so making a pointer vector smaller this way does not give
 * back any memory. This behavior might change in the future.
 * \param v The pointer vector to clear.
 *
 * Time complexity: O(1).
 */

void igraph_vector_ptr_clear     (igraph_vector_ptr_t* v) {
    assert(v != NULL);
    assert(v->stor_begin != NULL);
    igraph_i_vector_ptr_call_item_destructor_all(v);
    v->end = v->stor_begin;
}

/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_push_back
 * \brief Appends an element to the back of a pointer vector.
 *
 * \param v The pointer vector.
 * \param e The new element to include in the pointer vector.
 * \return Error code.
 * \sa igraph_vector_push_back() for the corresponding operation of
 * the ordinary vector type.
 *
 * Time complexity: O(1) or O(n), n is the number of elements in the
 * vector. The pointer vector implementation ensures that n subsequent
 * push_back operations need O(n) time to complete.
 */

int igraph_vector_ptr_push_back (igraph_vector_ptr_t* v, void* e) {
    assert(v != NULL);
    assert(v->stor_begin != NULL);

    /* full, allocate more storage */
    if (v->stor_end == v->end) {
        long int new_size = igraph_vector_ptr_size(v) * 2;
        if (new_size == 0) {
            new_size = 1;
        }
        IGRAPH_CHECK(igraph_vector_ptr_reserve(v, new_size));
    }

    *(v->end) = e;
    v->end += 1;

    return 0;
}

void *igraph_vector_ptr_pop_back (igraph_vector_ptr_t *v) {
    assert(v != NULL);
    assert(v->stor_begin != NULL);
    assert(v->stor_begin != v->end);
    v->end -= 1;
    return *(v->end);
}

/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_insert
 * \brief Inserts a single element into a pointer vector.
 *
 * Note that this function does not do range checking. Insertion will shift the
 * elements from the position given to the end of the vector one position to the
 * right, and the new element will be inserted in the empty space created at
 * the given position. The size of the vector will increase by one.
 *
 * \param v The pointer vector object.
 * \param pos The position where the new element is inserted.
 * \param e The inserted element
 */
int igraph_vector_ptr_insert(igraph_vector_ptr_t* v, long int pos, void* e) {
    long int size = igraph_vector_ptr_size(v);
    IGRAPH_CHECK(igraph_vector_ptr_resize(v, size + 1));
    if (pos < size) {
        memmove(v->stor_begin + pos + 1, v->stor_begin + pos,
                sizeof(void*) * (size_t) (size - pos));
    }
    v->stor_begin[pos] = e;
    return 0;
}

/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_e
 * \brief Access an element of a pointer vector.
 *
 * \param v Pointer to a pointer vector.
 * \param pos The index of the pointer to return.
 * \return The pointer at \p pos position.
 *
 * Time complexity: O(1).
 */

void* igraph_vector_ptr_e         (const igraph_vector_ptr_t* v, long int pos) {
    assert(v != NULL);
    assert(v->stor_begin != NULL);
    return * (v->stor_begin + pos);
}

/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_set
 * \brief Assign to an element of a pointer vector.
 *
 * \param v Pointer to a pointer vector.
 * \param pos The index of the pointer to update.
 * \param value The new pointer to set in the vector.
 *
 * Time complexity: O(1).
 */

void igraph_vector_ptr_set       (igraph_vector_ptr_t* v, long int pos, void* value) {
    assert(v != NULL);
    assert(v->stor_begin != NULL);
    *(v->stor_begin + pos) = value;
}

/**
 * \ingroup vectorptr
 * \brief Set all elements of a pointer vector to the NULL pointer.
 */

void igraph_vector_ptr_null      (igraph_vector_ptr_t* v) {
    assert(v != NULL);
    assert(v->stor_begin != NULL);
    if (igraph_vector_ptr_size(v) > 0) {
        memset(v->stor_begin, 0, sizeof(void*) *
               (size_t) igraph_vector_ptr_size(v));
    }
}

/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_resize
 * \brief Resizes a pointer vector.
 *
 * </para><para>
 * Note that if a vector is made smaller the pointed object are not
 * deallocated by this function and the item destructor is not called
 * on the extra elements.
 *
 * \param v A pointer vector.
 * \param newsize The new size of the pointer vector.
 * \return Error code.
 *
 * Time complexity: O(1) if the vector if made smaller. Operating
 * system dependent otherwise, the amount of \quote time \endquote
 * needed to allocate the memory for the vector elements.
 */

int igraph_vector_ptr_resize(igraph_vector_ptr_t* v, long int newsize) {
    IGRAPH_CHECK(igraph_vector_ptr_reserve(v, newsize));
    v->end = v->stor_begin + newsize;
    return 0;
}

/**
 * \ingroup vectorptr
 * \brief Initializes a pointer vector from an array (constructor).
 *
 * \return Error code:
 *         \c IGRAPH_ENOMEM if out of memory
 */

int igraph_vector_ptr_init_copy(igraph_vector_ptr_t *v, void * *data, long int length) {
    v->stor_begin = igraph_Calloc(length, void*);
    if (v->stor_begin == 0) {
        IGRAPH_ERROR("cannot init ptr vector from array", IGRAPH_ENOMEM);
    }
    v->stor_end = v->stor_begin + length;
    v->end = v->stor_end;
    v->item_destructor = 0;
    memcpy(v->stor_begin, data, (size_t) length * sizeof(void*));

    return 0;
}

/**
 * \ingroup vectorptr
 * \brief Copy the contents of a pointer vector to a regular C array.
 */

void igraph_vector_ptr_copy_to(const igraph_vector_ptr_t *v, void** to) {
    assert(v != NULL);
    assert(v->stor_begin != NULL);
    if (v->end != v->stor_begin) {
        memcpy(to, v->stor_begin, sizeof(void*) *
               (size_t) (v->end - v->stor_begin));
    }
}

/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_copy
 * \brief Copy a pointer vector (constructor).
 *
 * </para><para>
 * This function creates a pointer vector by copying another one. This
 * is shallow copy, only the pointers in the vector will be copied.
 *
 * </para><para>
 * It is potentially dangerous to copy a pointer vector with an associated
 * item destructor. The copied vector will inherit the item destructor,
 * which may cause problems when both vectors are destroyed as the items
 * might get destroyed twice. Make sure you know what you are doing when
 * copying a pointer vector with an item destructor, or unset the item
 * destructor on one of the vectors later.
 *
 * \param to Pointer to an uninitialized pointer vector object.
 * \param from A pointer vector object.
 * \return Error code:
 *         \c IGRAPH_ENOMEM if out of memory
 *
 * Time complexity: O(n) if allocating memory for n elements can be
 * done in O(n) time.
 */

int igraph_vector_ptr_copy(igraph_vector_ptr_t *to, const igraph_vector_ptr_t *from) {
    assert(from != NULL);
    /*   assert(from->stor_begin != NULL); */ /* TODO */
    to->stor_begin = igraph_Calloc(igraph_vector_ptr_size(from), void*);
    if (to->stor_begin == 0) {
        IGRAPH_ERROR("cannot copy ptr vector", IGRAPH_ENOMEM);
    }
    to->stor_end = to->stor_begin + igraph_vector_ptr_size(from);
    to->end = to->stor_end;
    to->item_destructor = from->item_destructor;
    memcpy(to->stor_begin, from->stor_begin,
           (size_t) igraph_vector_ptr_size(from)*sizeof(void*));

    return 0;
}

/**
 * \ingroup vectorptr
 * \brief Remove an element from a pointer vector.
 */

void igraph_vector_ptr_remove(igraph_vector_ptr_t *v, long int pos) {
    assert(v != NULL);
    assert(v->stor_begin != NULL);
    if (pos + 1 < igraph_vector_ptr_size(v)) { /* TOOD: why is this needed */
        memmove(v->stor_begin + pos, v->stor_begin + pos + 1,
                sizeof(void*) * (size_t) (igraph_vector_ptr_size(v) - pos - 1));
    }
    v->end--;
}

/**
 * \ingroup vectorptr
 * \brief Sort the pointer vector based on an external comparison function
 *
 * Sometimes it is necessary to sort the pointers in the vector based on
 * the property of the element being referenced by the pointer. This
 * function allows us to sort the vector based on an arbitrary external
 * comparison function which accepts two \c void* pointers \c p1 and \c p2
 * and returns an integer less than, equal to or greater than zero if the
 * first argument is considered to be respectively less than, equal to, or
 * greater than the second. \c p1 and \c p2 will point to the pointer in the
 * vector, so they have to be double-dereferenced if one wants to get access
 * to the underlying object the address of which is stored in \c v .
 */
void igraph_vector_ptr_sort(igraph_vector_ptr_t *v, int (*compar)(const void*, const void*)) {
    qsort(v->stor_begin, (size_t) igraph_vector_ptr_size(v), sizeof(void*),
          compar);
}

int igraph_vector_ptr_index_int(igraph_vector_ptr_t *v,
                                const igraph_vector_int_t *idx) {
    void **tmp;
    int i, n = igraph_vector_int_size(idx);

    tmp = igraph_Calloc(n, void*);
    if (!tmp) {
        IGRAPH_ERROR("Cannot index pointer vector", IGRAPH_ENOMEM);
    }

    for (i = 0; i < n; i++) {
        tmp[i] = VECTOR(*v)[ VECTOR(*idx)[i] ];
    }

    igraph_Free(v->stor_begin);
    v->stor_begin = tmp;
    v->stor_end = v->end = tmp + n;

    return 0;
}

int igraph_vector_ptr_append    (igraph_vector_ptr_t *to,
                                 const igraph_vector_ptr_t *from) {
    long int origsize = igraph_vector_ptr_size(to);
    long int othersize = igraph_vector_ptr_size(from);
    long int i;

    IGRAPH_CHECK(igraph_vector_ptr_resize(to, origsize + othersize));
    for (i = 0; i < othersize; i++, origsize++) {
        to->stor_begin[origsize] = from->stor_begin[i];
    }

    return 0;
}


/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_set_item_destructor
 * \brief Sets the item destructor for this pointer vector.
 *
 * The item destructor is a function which will be called on every non-null
 * pointer stored in this vector when \ref igraph_vector_ptr_destroy(),
 * igraph_vector_ptr_destroy_all() or \ref igraph_vector_ptr_free_all()
 * is called.
 *
 * \return The old item destructor.
 *
 * Time complexity: O(1).
 */
igraph_finally_func_t* igraph_vector_ptr_set_item_destructor(
    igraph_vector_ptr_t *v, igraph_finally_func_t *func) {
    igraph_finally_func_t* result = v->item_destructor;

    v->item_destructor = func;

    return result;
}

/**
 * \ingroup vectorptr
 * \function igraph_vector_ptr_get_item_destructor
 * \brief Gets the current item destructor for this pointer vector.
 *
 * The item destructor is a function which will be called on every non-null
 * pointer stored in this vector when \ref igraph_vector_ptr_destroy(),
 * igraph_vector_ptr_destroy_all() or \ref igraph_vector_ptr_free_all()
 * is called.
 *
 * \return The current item destructor.
 *
 * Time complexity: O(1).
 */
igraph_finally_func_t* igraph_vector_ptr_get_item_destructor(const igraph_vector_ptr_t *v) {
    assert(v != 0);
    return v->item_destructor;
}