generic -- GENERIC_SEARCH ( ELEMENT , INDEX , VECTOR , ">" )

-- See GENERIC_SEARCH_DEMO_*.ADA for examples of useage
--     This is a companion package to GENERIC_SORT
--     The same generic actual parameters are used to instantiate the
--     search as were used to instantiate the sort.

--     "FIND" is used when the element being searched for should be there.
--     "SEARCH" is used when the element may not be there.

  type ELEMENT is private ; -- simple objects, records or arrays
  type INDEX is ( <> ) ; -- any discrete type
  type VECTOR is array ( INDEX range <> ) of ELEMENT ; -- structure form

--              a comparison function must be provided if ELEMENT
--              is not a type or subtype for which ">" is visable.
--              Return true if the first parameter is larger than the second

  with function ">" ( LEFT , RIGHT : ELEMENT ) return BOOLEAN is <> ;

package GENERIC_SEARCH is

  FIND_ERROR : exception ; -- raised only by FIND function calls
--                            not by SEARCH procedure calls

-- order log N  FIND for sorted arrays ( binary search )

  function FIND ( KEY : ELEMENT ;         -- key being searched for
                  ARR1 : VECTOR )         -- array being searched
                  return ELEMENT ;        -- found element of array

-- a FIND for use on unsorted arrays

  function LINEAR_FIND ( KEY : ELEMENT ;         -- key being searched for
                         ARR1 : VECTOR )         -- array being searched
                         return ELEMENT ;        -- found element of array

-- order log N SEARCH for sorted arrays ( binary search )

  procedure SEARCH ( KEY : ELEMENT ;         -- key being searched for
                     ARR1 : VECTOR ;         -- array being searched
                     POSITION : out INDEX ;  -- position, subscript, where found
                     FOUND : out BOOLEAN ) ; -- TRUE if found


-- a SEARCH for use on unsorted arrays

  procedure LINEAR_SEARCH ( KEY : ELEMENT ;         -- key being searched for
                            ARR1 : VECTOR ;         -- array being searched
                            POSITION : out INDEX ;  -- position, subscript, where found
                            FOUND : out BOOLEAN ) ; -- TRUE if found

end GENERIC_SEARCH ;

package body GENERIC_SEARCH is


-- order log N  FIND for sorted arrays ( binary search )

  function FIND ( KEY : ELEMENT ;         -- key being searched for
                  ARR1 : VECTOR )         -- array being searched
                  return ELEMENT is       -- found element of array

    LOW : INDEX := ARR1'FIRST ;
    HIGH : INDEX := ARR1'LAST ;
    MID : INDEX ;
  begin
    loop
      MID := INDEX'VAL( (INDEX'POS(LOW) + INDEX'POS(HIGH) ) / 2 ) ;
      if KEY > ARR1 ( MID ) then
        LOW := INDEX'SUCC(MID) ; -- next look in upper half
      elsif ARR1 ( MID ) > KEY then
        HIGH := INDEX'PRED(MID) ; -- next look in lower half
      else
        return ARR1 ( MID ) ;
      end if ;
    end loop ;
  exception
    when CONSTRAINT_ERROR => -- because LOW goes above HIGH or visa versa
      raise FIND_ERROR ; -- not found
  end FIND ;

-- a FIND for use on unsorted arrays

  function LINEAR_FIND ( KEY : ELEMENT ;         -- key being searched for
                         ARR1 : VECTOR )         -- array being searched
                         return ELEMENT is       -- found element of array
  begin

    for I in ARR1'FIRST .. ARR1'LAST  loop
        if not ( KEY > ARR1 ( I ) ) and then
           not ( ARR1 ( I ) > KEY ) then
           return ARR1 ( I ) ;
        end if ;
    end loop ;
    raise FIND_ERROR ;
  end LINEAR_FIND ;


-- order log N SEARCH for sorted arrays ( binary search )

  procedure SEARCH ( KEY : ELEMENT ;
                     ARR1 : VECTOR ;
                     POSITION : out INDEX ;
                     FOUND : out BOOLEAN ) is

    LOW : INDEX := ARR1'FIRST ;
    HIGH : INDEX := ARR1'LAST ;
    MID : INDEX ;
  begin
    FOUND := FALSE ;
    loop
      MID := INDEX'VAL( (INDEX'POS(LOW) + INDEX'POS(HIGH) ) / 2 ) ;
      if KEY > ARR1 ( MID ) then
        LOW := INDEX'SUCC(MID) ; -- next look in upper half
      elsif ARR1 ( MID ) > KEY then
        HIGH := INDEX'PRED(MID) ; -- next look in lower half
      else
        FOUND := TRUE ;
        POSITION := MID ;
        return ;
      end if ;
    end loop ;
  exception
    when CONSTRAINT_ERROR => -- because LOW goes above HIGH or visa versa
      null ; -- return with not found
  end SEARCH ;


-- a SEARCH for use on unsorted arrays

  procedure LINEAR_SEARCH ( KEY : ELEMENT ;
                            ARR1 : VECTOR ;
                            POSITION : out INDEX ;
                            FOUND : out BOOLEAN ) is
  begin
    FOUND := FALSE ;
    for I in ARR1'FIRST .. ARR1'LAST  loop
        if not ( KEY > ARR1 ( I ) ) and then
           not ( ARR1 ( I ) > KEY ) then
          FOUND := TRUE ;
          POSITION := I ;
        end if ;
    end loop ;
  end LINEAR_SEARCH ;

end GENERIC_SEARCH ;