/* state.h needs to be included before this file 
* because state.h defines the State type.
*/


/* An expand_state function inputs a state and returns an array of states.
* The last element in the array should be set to NULL.
* It should be safe to free the array if it is no longer needed.
* It should be safe to free a state if it is no longer needed.
*/

typedef State * (* expand_state)(State);


/* A free_state function frees the space used by the State.
*/

typedef void (* free_state)(State);


/* A goal_state function inputs a state and returns true (1)
* if the state is a goal state and false (0) otherwise.
*/

typedef int (* goal_state)(State);


/* An equal_states function inputs two states and returns true (1)
* if the two states are equal and false (0) otherwise.
* NULL is a possible value for a State.
*/

typedef int (* equal_states)(State, State);


/* A heuristic_state function inputs a state and returns an estimate
* of the distance from the state to a goal state.
*/

typedef int (* heuristic_state)(State);


/* An edge_cost function inputs two states and returns the cost of
* moving from the first state to the second state.
*/

typedef int (* edge_cost)(State, State);


/* This structure holds the functions we need for heuristic search. */

struct statefns {
    expand_state expandfn;
    free_state freefn;
    goal_state goalfn;
    equal_states equalfn;
    heuristic_state heuristicfn;
    edge_cost costfn;
};


/* dfs_contour implements the depth-limited search needed by idastar.
* It probably would be a bit more efficient if the functions were global
* rather than recursively passed everywhere.
* It probably would be better to do this in an object-oriented
* language.
*/

State * dfs_contour(State current_state, State parent_state,
                    int g_cost, int f_limit, int *next_f,
                    struct statefns fns);


#define TIMEOUT 60


/* idastar returns a path from the initial state to a goal state or
* NULL if it times out (more than TIMEOUT seconds) or runs out of
* states to search.
*/

State * idastar(State initial_state, struct statefns fns);



/* dfsearch implements the depth-limited search needed by idsearch.
*/

State * dfsearch(State current_state, State parent_state,
                 int depth, struct statefns fns);



/* idsearch returns a path from the initial state to a goal state or
* NULL if it times out (more than TIMEOUT seconds).
*/

State *idsearch(State initial_state, struct statefns fns);