Home » Archimedes archive » Archimedes World » AW-1995-01-Disc2.adf » Disk2Jan95 » !AWJan95/Goodies/Event/Docs/Misc
!AWJan95/Goodies/Event/Docs/Misc
This website contains an archive of files for the Acorn Electron, BBC Micro, Acorn Archimedes, Commodore 16 and Commodore 64 computers, which Dominic Ford has rescued from his private collection of floppy disks and cassettes.
Some of these files were originally commercial releases in the 1980s and 1990s, but they are now widely available online. I assume that copyright over them is no longer being asserted. If you own the copyright and would like files to be removed, please contact me.
| Tape/disk: | Home » Archimedes archive » Archimedes World » AW-1995-01-Disc2.adf » Disk2Jan95 |
| Filename: | !AWJan95/Goodies/Event/Docs/Misc |
| Read OK: | ✔ |
| File size: | 1239 bytes |
| Load address: | 0000 |
| Exec address: | 0000 |
File contents
PROCshell_QuickSort()
Params =>
str comparison function
str swap function
bool ascending flag, non 0 for ascending
sort, 0 for descending sort
int minimum element number to sort
int maximum element number to sort
The QuickSort routine uses a fast sorting technique
which is capable of sorting any type of data. An
example of the speed is that 1000 random integers
can be sorted in around 15 seconds on an ARM3
machine.
Comparision FN (QuickSort)
Params =>
int first element nr
int second element nr
<=
bool TRUE if value of first element
is less than the second,
otherwise FALSE
This function returns TRUE or FALSE depending
on the outcome of the comparison. Exactly what
is compared is up to you!
The function name must start with a '_'
character if the program is to be compressed.
Swap FN (QuickSort)
Params =>
int first element nr
int second element nr
<=
int junk (ignore)
This function swaps element 1 with element
2.
The function name must start with a '_'
character if the program is to be compressed.
Example code (QuickSort)
Assume a 100 element string array name$(), each element
containing a list of names which must be sorted into
alphabetic order. This can be achieved with:
REM Rest of code....
PROCshell_QuickSort("_QS_comp","_QS_swap",1,0,100)
REM More code..
DEF FN_QS_comp(el1%,el2%)
IF VAL(name$(el1%)) < VAL(name$(el2%)) THEN = TRUE ELSE = FALSE
:
DEF FN_QS_swap(el1%,el2%)
LOCAL temp$
temp$ = name$(el1%)
name$(el1%) = name$(el2%)
name$(el2%) = temp$
=0
The complexity of FN_QS_comp and FN_QS_swap is completely up to
you (wildcards could be allowed for example). By this means any
set of data can be sorted.
--------------------------------------------------------
FNshell_BinarySearch()
Params =>
str search term
str get term function
str comparison function
int minimum element number
int maximum element number
<=
int element number of first match
found (first element is 1) or
-1 if match not found
The Binary Search technique is a powerful way of
quickly searching a set of sorted data. The way in
which it has been implemented for EvntShell makes
it even more useful in that any set of data can be
searched by the same routine.
The key to this are the two routines called during
the search to get an element of data and to compare
one element to another.
Search term (BinarySearch)
The search term is the string which will be searched
for during the binary search. Note that a string must
be passed to the search routine, numbers must be
converted first using STR$.
Get Term FN (BinarySearch)
Params =>
int element number to fetch
<=
str value of element number
This function returns a string representing
the value of the specified element.
The function name must start with a '_'
character if the program is to be compressed.
Comparision FN (BinarySearch)
Params =>
str term 1
str term 2
<=
bool TRUE if term 1 is less than
term 2, otherwise FALSE
This function returns TRUE or FALSE depending
on the outcome of the comparison. Exactly what
is compared is up to you!
The function name must start with a '_'
character if the program is to be compressed.
The Binary Search Technique
Given a set of sorted data, a check is first made halfway
through the list. If the searched for data is 'greater than'
this value then the next check is made half way between the
first point and the end of the list, otherwise the next check
is made half way between the first check and the start of the
list.
This continues (eliminating half the remaining data with each
check) until the data is found, or the list can contain no
more matches.
By this means very large amounts of data can be searched very
quickly indeed.
Example code (BinarySearch)
Assume a 100 element string array array$(), each element
containing a list of names sorted into alphabetic order.
The search can be carried out with:
result%=FNshell_BinarySearch("Fred","_GetTerm","_Comp",0,99)
REM rest of code....
DEF FN_GetTerm(nr%)
=array$(nr%)
:
DEF FN_Comp(term1$,term2$)
IF term1$ < term2$ THEN = TRUE ELSE =FALSE
result% contains -1 if 'Fred' is not present in array$, or
the element number if it is. The complexity of FN_GetTerm
and FN_Comp is completely up to you (wildcards could be
allowed for example). By this means any set of sorted data
can be searched - simply define the 'get term' and 'comparision'
functions to suit. 00000000 50 52 4f 43 73 68 65 6c 6c 5f 51 75 69 63 6b 53 |PROCshell_QuickS|
00000010 6f 72 74 28 29 0a 50 61 72 61 6d 73 20 3d 3e 0a |ort().Params =>.|
00000020 20 20 20 20 20 20 20 20 20 73 74 72 20 63 6f 6d | str com|
00000030 70 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e |parison function|
00000040 0a 20 20 20 20 20 20 20 20 20 73 74 72 20 73 77 |. str sw|
00000050 61 70 20 66 75 6e 63 74 69 6f 6e 0a 20 20 20 20 |ap function. |
00000060 20 20 20 20 20 62 6f 6f 6c 20 61 73 63 65 6e 64 | bool ascend|
00000070 69 6e 67 20 66 6c 61 67 2c 20 6e 6f 6e 20 30 20 |ing flag, non 0 |
00000080 66 6f 72 20 61 73 63 65 6e 64 69 6e 67 0a 20 20 |for ascending. |
00000090 20 20 20 20 20 20 20 20 20 20 20 20 73 6f 72 74 | sort|
000000a0 2c 20 30 20 66 6f 72 20 64 65 73 63 65 6e 64 69 |, 0 for descendi|
000000b0 6e 67 20 73 6f 72 74 0a 20 20 20 20 20 20 20 20 |ng sort. |
000000c0 20 69 6e 74 20 6d 69 6e 69 6d 75 6d 20 65 6c 65 | int minimum ele|
000000d0 6d 65 6e 74 20 6e 75 6d 62 65 72 20 74 6f 20 73 |ment number to s|
000000e0 6f 72 74 0a 20 20 20 20 20 20 20 20 20 69 6e 74 |ort. int|
000000f0 20 6d 61 78 69 6d 75 6d 20 65 6c 65 6d 65 6e 74 | maximum element|
00000100 20 6e 75 6d 62 65 72 20 74 6f 20 73 6f 72 74 0a | number to sort.|
00000110 0a 54 68 65 20 51 75 69 63 6b 53 6f 72 74 20 72 |.The QuickSort r|
00000120 6f 75 74 69 6e 65 20 75 73 65 73 20 61 20 66 61 |outine uses a fa|
00000130 73 74 20 73 6f 72 74 69 6e 67 20 74 65 63 68 6e |st sorting techn|
00000140 69 71 75 65 0a 77 68 69 63 68 20 69 73 20 63 61 |ique.which is ca|
00000150 70 61 62 6c 65 20 6f 66 20 73 6f 72 74 69 6e 67 |pable of sorting|
00000160 20 61 6e 79 20 74 79 70 65 20 6f 66 20 64 61 74 | any type of dat|
00000170 61 2e 20 41 6e 0a 65 78 61 6d 70 6c 65 20 6f 66 |a. An.example of|
00000180 20 74 68 65 20 73 70 65 65 64 20 69 73 20 74 68 | the speed is th|
00000190 61 74 20 31 30 30 30 20 72 61 6e 64 6f 6d 20 69 |at 1000 random i|
000001a0 6e 74 65 67 65 72 73 0a 63 61 6e 20 62 65 20 73 |ntegers.can be s|
000001b0 6f 72 74 65 64 20 69 6e 20 61 72 6f 75 6e 64 20 |orted in around |
000001c0 31 35 20 73 65 63 6f 6e 64 73 20 6f 6e 20 61 6e |15 seconds on an|
000001d0 20 41 52 4d 33 0a 6d 61 63 68 69 6e 65 2e 0a 0a | ARM3.machine...|
000001e0 43 6f 6d 70 61 72 69 73 69 6f 6e 20 46 4e 20 28 |Comparision FN (|
000001f0 51 75 69 63 6b 53 6f 72 74 29 0a 50 61 72 61 6d |QuickSort).Param|
00000200 73 20 3d 3e 0a 20 20 20 20 20 20 20 20 20 69 6e |s =>. in|
00000210 74 20 66 69 72 73 74 20 20 65 6c 65 6d 65 6e 74 |t first element|
00000220 20 6e 72 0a 20 20 20 20 20 20 20 20 20 69 6e 74 | nr. int|
00000230 20 73 65 63 6f 6e 64 20 65 6c 65 6d 65 6e 74 20 | second element |
00000240 6e 72 0a 0a 20 20 20 20 20 20 20 3c 3d 0a 20 20 |nr.. <=. |
00000250 20 20 20 20 20 20 20 62 6f 6f 6c 20 54 52 55 45 | bool TRUE|
00000260 20 69 66 20 76 61 6c 75 65 20 6f 66 20 66 69 72 | if value of fir|
00000270 73 74 20 65 6c 65 6d 65 6e 74 0a 20 20 20 20 20 |st element. |
00000280 20 20 20 20 20 20 20 20 20 69 73 20 6c 65 73 73 | is less|
00000290 20 74 68 61 6e 20 74 68 65 20 73 65 63 6f 6e 64 | than the second|
000002a0 2c 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 |,. |
000002b0 6f 74 68 65 72 77 69 73 65 20 46 41 4c 53 45 0a |otherwise FALSE.|
000002c0 0a 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 72 |.This function r|
000002d0 65 74 75 72 6e 73 20 54 52 55 45 20 6f 72 20 46 |eturns TRUE or F|
000002e0 41 4c 53 45 20 64 65 70 65 6e 64 69 6e 67 0a 6f |ALSE depending.o|
000002f0 6e 20 74 68 65 20 6f 75 74 63 6f 6d 65 20 6f 66 |n the outcome of|
00000300 20 74 68 65 20 63 6f 6d 70 61 72 69 73 6f 6e 2e | the comparison.|
00000310 20 45 78 61 63 74 6c 79 20 77 68 61 74 0a 69 73 | Exactly what.is|
00000320 20 63 6f 6d 70 61 72 65 64 20 69 73 20 75 70 20 | compared is up |
00000330 74 6f 20 79 6f 75 21 0a 0a 54 68 65 20 66 75 6e |to you!..The fun|
00000340 63 74 69 6f 6e 20 6e 61 6d 65 20 6d 75 73 74 20 |ction name must |
00000350 73 74 61 72 74 20 77 69 74 68 20 61 20 27 5f 27 |start with a '_'|
00000360 0a 63 68 61 72 61 63 74 65 72 20 69 66 20 74 68 |.character if th|
00000370 65 20 70 72 6f 67 72 61 6d 20 69 73 20 74 6f 20 |e program is to |
00000380 62 65 20 63 6f 6d 70 72 65 73 73 65 64 2e 0a 0a |be compressed...|
00000390 53 77 61 70 20 46 4e 20 28 51 75 69 63 6b 53 6f |Swap FN (QuickSo|
000003a0 72 74 29 0a 50 61 72 61 6d 73 20 3d 3e 0a 20 20 |rt).Params =>. |
000003b0 20 20 20 20 20 20 20 69 6e 74 20 66 69 72 73 74 | int first|
000003c0 20 20 65 6c 65 6d 65 6e 74 20 6e 72 0a 20 20 20 | element nr. |
000003d0 20 20 20 20 20 20 69 6e 74 20 73 65 63 6f 6e 64 | int second|
000003e0 20 65 6c 65 6d 65 6e 74 20 6e 72 0a 0a 20 20 20 | element nr.. |
000003f0 20 20 20 20 3c 3d 0a 20 20 20 20 20 20 20 20 20 | <=. |
00000400 69 6e 74 20 6a 75 6e 6b 20 28 69 67 6e 6f 72 65 |int junk (ignore|
00000410 29 0a 0a 54 68 69 73 20 66 75 6e 63 74 69 6f 6e |)..This function|
00000420 20 73 77 61 70 73 20 65 6c 65 6d 65 6e 74 20 31 | swaps element 1|
00000430 20 77 69 74 68 20 65 6c 65 6d 65 6e 74 0a 32 2e | with element.2.|
00000440 0a 0a 54 68 65 20 66 75 6e 63 74 69 6f 6e 20 6e |..The function n|
00000450 61 6d 65 20 6d 75 73 74 20 73 74 61 72 74 20 77 |ame must start w|
00000460 69 74 68 20 61 20 27 5f 27 0a 63 68 61 72 61 63 |ith a '_'.charac|
00000470 74 65 72 20 69 66 20 74 68 65 20 70 72 6f 67 72 |ter if the progr|
00000480 61 6d 20 69 73 20 74 6f 20 62 65 20 63 6f 6d 70 |am is to be comp|
00000490 72 65 73 73 65 64 2e 0a 0a 45 78 61 6d 70 6c 65 |ressed...Example|
000004a0 20 63 6f 64 65 20 28 51 75 69 63 6b 53 6f 72 74 | code (QuickSort|
000004b0 29 0a 41 73 73 75 6d 65 20 61 20 31 30 30 20 65 |).Assume a 100 e|
000004c0 6c 65 6d 65 6e 74 20 73 74 72 69 6e 67 20 61 72 |lement string ar|
000004d0 72 61 79 20 6e 61 6d 65 24 28 29 2c 20 65 61 63 |ray name$(), eac|
000004e0 68 20 65 6c 65 6d 65 6e 74 0a 63 6f 6e 74 61 69 |h element.contai|
000004f0 6e 69 6e 67 20 61 20 6c 69 73 74 20 6f 66 20 6e |ning a list of n|
00000500 61 6d 65 73 20 77 68 69 63 68 20 6d 75 73 74 20 |ames which must |
00000510 62 65 20 73 6f 72 74 65 64 20 69 6e 74 6f 0a 61 |be sorted into.a|
00000520 6c 70 68 61 62 65 74 69 63 20 6f 72 64 65 72 2e |lphabetic order.|
00000530 20 54 68 69 73 20 63 61 6e 20 62 65 20 61 63 68 | This can be ach|
00000540 69 65 76 65 64 20 77 69 74 68 3a 0a 0a 52 45 4d |ieved with:..REM|
00000550 20 52 65 73 74 20 6f 66 20 63 6f 64 65 2e 2e 2e | Rest of code...|
00000560 2e 0a 50 52 4f 43 73 68 65 6c 6c 5f 51 75 69 63 |..PROCshell_Quic|
00000570 6b 53 6f 72 74 28 22 5f 51 53 5f 63 6f 6d 70 22 |kSort("_QS_comp"|
00000580 2c 22 5f 51 53 5f 73 77 61 70 22 2c 31 2c 30 2c |,"_QS_swap",1,0,|
00000590 31 30 30 29 0a 52 45 4d 20 4d 6f 72 65 20 63 6f |100).REM More co|
000005a0 64 65 2e 2e 0a 0a 44 45 46 20 46 4e 5f 51 53 5f |de....DEF FN_QS_|
000005b0 63 6f 6d 70 28 65 6c 31 25 2c 65 6c 32 25 29 0a |comp(el1%,el2%).|
000005c0 49 46 20 56 41 4c 28 6e 61 6d 65 24 28 65 6c 31 |IF VAL(name$(el1|
000005d0 25 29 29 20 3c 20 56 41 4c 28 6e 61 6d 65 24 28 |%)) < VAL(name$(|
000005e0 65 6c 32 25 29 29 20 54 48 45 4e 20 3d 20 54 52 |el2%)) THEN = TR|
000005f0 55 45 20 45 4c 53 45 20 3d 20 46 41 4c 53 45 0a |UE ELSE = FALSE.|
00000600 3a 0a 44 45 46 20 46 4e 5f 51 53 5f 73 77 61 70 |:.DEF FN_QS_swap|
00000610 28 65 6c 31 25 2c 65 6c 32 25 29 0a 4c 4f 43 41 |(el1%,el2%).LOCA|
00000620 4c 20 74 65 6d 70 24 0a 74 65 6d 70 24 20 3d 20 |L temp$.temp$ = |
00000630 6e 61 6d 65 24 28 65 6c 31 25 29 0a 6e 61 6d 65 |name$(el1%).name|
00000640 24 28 65 6c 31 25 29 20 3d 20 6e 61 6d 65 24 28 |$(el1%) = name$(|
00000650 65 6c 32 25 29 0a 6e 61 6d 65 24 28 65 6c 32 25 |el2%).name$(el2%|
00000660 29 20 3d 20 74 65 6d 70 24 0a 3d 30 0a 0a 54 68 |) = temp$.=0..Th|
00000670 65 20 63 6f 6d 70 6c 65 78 69 74 79 20 6f 66 20 |e complexity of |
00000680 46 4e 5f 51 53 5f 63 6f 6d 70 20 61 6e 64 20 46 |FN_QS_comp and F|
00000690 4e 5f 51 53 5f 73 77 61 70 20 69 73 20 63 6f 6d |N_QS_swap is com|
000006a0 70 6c 65 74 65 6c 79 20 75 70 20 74 6f 0a 79 6f |pletely up to.yo|
000006b0 75 20 28 77 69 6c 64 63 61 72 64 73 20 63 6f 75 |u (wildcards cou|
000006c0 6c 64 20 62 65 20 61 6c 6c 6f 77 65 64 20 66 6f |ld be allowed fo|
000006d0 72 20 65 78 61 6d 70 6c 65 29 2e 20 42 79 20 74 |r example). By t|
000006e0 68 69 73 20 6d 65 61 6e 73 20 61 6e 79 0a 73 65 |his means any.se|
000006f0 74 20 6f 66 20 64 61 74 61 20 63 61 6e 20 62 65 |t of data can be|
00000700 20 73 6f 72 74 65 64 2e 0a 0a 2d 2d 2d 2d 2d 2d | sorted...------|
00000710 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d |----------------|
*
00000740 2d 2d 0a 0a 46 4e 73 68 65 6c 6c 5f 42 69 6e 61 |--..FNshell_Bina|
00000750 72 79 53 65 61 72 63 68 28 29 0a 50 61 72 61 6d |rySearch().Param|
00000760 73 20 3d 3e 0a 20 20 20 20 20 20 20 20 20 73 74 |s =>. st|
00000770 72 20 73 65 61 72 63 68 20 74 65 72 6d 0a 20 20 |r search term. |
00000780 20 20 20 20 20 20 20 73 74 72 20 67 65 74 20 74 | str get t|
00000790 65 72 6d 20 66 75 6e 63 74 69 6f 6e 0a 20 20 20 |erm function. |
000007a0 20 20 20 20 20 20 73 74 72 20 63 6f 6d 70 61 72 | str compar|
000007b0 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 0a 20 20 |ison function. |
000007c0 20 20 20 20 20 20 20 69 6e 74 20 6d 69 6e 69 6d | int minim|
000007d0 75 6d 20 65 6c 65 6d 65 6e 74 20 6e 75 6d 62 65 |um element numbe|
000007e0 72 0a 20 20 20 20 20 20 20 20 20 69 6e 74 20 6d |r. int m|
000007f0 61 78 69 6d 75 6d 20 65 6c 65 6d 65 6e 74 20 6e |aximum element n|
00000800 75 6d 62 65 72 0a 0a 20 20 20 20 20 20 20 3c 3d |umber.. <=|
00000810 0a 20 20 20 20 20 20 20 20 20 69 6e 74 20 65 6c |. int el|
00000820 65 6d 65 6e 74 20 6e 75 6d 62 65 72 20 6f 66 20 |ement number of |
00000830 66 69 72 73 74 20 6d 61 74 63 68 0a 20 20 20 20 |first match. |
00000840 20 20 20 20 20 20 20 20 20 66 6f 75 6e 64 20 28 | found (|
00000850 66 69 72 73 74 20 65 6c 65 6d 65 6e 74 20 69 73 |first element is|
00000860 20 31 29 20 6f 72 0a 20 20 20 20 20 20 20 20 20 | 1) or. |
00000870 20 20 20 20 2d 31 20 69 66 20 6d 61 74 63 68 20 | -1 if match |
00000880 6e 6f 74 20 66 6f 75 6e 64 0a 0a 54 68 65 20 42 |not found..The B|
00000890 69 6e 61 72 79 20 53 65 61 72 63 68 20 74 65 63 |inary Search tec|
000008a0 68 6e 69 71 75 65 20 69 73 20 61 20 70 6f 77 65 |hnique is a powe|
000008b0 72 66 75 6c 20 77 61 79 20 6f 66 0a 71 75 69 63 |rful way of.quic|
000008c0 6b 6c 79 20 73 65 61 72 63 68 69 6e 67 20 61 20 |kly searching a |
000008d0 73 65 74 20 6f 66 20 73 6f 72 74 65 64 20 64 61 |set of sorted da|
000008e0 74 61 2e 20 54 68 65 20 77 61 79 20 69 6e 0a 77 |ta. The way in.w|
000008f0 68 69 63 68 20 69 74 20 68 61 73 20 62 65 65 6e |hich it has been|
00000900 20 69 6d 70 6c 65 6d 65 6e 74 65 64 20 66 6f 72 | implemented for|
00000910 20 45 76 6e 74 53 68 65 6c 6c 20 6d 61 6b 65 73 | EvntShell makes|
00000920 0a 69 74 20 65 76 65 6e 20 6d 6f 72 65 20 75 73 |.it even more us|
00000930 65 66 75 6c 20 69 6e 20 74 68 61 74 20 61 6e 79 |eful in that any|
00000940 20 73 65 74 20 6f 66 20 64 61 74 61 20 63 61 6e | set of data can|
00000950 20 62 65 0a 73 65 61 72 63 68 65 64 20 62 79 20 | be.searched by |
00000960 74 68 65 20 73 61 6d 65 20 72 6f 75 74 69 6e 65 |the same routine|
00000970 2e 0a 0a 54 68 65 20 6b 65 79 20 74 6f 20 74 68 |...The key to th|
00000980 69 73 20 61 72 65 20 74 68 65 20 74 77 6f 20 72 |is are the two r|
00000990 6f 75 74 69 6e 65 73 20 63 61 6c 6c 65 64 20 64 |outines called d|
000009a0 75 72 69 6e 67 0a 74 68 65 20 73 65 61 72 63 68 |uring.the search|
000009b0 20 74 6f 20 67 65 74 20 61 6e 20 65 6c 65 6d 65 | to get an eleme|
000009c0 6e 74 20 6f 66 20 64 61 74 61 20 61 6e 64 20 74 |nt of data and t|
000009d0 6f 20 63 6f 6d 70 61 72 65 0a 6f 6e 65 20 65 6c |o compare.one el|
000009e0 65 6d 65 6e 74 20 74 6f 20 61 6e 6f 74 68 65 72 |ement to another|
000009f0 2e 0a 0a 53 65 61 72 63 68 20 74 65 72 6d 20 28 |...Search term (|
00000a00 42 69 6e 61 72 79 53 65 61 72 63 68 29 0a 54 68 |BinarySearch).Th|
00000a10 65 20 73 65 61 72 63 68 20 74 65 72 6d 20 69 73 |e search term is|
00000a20 20 74 68 65 20 73 74 72 69 6e 67 20 77 68 69 63 | the string whic|
00000a30 68 20 77 69 6c 6c 20 62 65 20 73 65 61 72 63 68 |h will be search|
00000a40 65 64 0a 66 6f 72 20 64 75 72 69 6e 67 20 74 68 |ed.for during th|
00000a50 65 20 62 69 6e 61 72 79 20 73 65 61 72 63 68 2e |e binary search.|
00000a60 20 4e 6f 74 65 20 74 68 61 74 20 61 20 73 74 72 | Note that a str|
00000a70 69 6e 67 20 6d 75 73 74 0a 62 65 20 70 61 73 73 |ing must.be pass|
00000a80 65 64 20 74 6f 20 74 68 65 20 73 65 61 72 63 68 |ed to the search|
00000a90 20 72 6f 75 74 69 6e 65 2c 20 6e 75 6d 62 65 72 | routine, number|
00000aa0 73 20 6d 75 73 74 20 62 65 0a 63 6f 6e 76 65 72 |s must be.conver|
00000ab0 74 65 64 20 66 69 72 73 74 20 75 73 69 6e 67 20 |ted first using |
00000ac0 53 54 52 24 2e 0a 0a 47 65 74 20 54 65 72 6d 20 |STR$...Get Term |
00000ad0 46 4e 20 28 42 69 6e 61 72 79 53 65 61 72 63 68 |FN (BinarySearch|
00000ae0 29 0a 50 61 72 61 6d 73 20 3d 3e 0a 20 20 20 20 |).Params =>. |
00000af0 20 20 20 20 20 69 6e 74 20 65 6c 65 6d 65 6e 74 | int element|
00000b00 20 6e 75 6d 62 65 72 20 74 6f 20 66 65 74 63 68 | number to fetch|
00000b10 0a 0a 20 20 20 20 20 20 20 3c 3d 0a 20 20 20 20 |.. <=. |
00000b20 20 20 20 20 20 73 74 72 20 76 61 6c 75 65 20 6f | str value o|
00000b30 66 20 65 6c 65 6d 65 6e 74 20 6e 75 6d 62 65 72 |f element number|
00000b40 0a 0a 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 |..This function |
00000b50 72 65 74 75 72 6e 73 20 61 20 73 74 72 69 6e 67 |returns a string|
00000b60 20 72 65 70 72 65 73 65 6e 74 69 6e 67 0a 74 68 | representing.th|
00000b70 65 20 76 61 6c 75 65 20 6f 66 20 74 68 65 20 73 |e value of the s|
00000b80 70 65 63 69 66 69 65 64 20 65 6c 65 6d 65 6e 74 |pecified element|
00000b90 2e 0a 0a 54 68 65 20 66 75 6e 63 74 69 6f 6e 20 |...The function |
00000ba0 6e 61 6d 65 20 6d 75 73 74 20 73 74 61 72 74 20 |name must start |
00000bb0 77 69 74 68 20 61 20 27 5f 27 0a 63 68 61 72 61 |with a '_'.chara|
00000bc0 63 74 65 72 20 69 66 20 74 68 65 20 70 72 6f 67 |cter if the prog|
00000bd0 72 61 6d 20 69 73 20 74 6f 20 62 65 20 63 6f 6d |ram is to be com|
00000be0 70 72 65 73 73 65 64 2e 0a 0a 43 6f 6d 70 61 72 |pressed...Compar|
00000bf0 69 73 69 6f 6e 20 46 4e 20 28 42 69 6e 61 72 79 |ision FN (Binary|
00000c00 53 65 61 72 63 68 29 0a 50 61 72 61 6d 73 20 3d |Search).Params =|
00000c10 3e 0a 20 20 20 20 20 20 20 20 20 73 74 72 20 74 |>. str t|
00000c20 65 72 6d 20 31 0a 20 20 20 20 20 20 20 20 20 73 |erm 1. s|
00000c30 74 72 20 74 65 72 6d 20 32 0a 0a 20 20 20 20 20 |tr term 2.. |
00000c40 20 20 3c 3d 0a 20 20 20 20 20 20 20 20 20 62 6f | <=. bo|
00000c50 6f 6c 20 54 52 55 45 20 69 66 20 74 65 72 6d 20 |ol TRUE if term |
00000c60 31 20 69 73 20 6c 65 73 73 20 74 68 61 6e 0a 20 |1 is less than. |
00000c70 20 20 20 20 20 20 20 20 20 20 20 20 20 74 65 72 | ter|
00000c80 6d 20 32 2c 20 6f 74 68 65 72 77 69 73 65 20 46 |m 2, otherwise F|
00000c90 41 4c 53 45 0a 0a 54 68 69 73 20 66 75 6e 63 74 |ALSE..This funct|
00000ca0 69 6f 6e 20 72 65 74 75 72 6e 73 20 54 52 55 45 |ion returns TRUE|
00000cb0 20 6f 72 20 46 41 4c 53 45 20 64 65 70 65 6e 64 | or FALSE depend|
00000cc0 69 6e 67 0a 6f 6e 20 74 68 65 20 6f 75 74 63 6f |ing.on the outco|
00000cd0 6d 65 20 6f 66 20 74 68 65 20 63 6f 6d 70 61 72 |me of the compar|
00000ce0 69 73 6f 6e 2e 20 45 78 61 63 74 6c 79 20 77 68 |ison. Exactly wh|
00000cf0 61 74 0a 69 73 20 63 6f 6d 70 61 72 65 64 20 69 |at.is compared i|
00000d00 73 20 75 70 20 74 6f 20 79 6f 75 21 0a 0a 54 68 |s up to you!..Th|
00000d10 65 20 66 75 6e 63 74 69 6f 6e 20 6e 61 6d 65 20 |e function name |
00000d20 6d 75 73 74 20 73 74 61 72 74 20 77 69 74 68 20 |must start with |
00000d30 61 20 27 5f 27 0a 63 68 61 72 61 63 74 65 72 20 |a '_'.character |
00000d40 69 66 20 74 68 65 20 70 72 6f 67 72 61 6d 20 69 |if the program i|
00000d50 73 20 74 6f 20 62 65 20 63 6f 6d 70 72 65 73 73 |s to be compress|
00000d60 65 64 2e 0a 0a 54 68 65 20 42 69 6e 61 72 79 20 |ed...The Binary |
00000d70 53 65 61 72 63 68 20 54 65 63 68 6e 69 71 75 65 |Search Technique|
00000d80 0a 47 69 76 65 6e 20 61 20 73 65 74 20 6f 66 20 |.Given a set of |
00000d90 73 6f 72 74 65 64 20 64 61 74 61 2c 20 61 20 63 |sorted data, a c|
00000da0 68 65 63 6b 20 69 73 20 66 69 72 73 74 20 6d 61 |heck is first ma|
00000db0 64 65 20 68 61 6c 66 77 61 79 0a 74 68 72 6f 75 |de halfway.throu|
00000dc0 67 68 20 74 68 65 20 6c 69 73 74 2e 20 49 66 20 |gh the list. If |
00000dd0 74 68 65 20 73 65 61 72 63 68 65 64 20 66 6f 72 |the searched for|
00000de0 20 64 61 74 61 20 69 73 20 27 67 72 65 61 74 65 | data is 'greate|
00000df0 72 20 74 68 61 6e 27 0a 74 68 69 73 20 76 61 6c |r than'.this val|
00000e00 75 65 20 74 68 65 6e 20 74 68 65 20 6e 65 78 74 |ue then the next|
00000e10 20 63 68 65 63 6b 20 69 73 20 6d 61 64 65 20 68 | check is made h|
00000e20 61 6c 66 20 77 61 79 20 62 65 74 77 65 65 6e 20 |alf way between |
00000e30 74 68 65 0a 66 69 72 73 74 20 70 6f 69 6e 74 20 |the.first point |
00000e40 61 6e 64 20 74 68 65 20 65 6e 64 20 6f 66 20 74 |and the end of t|
00000e50 68 65 20 6c 69 73 74 2c 20 6f 74 68 65 72 77 69 |he list, otherwi|
00000e60 73 65 20 74 68 65 20 6e 65 78 74 20 63 68 65 63 |se the next chec|
00000e70 6b 0a 69 73 20 6d 61 64 65 20 68 61 6c 66 20 77 |k.is made half w|
00000e80 61 79 20 62 65 74 77 65 65 6e 20 74 68 65 20 66 |ay between the f|
00000e90 69 72 73 74 20 63 68 65 63 6b 20 61 6e 64 20 74 |irst check and t|
00000ea0 68 65 20 73 74 61 72 74 20 6f 66 20 74 68 65 0a |he start of the.|
00000eb0 6c 69 73 74 2e 0a 0a 54 68 69 73 20 63 6f 6e 74 |list...This cont|
00000ec0 69 6e 75 65 73 20 28 65 6c 69 6d 69 6e 61 74 69 |inues (eliminati|
00000ed0 6e 67 20 68 61 6c 66 20 74 68 65 20 72 65 6d 61 |ng half the rema|
00000ee0 69 6e 69 6e 67 20 64 61 74 61 20 77 69 74 68 20 |ining data with |
00000ef0 65 61 63 68 0a 63 68 65 63 6b 29 20 75 6e 74 69 |each.check) unti|
00000f00 6c 20 74 68 65 20 64 61 74 61 20 69 73 20 66 6f |l the data is fo|
00000f10 75 6e 64 2c 20 6f 72 20 74 68 65 20 6c 69 73 74 |und, or the list|
00000f20 20 63 61 6e 20 63 6f 6e 74 61 69 6e 20 6e 6f 0a | can contain no.|
00000f30 6d 6f 72 65 20 6d 61 74 63 68 65 73 2e 0a 0a 42 |more matches...B|
00000f40 79 20 74 68 69 73 20 6d 65 61 6e 73 20 76 65 72 |y this means ver|
00000f50 79 20 6c 61 72 67 65 20 61 6d 6f 75 6e 74 73 20 |y large amounts |
00000f60 6f 66 20 64 61 74 61 20 63 61 6e 20 62 65 20 73 |of data can be s|
00000f70 65 61 72 63 68 65 64 20 76 65 72 79 0a 71 75 69 |earched very.qui|
00000f80 63 6b 6c 79 20 69 6e 64 65 65 64 2e 0a 0a 45 78 |ckly indeed...Ex|
00000f90 61 6d 70 6c 65 20 63 6f 64 65 20 28 42 69 6e 61 |ample code (Bina|
00000fa0 72 79 53 65 61 72 63 68 29 0a 41 73 73 75 6d 65 |rySearch).Assume|
00000fb0 20 61 20 31 30 30 20 65 6c 65 6d 65 6e 74 20 73 | a 100 element s|
00000fc0 74 72 69 6e 67 20 61 72 72 61 79 20 61 72 72 61 |tring array arra|
00000fd0 79 24 28 29 2c 20 65 61 63 68 20 65 6c 65 6d 65 |y$(), each eleme|
00000fe0 6e 74 0a 63 6f 6e 74 61 69 6e 69 6e 67 20 61 20 |nt.containing a |
00000ff0 6c 69 73 74 20 6f 66 20 6e 61 6d 65 73 20 73 6f |list of names so|
00001000 72 74 65 64 20 69 6e 74 6f 20 61 6c 70 68 61 62 |rted into alphab|
00001010 65 74 69 63 20 6f 72 64 65 72 2e 0a 54 68 65 20 |etic order..The |
00001020 73 65 61 72 63 68 20 63 61 6e 20 62 65 20 63 61 |search can be ca|
00001030 72 72 69 65 64 20 6f 75 74 20 77 69 74 68 3a 0a |rried out with:.|
00001040 0a 72 65 73 75 6c 74 25 3d 46 4e 73 68 65 6c 6c |.result%=FNshell|
00001050 5f 42 69 6e 61 72 79 53 65 61 72 63 68 28 22 46 |_BinarySearch("F|
00001060 72 65 64 22 2c 22 5f 47 65 74 54 65 72 6d 22 2c |red","_GetTerm",|
00001070 22 5f 43 6f 6d 70 22 2c 30 2c 39 39 29 0a 52 45 |"_Comp",0,99).RE|
00001080 4d 20 72 65 73 74 20 6f 66 20 63 6f 64 65 2e 2e |M rest of code..|
00001090 2e 2e 0a 0a 44 45 46 20 46 4e 5f 47 65 74 54 65 |....DEF FN_GetTe|
000010a0 72 6d 28 6e 72 25 29 0a 3d 61 72 72 61 79 24 28 |rm(nr%).=array$(|
000010b0 6e 72 25 29 0a 3a 0a 44 45 46 20 46 4e 5f 43 6f |nr%).:.DEF FN_Co|
000010c0 6d 70 28 74 65 72 6d 31 24 2c 74 65 72 6d 32 24 |mp(term1$,term2$|
000010d0 29 0a 49 46 20 74 65 72 6d 31 24 20 3c 20 74 65 |).IF term1$ < te|
000010e0 72 6d 32 24 20 54 48 45 4e 20 3d 20 54 52 55 45 |rm2$ THEN = TRUE|
000010f0 20 45 4c 53 45 20 3d 46 41 4c 53 45 0a 0a 72 65 | ELSE =FALSE..re|
00001100 73 75 6c 74 25 20 63 6f 6e 74 61 69 6e 73 20 2d |sult% contains -|
00001110 31 20 69 66 20 27 46 72 65 64 27 20 69 73 20 6e |1 if 'Fred' is n|
00001120 6f 74 20 70 72 65 73 65 6e 74 20 69 6e 20 61 72 |ot present in ar|
00001130 72 61 79 24 2c 20 6f 72 0a 74 68 65 20 65 6c 65 |ray$, or.the ele|
00001140 6d 65 6e 74 20 6e 75 6d 62 65 72 20 69 66 20 69 |ment number if i|
00001150 74 20 69 73 2e 20 54 68 65 20 63 6f 6d 70 6c 65 |t is. The comple|
00001160 78 69 74 79 20 6f 66 20 46 4e 5f 47 65 74 54 65 |xity of FN_GetTe|
00001170 72 6d 0a 61 6e 64 20 46 4e 5f 43 6f 6d 70 20 69 |rm.and FN_Comp i|
00001180 73 20 63 6f 6d 70 6c 65 74 65 6c 79 20 75 70 20 |s completely up |
00001190 74 6f 20 79 6f 75 20 28 77 69 6c 64 63 61 72 64 |to you (wildcard|
000011a0 73 20 63 6f 75 6c 64 20 62 65 0a 61 6c 6c 6f 77 |s could be.allow|
000011b0 65 64 20 66 6f 72 20 65 78 61 6d 70 6c 65 29 2e |ed for example).|
000011c0 20 42 79 20 74 68 69 73 20 6d 65 61 6e 73 20 61 | By this means a|
000011d0 6e 79 20 73 65 74 20 6f 66 20 73 6f 72 74 65 64 |ny set of sorted|
000011e0 20 64 61 74 61 0a 63 61 6e 20 62 65 20 73 65 61 | data.can be sea|
000011f0 72 63 68 65 64 20 2d 20 73 69 6d 70 6c 79 20 64 |rched - simply d|
00001200 65 66 69 6e 65 20 74 68 65 20 27 67 65 74 20 74 |efine the 'get t|
00001210 65 72 6d 27 20 61 6e 64 20 27 63 6f 6d 70 61 72 |erm' and 'compar|
00001220 69 73 69 6f 6e 27 0a 66 75 6e 63 74 69 6f 6e 73 |ision'.functions|
00001230 20 74 6f 20 73 75 69 74 2e | to suit.|
00001239 
.