/* Jumble rewritten using canonical solution, to be translated to Java -- DRH */

#include 
#include 
#include 
#include 

#define MAX_STRING 32
#define MAX_ENTRIES 3 
#define MAX_ARRAY 64000
#define TRUE  1
#define FALSE 0
#define DICTIONARY "/usr/dict/words"

/******************************************************/
char bubble_char(char *candidate, int bound)
{
 char temp;
 char exchange = FALSE;
 int i,j;

 for (i = 0; i < bound; i++)
    {
     j = i + 1;
     if (candidate[i] > candidate[j])
        {
         /* exchange */
         exchange = TRUE;
         temp = candidate[i];
         candidate[i] = candidate[j];
         candidate[j] = temp;
        }
    }
 return(exchange);
};

void canonicalize(char *candidate, char *canonical)
{
 char exchange = TRUE;
 int bound = strlen(candidate) - 1;
 strcpy(canonical, candidate);
 while (exchange)
    {
     exchange = bubble_char(canonical, bound);
    }
 return;
};
/******************************************************/

/******************************************************/
struct dict_entry
{
 char canonical[MAX_STRING];
 char string[MAX_STRING];
};

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

/******************************************************/
class dict
{
private: 
 void dict::sort();
public: 
 static int compare_strings(const void *, const void *);
 struct dict_entry array[MAX_ARRAY];
 int num_words;
 FILE *fd;
 dict();
 struct dict_entry *dict::find(char *);
 void dict::dump();
};

dict::dict()
{
 char string[MAX_STRING];
 char canonical[MAX_STRING];

 /* first open dictionary file */
 fd = fopen(DICTIONARY, "r");
 if (fd == NULL)
    {
     fprintf(stderr, "Cannot open dictionary file\n");
     exit(-1);
    }

 /* read in each word of the dictionary into an array */
 num_words = 0;
 while (fscanf(fd, "%s", string) != EOF)
    {
     canonicalize(string, canonical);
     strcpy(array[num_words].canonical, canonical);
     strcpy(array[num_words].string, string);
     num_words++;
    }
 sort();
};

int dict::compare_strings(const void *s1, const void *s2)
{
 return(strcmp(((const dict_entry *)s1)->canonical, ((const dict_entry *)s2)->canonical)); 
}

void dict::sort()
{
 qsort((void *) array, num_words, sizeof(struct dict_entry),
compare_strings);
}


struct dict_entry *dict::find(char *canonical)
{
 struct dict_entry key;
 strcpy(key.canonical, canonical);
 return ((struct dict_entry *) 
          bsearch(&key, (void *)array, num_words, sizeof(struct dict_entry),
          compare_strings));
}

void dict::dump()
{
 fprintf(stderr, "numwords: %d\n", num_words); 
 for  (int i = 0; i < num_words; i++)
    {
     fprintf(stderr, "i: %d, canonical: %s   string: %s\n",
                      i, array[i].canonical, array[i].string);
    }
};
/******************************************************/

main(int argc, char * argv[])
{
 char candidate[MAX_STRING];
 char canonical[MAX_STRING];
 struct dict_entry *dict_ptr;

 /*****************************************************/
 /* get candidate */
 if (argc != 2)
    {
     fprintf(stderr, "Usage: jumble \n");
     exit(-1);
    }
 strcpy(candidate, argv[1]);
 canonicalize(candidate, canonical);
 /*****************************************************/

 /*****************************************************/
 /* build up dictionary */
 class dict *dictionary = new dict();
 /* dictionary->dump(); */
 /*****************************************************/

 /*****************************************************/
 /* find entry */
 dict_ptr = dictionary->find(canonical);
 if (dict_ptr != NULL)
    {
     fprintf(stdout, "Found following matches:\n");
     fprintf(stdout, "     %s\n", dict_ptr->string);
     /* walk forward in sorted list looking for additional matches */
     int current_index = 
        (((int) dict_ptr - (int) dictionary->array) / sizeof(struct dict_entry)) + 1;
     while (current_index < dictionary->num_words)
        {
         if (strcmp(dictionary->array[current_index].canonical, canonical) == 0)
            {
             fprintf(stdout, "     %s\n", dictionary->array[current_index].string);
             current_index++;
            }
         else
            {
             break;
            }
        }
     /* walk backwards in sorted list looking for additional matches */
     current_index = 
        (((int) dict_ptr - (int) dictionary->array) / sizeof(struct dict_entry)) - 1;

     while (current_index > -1)
        {
         if (strcmp(dictionary->array[current_index].canonical, canonical) == 0)
            {
             fprintf(stdout, "     %s\n", dictionary->array[current_index].string);
             current_index--;
            }
         else
            {
             break;
            }
        }
    }
 else
    {
     fprintf(stdout, "No matches found\n");
    }
 /*****************************************************/
}

    Source: geocities.com/drhenke