    indexing
    	description: "[
    		Helper to perform efficient search of a string in another one.
    		Note: The algorithm used is the one described in Communications of the ACM,
    			volume 33, number 8, August 1990, by Daniel M. Sunday. The fuzzy
    			version was presented by Peter R. Sibbald in Communications of the
    			ACM, volume 35, number 4, April 1992 (Technical Correspondance).
    	]"
    	legal: "See notice at end of class."
    	status: "See notice at end of class."
    	date: "$Date: 2006-03-22 15:17:14 -0800 (Wed, 22 Mar 2006) $"
    	revision: "$Revision: 57607 $"

    class interface
    	STRING_SEARCHER

    create
    	make
    			-- Initialize current

    feature -- Initialization

    	initialize_deltas (a_pattern: STRING_GENERAL)
    			-- Initialize deltas with `a_pattern'.
    			-- Optimized for ASCII characters only.
    		require
    			a_pattern_not_void: a_pattern /= Void
    			a_pattern_valid: a_pattern.is_valid_as_string_8

    feature -- Access

    	generating_type: STRING_8
    			-- Name of current object's generating type
    			-- (type of which it is a direct instance)
    			-- (from ANY)

    	generator: STRING_8
    			-- Name of current object's generating class
    			-- (base class of the type of which it is a direct instance)
    			-- (from ANY)

    	max_ascii_character_value: INTEGER_32 is 255
    			-- Number of characters in the extended ASCII character set.

    feature -- Comparison

    	frozen deep_equal (some: ANY; other: like arg #1): BOOLEAN
    			-- Are `some' and `other' either both void
    			-- or attached to isomorphic object structures?
    			-- (from ANY)
    		ensure -- from ANY
    			shallow_implies_deep: standard_equal (some, other) implies Result
    			both_or_none_void: (some = Void) implies (Result = (other = Void))
    			same_type: (Result and (some /= Void)) implies some.same_type (other)
    			symmetric: Result implies deep_equal (other, some)

    	frozen equal (some: ANY; other: like arg #1): BOOLEAN
    			-- Are `some' and `other' either both void or attached
    			-- to objects considered equal?
    			-- (from ANY)
    		ensure -- from ANY
    			definition: Result = (some = Void and other = Void) or else ((some /= Void and other /= Void) and then some.is_equal (other))

    	is_equal (other: like Current): BOOLEAN
    			-- Is `other' attached to an object considered
    			-- equal to current object?
    			-- (from ANY)
    		require -- from ANY
    			other_not_void: other /= Void
    		ensure -- from ANY
    			symmetric: Result implies other.is_equal (Current)
    			consistent: standard_is_equal (other) implies Result

    	frozen standard_equal (some: ANY; other: like arg #1): BOOLEAN
    			-- Are `some' and `other' either both void or attached to
    			-- field-by-field identical objects of the same type?
    			-- Always uses default object comparison criterion.
    			-- (from ANY)
    		ensure -- from ANY
    			definition: Result = (some = Void and other = Void) or else ((some /= Void and other /= Void) and then some.standard_is_equal (other))

    	frozen standard_is_equal (other: like Current): BOOLEAN
    			-- Is `other' attached to an object of the same type
    			-- as current object, and field-by-field identical to it?
    			-- (from ANY)
    		require -- from ANY
    			other_not_void: other /= Void
    		ensure -- from ANY
    			same_type: Result implies same_type (other)
    			symmetric: Result implies other.standard_is_equal (Current)

    feature -- Status report

    	conforms_to (other: ANY): BOOLEAN
    			-- Does type of current object conform to type
    			-- of `other' (as per Eiffel: The Language, chapter 13)?
    			-- (from ANY)
    		require -- from ANY
    			other_not_void: other /= Void

    	same_type (other: ANY): BOOLEAN
    			-- Is type of current object identical to type of `other'?
    			-- (from ANY)
    		require -- from ANY
    			other_not_void: other /= Void
    		ensure -- from ANY
    			definition: Result = (conforms_to (other) and other.conforms_to (Current))

    feature -- Duplication

    	copy (other: like Current)
    			-- Update current object using fields of object attached
    			-- to `other', so as to yield equal objects.
    			-- (from ANY)
    		require -- from ANY
    			other_not_void: other /= Void
    			type_identity: same_type (other)
    		ensure -- from ANY
    			is_equal: is_equal (other)

    	frozen deep_copy (other: like Current)
    			-- Effect equivalent to that of:
    			--		copy (`other' . deep_twin)
    			-- (from ANY)
    		require -- from ANY
    			other_not_void: other /= Void
    		ensure -- from ANY
    			deep_equal: deep_equal (Current, other)

    	frozen deep_twin: like Current
    			-- New object structure recursively duplicated from Current.
    			-- (from ANY)
    		ensure -- from ANY
    			deep_equal: deep_equal (Current, Result)

    	frozen standard_copy (other: like Current)
    			-- Copy every field of `other' onto corresponding field
    			-- of current object.
    			-- (from ANY)
    		require -- from ANY
    			other_not_void: other /= Void
    			type_identity: same_type (other)
    		ensure -- from ANY
    			is_standard_equal: standard_is_equal (other)

    	frozen standard_twin: like Current
    			-- New object field-by-field identical to `other'.
    			-- Always uses default copying semantics.
    			-- (from ANY)
    		ensure -- from ANY
    			standard_twin_not_void: Result /= Void
    			equal: standard_equal (Result, Current)

    	frozen twin: like Current
    			-- New object equal to `Current'
    			-- twin calls copy; to change copying/twining semantics, redefine copy.
    			-- (from ANY)
    		ensure -- from ANY
    			twin_not_void: Result /= Void
    			is_equal: Result.is_equal (Current)

    feature -- Basic operations

    	frozen default: like Current
    			-- Default value of object's type
    			-- (from ANY)

    	frozen default_pointer: POINTER
    			-- Default value of type `POINTER'
    			-- (Avoid the need to write `p'.default for
    			-- some `p' of type `POINTER'.)
    			-- (from ANY)

    	default_rescue
    			-- Process exception for routines with no Rescue clause.
    			-- (Default: do nothing.)
    			-- (from ANY)

    	frozen do_nothing
    			-- Execute a null action.
    			-- (from ANY)

    feature -- Output

    	io: STD_FILES
    			-- Handle to standard file setup
    			-- (from ANY)

    	out: STRING_8
    			-- New string containing terse printable representation
    			-- of current object
    			-- Was declared in ANY as synonym of tagged_out.
    			-- (from ANY)

    	print (some: ANY)
    			-- Write terse external representation of `some'
    			-- on standard output.
    			-- (from ANY)

    	frozen tagged_out: STRING_8
    			-- New string containing terse printable representation
    			-- of current object
    			-- Was declared in ANY as synonym of out.
    			-- (from ANY)

    feature -- Platform

    	operating_environment: OPERATING_ENVIRONMENT
    			-- Objects available from the operating system
    			-- (from ANY)

    feature -- Search

    	fuzzy_index (a_string, a_pattern: STRING_GENERAL; start_pos, end_pos, fuzzy: INTEGER_32): INTEGER_32
    			-- Position of first occurrence of `a_pattern' at or after `start_pos' in
    			-- `a_string' with 0..`fuzzy' mismatches between `a_string' and `a_pattern'.
    			-- 0 if there are no fuzzy matches.
    		require
    			a_string_not_void: a_string /= Void
    			a_pattern_not_void: a_pattern /= Void
    			a_pattern_valid: a_pattern.is_valid_as_string_8
    			a_pattern_not_empty: not a_pattern.is_empty
    			start_large_enough: start_pos >= 1
    			end_pos_large_enough: start_pos <= end_pos + 1
    			end_pos_small_enough: end_pos <= a_string.count
    			fuzzy_non_negative: fuzzy >= 0
    			acceptable_fuzzy: fuzzy <= a_pattern.count

    	substring_index (a_string, a_pattern: STRING_GENERAL; start_pos, end_pos: INTEGER_32): INTEGER_32
    			-- Position of first occurrence of `a_pattern' at or after `start_pos'
    			-- and before `end_pos' in `a_string'.
    			-- 0 if there are no matches.
    		require
    			a_string_not_void: a_string /= Void
    			a_pattern_not_void: a_pattern /= Void
    			a_pattern_valid: a_pattern.is_valid_as_string_8
    			start_large_enough: start_pos >= 1
    			end_pos_large_enough: start_pos <= end_pos + 1
    			end_pos_small_enough: end_pos <= a_string.count

    	substring_index_with_deltas (a_string, a_pattern: STRING_GENERAL; start_pos, end_pos: INTEGER_32): INTEGER_32
    			-- Position of first occurrence of `a_pattern' at or after `start_pos' in `a_string'.
    			-- 0 if there are no matches.
    		require
    			a_string_not_void: a_string /= Void
    			a_pattern_not_void: a_pattern /= Void
    			a_pattern_valid: a_pattern.is_valid_as_string_8
    			a_pattern_not_empty: not a_pattern.is_empty
    			start_large_enough: start_pos >= 1
    			end_pos_large_enough: start_pos <= end_pos + 1
    			end_pos_small_enough: end_pos <= a_string.count

    invariant
    	deltas_not_void: deltas /= Void
    	deltas_valid: deltas.count = max_ascii_character_value + 1

    		-- from ANY
    	reflexive_equality: standard_is_equal (Current)
    	reflexive_conformance: conforms_to (Current)

    indexing
    	library: "EiffelBase: Library of reusable components for Eiffel."
    	copyright: "Copyright (c) 1984-2006, Eiffel Software and others"
    	license: "Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)"
    	source: "[
    		Eiffel Software
    		356 Storke Road, Goleta, CA 93117 USA
    		Telephone 805-685-1006, Fax 805-685-6869
    		Website http://www.eiffel.com
    		Customer support http://support.eiffel.com
    	]"

    end -- class STRING_SEARCHER