/*
    ragmaan/search.c            (C) 2003 Raymond (zandbergen@home.nl)

    "ragmaan" is an anagram generator

    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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#include <string.h>
#include <stdio.h>
#include <assert.h>
#include <glib.h>
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include "ragmaan.h"
#include "search.h"

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

gint
rm_str_real_len (const gchar *s)
{
  gint i;
  gint length = 0;

  for (i = 0; s[i]; i++)
    if (g_ascii_isalnum (s[i]))
      length++;
  return length;
}

void
init_search (HASH_TABLE_T * ht, SEARCH_STATE_T * ss,
	     const gchar *target,
	     gint search_length_max, gint search_length_min, void *pc)
{
  gint 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);
#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 gchar *target,
		     gint search_length_max, gint search_length_min, void *pc)
{
  gint 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);
#ifdef       HASH_STATS
  hs_match_l1 = 0;
  hs_match_l2 = 0;
  hs_checked_total = 0;
#endif

}

gchar *
find_word_wl (SEARCH_STATE_T * ss, HASH_TABLE_T * ht)
{
  gint i, i_end;
  gint *keys;
  gint inv_hash2;
  gchar *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, 0);
	}
      else
	{
	  break;
	}
    }

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

gchar *
find_word_wl_reverse (SEARCH_STATE_T * ss, HASH_TABLE_T * ht)
{
  gint i, i_end;
  gint *keys;
  gint inv_hash2;
  gchar *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, 0);
      else
	break;
    }

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