------------------------->  GNU Sather - sourcefile  <-------------------------
-- Copyright (C) 1995 by International Computer Science Institute            --
-- This file is part of the GNU Sather library. It is free software; you may --
-- redistribute  and/or modify it under the terms of the GNU Library General --
-- Public  License (LGPL)  as published  by the  Free  Software  Foundation; --
-- either version 2 of the license, or (at your option) any later version.   --
-- This  library  is distributed  in the  hope that it will  be  useful, but --
-- WITHOUT ANY WARRANTY without even the implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE. See Doc/LGPL for more details.       --
-- The license text is also available from:  Free Software Foundation, Inc., --
-- 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA                     --
-------------->  Please email comments to <bug-sather@gnu.org>  <--------------

-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>

class ARR_SEARCH_ALG{ETP,ATP<$ARR{ETP}} 
-- Searching algorithms on arrays.
-- Note that the element comparison is defined here bu the percondition
-- checks may use a different lt when calling  the is_sorted routine
-- in ARR_SORT_ALG
is
   include COMPARE{ETP};
   
   private is_sorted(a: ATP,l,u:INT): BOOL is
      return ARR_SORT_ALG{ETP,ATP}::is_sorted(a,l,u);
   end;
   
   binary_search(a: ATP,e: ETP): INT is 
      return binary_search(a,e,0,a.size-1);
   end;
   
   binary_search(a: ATP,e:ETP,l,u: INT):INT 
      -- Assuming self is sorted, return the index of the element
      -- preceding the first element greater than `e' according to
      -- `elt_lt' in the range [l,u].
      -- -1 if all elements are greater than `e'.
      pre check_range(a,l,u) and is_sorted(a,l,u) 
   is
      if ~elt_lt(e,a[u]) then return u end;
      if elt_lt(e,a[l]) then return -1 end;
      -- From now on [u] is always known to be greater than `e', and
      -- [l] is not greater than `e'.
      loop while!(u>l+1); j::=(u+l)/2;
	 if elt_lt(e,a[j]) then u:=j 
	 else l:=j end 
      end;
      return l 
   end;

   binary_search(a: ATP,e:ETP,lt: ROUT{ETP,ETP}:BOOL,l,u: INT):INT 
      -- Assuming self is sorted, return the index of the element
      -- preceding the first element greater than `e' according to
      -- `elt_lt' in the range [l,u].
      -- -1 if all elements are greater than `e'.
      pre check_range(a,l,u) and is_sorted(a,l,u) 
   is
      if ~elt_lt(e,a[u]) then return u end;
      if elt_lt(e,a[l]) then return -1 end;
      -- From now on [u] is always known to be greater than `e', and
      -- [l] is not greater than `e'.
      loop while!(u>l+1); j::=(u+l)/2;
	 if lt.call(e,a[j]) then u:=j 
	 else l:=j end 
      end;
      return l 
   end;

   index_of(a: ATP, e: ETP): INT is
      -- Return the index of the elemetn 'e' in 'a'
      -- Return -1 if the element is not found. Does not assume a is sorted
      i ::= 0; loop until!(i>a.size); 
	 if elt_eq(e,a[i]) then return i end;
	 i := i + 1; 
      end;
   end;


   index_if(a: ATP,test:ROUT{ETP}:BOOL):INT is
      -- Return the index of the leftmost element that satisfies `test', 
      -- or -1 if there is none. 
      loop 
	 r::=0.upto!(a.size-1);
	 if test.call(a[r]) then return r end 
      end; 
      return -1 
   end;
   
   match_subarray(a: ATP, marr:ARRAY{ETP},l,u: INT):INT 
   -- The index of the leftmost subarray of marr which matches 'a'
   -- Confine search to subrange [l,u] of a
   -- -1 if none. Uses simple algorithm which has good performance 
   -- unless the arrays are special (eg. many repeated values).
   -- Also uses ARRAY{ETP} rather than a general $ARR since it
   -- will almost certainly be worthwhile to copy into a concrete
   -- class rather than use dispatching on the argument
      pre check_range(a,l,u)
   is
      loop 
	 r::=l.upto!(u-marr.size); 
	 match::=true;
	 mind: INT := 0; 
	 msz: INT := marr.size;
	 -- Check for a match from location r to the end of 'a' or 'marr'
	 loop until!(mind >= (u-r) or mind >= msz);
	    if ~elt_eq(a[mind+r],marr[mind]) then match:=false; break! end;
	    mind := mind+1;
	 end;
	 if match=true then return r end 
      end; 
      return -1 
   end;
   
   private check_range(a: ATP,l,u: INT): BOOL is
      if void(a) then
	 #ERR+"The sort array is void!\n"; return false;
      end;
      if l.is_bet(0,a.size-1) and u.is_bet(l,a.size-1) then
	 return true;
      else 
	 #ERR+"Can't sort the specified range:["+l+","+u+"]\n";
	 #ERR+"The array is of size:"+a.size+"\n";
	 return false;
      end;
   end;


end; -- class ARR_SEARCH_ALG{ETP,ATP<$ARR{ETP}}
-------------------------------------------------------------------

