~ubuntu-branches/ubuntu/natty/freecell-solver/natty

/*

 * intrface.c - instance interface functions for Freecell Solver

 *

 *

 * This file is in the public domain (it's uncopyrighted).

 */

 

/*

    General use of this interface:

    2. Set the parameters of the game

    3. If you wish to revert, go to step #11.

    6. If it returns FCS_STATE_SUSPEND_PROCESS and you wish to proceed,

       then increase the iteration limit and call

    7. Repeat Step #6 zero or more times.

    8. If the last call to solve_instance() or resume_instance() returned

       FCS_STATE_SUSPEND_PROCESS then call

    9. If the solving was successful you can use the move stacks or the

       intermediate stacks. (Just don't destory them in any way).

 

    The library functions inside lib.c (a.k.a fcs_user()) give an

    easier approach for embedding Freecell Solver into your library. The

*/

 

#if 0

#else

#endif

 

 

 

 

 

{

    /* Initialize the BFS queue. We have one dummy element at the beginning

       in order to make operations simpler. */

}

 

static void foreach_soft_thread(

    void (*soft_thread_callback)(

        void * context

        ),

    void * context

 

{

    int ht_idx, st_idx;

    int num_soft_threads;

    for(ht_idx = 0 ; ht_idx<instance->num_hard_threads; ht_idx++)

    {

        hard_thread = instance->hard_threads[ht_idx];

 

 

static void soft_thread_clean_soft_dfs(

    void * context

    )

{

}

 

static void clean_soft_dfs(

        )

{

    foreach_soft_thread(instance, soft_thread_clean_soft_dfs, NULL);

}

 

        )

{

    int a;

 

    /* Make sure we are not exceeding the maximal number of soft threads

        return NULL;

    }

 

 

    soft_thread->hard_thread = hard_thread;

 

 

    soft_thread->orig_method = FCS_METHOD_NONE;

 

 

    /* Initialize the priotity queue of the A* scan */

    soft_thread->a_star_pqueue = malloc(sizeof(PQUEUE));

        soft_thread->a_star_pqueue,

        1024

        );

    /* Set the default A* weigths */

    for(a=0;a<(sizeof(soft_thread->a_star_weights)/sizeof(soft_thread->a_star_weights[0]));a++)

    {

    }

 

 

    soft_thread->initialized = 0;

 

#if 0

    {

        char * no_use;

    }

#else

    soft_thread->tests_order.num = soft_thread->hard_thread->instance->instance_tests_order.num;

    return soft_thread;

}

 

        )

{

 

    /* Make sure we are not exceeding the maximal number of soft threads

     * for an instance. */

        return NULL;

    }

 

 

    hard_thread->instance = instance;

 

 

#ifdef INDIRECT_STACK_STATES

    hard_thread->stacks_allocator = 

#endif

    hard_thread->move_stacks_allocator =

 

    fcs_move_stack_alloc_into_var(hard_thread->reusable_move_stack);

 

    default values in it. After the call to this function, the program can

    set parameters in it which are different from the default.

 

    to really prepare it for solving.

  */

{

 

 

#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INDIRECT)

    instance->num_indirect_prev_states = 0;

 

    instance->num_hard_threads = 0;

 

 

    /****************************************/

 

 

 

 

{

    /* Free the BFS linked list */

    fcs_states_linked_list_item_t * item, * next_item;

    }

}

 

{

    free_bfs_queue(soft_thread);

 

    free(soft_thread->a_star_pqueue);

 

    free(soft_thread->tests_order.tests);

    free(soft_thread);

}

 

{

    if (hard_thread->prelude_as_string)

    {

 

    if (hard_thread->move_stacks_allocator)

    {

    }

#ifdef INDIRECT_STACK_STATES

    if (hard_thread->stacks_allocator)

    {

    }

#endif

    free(hard_thread);    

    sequence of operations on instance, and it is meant for de-allocating

    whatever memory was allocated by alloc_instance().

  */

{

    int ht_idx;

 

 

 

static void normalize_a_star_weights(

    void * context

    )

{

    {

        if (soft_thread->a_star_weights[a] < 0)

        {

        }

        sum += soft_thread->a_star_weights[a];

    }

}

 

static void accumulate_tests_order(

    void * context

    )

{

}

 

static void determine_scan_completeness(

    void * context

    )

{

};

 

static int compile_prelude(

    )

{

    char * p_quota, * p_scan, * p;

}

 

 

{

    int ht_idx;

#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INDIRECT)

    instance->num_prev_states_margin = 0;

 

        }

        hard_thread->num_times_left_for_soft_thread =

            hard_thread->soft_threads[0]->num_times_step;

    }

 

    /* Normalize the A* Weights, so the sum of all of them would be 1. */

*/

#if defined(INDIRECT_STACK_STATES)

 

 

#if ((FCS_STACK_STORAGE != FCS_STACK_STORAGE_GLIB_TREE) && (FCS_STACK_STORAGE != FCS_STACK_STORAGE_GLIB_HASH))

static int fcs_stack_compare_for_comparison_with_context(

 

    )

{

}

#endif

 

 

#if (FCS_STACK_STORAGE == FCS_STACK_STORAGE_GLIB_HASH)

/* A hash calculation function for use in glib's hash */

    gconstpointer key

    )

{

 

 

 

    gconstpointer a,

    gconstpointer b

)

 * This hash function is defined in caas.c

 *

 * */

#endif

 

/*

 * to the initial state

 * */

static void trace_solution(

    )

{

    /*

        Trace the solution.

    */

    fcs_move_stack_t * solution_moves;

    int move_idx;

    fcs_move_stack_t * stack;

    fcs_move_stack_alloc_into_var(solution_moves);

    instance->solution_moves = solution_moves;

 

 

    /* Retrace the step from the current state to its parents */

    {

        /* Mark the state as part of the non-optimized solution */

        /* Duplicate the move stack */

        {

            moves = stack->moves;

            for(move_idx=stack->num_moves-1;move_idx>=0;move_idx--)

            {

        /* Duplicate the state to a freshly malloced memory */

 

        /* Move to the parent state */

    }

    /* There's one more state than there are move stacks */

}

 

 

    This function optimizes the solution path using a BFS scan on the

    states in the solution path.

*/

    )

{

    

    optimization_thread = alloc_hard_thread(instance);

    instance->optimization_thread = optimization_thread;

 

    /* Initialize the optimization hard-thread and soft-thread */

    optimization_thread->num_times_left_for_soft_thread = 1000000;

 

    /* Instruct the optimization hard thread to run indefinitely AFA it

     * is concerned */

    optimization_thread->ht_max_num_times = -1;

 

    return 

            optimization_thread->soft_threads[0],

            0

            );

 

}

 

 

    );

 

/*

    This function starts the solution process _for the first time_. If one

    wishes to proceed after the iterations limit was reached, one should

 

  */

    )

{

 

    /* Allocate the first state and initialize it to init_state */

 

 

    {

        int a;

        for(a=0;a<instance->stacks_num;a++)

        {

        }

    }

 

    /* Initialize the state to be a base state for the game tree */

 

 

    /* Initialize the data structure that will manage the state collection */

#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBREDBLACK_TREE)

#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBAVL_AVL_TREE)

#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBAVL_REDBLACK_TREE)

#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_TREE)

#endif

 

#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_HASH)

    instance->hash = g_hash_table_new(

        );

#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INTERNAL_HASH)

            2048,

            NULL

       );

#endif

    /* Initialize the data structure that will manage the stack

       collection */

#if FCS_STACK_STORAGE == FCS_STACK_STORAGE_INTERNAL_HASH

            2048,

            fcs_stack_compare_for_comparison_with_context,

            NULL

    instance->stacks_tree = g_tree_new(fcs_stack_compare_for_comparison);

#elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_GLIB_HASH)

    instance->stacks_hash = g_hash_table_new(

        );

#endif

#endif

    /* Initialize the Talon's Cache */

    if (instance->talon_type == FCS_TALON_KLONDIKE)

    {

            512,

            fcs_talon_compare_with_context,

            NULL

            );

 

    }

#endif

 

#endif

 

    {

 

            instance->hard_threads[0]->soft_threads[0],

            );

 

    }

        int ht_idx;

        for(ht_idx=0; ht_idx < instance->num_hard_threads ; ht_idx++)

        {

            hard_thread = instance->hard_threads[ht_idx];

            

            if (hard_thread->prelude != NULL)

        }

    }

 

}

 

 

{

    int num_times_started_at;

    int ret;

    /* 

     * Again, making sure that not all of the soft_threads in this 

     * hard thread are finished.

                

            if (! soft_thread->initialized)

            {

                    soft_thread,

                    0,

                    0);

 

            }

            else

            {

            }

            break;

 

            if (! soft_thread->initialized)

            {

                ret = 

                        soft_thread,

                        0,

                        0

                        );

            else

            {

                ret = 

                        soft_thread,

                        NULL,

                        1,

                        0

                        );

            if (! soft_thread->initialized)

            {

                ret = 

                        soft_thread,

                        0,

                        1

                        );

            else

            {

                ret = 

                        soft_thread,

                        NULL,

                        1,

                        1

                        );

            {

                if (soft_thread->method == FCS_METHOD_A_STAR)

                {

                        soft_thread,

                        );

                }

 

                    soft_thread,

                    0

                );

 

            else

            {

                ret =

                        soft_thread,

                        1

                        );

            }

 

 

/* Resume a solution process that was stopped in the middle */

    )

{

    int ret = FCS_STATE_SUSPEND_PROCESS;

 

    /*

     * If the optimization thread is defined, it means we are in the 

    if (instance->optimization_thread)

    {

        ret =

                instance->optimization_thread->soft_threads[0],

                1

                );

    }

             * it has already run - we retain the old ret. */

            if (! instance->optimization_thread)

            {

            }

            if (ret == FCS_STATE_WAS_SOLVED)

            {

    This function does not substitute for later calling

    finish_instance() and free_instance().

  */

    )

{

    /*

 

#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBAVL_AVL_TREE) || (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBAVL_REDBLACK_TREE)

 

{

}

 

#ifdef INDIRECT_STACK_STATES

#if (FCS_STACK_STORAGE == FCS_STACK_STORAGE_INTERNAL_HASH) || (FCS_STACK_STORAGE == FCS_STACK_STORAGE_LIBAVL_AVL_TREE) || (FCS_STACK_STORAGE == FCS_STACK_STORAGE_LIBAVL_REDBLACK_TREE)

#if 0

{

    free(key);

}

#endif

 

#elif FCS_STACK_STORAGE == FCS_STACK_STORAGE_LIBREDBLACK_TREE

(

    const void * nodep,

    const VISIT which,

    }

}

#elif FCS_STACK_STORAGE == FCS_STACK_STORAGE_GLIB_TREE

(

    gpointer key,

    gpointer value,

}

 

#elif FCS_STACK_STORAGE == FCS_STACK_STORAGE_GLIB_HASH

(

    gpointer key,

    gpointer value,

 

 

 

        void * context

        )

{

    {

    }

}

 

    This function should be called after the user has retrieved the

    results generated by the scan as it will destroy them.

  */

    )

{

    int ht_idx;

 

#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INDIRECT)

    free(instance->indirect_prev_states);

    for(ht_idx=0;ht_idx<instance->num_hard_threads;ht_idx++)

    {

        hard_thread = instance->hard_threads[ht_idx];

 

#ifdef INDIRECT_STACK_STATES

        hard_thread->stacks_allocator = NULL;

#endif

        hard_thread->move_stacks_allocator = NULL;

        

    }

 

    if (instance->optimization_thread)

    {

    }

 

 

#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBREDBLACK_TREE)

    rbdestroy(instance->tree);

#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBAVL_AVL_TREE)

#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_LIBAVL_REDBLACK_TREE)

#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_TREE)

    g_tree_destroy(instance->tree);

#endif

#if (FCS_STATE_STORAGE == FCS_STATE_STORAGE_GLIB_HASH)

    g_hash_table_destroy(instance->hash);

#elif (FCS_STATE_STORAGE == FCS_STATE_STORAGE_INTERNAL_HASH)

#endif

 

 

#ifdef INDIRECT_STACK_STATES

#if FCS_STACK_STORAGE == FCS_STACK_STORAGE_INTERNAL_HASH

#if 0

#else

#endif

#elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_LIBAVL_AVL_TREE)

#if 0

#else

    avl_destroy(instance->stacks_tree, NULL);

#endif

#elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_LIBAVL_REDBLACK_TREE)

#if 0

#else

    rb_destroy(instance->stacks_tree, NULL);

#endif

#elif (FCS_STACK_STORAGE == FCS_STACK_STORAGE_LIBREDBLACK_TREE)

#if 0

    rbwalk(instance->stacks_tree,

        NULL

        );

#endif

#if 0

    g_tree_traverse(

        instance->stacks_tree,

        G_IN_ORDER,

        NULL

        );

#if 0

    g_hash_table_foreach(

        instance->stacks_hash,

        NULL

        );

#endif

    clean_soft_dfs(instance);    

}

 

        int ht_idx,

        int st_idx

        )

    }

    else

    {

        hard_thread = instance->hard_threads[ht_idx];

        if (st_idx >= hard_thread->num_soft_threads)

        {

    }

}

 

    )

{

 

    hard_thread = soft_thread->hard_thread;

    ret = alloc_soft_thread(hard_thread);

    return ret;

}

 

    )

{

 

    /* Exceeded the maximal number of Soft-Threads in an instance */

    ret = alloc_hard_thread(instance);

    return ret->soft_threads[0];

}

 

        )

{

    int ht_idx, st_idx;

    

 

    instance->num_times = 0;

 

        hard_thread->max_num_times = -1;

        hard_thread->num_soft_threads_finished = 0;

        hard_thread->move_stacks_allocator =

#ifdef INDIRECT_STACK_STATES

        hard_thread->stacks_allocator = 

#endif

        for(st_idx = 0; st_idx < hard_thread->num_soft_threads ; st_idx++)

        {

            soft_thread->is_finished = 0;

            soft_thread->initialized = 0;

 

            /* Reset the priority queue */

            soft_thread->a_star_pqueue->CurrentSize = 0;

        }