summaryrefslogtreecommitdiffstats
path: root/kpat/freecell-solver/fcs_dm.c
diff options
context:
space:
mode:
Diffstat (limited to 'kpat/freecell-solver/fcs_dm.c')
-rw-r--r--kpat/freecell-solver/fcs_dm.c146
1 files changed, 146 insertions, 0 deletions
diff --git a/kpat/freecell-solver/fcs_dm.c b/kpat/freecell-solver/fcs_dm.c
new file mode 100644
index 00000000..9fd8c9a8
--- /dev/null
+++ b/kpat/freecell-solver/fcs_dm.c
@@ -0,0 +1,146 @@
+/*
+ fcs_dm.c - Freecell Solver's data management routines.
+
+ Written by Shlomi Fish, 2000
+
+ This file is distributed under the public domain.
+ (It's not copyrighted)
+*/
+
+#include <stddef.h>
+#include <string.h>
+
+#include "fcs_dm.h"
+
+#ifdef DMALLOC
+#include "dmalloc.h"
+#endif
+
+/*
+ freecell_solver_bsearch - an improved binary search function. Highlights:
+
+ * The comparison function accepts a common context argument that
+ is passed to SFO_bsearch.
+ * If the item was not found the function returns the place in which
+ it should be placed, while setting *found to 0. If it was found
+ (*found) is set to 1.
+*/
+void * freecell_solver_bsearch
+(
+ void * key,
+ void * void_array,
+ size_t len,
+ size_t width,
+ int (* compare)(const void *, const void *, void *),
+ void * context,
+ int * found
+)
+{
+ int low = 0;
+ int high = len-1;
+ int mid;
+ int result;
+
+ char * array = void_array;
+
+ while (low <= high)
+ {
+ mid = ((low+high)>>1);
+
+ result = compare(key, (void*)(array+mid*width), context);
+
+ if (result < 0)
+ {
+ high = mid-1;
+ }
+ else if (result > 0)
+ {
+ low = mid+1;
+ }
+ else
+ {
+ *found = 1;
+ return (void*)(array+mid*width);
+ }
+ }
+
+ *found = 0;
+ return ((void*)(array+(high+1)*width));
+}
+
+
+
+/*
+ freecell_solver_merge_large_and_small_sorted_array - merges a large sorted
+ array with a small sorted array. The arrays could be of any length
+ whatsoever, but it works faster if the first is significantly bigger
+ than the second.
+
+ This function assumes that big_array is allocated with enough
+ space to hold the extra elements.
+
+ The array should be distinct or else there would be unexpected
+ results.
+*/
+int freecell_solver_merge_large_and_small_sorted_arrays
+(
+ void * void_big_array,
+ size_t size_big_array,
+ void * void_small_array,
+ size_t size_small_array,
+ size_t width,
+ int (*compare) (const void *, const void *, void *),
+ void * context
+)
+{
+ int item_to_move, num_big_items_moved, pos;
+ char * pos_ptr;
+ char * big_array;
+ char * small_array;
+ int found;
+ int start_offset, end_offset;
+
+ big_array = (char*)void_big_array;
+ small_array = (char*)void_small_array;
+
+ num_big_items_moved = 0;
+
+ for(item_to_move = size_small_array-1 ; item_to_move>=0; item_to_move--)
+ {
+ pos_ptr = freecell_solver_bsearch (
+ small_array+item_to_move*width,
+ big_array,
+ size_big_array-num_big_items_moved,
+ width,
+ compare,
+ context,
+ &found
+ );
+
+ pos = (pos_ptr-big_array)/width;
+
+ end_offset = size_big_array + size_small_array -
+ num_big_items_moved -
+ (size_small_array-item_to_move-1);
+
+ start_offset = end_offset + pos -
+ (size_big_array - num_big_items_moved);
+
+ memmove(
+ big_array+start_offset*width,
+ big_array+pos*width,
+ (end_offset-start_offset)*width
+ );
+
+ memcpy(
+ big_array+(start_offset-1)*width,
+ small_array+item_to_move*width,
+ width
+ );
+
+ num_big_items_moved += (end_offset - start_offset);
+ }
+
+ return 1;
+}
+