#ifndef _PSO_H_
#define _PSO_H_

/*******************************************************************************
 * The following code is an implementation of PSO as described in Essentials of
 * Metaheuristics, Sean Luke, 2009, http://cs.gmu.edu/~sean/book/metaheuristics/
 * Please reference the book for a more in depth discussion of the algorithm
 ******************************************************************************/


/*******************************************************************************
 * If you want to use a different random number generator, you can substitute it
 * here for drand48.  Code expects this to be a function that takes no parameters
 * and returns a number in [0,1] inclusive.
 ******************************************************************************/
#ifndef RNDM
#define RNDM drand48
#endif

/*******************************************************************************
 * The swarm struct
 * This needs to get passed into every function.  Typical usage is to make a 
 * local statically allocated swarm struct, pass it into init_swarm(...) with 
 * appropriate parameters (explained in a minute), then pass the struct into
 * randomize (or do your own particle initialization), then pass it to run(...),
 * or run_one_step(...) (managing the loop yourself).  Then, once done with the
 * struct, pass it to free_swarm(...) to clean up all the dynamic memory.  Of
 * course, all the steps of a single iteration are further broken out into 
 * functions if you want to alter some of the internals.
 *
 * Data members
 * num_particles  - the number of particles in the population
 * dimensions     - the dimensionality of the problem (size of a particle)
 * neighborhood   - Number of ``informers'' used to determin neighborhood best
 * particles      - big 2D double array of particles. First index goes from 0 to
 *                  num_particles. Second index is from 0 to dimensions.
 * velocities     - big 2D double array of velocities for the particles. Indecies
 *                  are the same as for particles
 * personal_bests - big 2D double array of the personal best for the particles.
 *                  indecies are the same as for particles
 * global_best    - The best particle we've seen so far. Index from 0 to 
 *                  dimensions
 *
 * Swarm parameters
 * alpha, beta, gamma, delta and epsilon are the swarm parameters, dictating how
 * members of the swarm update their velocities.  They are:
 * alpha          - Prior Speed (Momentum): Proportion of the prior velocity
 * beta           - Personal Best (Memory): Proportion of the personal best
 * gamma          - Neighborhood Best (Social): Proportion of the neighborhood
 *                  best
 * delta          - Global Best (Cognitive): Proportion of the global best.
 * epsilon        - Scaling Factor: How much to scale the velocity vector by
 *                  when updating the particles position
 * How the first 4 parameters are used and combined is explained in the comments
 * for the update_velocities(...) function further down.
 *
 * evaluate(...)
 * The evaluate function pointer is used whenever the fitness of a particle 
 * needs to be determined.  This happens in update_bests(...), 
 * neighborhood_best(...) (which is called in update_velocities(...)), and
 * run(...).  Note that the swarm does not keep around fitnesses (so you could
 * potentially have a dynamic fitness function), which also means you need to
 * make your evaluation function as optimized as possible.
 ******************************************************************************/
struct swarm{
	unsigned int num_particles;
	unsigned int dimensions;
	unsigned int neighborhood;
	double **particles;
	double **velocities;
	double **personal_bests;
	double *global_best;
	double alpha, beta, gamma, delta, epsilon;
	double (*evaluate)(const double *particle, const unsigned int dim);
};

/*******************************************************************************
 * This function sets all of the parameters in the swarm struct, allocates 
 * memory for the particles, velocities, personal bests, and the global best.
 * THIS FUNCTION DOES NOT ALLOCATE A NEW SWARM STRUCT
 * You must handle the creation/allocation/deallocation of the struct yourself.
 * This function also does not check to see if any part of the arrays have 
 * been allocated already, it just re-assigns the pointers, so DON'T call this
 * function unless you've called free_swarm(...), or unless this is a new struct
 * that has never been passed to init_swarm(...) before.
 ******************************************************************************/
void init_swarm(const unsigned int particles,
				const unsigned int dimension,
				const unsigned int neighborhood,
				const double alpha,
				const double beta,
				const double gamma,
				const double delta,
				const double epsilon,
				double (*evaluate)(const double *particle, const unsigned int dim),
				struct swarm *s);
/*******************************************************************************
 * This function deallocates all memory allocated by init_swarm(...) and sets
 * the structs pointers to NULL. This does NOT deallocate the swarm struct. You 
 * must handle the creation/allocation/deallocation of the struct yourself. This
 * function also does not check to see if the arrays are still allocated, so 
 * ONLY call this on a struct that has been passed to init_swarm(...).
 ******************************************************************************/
void free_swarm(struct swarm *s);
/*******************************************************************************
 * This function randomizes the components of all particles and their velocities
 * The components are set between the min and max range given.
 ******************************************************************************/
void randomize(const double min, const double max, struct swarm *s);


/*******************************************************************************
 * This function iterates over all of the particles, evaluates them, and updates
 * the personal bests, and global best. If the parameter first is zero, it is 
 * assumed that the global best has not been evaluated yet
 ******************************************************************************/
void update_bests(const char first, struct swarm *s);
/*******************************************************************************
 * This function picks ``neighborhood'' particles from the swarm randomly and 
 * returns a pointer to the one with the best fitness.  This pointer is a direct 
 * pointer inside the double array, do not modify it.
 ******************************************************************************/
const double* neighborhood_best(const unsigned int particle, struct swarm *s);
/*******************************************************************************
 * This function iterates over all the velocities, and updates them using a 
 * linear combination of the current velocity, personal best, neighborhood best,
 * and global best.  The weights are alpha, beta, gamma and delta. See
 * ``Essentials of Metaheuristics'' for more details
 ******************************************************************************/
void update_velocities(struct swarm *s);
/*******************************************************************************
 * This function iterates over all the particles, adding in the velocity scaled
 * by epsilon
 ******************************************************************************/
void update_particles(struct swarm *s);
/*******************************************************************************
 * This function runs through one step of the PSO algorithm.  Specifically, it
 * calls update_bests(...), update_velocities(...), update_particles(...) in 
 * that order, passing in ``first'' to update_bests(...). Use this function if
 * you want greater control over statistics, stopping criteria, or if you want 
 * to do something in between iterations.
 ******************************************************************************/
void run_one_step(const char first, struct swarm *s);

/*******************************************************************************
 * This function handles the main loop of the PSO algorithm. You can specify 
 * three different stopping criteria, a maximum number of iterations, an ideal
 * fitness value (stops after global_bests fitness meets/exceeds this value), or
 * convergence (stops once the average distance of the particles to the global 
 * best is less than the provided value).  If use_* is non-zero, that condition
 * will be checked. If all use_* parameters are 0, this will loop forever.
 * Prints out which check stoped the loop, and the best particle of each 
 * iteration.
 ******************************************************************************/
void run(const char use_iterations, const unsigned int num_iterations,
		 const char use_ideal, const double ideal_fitness,
		 const char use_convergence, const double distance_epsilon,
		 struct swarm *s);
#endif