note 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). ]" library: "Free implementation of ELKS library" status: "See notice at end of class." legal: "See notice at end of class." date: "$Date: 2012-05-24 04:13:10 +0000 (Thu, 24 May 2012) $" revision: "$Revision: 91981 $" deferred class interface STRING_SEARCHER feature -- Initialization initialize_deltas (a_pattern: READABLE_STRING_GENERAL) -- Initialize deltas with a_pattern. -- Optimized for the top max_code_point_value characters only. require a_pattern_not_void: a_pattern /= Void feature -- Access generating_type: TYPE [detachable STRING_SEARCHER] -- Type of current object -- (type of which it is a direct instance) -- (from ANY) ensure -- from ANY generating_type_not_void: Result /= Void generator: STRING_8 -- Name of current object's generating class -- (base class of the type of which it is a direct instance) -- (from ANY) ensure -- from ANY generator_not_void: Result /= Void generator_not_empty: not Result.is_empty max_code_point_value: INTEGER_32 -- Maximum character value for which we optimize the lookup of a pattern. -- If any item's code of the searched string is above that limit, search will -- not be as efficient. ensure positive: Result > 0 string_type: READABLE_STRING_GENERAL -- Type of strings Current manipulate to perform searches. ensure for_typing_only: False feature -- Comparison frozen deep_equal (a: detachable ANY; b: like arg #1): BOOLEAN -- Are a and b either both void -- or attached to isomorphic object structures? -- (from ANY) ensure -- from ANY instance_free: class shallow_implies_deep: standard_equal (a, b) implies Result both_or_none_void: (a = Void) implies (Result = (b = Void)) same_type: (Result and (a /= Void)) implies (b /= Void and then a.same_type (b)) symmetric: Result implies deep_equal (b, a) frozen equal (a: detachable ANY; b: like arg #1): BOOLEAN -- Are a and b either both void or attached -- to objects considered equal? -- (from ANY) ensure -- from ANY instance_free: class definition: Result = (a = Void and b = Void) or else ((a /= Void and b /= Void) and then a.is_equal (b)) frozen is_deep_equal alias "≡≡≡" (other: STRING_SEARCHER): BOOLEAN -- Are Current and other attached to isomorphic object structures? -- (from ANY) require -- from ANY other_not_void: other /= Void ensure -- from ANY shallow_implies_deep: standard_is_equal (other) implies Result same_type: Result implies same_type (other) symmetric: Result implies other.is_deep_equal (Current) is_equal (other: STRING_SEARCHER): 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 ~ Current consistent: standard_is_equal (other) implies Result frozen standard_equal (a: detachable ANY; b: like arg #1): BOOLEAN -- Are a and b 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 instance_free: class definition: Result = (a = Void and b = Void) or else ((a /= Void and b /= Void) and then a.standard_is_equal (b)) frozen standard_is_equal alias "≜" (other: STRING_SEARCHER): 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: STRING_SEARCHER) -- 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: Current ~ other frozen deep_copy (other: STRING_SEARCHER) -- 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: STRING_SEARCHER -- New object structure recursively duplicated from Current. -- (from ANY) ensure -- from ANY deep_twin_not_void: Result /= Void deep_equal: deep_equal (Current, Result) frozen standard_copy (other: STRING_SEARCHER) -- 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: STRING_SEARCHER -- 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: STRING_SEARCHER -- New object equal to Current -- twin calls copy; to change copying/twinning semantics, redefine copy. -- (from ANY) ensure -- from ANY twin_not_void: Result /= Void is_equal: Result ~ Current feature -- Basic operations frozen default: detachable STRING_SEARCHER -- 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) ensure -- from ANY instance_free: class default_rescue -- Process exception for routines with no Rescue clause. -- (Default: do nothing.) -- (from ANY) frozen do_nothing -- Execute a null action. -- (from ANY) ensure -- from ANY instance_free: class feature -- Output Io: STD_FILES -- Handle to standard file setup -- (from ANY) ensure -- from ANY instance_free: class io_not_void: Result /= Void out: STRING_8 -- New string containing terse printable representation -- of current object -- (from ANY) ensure -- from ANY out_not_void: Result /= Void print (o: detachable ANY) -- Write terse external representation of o -- on standard output. -- (from ANY) ensure -- from ANY instance_free: class frozen tagged_out: STRING_8 -- New string containing terse printable representation -- of current object -- (from ANY) ensure -- from ANY tagged_out_not_void: Result /= Void feature -- Platform Operating_environment: OPERATING_ENVIRONMENT -- Objects available from the operating system -- (from ANY) ensure -- from ANY instance_free: class operating_environment_not_void: Result /= Void feature -- Search fuzzy_index (a_string: like string_type; a_pattern: READABLE_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_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: like string_type; a_pattern: READABLE_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 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_list_with_deltas (a_string: like string_type; a_pattern: READABLE_STRING_GENERAL; start_pos, end_pos: INTEGER_32): detachable ARRAYED_LIST [INTEGER_32] -- Index positions of all occurrences of a_pattern at or after start_pos until end_pos in a_string. -- Result is Void if there are no matches. require a_string_not_void: a_string /= Void a_pattern_not_void: a_pattern /= Void 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 ensure matches: Result /= Void implies not Result.is_empty substring_index_with_deltas (a_string: like string_type; a_pattern: READABLE_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_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.capacity = max_code_point_value + 1 -- from ANY reflexive_equality: standard_is_equal (Current) reflexive_conformance: conforms_to (Current) note copyright: "Copyright (c) 1984-2012, Eiffel Software and others" license: "Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt)" source: "[ Eiffel Software 5949 Hollister Ave., 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
Generated by ISE EiffelStudio