Unique

An example of how to create a real-time list of unique items. Some points of interest for those less experienced with S*BASIC:

The technique here uses two subroutines: BSearch and Insert. BSearch is a fast binary search routine (borrowed from Donald Knuth's seminal The Art of Computer Programming, or TAOCP), which returns the position of an item if found, or the position an item would have had, had it been found, as a negative position. Ie -v => Not Found Here.

It is not a requirement of the BSearch algorithm as such to have a sentinel, ie the minimal possible seed value at position 0. It just simplifies a number of things a bit. Take for instance S*BASIC's way of handling array parameters: If you pass the test$() array to BSearch as test$(0 TO 2), DIMN(Arr$) (line 128) returns 2. However, if you pass it as test$(0 TO 0), DIMN(Arr$) returns 8! Why? Because S*BASIC then sees test$ as a substring, and as you see from line 13, that has the dimension 8.

You may notice that the Insert routine is OK with the parameters item and Arr - ie apparent floats! although the routine is used here for handling a string and a string array. Well, S*BASIC doesnt really care about the type of formal parameters: They are taken to be of the type that is actually passed to them. Useful here, as the Insert routine is "universal", ie: The same routine can be used for integers and floats too without change. At other times it can be a real nuisance, so beware!

The only reason for specifying a type in the prameters list it to give an indication of the type expected. And that is the point of specifying item$ and Arr$ as such in BSearch: The CMP% function only eats strings. The reason for using CMP% rather than the normal S*BASIC comparison sybols, is that there is no << or >> in S*BASIC, only ==. If one were to use < or >, then the comparison would not be case agnostic; ie ABC is NOT abc; ABC < abc. If case-dependence is desirable, then simply swap the line 136 and 138 with:

136  IF item$ = Arr$(i%): EXIT loop
138  IF item$ < Arr$(i%) THEN

In that case you have a universal routine, that will handle, not only strings, but numbers too. You can still make the routine quasi-case agnostic: Just lowercase (or uppercase) all strings that go into it!

Heres the program. As usual, the first bit is just a simple harness to demonstrate. As it stands, it expects to be LRUNed in the standard 3-window SuperBASIC console:

10 rem Scan a list using binary search routine and return +ve if found.
11 rem If not found, add item to list, creating a list of unique items.
12 :
13 DIM test$(10, 8)
14 FOR i% = 0 TO 2: CLS#i%
15 :
16 cnt% = 0: test$(cnt%) = '': rem Set sentinel to lowest value
17 REPeat lp
18  INPUT#0; 'Enter item'! n$: IF n$ = '': EXIT lp
19  IF cnt% = 0 THEN
20   cnt% = 1: test$(cnt%) = n$
21  ELSE
22   n% = BSearch%(n$, test$(0 TO cnt%))
23   IF n% >= 0 THEN
24    PRINT n%! test$(n%)
25   ELSE
26    PRINT n%! '['; n$; ']'
27    Insert n$, test$, ABS(n%)
28   END IF
29  END IF
30  CLS#2: FOR i = 1 TO cnt%: PRINT#2; i! test$(i)
31  IF cnt% = DIMN(test$): PRINT#2; '** Array full **': EXIT lp
32 END REPeat lp
33 :
34 :
100 rem + ------------------------------------------------------------------------ +
102 rem |<                                BSearch                                 >|
104 rem + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +
106 rem |                              Binary Search                               |
108 rem |                                                                          |
110 rem | Returns position if found, or -position where item should go. Thus it    |
112 rem | can be used to add new, unique items to a list, in alphabetical order.   |
114 rem | Strings only! Uses CMP%                                                  |
116 rem + ------------------------------------------------------------------------ +
118 rem | V0.01, From TAOCP 6.2.1                                                  |
120 rem + ------------------------------------------------------------------------ +
122 :
124 DEFine FuNction BSearch%(item$, Arr$)
126 LOCal loop, u%, l%, i%
128 l% = 0: u% = DIMN(Arr$)
130 REPeat loop
132  IF u% < l%: i% = -l%: EXIT loop
134  i% = INT((l% + u%) / 2)
136  IF item$ == Arr$(i%): EXIT loop
138  IF CMP%(item$, Arr$(i%); 1) < 0 THEN
140   u% = i% - 1
142  ELSE
144   l% = i% + 1
146  END IF
148 END REPeat loop
150 RETurn i%
152 END DEFine BSearch%
154 :
156 :
158 DEFine PROCedure Insert(item, Arr, at%)
160 LOCal i%
162 rem GLOBal cnt%
164 cnt% = cnt% + 1
166 IF at% = cnt% THEN
168  Arr(at%) = item
170 ELSE
172  FOR i% = cnt% TO at% STEP -1
174   Arr(i%) = Arr(i% - 1)
176  END FOR i%
178  Arr(at%) = item
180 END IF
182 END DEFine Insert
184 :
186 :
  
Generated with sb2htm on 2019 Jul 04
©pjwitte March 2oi9