// Copyright 1998 by Kevin Atkinson under the terms of the LGPL

#ifndef __approx_t_hh
#define __approx_t_hh

//
// approx_match_fast looks only for matching charters irrespective of
// order. It is designed to give a high score to typoes like "becuase"
// vs.  "becuaes".
//
// The distance calculation is:
//   (mismatched charters + size diff)/2
// And the score is:
//   (max size - distance)/max size
// For example "becuase" vs "because" would be 0 or 0 for the distance
// and (8-0)/8 or 1 for the score
// "matched" vs "matchd" would be 1+1 or 2 for the distance and
// (7-1)/7 or .857
//
// This score is ALWAYS bigger than approx_match.
//

template <class ToLower1, class ToLower2>
class ap_fast {
  unsigned int max_size, max2size;
  int mismatched_letters;
public:
  ap_fast(const char *s1, const char *s2, const ToLower1&, const ToLower2&);
  int distance() {return mismatched_letters/2;}
  double score() {return static_cast<double>(mismatched_letters)/ max2size;}
};

template <class ToLower1, class ToLower2>
ap_fast<ToLower1,ToLower2>::ap_fast (const char *s1, const char *s2, 
				     const ToLower1 &to_lower1, const ToLower2 &to_lower2)
  : mismatched_letters(0)
{
  int characters[256] = {0};
  char begin[256];
  char *end = begin;

  const char *i;
  for (i = s1; *i; ++i) {
    if (!characters[static_cast<unsigned char>(to_lower1(*i))]++) {
      *end = *i;
      ++end;
    }
  }
  unsigned int size1 = i - s1;

  for (i = s2; *i; ++i) {
    if (!characters[static_cast<unsigned char>(to_lower2(*i))]--) {
      *end = *i;
      ++end;
    }
  }
  unsigned int size2 = i - s2;

  int j;
  for (char *i = begin; i != end; ++i) {
    j = characters[static_cast<unsigned char>(*i)];
    if (j > 0)
      mismatched_letters += j;
    else
      mismatched_letters -= j;
  }

  max_size = size1 > size2 ? size1 : size2;
  max2size = 2*max_size;
  mismatched_letters += max2size - (size1 + size2);
}

struct DoNothing {
  char operator() (char c) const {return c;}
};

template <class ToLower1, class ToLower2>
double approx_match_score_fast(const char *s1, const char *s2,
			       const ToLower1 &to_lower1, const ToLower2 &to_lower2) {
  return ap_fast<ToLower1,ToLower2>(s1,s2,to_lower1,to_lower2).score();
}

template <class ToLower1, class ToLower2>
int approx_match_dist_fast(const char *s1, const char *s2,
			   const ToLower1 &to_lower1, const ToLower2 &to_lower2) {
  return ap_fast<ToLower1,ToLower2>(s1,s2,to_lower1,to_lower2).distance();
}

template <class ToLower1, class ToLower2>
void approx_match_fast(const char *s1, const char *s2, 
		       double &score, int &dist,
		       const ToLower1 &to_lower1, const ToLower2 &to_lower2) {
  ap_fast<ToLower1,ToLower2> s(s1,s2,to_lower1,to_lower2);
  score = s.score();
  dist = s.distance();
}

#endif
