Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!caip!im4u!ut-sally!seismo!mcvax!ukc!reading!minster!idc
From: idc@minster.UUCP (idc)
Newsgroups: net.lang.pascal
Subject: Linear search again
Message-ID: <871@minster.UUCP>
Date: Wed, 6-Aug-86 06:31:00 EDT
Article-I.D.: minster.871
Posted: Wed Aug  6 06:31:00 1986
Date-Received: Sat, 9-Aug-86 05:32:57 EDT
Organization: University of York, England
Lines: 57


A small contribution to the debate re. forced termination of linear search
in Pascal.  Below is a little program in ISO level 1 Pascal that
illustrates the method.  It is not original; for example see the paper

R.G. Dromey, "Forced termination of loops", Softw.pract.exp., pp 29-40,
Vol. 15 No. 1, January 1985.

which I strongly recommend.  It has only two disadvantages over the
state indicators method: (i) The index variable cannot have the same
subrange as the indextype of the array (but that is not possible with
conformant array parameters anyway), and (ii) really the same as (i),
-maxint may not be the lower bound (in general pred(lowerbound) must be
defined.  N.B. Neither a goto nor a Boolean in sight!  Read the ref. for
full details.
Here is the example dressed up as a "find a character in a string" function.
------------

program ForcedTerminationTest(Output);




function find(ch:Char; string: packed array[lo..hi:Integer] of Char):Integer;
{
*  pre: lo > -maxint
* post: if find(ch,string) = -maxint then true else string[find(ch,string)]=ch
}
 var
	i, N: Integer;
begin
	{ -- Initialise loop variables }
	i := lo-1;  N := hi;
	{ -- Linear search with possible forced termination on hit }
	while i <> N do
	   if string[i+1]=ch then N := i else i := i+1;
	{ -- Test termination state }
	if i <> hi then find := i+1 else find := -maxint
end{ find};




begin

{ -- Test cases }
writeln(Output,
	find('!', 'Forced termination is a good thing!'):1,
	' ',
	find('?', 'There is no question mark in this string')
       )
 
end.
----------


ps. am really ian@ux.cs.man.ac.uk but am experiencing trouble posting from there.