/**
 * @file   vector.h
 * @brief  Functions for creating and manipulating vectors.
 *
 * A vector is an array that can be resized to meet changing storage
 * requirements.  Usage is typically as follows:

 \include vector_test.c


 *
 * @author Jon Schutz
 * @date   05-Feb-2001
 **/

#ifndef __VECTOR_H
#define __VECTOR_H    /* To stop multiple inclusions. */

#include <stddef.h>
#include <stdint.h>

/** Vector */
typedef struct _vector {
  /** The array to hold the data. */
  void *array;
  /** The size of the array. */
  size_t array_size;
  /** The used size, assuming vector_append is the only operation
      which adds elements to the vector. */
  size_t index;
} vector;

    
/** Add a new item to the end of a vector.

    @param v The vector to which to add an item.
    @param item The item to add.
    @param increment The capacity to add when the array is resized.
           Should be >0, or at least =0 if factor>1.
    @param factor The factor by which to increase storage when the array is
           resized.  Should be >1, or at least =1 if increment>0.
    @return 0 on success, -1 if vector_resize() fails.
*/
#define vector_append(v, item, increment, factor)		\
({								\
  int rv=0;							\
								\
  if ((v)->index >= (v)->array_size)				\
    rv = vector_resize((v), 					\
	 (v)->array_size * factor + increment, sizeof(item));	\
  if (0 == rv)							\
    ((typeof(item) *)(v)->array)[(v)->index++] = item;		\
  rv;								\
})

/** Insert space for several items into a vector at the given
    position.  No items are actually inserted.

    If the given position exceeds the current end index of the array,
    the new end index, then item is inserted before the specified
    position and the end index points to the next position after the
    inserted item.

    If necessary, the vector is resized to accommodate the request.

    @param v The vector to which to insert space.
    @param item An instance or type of the items in the vector.
    @param pos The position at which to insert space.
    @param n The number of items for which to insert space.
    @param increment The capacity to add when the array is resized.
           Should be >0, or at least =0 if factor>1.
    @param factor The factor by which to increase storage when the array is
           resized.  Should be >1, or at least =1 if increment>0.
    @return 0 on success, -1 if vector_resize() fails.
*/
#define vector_insert_space(v, item, pos, n, increment, factor)		\
({									\
  int _rv=0;								\
  int new_end = ((pos)>(v)->index)?((pos)+(n)):((v)->index+(n));	\
  if (new_end > (v)->array_size) {					\
    size_t new_size = (v)->array_size * factor + increment;		\
    if (new_end > new_size)						\
      new_size = new_end;						\
    _rv = vector_resize((v), new_size, sizeof(item));			\
    }									\
  if (0 == _rv) {							\
    if ((v)->index > pos) {						\
      memmove(((char *)(v)->array) + sizeof(item)*((pos)+(n)),		\
	      ((char *)(v)->array) + sizeof(item)*(pos),		\
	      sizeof(item)*((v)->index - pos));				\
     (v)->index += (n);							\
    }									\
    else								\
      (v)->index = new_end;						\
  }									\
  _rv;									\
})

    
/** Add a new item to the vector at a given position. The item is
    inserted before the specified position.

    If the given position exceeds the current end index of the array,
    the new end index, the item is inserted before the specified
    position and the end index points to the next position after the
    inserted item.

    If necessary, the vector is resized to accommodate the request.

    @param v The vector to which to insert an item.
    @param item The item to insert.
    @param pos The position at which to insert the item.
    @param increment The capacity to add when the array is resized.
           Should be >0, or at least =0 if factor>1.
    @param factor The factor by which to increase storage when the array is
           resized.  Should be >1, or at least =1 if increment>0.
    @return 0 on success, -1 if vector_resize() fails.
*/
#define vector_insert(v, item, pos, increment, factor)			\
({									\
  const int c_pos = pos;						\
  int rv = vector_insert_space(v, item, pos, 1, increment, factor);	\
  if (0 == rv) {							\
    ((typeof(item) *)(v)->array)[c_pos] = item;				\
    }									\
  rv;									\
})									\

/** Delete several item from a vector.

    @param v The vector in which to delete the item.
    @param item An instance or type of the item to delete.
    @param pos The first position at which to delete.
    @param n The number of items to delete.
*/
#define vector_delete_n(v, item, pos, n)		\
  if ((v)->index > ((pos) + (n))) {			\
    memmove((v)->array + sizeof(item)*(pos),		\
	   (v)->array + sizeof(item)*((pos)+(n)),	\
	   sizeof(item)*((v)->index - (pos) - (n)));	\
    (v)->index -= (n);					\
  }							\
  else							\
    (v)->index = pos;

/** Delete an item from a vector.

    @param v The vector in which to delete the item.
    @param item An instance or type of the item to delete.
    @param pos The position at which to delete.
*/
#define vector_delete(v, item, pos) \
  vector_delete_n(v, item, pos, 1)		


/** Access a member of a vector. 
    @param v The vector to access
    @param index The index to read.
    @param element_type  The type name or an instance of the 
      type of which the vector is comprised.

    @return v[index]
*/
#define element_at(v, index,  element_type) \
  (((typeof(element_type) *)(v)->array)[index])

/** Reverse items in a vector.
    @param v The vector in which to reverse items.
    @param item The type name or an instance of the 
      type of which the vector is comprised.
    @param start The starting index of the sequence to be reversed.
    @param end The index following the end of the sequence to be
    reversed.
*/
#define vector_reverse(v, item, start, end) {				\
  int _i;								\
  int _half = (end-start)/2;						\
  typeof(item) _temp;							\
  for (_i=0; _i<_half; _i++) {						\
    _temp = element_at(v, (start)+_i, item);				\
    element_at(v, (start)+_i, item) = element_at(v, (end)-_i-1, item);	\
    element_at(v, (end)-_i-1, item) = _temp;				\
  }									\
}

int vector_resize(vector *v, size_t size, size_t element_size);
int vector_create(vector *v, size_t size, size_t element_size);
void vector_destroy(vector *v);


/** Finds the next unused slot in a vector, by comparing the contents
 * of a given \a field with \a thing that indicates a free slot.
 *
 * @param v     The vector to search through.
 * @param item  The type of data held by the vector.
 * @param field A field of a struct which is held in the vector's array.
 * @param thing If the contents of the above field match this thing, we
 *              have found an unused slot.
 *
 * @return the index of the first unused slot.
 **/
#define vector_find_next_free_slot(v, item, field, thing) \
({							  \
  int i = 0;						  \
  if ((NULL != (v)->array) && (0 < (v)->index))		  \
    for (i = 0; i < (v)->index; i++)			  \
      if (thing == ((typeof(item) *)(v)->array)[i]field)  \
	break;						  \
  i;							  \
})


/**
 * Stores a \a token of type \a item into \a v, in the first location in
 * \a v whose \a field matches \a thing.  If all \a v->index slots in \a
 * v are in use, a new element is inserted at the end of the vector and
 * \a v->index is incremented, otherwise, \a token is inserted at the
 * first available slot, and \a v->index is left unchanged.  An
 * extension of the "vector" class, which can be used when
 * "vector_delete" is not suitable (e.g. if the index into the vector
 * is being remembered by external software, then vector_delete will not
 * work, because it deletes from the middle of a vector and moves all
 * the top entries down to fill the vacated slot(s)).
 *
 * @param v     Vector into which we will insert the token.
 * @param token The object to store in the vector.
 * @param item  The data-type of the token that we're inserting.
 * @param size  The size of the token that we're inserting.
 * @param field A field of a struct which is held in the vector's array.
 *              (May be empty if not using a struct).
 * @param thing If the contents of the above field match this thing, we
 *              have found an unused slot.
 *
 * @return The location of the slot in the vector where the data was
 *         stored. 
 **/
#define vector_store(v, token, item, size,field, thing)	      \
({							      \
  int pos = vector_find_next_free_slot(v, item,field, thing); \
  if (pos == (v)->index)				      \
    /* Increment (v)->index */				      \
    vector_append((v), token, size, 1);          	      \
  else							      \
    /* Ignore (v)->index */				      \
    element_at((v), pos, item) = token;			      \
  pos;							      \
})

#endif /* __VECTOR_H */