next up previous
Next: simioprocess Up: libsim Previous: libsimmath

libsimsort


     NAME
	  libsimsort - routines	for sorting and	searching

     DESCRIPTION
	  These	routines can sorting arrays of type Integer, Real,
	  LongReal, or Text.  There is also some more advanced support
	  for texts.

	  There	are also some stright forward routines for searching
	  for characters and ! strings in texts	(ScanTo, Skip, Search,
	  FindTrigger),	see libsimtexts.

     EXAMPLE
	     external real procedure Sigma2;
	     long real array A(1:1000);
	     integer N,ix;
	       N:=init;	N:=min(N,1000);
	     for ix:=1 step 1 until N do
		A(ix):=inreal;
	     SortLA(A,N);
	     Outtext( Smallest and biggest numbers:"); outimage;"
	     OutReal(A(1),5,10);OutReal(A(N),5,10);outimage;

     AUTHOR
	  Various people at QZ and FOA,	Stockholm.

     DETAILED INTERFACE
     SortIA
	     procedure SortIA (Arr,N); integer array Arr; integer N;!
	     Sort Arr(1:N). ;
	  Sort	 the   Integer	 array	 Arr   in   Ascending	 order
	  (Arr(i+1)>=Arr(i)).  N  is the size of A.  Note that you can
	  call:	SortIA(Arr, UpBound(Arr,1) ).

     SortID
	     procedure SortID (Arr,N); integer array Arr; integer N;!
	     Sort Ar(1:N). ;
	  Sort	 the   Integer	 array	 Arr   in   Descending	 order
	  (Arr(i+1)<=Arr(i)). See SortIA for details.

     SortIA
	     procedure SortRA (Arr,N);real array Arr; integer N;! Sort
	     Arr(1:N). ;
	  Sort the Real	array Arr in Ascending order. See  SortIA  for
	  details.

     SortRD
	     procedure SortRD (Arr,N);real array Arr; integer N;! Sort
	     Arr(1:N). ;
	  Sort the Real	array Arr in Descending	order. See SortIA  for
	  details.

     SortLA
	     procedure SortLA (Arr,N);long real	array Arr; integer N;!
	     Sort Arr(1:N). ;
	  Sort the Long	array Arr in Ascending order. See  SortIA  for
	  details.

     SortLD
	     procedure SortLD (Arr,N);long real	array Arr; integer N;!
	     Sort Arr(1:N). ;
	  Sort the Long	array Arr in Descending	order. See SortIA  for
	  details.

     SortTA
	     procedure SortTA (Arr,N);text array Arr; integer N;! Sort
	     Arr(1:N). ;
	  Sort the Text	array Arr in Ascending order. See  SortIA  for
	  details.

     SortTD
	     procedure SortTD (Arr,N);text array Arr; integer N;! Sort
	     Arr(1:N). ;
	  Sort the Text	array Arr in Descending	order. See SortIA  for
	  details.

     Hash
	     integer procedure Hash(T,N);
	     text T; ! String to hash, pos not used, unchanged;
	     integer N;	! Result returned is modulus N.;
	  Returns a hash coded value of	T in the interval (0:N-1).  It
	  is recommended to choose N as	a prime	number.

     Menu
	     Boolean procedure Menu(T,I,Table,N);
	     name I; integer I;	! Result index when found (or 0, -1);
	     text T;		! String to look for ;
	     text array	Table;	! Table	of valid menu commands ;
	     integer N;		! Length of the	array Table (1:N) ;
	  Identifies a command in a set	of  commands.	It  check  for
	  nonambiguous	correspondence	between	 T and an element from
	  the text array Table.	(Note that an exact match will	always
	  be  accepted,	 even  if  it  is a substring of another table
	  element.) The	table must contain  upper  case	 letters  only
	  with	no  trailing  blanks.  The  input  may have lower case
	  letters. If a	match is found Menu returns True and Index  is
	  the matching table entry.  If	no match is found Menu returns
	  False	then I will return 0.  If T is	ambiguous,  I  returns
	  -1.  Example:

	     begin text	array Menutable(1:5);
		integer	Index;	Boolean	OK;  text T;
		  Menutable(1):-    Copy(    STOP");	Menutable(2):-
	  Copy("START");"
		   Menutable(3):-    Copy(    END");	Menutable(4):-
	  Copy("ENDURE");"
		Menutable(5):- Copy( EXIT");"
		T:- <... input ...>;
		OK:= Menu(T,Index,Menutable,5);

	  OK will become True if T is equal to:
	       START,start,Sta	 (Index=2),    sto   (Index=1),	   enD
	  (Index=3),
	     endure,endu     (Index=4)
	  OK becomes False for T equal to:
	     ST,e,en	     (Index=-1),  x   (Index=0)


     Lookup
	     Boolean procedure Lookup(T,TA,Low,High,I);
	     name I;  integer I; ! The resulting index;
	     text T; ! Text-Key	to look	for;
	     text array	TA; integer Low,High; !	Sorted array
	     TA(Low:High) to look in;
	  Perform a binary search for  T  in  the  sorted  text	 array
	  TA(Low:High).

	  - If the text, T, is found in	TA Lookup  will	 return	 True,
	  and  the  matching  index  I	will  be  returned  (for which
	  TA(I)=T)

	  - If the text	is Not found Lookup will return	 False	and  I
	  will indicate	where T	should have been in TA.	 (I will be in
	  the range (Low,High-1) in case TA(I)<TFSrch
	     integer Procedure FSrch (String, SData);
	     name String;
	     text String; ! String to search;
	     text SData; ! data	as returned by a call to StSrcB/StSrcH
	     ;
	  Performs a fast search in String for a pattern.  The	result
	  is  returned	as  the	Pos in String of the first occrance of
	  the Pattern.	Before calling FSrch the pattern to search for
	  must	be  initialized	 by  a call to StSrcB (or StSrch). The
	  result (SData) is used  with	succsive  calls	 to  FSrch  to
	  search  for  the pattern in various Strings.	Results, value
	  returned by FSrch:

	  n	(n is a	non-negative integer)  A  match	 is  found,  n
	  characters   long  String.sub(String.Pos,n)  is  the	string
	  found.

	  -1	No match

	  -2	String too long.

     StSrcB
	     integer procedure StSrcB (Pattern,	SData);
	     name Sdata; ! result parameter (automatically alloacted);
	     text Pattern; ! In: Patter	specyfing what to search for.;
	     text SData;   ! Out: Intermediate result used as param to
	     FSrch. ;
	  StSrcB must be called	before FSearch can be  called.	StSrcB
	  analyzes  Pattern  (the  patern  so search for) and forms an
	  intermedate representation in	SData.

	  The  Pattern	is  in	its  simplest  form  the  sequence  of
	  characters to	search for (where upper	and lower case letters
	  match), but more complicated search crtieria can be specifed
	  with control sequences in the	following syntax:

	  ?C	Matches	any single character.

	  ?R	Matches	the beginning or end of	"string".

	  ?S	Matches	any character which is not a letter, digit  or
	  national  character.	 Also matches the beginning or the end
	  of a line.

	  ?T	Matches	one or more spaces or horizontal tabs.

	  ?D	Matches	any digit.

	  ?A	Matches	any letter or national character.

	  ?E	(=Exact), do not match upper  case  character  against
	  lower	case and vice versa.

	  ??	Representation of '?' in patterns.

	  Example I:  To find the next line beginning  with  "abcdef",
	  search for "?Rabcdef".

	  Example II:  To find the word	"man" but not when it  appears
	  as  part  of	a  longer  word	 like  "command",  search  for
	  "?Sman?S".

	  Example III:	To find	what is	probably the number of a year,
	  the  two digits 19, followed by two more digits, followed by
	  something which is neither a letter nor a digit, search  for
	  "19?D?D?S".

	  Resulting codes:

	  0    Initialization OK

	  -1	'?T' next to SPACE, HT or '?T'

	  -2	Empty pattern

	  -3	Illegal	letter after '?'

	  -4	'?R' inside pattern

	  -5	Pattern	too long

	  -6	SDATA too small.

     StSrch
	     integer procedure StSrch (Pattern,	SData);
	     name SData;   ! result parameter (automatically
	     alloacted);
	     text Pattern; ! In: Patter	specyfing what to search for.;
	     text SData;   ! Out: Intermediate result used as param to
	     FSrch. ;
	  StSrch is a variant of StSrcB	that orignally	accepted  only
	  short	 Patterns.  In	the current implementation the gain is
	  neglectable  and  StSrch  simply  calls  StsrcB.  Kept   for
	  compatibility	only.  See StSrcB for detailed documentation