The R Project SVN R

/*

Copyright (C) Jarkko Hietaniemi, 1998,1999,2000,2001. All Rights Reserved.

This program is free software; you can redistribute it and/or modify

it under the terms of either:

a) the GNU Library General Public License as published by the Free

   Software Foundation; either version 2, or (at your option) any

   later version, or

b) the "Artistic License" which comes with Perl source code.

Other free software licensing schemes are negotiable.

Furthermore:

(1) This software is provided as-is, without warranties or

    obligations of any kind.

(2) You shall include this copyright notice intact in all copies

    and derived materials.

*/

/*

  $Id: apse.c,v 1.2 2002/06/08 10:20:32 hornik Exp $

*/

#include "apse.h"

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <ctype.h>

#define APSE_BITS_IN_BITVEC	(8*sizeof(apse_vec_t))

#define APSE_CHAR_MAX		256

#ifdef APSE_DEBUGGING

#define APSE_DEBUG(x) x

#else

#define APSE_DEBUG(x)

#endif

#define APSE_BIT(i)		((apse_vec_t)1 << ((i)%APSE_BITS_IN_BITVEC))

#define APSE_IDX(p, q, i)	((p)*(q)+(i)/APSE_BITS_IN_BITVEC)

#define APSE_BIT_SET(bv, p, q, i) (bv[APSE_IDX(p, q, i)] |=  APSE_BIT(i))

#define APSE_BIT_CLR(bv, p, q, i) (bv[APSE_IDX(p, q, i)] &= ~APSE_BIT(i))

#define APSE_BIT_TST(bv, p, q, i) (bv[APSE_IDX(p, q, i)] &   APSE_BIT(i))

#define APSE_MATCH_STATE_BOT		0

#define APSE_MATCH_STATE_SEARCH		1

#define APSE_MATCH_STATE_BEGIN		2

#define APSE_MATCH_STATE_FAIL		3

#define APSE_MATCH_STATE_GREEDY		4

#define APSE_MATCH_STATE_END		5

#define APSE_MATCH_STATE_EOT		6

#define APSE_TEST_HIGH_BIT(i)	\

	(((i) & ((apse_vec_t)1 << (APSE_BITS_IN_BITVEC - 1))) ? 1 : 0)

/* In case you are reading the TR 91-11 of University of Arizona, page 6:

 * j+1	state

 * j	prev_state

 * d	i

 * d-1	prev_i

 */

#define APSE_NEXT_EXACT(state, prev_state, text, i, carry)		\

	(state[i] = ((prev_state[i] << 1 | carry) & text))

#define APSE_NEXT_APPROX(state, prev_state, text, i, prev_i, carry)	\

	(state[i]  = (((prev_state[i] << 1) & text)		  |	\

			prev_state[prev_i] 			  |	\

		      ((state[prev_i] | prev_state[prev_i]) << 1) |	\

			carry))

#define APSE_NEXT_COMMON(state, prev_state, text, i)			\

	(state[i]  = (prev_state[i] << 1) & text)

#define APSE_NEXT_INSERT(state, prev_state, i, prev_i)			\

	(state[i] |= prev_state[prev_i])

#define APSE_NEXT_DELETE(state, i, prev_i)				\

	(state[i] |= (state[prev_i] << 1))

#define APSE_NEXT_SUBSTI(state, prev_state, i, prev_i)			\

	(state[i] |= (prev_state[prev_i] << 1))

#define APSE_NEXT_CARRY(state, i, carry)				\

	(state[i] |= carry)

#define APSE_EXACT_MATCH_BEGIN(ap)	(ap->state[0] & 1)

#define APSE_APPROX_MATCH_BEGIN(ap)	\

	(ap->state[ap->largest_distance + ap->match_begin_bitvector] > \

	 ap->match_begin_prefix && \

	 ap->state[ap->largest_distance + ap->match_begin_bitvector] & \

	 ap->match_begin_prefix)

#define APSE_PREFIX_DELETE_MASK(ap)	\

	    do { if (ap->edit_deletions < ap->edit_distance &&	\

		     ap->text_position  < ap->edit_distance)	\

 	             ap->state[h] &= ap->match_begin_bitmask; } while (0)

#define APSE_DEBUG_SINGLE(ap, i)		\

	APSE_DEBUG(printf("%c %2ld %2ld %s\n",				\

			  isprint(ap->text[ap->text_position])?	\

			  ap->text[ap->text_position]:'.',		\

			  ap->text_position, i, 			\

			  _apse_fbin(ap->state[i],			\

				     ap->pattern_size, 1)))

#define APSE_DEBUG_MULTIPLE_FIRST(ap, i)	\

	APSE_DEBUG(printf("%c %2ld %2ld",				\

			  isprint(ap->text[ap->text_position])?	\

			  ap->text[ap->text_position]:'.',		\

			  ap->text_position, i))

#define APSE_DEBUG_MULTIPLE_REST(ap, i, j)	\

	APSE_DEBUG(printf(" %s",					\

			  _apse_fbin(ap->state[j],			\

				     ap->pattern_size, 			\

				     i == ap->bitvectors_in_state-1)))

#ifdef APSE_DEBUGGING

static char *_apse_fbin(apse_vec_t v, apse_size_t n, apse_bool_t last);

static char *_apse_fbin(apse_vec_t v, apse_size_t n, apse_bool_t last) {

    static char s[APSE_BITS_IN_BITVEC + 1] = { 0 }; /* non-reentrant */

    if (v) {

	static const char *b =

	    "0000100001001100001010100110111000011001010111010011101101111111";

	apse_size_t i;

	for (i = 0; i < APSE_BITS_IN_BITVEC && i < n && v; i += 4) {

	    (void)memcpy(s + i, b + ((v & 0x0f) << 2), (size_t)4);

	    v >>= 4;

	}

	if (i < APSE_BITS_IN_BITVEC)

	    memset(s + i, '0', APSE_BITS_IN_BITVEC - i);

    } else

	memset(s, '0', APSE_BITS_IN_BITVEC);

    if (last)

	s[n % APSE_BITS_IN_BITVEC] = 0;

    return s;

}

#endif

/* The code begins. */

apse_bool_t apse_set_pattern(apse_t*		ap,

			     unsigned char*	pattern,

			     apse_size_t	pattern_size) {

    apse_size_t	i;

    if (ap->case_mask)

	free(ap->case_mask);

    if (ap->fold_mask)

	free(ap->fold_mask);

    ap->pattern_mask = 0;

    ap->fold_mask    = 0;

    ap->case_mask    = 0;

    ap->is_greedy    = 0;

    ap->prev_equal   = 0;

    ap->prev_active  = 0;

    ap->pattern_size = pattern_size;

    ap->bitvectors_in_state = (pattern_size - 1)/APSE_BITS_IN_BITVEC + 1;

    if (ap->edit_distance)

	ap->largest_distance = ap->edit_distance * ap->bitvectors_in_state;

    ap->bytes_in_state = ap->bitvectors_in_state * sizeof(apse_vec_t);

    ap->case_mask = calloc((apse_size_t)APSE_CHAR_MAX, ap->bytes_in_state);

    if (!ap->case_mask)

	goto out;

    for (i = 0; i < pattern_size; i++)

	APSE_BIT_SET(ap->case_mask,

		     (unsigned)pattern[i],

		     ap->bitvectors_in_state, i);

    ap->pattern_mask = ap->case_mask;

    ap->match_end_bitmask =

	(apse_vec_t)1 << ((pattern_size - 1) % APSE_BITS_IN_BITVEC);

out:

    if (ap && ap->case_mask)

	return 1;

    else {

	if (ap->case_mask)

	    free(ap->case_mask);

	if (ap)

	    free(ap);

	return 0;

    }

}

void apse_set_greedy(apse_t *ap, apse_bool_t greedy) {

    ap->is_greedy = greedy;

}

apse_bool_t apse_get_greedy(apse_t *ap) {

    return ap->is_greedy;

}

void apse_set_match_bot_callback(apse_t *ap,

				 void* (*match_bot_callback)(apse_t* ap)) {

    ap->match_bot_callback = match_bot_callback;

}

void apse_set_match_begin_callback(apse_t *ap,

				   void* (*match_begin_callback)(apse_t* ap)) {

    ap->match_begin_callback = match_begin_callback;

}

void apse_set_match_fail_callback(apse_t *ap,

				  void* (*match_fail_callback)(apse_t* ap)) {

    ap->match_fail_callback = match_fail_callback;

}

void apse_set_match_end_callback(apse_t *ap,

				 void* (*match_end_callback)(apse_t* ap)) {

    ap->match_end_callback = match_end_callback;

}

void apse_set_match_eot_callback(apse_t *ap,

				 void* (*match_eot_callback)(apse_t* ap)) {

    ap->match_eot_callback = match_eot_callback;

}

void* (*apse_get_match_bot_callback(apse_t * ap))(apse_t *ap) {

    return ap->match_bot_callback;

}

void* (*apse_get_match_begin_callback(apse_t * ap))(apse_t *ap) {

    return ap->match_begin_callback;

}

void* (*apse_get_match_fail_callback(apse_t * ap))(apse_t *ap) {

    return ap->match_fail_callback;

}

void* (*apse_get_match_end_callback(apse_t * ap))(apse_t *ap) {

    return ap->match_end_callback;

}

void* (*apse_get_match_eot_callback(apse_t * ap))(apse_t *ap) {

    return ap->match_eot_callback;

}

static int _apse_wrap_slice(apse_t*		ap,

			    apse_ssize_t	begin_in,

			    apse_ssize_t	size_in,

			    apse_ssize_t*	begin_out,

			    apse_ssize_t*	size_out) {

    if (begin_in < 0) {

	if (-begin_in > ap->pattern_size)

	    return 0;

	begin_in = ap->pattern_size + begin_in;

    }

    if (size_in < 0) {

	if (-size_in > begin_in)

	    return 0;

	size_in   = -size_in;

	begin_in -=  size_in;

    }

    if (begin_in >= ap->pattern_size)

	return 0;

    if (begin_in + size_in > ap->pattern_size)

	size_in = ap->pattern_size - begin_in;

    if (begin_out)

	*begin_out = begin_in;

    if (size_out)

	*size_out = size_in;

    return 1;

}

apse_bool_t apse_set_anychar(apse_t *ap, apse_ssize_t pattern_index) {

    apse_size_t	bitvectors_in_state = ap->bitvectors_in_state;

    apse_ssize_t	true_index, i;

    apse_bool_t	okay = 0;

    if (!_apse_wrap_slice(ap, pattern_index, (apse_ssize_t)1,

			      &true_index, 0))

	goto out;

    for (i = 0; i < APSE_CHAR_MAX; i++)

	APSE_BIT_SET(ap->case_mask,

		      i, bitvectors_in_state, pattern_index);

    if (ap->fold_mask)

	for (i = 0; i < APSE_CHAR_MAX; i++)

	    APSE_BIT_SET(ap->fold_mask,

			  i, bitvectors_in_state, pattern_index);

    okay = 1;

  out:

    return okay;

}

apse_bool_t apse_set_charset(apse_t*		ap,

			     apse_ssize_t	pattern_index,

			     unsigned char*	set,

			     apse_size_t	set_size,

			     apse_bool_t	complement) {

    apse_size_t	bitvectors_in_state = ap->bitvectors_in_state;

    apse_ssize_t	true_index, i;

    apse_bool_t	okay = 0;

    if (!_apse_wrap_slice(ap, pattern_index, (apse_ssize_t)1,

			      &true_index, 0))

	goto out;

    if (complement) {

	for (i = 0; i < set_size; i++)

	    APSE_BIT_CLR(ap->case_mask,

			  (unsigned)set[i],

			  bitvectors_in_state, true_index);

    } else {

	for (i = 0; i < set_size; i++)

	    APSE_BIT_SET(ap->case_mask,

			  (unsigned)set[i],

			  bitvectors_in_state, true_index);

    }

    if (ap->fold_mask)

	apse_set_caseignore_slice(ap, pattern_index,

				   (apse_ssize_t)1, (apse_bool_t)1);

    okay = 1;

 out:

    return okay;

}

static void _apse_reset_state(apse_t* ap) {

    apse_size_t	i, j;

    (void)memset(ap->state,      0, ap->bytes_in_all_states);

    (void)memset(ap->prev_state, 0, ap->bytes_in_all_states);

    ap->prev_equal  = 0;

    ap->prev_active = 0;

    for (i = 1; i <= ap->edit_distance; i++) {

	for (j = 0; j < i; j++)

	    APSE_BIT_SET(ap->prev_state, i, ap->bitvectors_in_state, j);

    }

}

apse_bool_t apse_set_text_position(apse_t *ap,

					 apse_size_t text_position) {

    ap->text_position = text_position;

    return 1;

}

apse_size_t apse_get_text_position(apse_t *ap) {

    return ap->text_position;

}

apse_bool_t apse_set_text_initial_position(apse_t *ap,

					   apse_size_t text_initial_position) {

    ap->text_initial_position = text_initial_position;

    return 1;

}

apse_size_t apse_get_text_initial_position(apse_t *ap) {

    return ap->text_initial_position;

}

apse_bool_t apse_set_text_final_position(apse_t *ap,

					 apse_size_t text_final_position) {

    ap->text_final_position = text_final_position;

    return 1;

}

apse_size_t apse_get_text_final_position(apse_t *ap) {

    return ap->text_final_position;

}

apse_bool_t apse_set_text_position_range(apse_t *ap,

					 apse_size_t text_position_range) {

    ap->text_position_range = text_position_range;

    return 1;

}

apse_size_t apse_get_text_position_range(apse_t *ap) {

    return ap->text_position_range;

}

void apse_reset(apse_t *ap) {

    _apse_reset_state(ap);

    ap->text_position = ap->text_initial_position;

    ap->text_position_range = APSE_MATCH_BAD;

    ap->match_state = APSE_MATCH_STATE_BOT;

    ap->match_begin = APSE_MATCH_BAD;

    ap->match_end   = APSE_MATCH_BAD;

}

apse_bool_t apse_set_edit_distance(apse_t *ap, apse_size_t edit_distance) {

    /* TODO: waste not--reuse if possible */

    if (ap->state)

	free(ap->state);

    if (ap->prev_state)

	free(ap->prev_state);

    ap->edit_distance = edit_distance;

    ap->bytes_in_all_states = (edit_distance + 1) * ap->bytes_in_state;

    ap->state = ap->prev_state = 0;

    ap->state = calloc(edit_distance + 1, ap->bytes_in_state);

    if (!ap->state)

	goto out;

    ap->prev_state = calloc(edit_distance + 1, ap->bytes_in_state);

    if (!ap->prev_state)

	goto out;

    apse_reset(ap);

    if (!ap->has_different_distances) {

	ap->edit_insertions		= edit_distance;

	ap->edit_deletions		= edit_distance;

	ap->edit_substitutions		= edit_distance;

    }

    if (ap->edit_distance && ap->bitvectors_in_state)

	ap->largest_distance = ap->edit_distance * ap->bitvectors_in_state;

    ap->match_begin_bitvector	=

	(edit_distance + 1) / APSE_BITS_IN_BITVEC;

    ap->match_begin_prefix = ((apse_vec_t)1 << edit_distance) - 1;

    ap->match_begin_bitmask	=

	((apse_vec_t)1 << edit_distance) - 1;

    ap->match_end_bitvector =

	(ap->pattern_size - 1) / APSE_BITS_IN_BITVEC;

#ifdef APSE_DEBUGGING

    if (ap->has_different_distances) {

	printf("(edit distances: ");

	printf("insertions = %ld, deletions = %ld, substitutions = %ld)\n",

	       ap->edit_insertions,

	       ap->edit_deletions,

	       ap->edit_substitutions);

    } else

	printf("(edit_distance = %ld)\n", ap->edit_distance);

#endif

out:

    return ap->state && ap->prev_state;

}

apse_size_t apse_get_edit_distance(apse_t *ap) {

    return ap->edit_distance;

}

apse_bool_t apse_set_minimal_distance(apse_t* ap, apse_bool_t minimal) {

    ap->use_minimal_distance = minimal;

    return 1;

}

apse_bool_t apse_get_minimal_distance(apse_t *ap) {

    return ap->use_minimal_distance;

}

apse_bool_t apse_set_exact_slice(apse_t*	ap,

				 apse_ssize_t	exact_begin,

				 apse_ssize_t	exact_size,

				 apse_bool_t	exact) {

    apse_ssize_t	i, j, true_begin, true_size;

    apse_bool_t	okay = 0;

    if (!ap->exact_mask) {

	ap->exact_mask = calloc((size_t)1, ap->bytes_in_state);

	if (!ap->exact_mask)

	    goto out;

	ap->exact_positions = 0;

    }

    if (!_apse_wrap_slice(ap, exact_begin, exact_size,

			      &true_begin, &true_size))

	goto out;

    if (exact) {

	for (i = true_begin, j = true_begin +  true_size;

	     i < j && i < ap->pattern_size; i++) {

	    if (!APSE_BIT_TST(ap->exact_mask, 0, 0, i))

		ap->exact_positions++;

	    APSE_BIT_SET(ap->exact_mask, 0, 0, i);

	}

    } else {

	for (i = true_begin, j = true_begin +  true_size;

	     i < j && i < ap->pattern_size; i++) {

	    if (APSE_BIT_TST(ap->exact_mask, 0, 0, i))

		ap->exact_positions--;

	    APSE_BIT_CLR(ap->exact_mask, 0, 0, i);

	}

    }

    okay = 1;

out:

    return okay;

}

apse_bool_t apse_set_caseignore_slice(apse_t*		ap,

				      apse_ssize_t	caseignore_begin,

				      apse_ssize_t	caseignore_size,

				      apse_bool_t	caseignore) {

    apse_size_t		i, j;

    int			k;

    apse_ssize_t	true_begin, true_size;

    apse_bool_t		okay = 0;

    if (!ap->fold_mask) {

	ap->fold_mask = calloc((apse_size_t)APSE_CHAR_MAX,

			       ap->bytes_in_state);

	if (!ap->fold_mask)

	    goto out;

	memcpy(ap->fold_mask,

	       ap->case_mask,

	       APSE_CHAR_MAX * ap->bytes_in_state);

	ap->pattern_mask = ap->fold_mask;

    }

    if (!_apse_wrap_slice(ap, caseignore_begin, caseignore_size,

			      &true_begin, &true_size))

	goto out;

    if (caseignore) {

	for (i = true_begin, j = true_begin +  true_size;

	     i < j && i < ap->pattern_size; i++) {

	    for (k = 0; k < APSE_CHAR_MAX; k++) {

		if (APSE_BIT_TST(ap->case_mask,

				 k, ap->bitvectors_in_state, i)) {

		    if (isupper(k))

			APSE_BIT_SET(ap->fold_mask,

				     tolower(k),

				     ap->bitvectors_in_state, i);

		    else if (islower(k))

			APSE_BIT_SET(ap->fold_mask,

				     toupper(k),

				     ap->bitvectors_in_state, i);

		}

	    }

	}

    } else {

	for (i = true_begin, j = true_begin +  true_size;

	     i < j && i < ap->pattern_size; i++) {

	    for (k = 0; k < APSE_CHAR_MAX; k++) {

		if (APSE_BIT_TST(ap->case_mask,

				 k, ap->bitvectors_in_state, i)) {

		    if (isupper(k))

			APSE_BIT_CLR(ap->fold_mask,

				     tolower(k),

				     ap->bitvectors_in_state, i);

		    else

			if (islower(k))

			    APSE_BIT_CLR(ap->fold_mask,

					 toupper(k),

					 ap->bitvectors_in_state, i);

		}

	    }

	}

    }

    okay = 1;

out:

    return okay;

}

void apse_destroy(apse_t *ap) {

    if (ap->case_mask)		free(ap->case_mask);

    if (ap->fold_mask)		free(ap->fold_mask);

    if (ap->state)		free(ap->state);

    if (ap->prev_state)		free(ap->prev_state);

    if (ap->exact_mask)	 	free(ap->exact_mask);

    free(ap);

}

apse_t *apse_create(unsigned char*	pattern,

		    apse_size_t		pattern_size,

		    apse_size_t		edit_distance) {

    apse_t		*ap;

    apse_bool_t	okay = 0;

    APSE_DEBUG(printf("(apse version %u.%u)\n",

		      APSE_MAJOR_VERSION, APSE_MINOR_VERSION));

    APSE_DEBUG(

	printf("(pattern = \"%s\", pattern_size = %ld)\n",

	       pattern, pattern_size));

    ap = calloc((size_t)1, sizeof(*ap));

    if (!ap)

	return 0;

    ap->pattern_size		= 0;

    ap->pattern_mask		= 0;

    ap->edit_distance		= 0;

    ap->has_different_distances = 0;

    ap->edit_insertions		= 0;

    ap->edit_deletions		= 0;

    ap->edit_substitutions	= 0;

    ap->use_minimal_distance	= 0;

    ap->bitvectors_in_state	= 0;

    ap->bytes_in_state		= 0;

    ap->bytes_in_all_states	= 0;

    ap->largest_distance	= 0;

    ap->text			= 0;

    ap->text_size		= 0;

    ap->text_position		= 0;

    ap->text_initial_position	= 0;

    ap->text_final_position	= APSE_MATCH_BAD;

    ap->text_position_range	= APSE_MATCH_BAD;

    ap->state			= 0;

    ap->prev_state		= 0;

    ap->match_begin_bitmask	= 0;

    ap->match_begin_prefix	= 0;

    ap->match_end_bitvector	= 0;

    ap->match_end_bitmask	= 0;

    ap->match_state		= APSE_MATCH_STATE_BOT;

    ap->match_begin		= APSE_MATCH_BAD;

    ap->match_end		= APSE_MATCH_BAD;

    ap->match_bot_callback	= 0;

    ap->match_begin_callback	= 0;

    ap->match_fail_callback	= 0;

    ap->match_end_callback	= 0;

    ap->match_eot_callback	= 0;

    ap->exact_positions		= 0;

    ap->exact_mask		= 0;

    ap->is_greedy		= 0;

    ap->custom_data		= 0;

    ap->custom_data_size	= 0;

    if (!apse_set_pattern(ap, (unsigned char *)pattern, pattern_size))

	goto out;

    if (!apse_set_edit_distance(ap, edit_distance))

	goto out;

    ap->edit_insertions = ap->edit_deletions =

	ap->edit_substitutions = ap->edit_distance;

    ap->largest_distance = edit_distance * ap->bitvectors_in_state;

#ifdef APSE_DEBUGGING

    printf("(size of bitvector = %ld, bitvectors_in_state = %ld)\n",

	   (long)sizeof(apse_vec_t), ap->bitvectors_in_state);

    printf("(bytes_in_state = %ld, states = %ld, bytes_in_all_states = %ld)\n",

	   ap->bytes_in_state, ap->edit_distance + 1, ap->bytes_in_all_states);

    printf("(match_begin_bitvector = %ld, match_begin_bitmask = %s)\n",

	   ap->match_begin_bitvector,

	   _apse_fbin(ap->match_begin_bitmask, ap->pattern_size, 1));

    printf("(match_end_bitvector = %ld, match_end_bitmask = %s)\n",

	   ap->match_end_bitvector,

	   _apse_fbin(ap->match_end_bitmask, ap->pattern_size, 1));

    printf("(largest_distance = %ld, match_begin_prefix = %s)\n",

	   ap->largest_distance,

	   _apse_fbin(ap->match_begin_prefix, ap->pattern_size, 1));

    if (ap->bitvectors_in_state == 1)

	printf("(single bitvector");

    else

	printf("(multiple bitvectors");

    printf(")\n");

#endif

    okay = 1;

 out:

    if (!okay) {

	apse_destroy(ap);

	ap = 0;

    }

    return ap;

}

apse_bool_t apse_set_insertions(apse_t *ap, apse_size_t insertions) {

    apse_bool_t	okay = 0;

    if (insertions > ap->edit_distance)

	insertions = ap->edit_distance;

    ap->edit_insertions = insertions;

    ap->has_different_distances = 1;

    APSE_DEBUG((printf("(edit distances: insertions = %ld, deletions = %ld, substitutions = %ld)\n",

		       ap->edit_insertions,

		       ap->edit_deletions,

		       ap->edit_substitutions)));

    okay = 1;

    return okay;

}

apse_size_t apse_get_insertions(apse_t *ap) {

    if (ap->has_different_distances)

	return ap->edit_insertions;

    else

	return ap->edit_distance;

}

apse_bool_t apse_set_deletions(apse_t *ap, apse_size_t deletions) {

    apse_bool_t	okay = 0;

    if (deletions > ap->edit_distance)

	deletions = ap->edit_distance;

    ap->edit_deletions = deletions;

    ap->has_different_distances = 1;

    APSE_DEBUG((printf("(edit distances: insertions = %ld, deletions = %ld, substitutions = %ld)\n",

		       ap->edit_insertions,

		       ap->edit_deletions,

		       ap->edit_substitutions)));

    okay = 1;

    return okay;

}

apse_size_t apse_get_deletions(apse_t *ap) {

    if (ap->has_different_distances)

	return ap->edit_deletions;

    else

	return ap->edit_distance;

}

apse_bool_t apse_set_substitutions(apse_t *ap, apse_size_t substitutions) {

    apse_bool_t	okay = 0;

    if (substitutions > ap->edit_distance)

	substitutions = ap->edit_distance;

    ap->edit_substitutions = substitutions;

    ap->has_different_distances = 1;

    APSE_DEBUG((printf("(edit distances: insertions = %ld, deletions = %ld, substitutions = %ld)\n",

		       ap->edit_insertions,

		       ap->edit_deletions,

		       ap->edit_substitutions)));

    okay = 1;

    return okay;

}

apse_size_t apse_get_substitutions(apse_t *ap) {

    if (ap->has_different_distances)

	return ap->edit_substitutions;

    else

	return ap->edit_distance;

}

#ifdef APSE_DEBUGGING

static const char* apse_match_state_name(apse_t* ap) {

    switch (ap->match_state) {

    case APSE_MATCH_STATE_BOT:		return "BOT";

    case APSE_MATCH_STATE_SEARCH:	return "SEARCH";

    case APSE_MATCH_STATE_BEGIN:	return "BEGIN";

    case APSE_MATCH_STATE_FAIL:		return "FAIL";

    case APSE_MATCH_STATE_GREEDY:	return "GREEDY";

    case APSE_MATCH_STATE_END:		return "END";

    case APSE_MATCH_STATE_EOT:		return "EOT";

    default:				return "***UNKNOWN***";

    }

}

#endif

static void _apse_match_bot(apse_t *ap) {

    APSE_DEBUG(printf("(text = \"%*.*s\", text_size = %ld)\n",

		       (int)ap->text_size, (int)ap->text_size, ap->text,

		       ap->text_size));

    apse_reset(ap);

    APSE_DEBUG(printf("(match state %s)\n", apse_match_state_name(ap)));

    APSE_DEBUG(printf("(text begin %ld)\n", ap->text_position));

    if (ap->match_bot_callback)

	ap->match_bot_callback(ap);

}

static void _apse_match_begin(apse_t *ap) {

    ap->match_state = APSE_MATCH_STATE_BEGIN;

    APSE_DEBUG(printf("(match state %s)\n", apse_match_state_name(ap)));

    APSE_DEBUG(printf("(match begin %ld)\n", ap->text_position));

    ap->match_begin = ap->text_position;

    if (ap->match_begin_callback)

	ap->match_begin_callback(ap);

}

static void _apse_match_fail(apse_t *ap) {

    ap->match_state = APSE_MATCH_STATE_FAIL;

    APSE_DEBUG(printf("(match state %s)\n", apse_match_state_name(ap)));

    ap->match_begin = APSE_MATCH_BAD;

    APSE_DEBUG(printf("(match fail %ld)\n", ap->text_position));

    if (ap->match_fail_callback)

	ap->match_fail_callback(ap);

    ap->match_state = APSE_MATCH_STATE_SEARCH;

    APSE_DEBUG(printf("(match state %s)\n", apse_match_state_name(ap)));

}

static void _apse_match_end(apse_t *ap) {

    ap->match_state = APSE_MATCH_STATE_END;

    APSE_DEBUG(printf("(match state %s)\n", apse_match_state_name(ap)));

#ifdef APSE_DEBUGGING

    printf("(match end %ld)\n", ap->match_end);

    printf("(match string \"%.*s\")\n",

	   (int)(ap->match_end - ap->match_begin + 1),

	   ap->text + ap->match_begin);

    printf("(match length %ld)\n",

	   ap->match_end - ap->match_begin + 1);

#endif

    if (ap->match_end_callback)

	ap->match_end_callback(ap);

    ap->match_state = APSE_MATCH_STATE_SEARCH;

    APSE_DEBUG(printf("(match state %s)\n", apse_match_state_name(ap)));

}

static void _apse_match_eot(apse_t *ap) {

    ap->match_state = APSE_MATCH_STATE_EOT;

    APSE_DEBUG(printf("(match state %s)\n", apse_match_state_name(ap)));

    ap->text_position = ap->text_size;

    APSE_DEBUG(printf("(text end %ld)\n", ap->text_position));

    if (ap->match_eot_callback)

	ap->match_eot_callback(ap);

}

static apse_bool_t _apse_match_next_state(apse_t *ap) {

    apse_size_t	h, i, j, k;

    apse_vec_t	match;

    k = ap->edit_distance * ap->bitvectors_in_state;

    switch (ap->match_state) {

    case APSE_MATCH_STATE_SEARCH:

	if (APSE_EXACT_MATCH_BEGIN(ap) || APSE_APPROX_MATCH_BEGIN(ap))

	    _apse_match_begin(ap);

	break;

    case APSE_MATCH_STATE_BEGIN:

	{

	    apse_size_t		equal	= 0;

	    apse_size_t		active	= 0;

	    for (h = 0;

		 h <= k;

		 h += ap->bitvectors_in_state) {

		for (i = h, j = i + ap->bitvectors_in_state - 1; i < j; j--)

		    if (ap->state[j] != ap->prev_state[j])

			break;

		if (ap->prev_state[j] == ap->state[j])

		    equal++;

		if (ap->state[j])

		    active++;

	    }

#ifdef APSE_DEBUGGING

	    printf("(equal = %d, active = %d)\n", equal, active);

#endif

	    if ((equal == ap->edit_distance + 1 && ap->is_greedy == 0) ||

		(equal < ap->prev_equal && ap->prev_active &&

		 active > ap->prev_active &&

		 !APSE_BIT_TST(ap->state,

			       ap->edit_distance,

			       ap->bitvectors_in_state,

			       ap->text_position - ap->match_begin))) {

		ap->match_begin = ap->text_position;

#ifdef APSE_DEBUGGING

		printf("(slide begin %d)\n", ap->match_begin);

#endif

	    }

	    else if (active == 0)

		_apse_match_fail(ap);

	    ap->prev_equal  = equal;

	    ap->prev_active = active;

	}

	break;

    default:

	break;

    }

    for (match = 0, h = 0;

	 h <= k;

	 h += ap->bitvectors_in_state)

	match |= ap->state[h + ap->match_end_bitvector];

    if (match & ap->match_end_bitmask) {

	if (ap->match_state == APSE_MATCH_STATE_BEGIN) {

	    if (ap->is_greedy) {

		ap->match_state = APSE_MATCH_STATE_GREEDY;

		APSE_DEBUG(printf("(match state %s)\n",

				   apse_match_state_name(ap)));

		APSE_DEBUG(

		    printf("(greedy match continue %ld)\n",

			   ap->text_position));

	    } else {

		ap->match_state = APSE_MATCH_STATE_END;

		ap->match_end   = ap->text_position;

	    }

	}

    } else if (ap->match_state == APSE_MATCH_STATE_GREEDY) {

	ap->match_state = APSE_MATCH_STATE_END;

	APSE_DEBUG(printf("(match state %s)\n", apse_match_state_name(ap)));

	ap->match_end	= ap->text_position - 1;

	APSE_DEBUG(printf("(match end %ld)\n",  ap->match_end));

    }

    return ap->match_state;

}

static void _apse_exact_multiple(apse_t* ap) {

    apse_size_t	h;

    apse_size_t	g = ap->edit_distance * ap->bitvectors_in_state;

    for (h = 0; h < ap->bitvectors_in_state; h++)

	ap->state[g + h] &= ~ap->exact_mask[h];

} 

static apse_bool_t _apse_match_single_simple(apse_t *ap) {

    /* single apse_vec_t, edit_distance */

    APSE_DEBUG(printf("(match single simple)\n"));

    for ( ; ap->text_position < ap->text_size; ap->text_position++) {

	apse_vec_t	t =

      	    ap->pattern_mask[(unsigned)ap->text[ap->text_position] *

			    ap->bitvectors_in_state];

	apse_size_t	h, g;

	APSE_NEXT_EXACT(ap->state, ap->prev_state, t, (apse_size_t)0, 1);

	APSE_DEBUG_SINGLE(ap, (apse_size_t)0);

	for (g = 0, h = 1; h <= ap->edit_distance; g = h, h++) {

	    APSE_NEXT_APPROX(ap->state, ap->prev_state, t, h, g, 1);

	    APSE_DEBUG_SINGLE(ap, h);

	}

	if (ap->exact_positions)

	    ap->state[ap->edit_distance] &= ~ap->exact_mask[0];

	if (_apse_match_next_state(ap) == APSE_MATCH_STATE_END)

	    return 1;

	(void)memcpy(ap->prev_state, ap->state, ap->bytes_in_all_states);

    }

    return 0;

}

static apse_bool_t _apse_match_multiple_simple(apse_t *ap) {

    /* multiple apse_vec_t:s, has_different_distances */

    apse_size_t	h, i;

    APSE_DEBUG(printf("(match multiple simple)\n"));

    for ( ; ap->text_position < ap->text_size; ap->text_position++) {

	apse_vec_t	*t =

	    ap->pattern_mask +

	    (unsigned)ap->text[ap->text_position] * ap->bitvectors_in_state;

	apse_vec_t	c, d;

	APSE_DEBUG_MULTIPLE_FIRST(ap, (apse_size_t)0);

	for (c = 1, i = 0; i < ap->bitvectors_in_state; i++, c = d) {

	    d = APSE_TEST_HIGH_BIT(ap->state[i]);

	    APSE_NEXT_EXACT(ap->state, ap->prev_state, t[i], i, c);

	    APSE_DEBUG_MULTIPLE_REST(ap, i, i);

	}

	APSE_DEBUG(printf("\n"));

	for (h = 1; h <= ap->edit_distance; h++) {

	    apse_size_t	kj = h * ap->bitvectors_in_state,

			jj = kj - ap->bitvectors_in_state;

	    APSE_DEBUG_MULTIPLE_FIRST(ap, h);

	    for (c = 1, i = 0;