/*
   "search.c" - part of "RAGMAAN, een anagrammengenerator" 

   Copyright (C) 1999 Raymond Zandbergen

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

   The maintainer of this program is Raymond Zandbergen (ray@wirehub.nl)
 */

#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <assert.h>
#include "ragmaan.h"
#include "search.h"

#ifdef	HASH_STATS
static int hs_match_l1;
static int hs_match_l2;
static int hs_checked_total;
#endif

int
rm_str_real_len (const char *s)
{
  int i;
  int length = 0;

  for (i = 0; s[i]; i++)
    {

      if (isalnum (s[i]))
	length++;
    }
  return length;
}

void
init_search (HASH_TABLE_T * ht, SEARCH_STATE_T * ss,
	     const char *target,
	     int search_length_max, int search_length_min,
	     progress_callback_t pc)
{
  int temp;

  ss->target = target;
  ss->i = 0;

  if (search_length_max > ht->max_observed_word_length)
    {
      search_length_max = ht->max_observed_word_length;
    }

  if (rm_str_real_len (target) < search_length_max)
    {

      printf ("init_search: "
	      "clipping search_length_max (%d) to length '%s'\n",
	      search_length_max, target);
      search_length_max = rm_str_real_len (target);

    }
  ss->i_end = ht->hash2_table_length[search_length_max];
  ss->keys = ht->hash2_table_key[search_length_max];
  ss->search_length_max = search_length_max;
  ss->search_length_min = search_length_min;
  ss->search_length = search_length_max;
  make_hash2 (target, &temp);
  ss->target_inv_hash2 = ~temp;
  char_count (target, ss->target_char_count);
  ss->pc = pc;
/*
   #ifdef       HASH_STATS
   hs_match_l1=0;
   hs_match_l2=0;
   hs_checked_total = 0;
   #endif
 */

}
void
init_search_reverse (HASH_TABLE_T * ht, SEARCH_STATE_T * ss,
		     const char *target,
		     int search_length_max, int search_length_min,
		     progress_callback_t pc)
{
  int temp;

  ss->target = target;
  ss->i = 0;

  if (search_length_max > ht->max_observed_word_length)
    {
      search_length_max = ht->max_observed_word_length;
    }

  if (rm_str_real_len (target) < search_length_max)
    {

      printf ("init_search: "
	      "clipping search_length_max (%d) to length '%s'\n",
	      search_length_max, target);
      search_length_max = rm_str_real_len (target);

    }
  ss->i_end = ht->hash2_table_length[search_length_min];
  ss->keys = ht->hash2_table_key[search_length_min];
  ss->search_length_max = search_length_max;
  ss->search_length_min = search_length_min;
  ss->search_length = search_length_min;
  make_hash2 (target, &temp);
  ss->target_inv_hash2 = ~temp;
  char_count (target, ss->target_char_count);
  ss->pc = pc;
/*
   #ifdef       HASH_STATS
   hs_match_l1=0;
   hs_match_l2=0;
   hs_checked_total = 0;
   #endif
 */

}
char *
expand_result (HASH_TABLE_T * ht, char *target,
	       char *anagram, char *c, char *rest)
{
  char *s2;
  char temp[MAX_WORD_LENGTH];
  SEARCH_STATE_T sub_ss;

  if (rest)
    *rest = 0;

  if (!anagram)
    {
      *c = ' ';
      return 0;
    }
  if (rm_str_real_len (anagram) == rm_str_real_len (target))
    {
      *c = '!';
      return anagram;
    }
  strncpy (temp, target, MAX_WORD_LENGTH - 1);
  subtract (temp, anagram);
  init_search_reverse (ht, &sub_ss, temp, rm_str_real_len (temp), 1, 0);
  s2 = find_word_wl_reverse (&sub_ss, ht);
  if (rest)
    {
      strcpy (rest, "(");
      strcat (rest, temp);
      strcat (rest, ")");
    }
  if (!s2)
    {
      *c = 'X';
      return anagram;
    }
  *c = '+';
  return anagram;
}

char *
find_word_wl2 (SEARCH_STATE_T * ss, HASH_TABLE_T * ht, char *c,
	       char *rest)
{
  char *anagram = find_word_wl (ss, ht);
  return expand_result (ht, (char *) ss->target, anagram, c, rest);
}

char *
find_word_wl (SEARCH_STATE_T * ss, HASH_TABLE_T * ht)
{
  int i, i_end;
  int *keys;
  int inv_hash2;
  char *possible_match;

  inv_hash2 = ss->target_inv_hash2;

  for (;;)
    {
      i_end = ss->i_end;
      keys = ss->keys;
      for (i = ss->i; i < i_end; i++)
	{

#ifdef	HASH_STATS
	  hs_checked_total++;
#endif

	  if (0 == (inv_hash2 & keys[i]))
	    {
#ifdef	HASH_STATS
	      hs_match_l1++;
#endif
	      possible_match =
		ht->hash2_table_string[
					ss->search_length][i];

	      if (is_sub2 (ss->target_char_count,
			   possible_match))
		{

		  ss->i = i + 1;
#ifdef	HASH_STATS
		  hs_match_l2++;
#endif

		  return possible_match;
		}
	    }
	}			/* found nothing, try shorter words */

      if (ss->search_length > ss->search_length_min)
	{

	  init_search (ht, ss, ss->target, ss->search_length - 1,
		       ss->search_length_min, ss->pc);
	}
      else
	{

	  break;
	}
    }

#ifdef	HASH_STATS
  printf ("hash stats: %d/%d/%d\n",
	  hs_checked_total, hs_match_l1, hs_match_l2);
#endif
  return 0;
}

char *
find_word_wl_reverse (SEARCH_STATE_T * ss, HASH_TABLE_T * ht)
{
  int i, i_end;
  int *keys;
  int inv_hash2;
  char *possible_match;

  inv_hash2 = ss->target_inv_hash2;

  for (;;)
    {
      i_end = ss->i_end;
      keys = ss->keys;
      for (i = ss->i; i < i_end; i++)
	{

#ifdef	HASH_STATS
	  hs_checked_total++;
#endif

	  if (0 == (inv_hash2 & keys[i]))
	    {
#ifdef	HASH_STATS
	      hs_match_l1++;
#endif
	      possible_match =
		ht->hash2_table_string[
					ss->search_length][i];

	      if (is_sub2 (ss->target_char_count,
			   possible_match))
		{

		  ss->i = i + 1;
#ifdef	HASH_STATS
		  hs_match_l2++;
#endif

		  return possible_match;
		}
	    }
	}			/* found nothing, try longer words */

      if (ss->search_length < ss->search_length_max)
	{

	  init_search_reverse (ht, ss, ss->target, ss->search_length_max,
			       ss->search_length_min + 1, ss->pc);
	}
      else
	{

	  break;
	}
    }

#ifdef	HASH_STATS
  printf ("hash stats: %d/%d/%d\n",
	  hs_checked_total, hs_match_l1, hs_match_l2);
#endif
  return 0;
}