Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!willett!ForthNet
From: ForthNet@willett.UUCP (ForthNet articles from GEnie)
Newsgroups: comp.lang.forth
Subject: All Sorts of Sorts
Message-ID: <426.UUL1.3#5129@willett.UUCP>
Date: 9 Feb 90 00:41:48 GMT
Organization: Latest link in the ForthNet chain.  (Pgh, PA)
Lines: 98


 Date: 02-07-90 (17:50)              Number: 2870 (Echo)
   To: ALL                           Refer#: NONE
 From: ZAFAR ESSAK                     Read: (N/A)
 Subj: LEARN TO SORT                 Status: PUBLIC MESSAGE

 \ SORTS.FLY     Part 1 - Generalizing the Sort Function 

 (( 
 For a sort utility to have flexibility some words have deferred 
 actions.  Essentially, when sorting a collection of data elements, 
 two elements are compared at a time.  Depending on the results of the 
 comparison the placement of two elements in the data collection may 
 require that they be exchanged. 

 The comparison test itself may need to be modified to suit the data 
 elements.  Also the exchange routine will need to be modified for the 
 particular data collection. 

 The following assumes the data elements are fixed length and uses the 
 space at PAD when comparing and exchanging elements. 

 )) 

 ONLY FORTH ALSO DEFINITIONS   DECIMAL 

 VARIABLE DATA.MAX# ( --adr)     \ maximum number of data elements 

 VARIABLE DATA.WIDTH ( --adr)    \ width of each data element 

 VARIABLE ~DATA@ ( --adr)        \ Vector for method to fetch data 

 : DATA@ ( adr,i--) ~DATA@ @EXECUTE ; 

 VARIABLE ~DATA! ( --adr)        \ Vector for method to store data 

 : DATA! ( adr,i--) ~DATA! @EXECUTE ; 

 (( 
 The following word uses PAD as the buffer and accesses different 
 parts of the buffer for temporary storage of different data elements. 

 )) 

 : data.buf ( n--adr) DATA.WIDTH @ * PAD + ; 

 : EXCHANGE ( n1,n2--)   \ n1,n2 are indexes to the data elements 
     2DUP >R >R >R >R 
     1 data.buf  R> DATA@    2 data.buf  R> DATA@ 
     2 data.buf  R> DATA!    1 data.buf  R> DATA! ; 

 (( 
 In the following comparison of data elements the flag returned shall 
 be -1, 0, or 1 to indicate if the data at adr1 is less than, equal 
 to, or greater than the data at adr2, respectively. 

 )) 

 VARIABLE ~SORT? ( --adr)        \ Vector action for comparison test 

 : SORT? ( adr1,adr2--?) ~SORT? @EXECUTE ; 

 (( 
 Various SORT algorhythms require the following variables be set by 
 any applications that call the sort. 

             DATA.MAX# 
             DATA.WIDTH 
             ~DATA@ 
             ~DATA! 
             ~SORT? 

 )) 

 \ The following is a sort of an array of 2 byte data elements 

 VARIABLE startdata ( --adr) 

 : CELL@ ( adr,i--) 2* startdata @ + @ SWAP ! ; 

 : CELL! ( adr,i--) >R @ R> 2* startdata @ + ! ; 

 : CELL.COMPARE ( adr1,adr2--?) SWAP @ SWAP @ - ; 

 : CELL.SORT ( --) 
     2 DATA.WIDTH ! 
     ['] CELL@        ~DATA@ ! 
     ['] CELL!        ~DATA! ! 
     ['] CELL.COMPARE ~SORT? ! ; 

                                                       Part 2... 
 ---
  * Via Qwikmail 2.01

 NET/Mail : British Columbia Forth Board - Burnaby BC - (604)434-5886   
-----
This message came from GEnie via willett through a semi-automated process.
Report problems to: 'uunet!willett!dwp' or 'willett!dwp@gateway.sei.cmu.edu'