
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "speller.h"

const char idchars[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_";

/**************************************************
 * Looks for correct spelling.
 * Currently only looks a 'distance' of one from the seed[].
 * This does an exhaustive search, so can potentially be very slow.
 * Input:
 *      seed            wrongly spelled word
 *      fp              search function
 *      fparg           argument to search function
 *      charset         character set
 * Returns:
 *      NULL            no correct spellings found
 *      void*           value returned by fp() for first possible correct spelling
 */

void *speller(const char *seed, fp_speller_t fp, void *fparg, const char *charset)
{
    size_t seedlen = strlen(seed);
    if (!seedlen)
        return NULL;

    char *buf = (char *)alloca(seedlen + 2);    // leave space for extra char
    if (!buf)
        return NULL;                            // no matches

    /* Deletions */
    memcpy(buf, seed + 1, seedlen);
    for (int i = 0; i < seedlen; i++)
    {
        //printf("del buf = '%s'\n", buf);
        void *p = (*fp)(fparg, buf);
        if (p)
            return p;

        buf[i] = seed[i];
    }

    /* Transpositions */
    memcpy(buf, seed, seedlen + 1);
    for (int i = 0; i + 1 < seedlen; i++)
    {
        // swap [i] and [i + 1]
        buf[i] = seed[i + 1];
        buf[i + 1] = seed[i];

        //printf("tra buf = '%s'\n", buf);
        void *p = (*fp)(fparg, buf);
        if (p)
            return p;

        buf[i] = seed[i];
    }

    if (charset && *charset)
    {
        /* Substitutions */
        memcpy(buf, seed, seedlen + 1);
        for (int i = 0; i < seedlen; i++)
        {
            for (const char *s = charset; *s; s++)
            {
                buf[i] = *s;

                //printf("sub buf = '%s'\n", buf);
                void *p = (*fp)(fparg, buf);
                if (p)
                    return p;
            }
            buf[i] = seed[i];
        }

        /* Insertions */
        memcpy(buf + 1, seed, seedlen + 1);
        for (int i = 0; i <= seedlen; i++)      // yes, do seedlen+1 iterations
        {
            for (const char *s = charset; *s; s++)
            {
                buf[i] = *s;

                //printf("ins buf = '%s'\n", buf);
                void *p = (*fp)(fparg, buf);
                if (p)
                    return p;
            }
            buf[i] = seed[i];   // going past end of seed[] is ok, as we hit the 0
        }
    }

    return NULL;                // didn't find any corrections
}
