Beta B-Tree String searcher......

[Agamemnus]

UPDATED!

Code:

DECLARE SUB btree.make.full.string (array() AS STRING, leaf() AS INTEGER, start() AS INTEGER, depthmax AS INTEGER)
DECLARE FUNCTION string.exists% (string.to.find AS STRING, array.to.search() AS STRING, leaf() AS INTEGER, start() AS INTEGER, depthmax AS INTEGER)
DECLARE SUB qsort.string.lowstart (array1() AS STRING, a.max%)
CLS
'$DYNAMIC
RANDOMIZE TIMER
DIM SHARED btpower2(0 TO 30) AS LONG
FOR i% = 0 TO 30: btpower2(i%) = 2 ^ i% - 1: NEXT i%

DIM array1(1 TO 100) AS STRING
FOR i% = 1 TO 100
L% = INT(RND * 4) + 1
array1(i%) = SPACE$(L%)
FOR j% = 1 TO L%
MID$(array1(i%), j%, 1) = CHR$(INT(RND * 26) + 97)
NEXT j%
NEXT i%

DIM leaf1%(0), start1%(0)
btree.make.full.string array1(), leaf1%(), start1%(), depthmax%
FOR m% = 1 TO UBOUND(array1)
a% = string.exists%(array1(m%), array1$(), leaf1%(), start1%(), depthmax%)
IF a% = 0 THEN PRINT "eep..!": SYSTEM ELSE PRINT "yay!"
NEXT m%
PRINT string.exists%("blarg", array1$(), leaf1%(), start1%(), depthmax%)

REM $STATIC
SUB btree.make.full.string (array() AS STRING, leaf() AS INTEGER, start() AS INTEGER, depthmax AS INTEGER)
DIM i AS INTEGER, j AS INTEGER, k AS INTEGER
DIM temp AS INTEGER, count AS INTEGER, length AS INTEGER
depthmax = 0

'sort array().
k% = UBOUND(array)
qsort.string.lowstart array(), k%

'get rid of duplicates, sort of.
FOR i% = 1 TO k% - 1
IF array(i% + 1) <> array(i%) THEN j% = j% + 1: array(j%) = array(i%)
NEXT i%

'copy to temporary array, redim array, and copy back all non-duplicates.
IF j% <> k% - 1 THEN
DIM temp2(1 TO j%) AS STRING
FOR i% = 1 TO j%: temp2(i%) = array(i%): NEXT i%
REDIM array(1 TO j%) AS STRING
FOR i% = 1 TO j%: array(i%) = temp2(i%): NEXT i%: ERASE temp2
k% = j%
END IF

'find out the depthmax%. [ depthmax% = log2(k%) ]
i% = k% - 1
DO
IF temp% AND 1 THEN i% = (i% - 1) \ 2 ELSE i% = i% \ 2
temp% = temp% + btpower2(depthmax%) + 1
depthmax% = depthmax% + 1
IF i% = 1 THEN EXIT DO
LOOP
temp% = temp% - 1

'make and calculate the leaf() aray and make arrays length1() and length2().
REDIM leaf(0 TO temp%) AS INTEGER
DIM length1(0 TO (temp% + 1) * 2) AS INTEGER, length2(0 TO (temp% + 1) * 2) AS INTEGER
length2(0) = k%: count% = 0
FOR i% = 0 TO depthmax% - 1: k% = 1
FOR j% = 0 TO btpower2(i%): length1%(j%) = length2%(j%): NEXT j%
FOR j% = 0 TO btpower2(i%)
length% = length1%(j%)
temp% = length% \ 2
length2%(j% * 2) = temp%
length2%(j% * 2 + 1) = temp% + (length% AND 1)
leaf(count%) = k% + temp% - 1
count% = count% + 1
k% = k% + length%
NEXT j%, i%
ERASE length1

'make and calculate the start() array.
REDIM start(0 TO btpower2(depthmax%) + 1) AS INTEGER
start(btpower2(depthmax%) + 1) = UBOUND(array) + 1
k% = 1: FOR j% = 0 TO btpower2(i%)
start(j%) = k%: k% = k% + length2%(j%)
NEXT j%

ERASE length2
END SUB

SUB qsort.string.lowstart (array1() AS STRING, a.max%)
DIM g2(1 TO a.max%) AS INTEGER, h2(1 TO a.max%) AS INTEGER, i AS INTEGER, j AS INTEGER, r AS INTEGER, E AS INTEGER, g AS INTEGER, h AS INTEGER, k AS STRING
E = 1: g2(1) = 1: h2(1) = a.max%
r1: g = g2(E): h = h2(E)
r2: i = g: j = h: r = (g + h) \ 2: k = array1(r)
r3: IF array1(i) < k THEN i = i + 1: GOTO r3
r4: IF array1(j) > k THEN j = j - 1: GOTO r4
IF i <= j THEN SWAP array1(i), array1(j): i = i + 1: j = j - 1: IF i <= j THEN GOTO r3
IF j - g + i < h THEN
IF i < h THEN g2(E) = i: h2(E) = h: E = E + 1
h = j
ELSE
IF g < j THEN g2(E) = g: h2(E) = j: E = E + 1
g = i
END IF
IF g < h THEN GOTO r2 ELSE E = E - 1: IF E THEN GOTO r1
ERASE g2, h2
END SUB

FUNCTION string.exists% (string.to.find AS STRING, array.to.search() AS STRING, leaf() AS INTEGER, start() AS INTEGER, depthmax AS INTEGER)
DIM depth AS INTEGER, i AS INTEGER, j AS INTEGER
DO
j = j * 2
IF string.to.find > array.to.search(leaf(i)) THEN j = j + 1
depth = depth + 1
i = btpower2(depth) + j
IF depth = depthmax THEN EXIT DO
LOOP
FOR i% = start(j) TO start(j + 1) - 1
IF string.to.find = array.to.search(i%) THEN string.exists = 1: EXIT FUNCTION
NEXT i%
END FUNCTION

[arven]

no cookies for you!

[adosorken]

No comments yet as you can see..... you're welcome to poke holes......

*poke* *poke* *poke*

[Agamemnus]

=[

Think you can fix the bug which I patched by subtracting t in the search function? :\

[Agamemnus]

Everything is now FIXED. Uses much less memory than before! No bugs! Faster!

[Zack]

Not that I can understand it, but I can make a comment:
That's a very good example of spaghetti code.
But it works. Very nice.