UniqueInd

This routine is in essence identical to Unique, except that the items (here, strings) are not kept in an array but in a heap in memory. Only the index is kept in an array. In this case, to keep the index compact, only the offsets from some datum within the heap (here, its start address addr) are maintained. This particular arrangement might be useful for a data set with a smallish number of strings of a very variable length. But this is just an example. There are so many variations and tweaks that could be made, depending on requirements and circumstance.

To test, EXecute it (SBASIC only) or run it directly from QD with the SBAS/QD Thing. It will probably also work directly from SuperBASIC: Just replace line 20 with: cd = 1, and line 55 with: RECHP addr, and then just RUN it.

Note: You need to LRESPR the extra commands from my toolkits first! (or modify the code accordingly).

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 rem This version uses an index of offsets to address items in memory.
14 rem Note: Only the index is sorted; the heap items remain in the order
15 rem they were added to the heap
16 :
17 EXT_PROC 'POKESTR$'
18 EXT_FN   'PEEKSTR$', 'EVEN', 'CMP%'
19 :
20 cd = FOPEN("con"): BORDER#cd; 1, 2: CLS#cd
21 :
22 rem     Initialise GLOBal values
23 max = 512: max% = 10:           rem Size of heap & index
24 DIM index%(max%):               rem Init index
25 addr = ALCHP(max):              rem Heap
26 cnt% = 0:                       rem Current number of items
27 :
28 rem     Set sentinel to lowest value
29 index%(0) = 0: POKE_W addr, 0: ofs = 2
30 :
31 rem     Test harness
32 REPeat lp
33  INPUT#cd; 'Enter item'! n$: IF n$ = '': EXIT lp
34  IF cnt% = 0 THEN
35   rem   First item is special
36   cnt% = 1: index%(cnt%) = ofs
37   POKESTR$ addr + ofs, n$: ofs = ofs + 2 + EVEN(LEN(n$))
38  ELSE
39   n% = IndBSearch%(n$, index%(0 TO cnt%))
40   IF n% >= 0 THEN
41    PRINT#cd; n%! PEEKSTR$(addr + index%(n%))
42   ELSE
43    PRINT#cd; n%! '['; n$; ']'
44    er = IndInsert(n$, index%, ABS(n%))
45   END IF
46  END IF
47  IF er < 0: PRINT#cd; '** Array full **': PAUSE#cd: EXIT lp
48  :
49  rem    Print list of heap items in order:
50  FOR i = 1 TO cnt%: PRINT#cd; i! PEEKSTR$(addr + index%(i))
51 END REPeat lp
52 :
53 rem     Save heap (unordered)
54 rem sbytes_o 'ram1_test_bin', addr, ofs
55 :
56 :
100 rem + ------------------------------------------------------------------------ +
102 rem |<                              IndBSearch                                >|
104 rem + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +
106 rem |                              Binary Search                               |
108 rem |                                                                          |
110 rem | This version uses an integer array of offsets. The offsets point to      |
112 rem | strings in a heap.                                                       |
114 rem | Returns position if found, or -position where item should go. Thus it    |
116 rem | can be used to add new, unique items to a list, in alphabetical order.   |
118 rem |                                                                          |
120 rem | GLObal addr, ofs                                                         |
122 rem | Uses external FNs CMP% & PEEKSTR$                                        |
124 rem + ------------------------------------------------------------------------ +
126 rem | V0.01, From TAOCP 6.2.1                                                  |
128 rem | V0.01, pjw, 2020 Mar 10, Indirect offset version                         |
130 rem + ------------------------------------------------------------------------ +
132 :
134 DEFine FuNction IndBSearch%(item$, Arr%)
136 LOCal loop, u%, l%, i%
138 l% = 0: u% = DIMN(Arr%)
140 REPeat loop
142  IF u% < l%: i% = -l%: EXIT loop
144  i% = INT((l% + u%) / 2)
146  IF item$ == PEEKSTR$(addr + Arr%(i%)): EXIT loop
148  IF CMP%(item$, PEEKSTR$(addr + Arr%(i%)); 1) < 0 THEN
150   u% = i% - 1
152  ELSE
154   l% = i% + 1
156  END IF
158 END REPeat loop
160 RETurn i%
162 END DEFine BSearch%
164 :
166 :
168 rem + ------------------------------------------------------------------------ +
170 rem |<                               IndInsert                                >|
172 rem + ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +
174 rem |                             Indirect Insert                              |
176 rem |                                                                          |
178 rem | Appends an item into a heap, updating its offset index accordingly       |
180 rem | This version only for strings. Index items are offsets from addr.        |
182 rem | Index could be integer or float array.                                   |
184 rem | Does basic checking on index and heap that buffers dont overflow:        |
186 rem | Returns -4 => index overflow, -11 => heap space used up, 0 => ok         |
188 rem |                                                                          |
190 rem | GLOBal cnt%, addr, ofs, max                                              |
192 rem | Uses external PROCs/FNs POKESTR$ & EVEN                                  |
194 rem + ------------------------------------------------------------------------ +
196 rem | V0.01, pjw, 2020 Mar 10                                                  |
198 rem + ------------------------------------------------------------------------ +
200 :
202 DEFine FuNction IndInsert(item$, Arr, at%)
204 LOCal i%, l%
206 IF (cnt% + 1) > DIMN(Arr): RETurn -4
208 l% = EVEN(LEN(item$)) + 2
210 IF (ofs + l%) > max: RETurn -11
212 cnt% = cnt% + 1
214 :
216 IF at% = cnt% THEN
218  Arr(at%) = ofs
220 ELSE
222  FOR i% = cnt% TO at% STEP -1
224   Arr(i%) = Arr(i% - 1)
226  END FOR i%
228  Arr(at%) = ofs
230 END IF
232 POKESTR$ addr + ofs, item$
234 ofs = ofs + l%
236 RETurn 0
238 END DEFine IndInsert
240 :
242 :

  
Generated with sb2htm on 2020 Mar 10
©pjwitte March 2oi9