a_search.sa

 
---------------------------> Sather 1.1 source file <--------------------------
-- search_alg.sa: 
-- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
-- Copyright (C) 1995, International Computer Science Institute
-- $Id: a_search.sa,v 1.3 1996/06/01 21:36:10 gomes Exp $
--
-- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
-- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
-- LICENSE contained in the file: Sather/Doc/License of the
-- Sather distribution. The license is also available from ICSI,
-- 1947 Center St., Suite 600, Berkeley CA 94704, USA.



class A_SEARCH{ETP,ATP<$ARR{ETP}} 
class A_SEARCH{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 A_SORT
is
   include COMPARE{ETP};
   
   private is_sorted(a: ATP,l,u:INT): BOOL is
      return A_SORT{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 A_SEARCH{ETP,ATP<$ARR{ETP}}