-- (c) Copyright - See License.txt

--

namespace search

--****

-- == Searching

-- **Page Contents**

--

-- <>

include std/error.e

include std/types.e

--****

-- === Equality

--

--****

-- Signature:

-- function compare(object compared, object reference)

--

-- Description:

-- Compare two items returning less than, equal or greater than.

--

-- Parameters:

-- # ##compared## : the compared object

-- # ##reference## : the reference object

--

-- Returns:

-- An **integer**,

-- * 0 ~-- if objects are identical

-- * 1 ~-- if ##compared## is greater than ##reference##

-- * -1 ~-- if ##compared## is less than ##reference##

--

-- Comments:

-- Atoms are considered to be less than sequences. Sequences are compared alphabetically

-- starting with the first element until a difference is found or one of the sequences is exhausted. Atoms are compared as ordinary reals.

--

-- Example 1:

--

-- x = compare({1,2,{3,{4}},5}, {2-1,1+1,{3,{4}},6-1})

-- -- identical, x is 0

--

--

-- Example 2:

--

-- if compare("ABC", "ABCD") < 0 then -- -1

-- -- will be true: ABC is "less" because it is shorter

-- end if

--

--

-- Example 3:

--

-- x = compare('a', "a")

-- -- x will be -1 because 'a' is an atom

-- -- while "a" is a sequence

--

--

-- See Also:

-- [[:equal]], [[:relational operators]], [[:operations on sequences]], [[:sort]]

--****

-- Signature:

-- function equal(object left, object right)

--

-- Description:

-- Compare two Euphoria objects to see if they are the same.

--

-- Parameters:

-- # ##left## : one of the objects to test

-- # ##right## : the other object

--

-- Returns:

-- An **integer**, 1 if the two objects are identical, else 0.

--

-- Comments:

-- This is equivalent to the expression: ##compare(left, right) = 0##.

--

-- This routine, like most other built-in routines, is very fast. It does not have any

-- subroutine call overhead.

--

-- Example 1:

--

-- if equal(PI, 3.14) then

-- puts(1, "give me a better value for PI!\n")

-- end if

--

--

-- Example 2:

--

-- if equal(name, "George") or equal(name, "GEORGE") then

-- puts(1, "name is George\n")

-- end if

--

--

-- See Also:

-- [[:compare]]

--****

-- === Finding

--

--****

-- Signature:

-- function find(object needle, sequence haystack, integer start)

--

-- Description:

-- Find the first occurrence of a "needle" as an element of a "haystack", starting from position "start"..

--

-- Parameters:

-- # ##needle## : an object whose presence is being queried

-- # ##haystack## : a sequence, which is being looked up for ##needle##

-- # ##start## : an integer, the position at which to start searching. Defaults to 1.

--

-- Returns:

-- An **integer**, 0 if ##needle## is not on ##haystack##, else the smallest index of an

-- element of ##haystack## that equals ##needle##.

--

-- Comments:

--

-- ##find##() and [[:find_from]]() are identical, but you can omit giving ##find##() a starting point.

--

-- Example 1:

--

-- location = find(11, {5, 8, 11, 2, 3})

-- -- location is set to 3

--

--

-- Example 2:

--

-- names = {"fred", "rob", "george", "mary", ""}

-- location = find("mary", names)

-- -- location is set to 4

--

--

-- See Also:

-- [[:find_from]], [[:match]], [[:match_from]], [[:compare]]

--****

-- Signature:

-- function find_from(object needle, object haystack, integer start)

--

-- Description:

-- Find the first occurrence of a "needle" as an element of a "haystack". Search starts at a specified index.

--

--Parameters:

-- # ##needle## : an object whose presence is being queried

-- # ##haystack## : a sequence, which is being looked up for ##needle##

-- # ##start## : an integer, the index in ##haystack## at which to start searching.

--

-- Returns:

-- An **integer**, 0 if ##needle## is not on ##haystack## past position ##start##, else the smallest index, not less than ##start##, of an element of ##haystack## that equals ##needle##.

--

-- Comments:

-- start may have any value from 1 to the length of ##haystack## plus 1. (Analogous to the

-- first index of a slice of ##haystack##).

--

-- ##find##() and [[:find_from]]() are identical, but you can omit giving ##find##() a starting point.

--

-- Example 1:

--

-- location = find_from(11, {11, 8, 11, 2, 3}, 2)

-- -- location is set to 3

--

--

-- Example 2:

--

-- names = {"mary", "rob", "george", "mary", ""}

-- location = find_from("mary", names, 3)

-- -- location is set to 4

--

--

-- See Also:

-- [[:find]], [[:match]], [[:match_from]], [[:compare]]

--**

-- Find any element from a list inside a sequence. Returns the location of the first hit.

--

-- Parameters:

-- # ##needles## : a sequence, the list of items to look for

-- # ##haystack## : a sequence, in which "needles" are looked for

-- # ##start## : an integer, the starting point of the search. Defaults to 1.

--

-- Returns:

-- An **integer**, the smallest index in ##haystack## of an element of ##needles##, or 0 if no needle is found.

--

-- Comments:

-- This function may be applied to a string sequence or a complex

-- sequence.

--

-- Example 1:

--

-- location = find_any("aeiou", "John Smith", 3)

-- -- location is 8

--

--

-- Example 2:

--

-- location = find_any("aeiou", "John Doe")

-- -- location is 2

--

--

-- See Also:

-- [[:find]], [[:find_from]]

end if

end function

--**

-- Find all occurrences of an object inside a sequence, starting at some specified point.

--

-- Parameters:

-- # ##needle## : an object, what to look for

-- # ##haystack## : a sequence to search in

-- # ##start## : an integer, the starting index position (defaults to 1)

--

-- Returns:

-- A **sequence**, the list of all indexes no less than ##start## of elements of ##haystack## that equal ##needle##. This sequence is empty if no match found.

--

-- Example 1:

--

-- s = find_all('A', "ABCABAB")

-- -- s is {1,4,6}

--

--

-- See Also:

-- [[:find]], [[:match]], [[:match_all]]

entry

end function

public constant

--**

-- Find any object (among a list) in a sequence of arbitrary shape at arbitrary nesting.

--

-- Parameters:

-- # ##needle## : an object, either what to look up, or a list of items to look up

-- # ##haystack## : a sequence, where to look up

-- # ##flags## : options to the function, see Comments section. Defaults to 0.

-- # ##routine## : an integer, the routine_id of an user supplied equal function. Defaults to -1.

--

-- Returns:

-- A possibly empty **sequence**, of results, one for each hit.

--

-- Comments:

-- Each item in the returned sequence is either a sequence of indexes, or a pair {sequence of indexes, index in ##needle##}.

--

-- The following flags are available to fine tune the search:

-- * ##NESTED_BACKWARD## ~-- if on ##flags##, search is performed backward. Default is forward.

-- * ##NESTED_ALL## ~-- if on ##flags##, all occurrences are looked for. Default is one hit only.

-- * ##NESTED_ANY## ~-- if present on ##flags##, ##needle## is a list of items to look for. Not the default.

-- * ##NESTED_INDEXES## ~-- if present on ##flags##, an individual result is a pair {position, index

-- in ##needle##}. Default is just return the position.

--

-- If ##s## is a single index list, or position, from the returned sequence, then ##fetch(haystack, s) = needle##.

--

-- If a routine id is supplied, the routine must behave like [[:equal]]() if the NESTED_ANY

-- flag is not supplied, and like [[:find]]() if it is. The routine is being passed the current

-- ##haystack## item and ##needle##. The returned integer is interpreted as if returned by

-- [[:equal]]() or [[:find]]().

--

-- If the ##NESTED_ANY## flag is specified, and ##needle## is an atom, then the flag is removed.

--

-- Example 1:

--

-- sequence s = find_nested(3, {5, {4, {3, {2}}}})

-- -- s is {2 ,2 ,1}

--

--

-- Example 2:

--

-- sequence s = find_nested({3, 2}, {1, 3, {2,3}}, NESTED_ANY + NESTED_BACKWARD + NESTED_ALL)

-- -- s is {{3,2}, {3,1}, {2}}

--

--

-- Example 3:

--

-- sequence s = find_nested({3, 2}, {1, 3, {2,3}}, NESTED_ANY + NESTED_INDEXES + NESTED_ALL)

-- -- s is {{{2}, 1}, {{3, 1}, 2}, {{3, 2}, 1}}

--

--

-- See Also:

-- [[:find]], [[:rfind]], [[:find_any]], [[:fetch]]

object x

end if

-- is x what we want?

else

end if

else

end if

-- yes, it is

-- inline head() from sequence.e

else

end if

end if

else

end if

end if

-- either it wasn't, or we keep going

-- this is a subtree, search inside

-- save state

else

end if

-- set new state

else

end if

else

-- next item

end if

-- return or backtrack

end if

-- restore state

end function

--**

-- Find a needle in a haystack in reverse order.

--

-- Parameters:

-- # ##needle## : an object to search for

-- # ##haystack## : a sequence to search in

-- # ##start## : an integer, the starting index position (defaults to length(##haystack##))

--

-- Returns:

-- An **integer**, 0 if no instance of ##needle## can be found on ##haystack## before

-- index ##start##, or the highest such index otherwise.

--

-- Comments:

--

-- If ##start## is less than 1, it will be added once to length(##haystack##)

-- to designate a position counted backwards. Thus, if ##start## is -1, the

-- first element to be queried in ##haystack## will be ##haystack##[$-1],

-- then ##haystack##[$-2] and so on.

--

-- Example 1:

--

-- location = rfind(11, {5, 8, 11, 2, 11, 3})

-- -- location is set to 5

--

--

-- Example 2:

--

-- names = {"fred", "rob", "rob", "george", "mary"}

-- location = rfind("rob", names)

-- -- location is set to 3

-- location = rfind("rob", names, -4)

-- -- location is set to 2

--

--

-- See Also:

-- [[:find]], [[:rmatch]]

end if

end if

end if

end function

--**

-- Finds a "needle" in a "haystack", and replace any, or only the first few, occurrences with a replacement.

--

-- Parameters:

--

-- # ##needle## : an object to search and perhaps replace

-- # ##haystack## : a sequence to be inspected

-- # ##replacement## : an object to substitute for any (first) instance of ##needle##

-- # ##max## : an integer, 0 to replace all occurrences

--

-- Returns:

-- A **sequence**, the modified ##haystack##.

--

-- Comments:

-- Replacements will not be made recursively on the part of ##haystack## that was already changed.

--

-- If ##max## is 0 or less, any occurrence of ##needle## in ##haystack## will be replaced by ##replacement##. Otherwise, only the first ##max## occurrences are.

--

-- Example 1:

--

-- s = find_replace('b', "The batty book was all but in Canada.", 'c', 0)

-- -- s is "The catty cook was all cut in Canada."

--

--

-- Example 2:

--

-- s = find_replace('/', "/euphoria/demo/unix", '\\', 2)

-- -- s is "\\euphoria\\demo/unix"

--

--

-- Example 3:

--

-- s = find_replace("theater", { "the", "theater", "theif" }, "theatre")

-- -- s is { "the", "theatre", "theif" }

--

--

-- See Also:

-- [[:find]], [[:replace]], [[:match_replace]]

integer max=0)

end if

entry

end function

--**

-- Finds a "needle" in a "haystack", and replace any, or only the first few, occurrences with a replacement.

--

-- Parameters:

--

-- # ##needle## : an object to search and perhaps replace

-- # ##haystack## : a sequence to be inspected

-- # ##replacement## : an object to substitute for any (first) instance of ##needle##

-- # ##max## : an integer, 0 to replace all occurrences

--

-- Returns:

-- A **sequence**, the modified ##haystack##.

--

-- Comments:

-- Replacements will not be made recursively on the part of ##haystack## that was already changed.

--

-- If ##max## is 0 or less, any occurrence of ##needle## in ##haystack## will be replaced by ##replacement##. Otherwise, only the first ##max## occurrences are.

--

-- If either ##needle## or ##replacement## are atoms they will be treated as if you had passed in a

-- length-1 sequence containing the said atom.

--

-- Example 1:

--

-- s = match_replace("the", "the cat ate the food under the table", "THE", 0)

-- -- s is "THE cat ate THE food under THE table"

--

--

-- Example 2:

--

-- s = match_replace("the", "the cat ate the food under the table", "THE", 2)

-- -- s is "THE cat ate THE food under the table"

--

--

-- Example 3:

--

-- s = match_replace('/', "/euphoria/demo/unix", '\\', 2)

-- -- s is "\\euphoria\\demo/unix"

--

--

-- See Also:

-- [[:find]], [[:replace]], [[:regex:find_replace]], [[:find_replace]]

integer max=0)

integer posn, needle_len, replacement_len

end if

end if

haystack[posn + needle_len .. $]

end if

end function

--**

-- Finds a "needle" in an ordered "haystack". Start and end point can be given for the search.

--

-- Parameters:

-- # ##needle## : an object to look for

-- # ##haystack## : a sequence to search in

-- # ##start_point## : an integer, the index at which to start searching. Defaults to 1.

-- # ##end_point## : an integer, the end point of the search. Defaults to 0, ie search to end.

--

-- Returns:

-- An **integer**, either:

-- # a positive integer ##i##, which means ##haystack[i]## equals ##needle##.

-- # a negative integer, ##-i##, with ##i## between adjusted start and end

-- points. This means that ##needle## is not in the searched slice of

-- ##haystack##, but would be at index ##i## if it were there.

-- # a negative integer ##-i## with ##i## out of the searched range. This

-- means than ##needle##might be either below the start point if ##i##

-- is below the start point, or above the end point if ##i## is.

--

-- Comments:

-- * If ##end_point## is not greater than zero, it is added to

-- length(##haystack##) once only. Then, the end point of the search is

-- adjusted to length(haystack) if out of bounds.

-- * The start point is adjusted to 1 if below 1.

-- * The way this function returns is very similar to what [[:db_find_key]]

-- does. They use variants of the same algorithm. The latter is all the

-- more efficient as ##haystack## is long.

-- * ##haystack## is assumed to be in ascending order. Results are undefined

-- if it is not.

-- * If duplicate copies of ##needle## exist in the range searched on

-- ##haystack##, any of the possible contiguous indexes may be returned.

--

-- See Also:

-- [[:find]], [[:db_find_key]]

integer end_point = 0)

integer lo, hi, mid, c -- works up to 1.07 billion records

else

end if

end if

end if

else

end if

-- return the position it would have, if inserted now

end if

end function

--****

-- === Matching

--

--****

-- Signature:

-- function match(sequence needle, sequence haystack, integer start)

--

-- Description:

-- Try to match a "needle" against some slice of a "haystack", starting at position "start".

--

-- Parameters:

-- # ##needle## : a sequence whose presence as a "substring" is being queried

-- # ##haystack## : a sequence, which is being looked up for ##needle## as a sub-sequence

-- # ##start## : an integer, the point from which matching is attempted. Defaults to 1.

--

-- Returns:

-- An **integer**, 0 if no slice of ##haystack## is ##needle##, else the smallest index at which such a slice starts.

--

-- Comments:

--

-- ##match##() and [[:match_from]]() are identical, but you can omit giving ##match##() a starting point.

--

-- Example 1:

--

-- location = match("pho", "Euphoria")

-- -- location is set to 3

--

--

-- See Also:

-- [[:find]], [[:find_from]], [[:compare]], [[:match_from]], [[:wildcard:is_match]]

--****

-- Signature:

-- function match_from(sequence needle, sequence haystack, integer start)

--

-- Description:

-- Try to match a "needle" against some slice of a "haystack", starting from some index.

--

-- Parameters:

-- # ##needle## : an sequence whose presence as a sub-sequence is being queried

-- # ##haystack## : a sequence, which is being looked up for ##needle## as a sub-sequence

-- # ##start## : an integer, the index in ##haystack## at which to start searching.

--

-- Returns:

-- An **integer**, 0 if no slice of ##haystack## with lower index at least ##start## is ##needle##, else the smallest such index.

--

-- Comments:

-- ##start## may have any value from 1 to the length of ##haystack## plus 1. (Just like the first

-- index of a slice of ##haystack##.)

--

-- ##match##() and [[:match_from]]() are identical, but you can omit giving ##match##() a starting point.

--

-- Example 1:

--

-- location = match_from("pho", "phoEuphoria", 4)

-- -- location is set to 6

--

--

-- See Also:

-- [[:find]], [[:find_from]], [[:match]], [[:compare]], [[:wildcard:is_match]], [[:regex:find]]

--**

-- Match all items of haystack in needle.

--

-- Parameters:

-- # ##needle## : a sequence, what to look for

-- # ##haystack## : a sequence to search in

-- # ##start## : an integer, the starting index position (defaults to 1)

--

-- Returns:

-- A **sequence**, of integers, the list of all lower indexes, not less than ##start##, of all slices in ##haystack## that equal ##needle##. The list may be empty.

--

-- Example 1:

--

-- s = match_all("the", "the dog chased the cat under the table.")

-- -- s is {1,16,30}

--

--

-- See Also:

-- [[:match]], [[:regex:find_all]] [[:find]], [[:find_all]]

entry

end function

--**

-- Try to match a needle against some slice of a haystack in reverse order.

--

-- Parameters:

-- # ##needle## : a sequence to search for

-- # ##haystack## : a sequence to search in

-- # ##start## : an integer, the starting index position (defaults to length(##haystack##))

--

-- Returns:

-- An **integer**, either 0 if no slice of ##haystack## starting before

-- ##start## equals ##needle##, else the highest lower index of such a slice.

--

-- Comments:

-- If ##start## is less than 1, it will be added once to length(##haystack##)

-- to designate a position counted backwards. Thus, if ##start## is -1, the

-- first element to be queried in ##haystack## will be ##haystack##[$-1],

-- then ##haystack##[$-2] and so on.

--

-- Example 1:

--

-- location = rmatch("the", "the dog ate the steak from the table.")

-- -- location is set to 28 (3rd 'the')

-- location = rmatch("the", "the dog ate the steak from the table.", -11)

-- -- location is set to 13 (2nd 'the')

--

--

-- See Also:

-- [[:rfind]], [[:match]]

integer len, lenX

end if

end if

end if

end if

end function

--**

-- Test whether a sequence is the head of another one.

--

-- Parameters:

-- # ##sub_text## : an object to be looked for

-- # ##full_text## : a sequence, the head of which is being inspected.

--

-- Returns:

-- An **integer**, 1 if ##sub_text## begins ##full_text##, else 0.

--

-- Example 1:

--

-- s = begins("abc", "abcdef")

-- -- s is 1

-- s = begins("bcd", "abcdef")

-- -- s is 0

--

--

-- See Also:

-- [[:ends]], [[:head]]

end if

else

end if

end if

end if

else

end if

end function

--**

-- Test whether a sequence ends another one.

--

-- Parameters:

-- # ##sub_text## : an object to be looked for

-- # ##full_text## : a sequence, the tail of which is being inspected.

--

-- Returns:

-- An **integer**, 1 if ##sub_text## ends ##full_text##, else 0.

--

-- Example 1:

--

-- s = ends("def", "abcdef")

-- -- s is 1

-- s = begins("bcd", "abcdef")

-- -- s is 0

--

--

-- See Also:

-- [[:begins]], [[:tail]]

end if

else

end if

end if

end if

else

end if

end function

--**

-- Tests to see if the ##item## is in a range of values supplied by ##range_limits##

--

-- Parameters:

-- # ##item## : The object to test for.

-- # ##range_limits## : A sequence of two or more elements. The first is assumed

-- to be the smallest value and the last is assumed to be the highest value.

-- # ##boundries##: a sequence. This determines if the range limits are inclusive

-- or not. Must be one of "[]" (the default), "[)", "(]", or

-- "()".

--

-- Returns:

-- An **integer**, 0 if ##item## is not in the ##range_limits## otherwise it returns 1.

--

-- Comments:

-- * In ##boundries###, square brackets mean //inclusive// and round brackets

-- mean //exclusive//. Thus "[]" includes both limits in the range, while

-- "()" excludes both limits. And, "[)" includes the lower limit and excludes

-- the upper limits while "(]" does the reverse.

--

-- Example 1:

--

-- if is_in_range(2, {2, 75}) then

-- procA(user_data) -- Gets run (both limits included)

-- end if

-- if is_in_range(2, {2, 75}, "(]") then

-- procA(user_data) -- Does not get run

-- end if

--

end if

case "()" then

end if

end if

case "[)" then

end if

end if

case "(]" then

end if

end if

case else

end if

end if

end switch

end function

--**

-- Tests to see if the ##item## is in a list of values supplied by ##list##

--

-- Parameters:

-- # ##item## : The object to test for.

-- # ##list## : A sequence of elements that ##item## could be a member of.

--

-- Returns:

-- An **integer**, 0 if ##item## is not in the ##list##, otherwise

-- it returns 1.

--

-- Example 1:

--

-- if is_in_list(user_data, {100, 45, 2, 75, 121}) then

-- procA(user_data)

-- end if

--

end function

--**

-- If the supplied item is in the source list, this returns the corresponding

-- element from the target list.

-- Parameters:

-- # ##find_item##: an object that might exist in ##source_list##.

-- # ##source_list##: a sequence that might contain ##pITem##.

-- # ##target_list##: a sequence from which the corresponding item will be returned.

-- # ##def_value##: an object (defaults to zero). This is returned when ##find_item##

-- is not in ##source_list## **and** ##target_list## is not longer than ##source_list##.

--

-- Returns:

-- an object

-- * If ##find_item## is found in ##source_list## then this is the corresponding element

-- from ##target_list##

-- * If ##find_item## is not in ##source_list## then if ##target_list## is longer than ##source_list##

-- then the last item in ##target_list## is returned otherwise ##def_value## is returned.

--

-- Examples:

--

-- lookup('a', "cat", "dog") --> 'o'

-- lookup('d', "cat", "dogx") --> 'x'

-- lookup('d', "cat", "dog") --> 0

-- lookup('d', "cat", "dog", -1) --> -1

-- lookup("ant", {"ant","bear","cat"}, {"spider","seal","dog","unknown"}) --> "spider"

-- lookup("dog", {"ant","bear","cat"}, {"spider","seal","dog","unknown"}) --> "unknown"

--

--

integer lPosn

else

end if

-- Return the default built into the target list

else

-- Return the supplied default

end if

end function

--**

-- If the supplied item is in a source grid column, this returns the corresponding

-- element from the target column.

-- Parameters:

-- # ##find_item##: an object that might exist in ##source_col##.

-- # ##grid_data##: a 2D grid sequence that might contain ##pITem##.

-- # ##source_col##: an integer. The column number to look for ##find_item##.

-- # ##target_col##: an integer. The column number from which the corresponding

-- item will be returned.

-- # ##def_value##: an object (defaults to zero). This is returned when ##find_item##

-- is not found in the ##source_col## column, or if found but the target column

-- does not exist.

--

-- Comments:

-- * If a row in the grid is actually a single atom, the row is ignored.

-- * If a row's length is less than the ##source_col##, the row is ignored.

--

-- Returns:

-- an object

-- * If ##find_item## is found in the ##source_col## column then this is the corresponding element

-- from the ##target_col## column.

--

-- Examples:

--

-- sequence grid

-- grid = {

-- {"ant", "spider", "mortein"},

-- {"bear", "seal", "gun"},

-- {"cat", "dog", "ranger"},

-- $

-- }

-- vlookup("ant", grid, 1, 2, "?") --> "spider"

-- vlookup("ant", grid, 1, 3, "?") --> "mortein"

-- vlookup("seal", grid, 2, 3, "?") --> "gun"

-- vlookup("seal", grid, 2, 1, "?") --> "bear"

-- vlookup("mouse", grid, 2, 3, "?") --> "?"

--

--

integer lPosn

end if

end if

end if

end if

end function