SET (Steve's Extended Toolset)

[SMcNeill]

This one may be outdated and glitch with the newest version of QB64 with the fix to recursion being allowed in functions.  I thought I'd share anyway, and if anyone has any issues with anything in it, you're always welcome to bring them to my attention.  The more people who use one of these and points out a glitch in it, the easier and faster I can get around to fixing said glitch. 

[madscijr]

Steve can you maybe add a description of what this library actually does?
What are these extended tools, what are they for, etc.
Maybe post a couple of examples, so the person doesn't have to download, unzip and read through it, to find out what it's for?
Just my two cents!
(probably 1.5¢ with inflation)

[SMcNeill]

As soon as I get time, I will. Consider these just a placeholder for the more detailed topic which I'll share and elaborate upon once I manage to find a few free minutes in the week.

[SMcNeill]

As we've now managed to get a few different releases out for QB64 Phoenix Edition, and all seems like it's starting to get stable for the forums, wiki, repo, and all, I'm going to try and sit down and write up a little demo of the various different routines inside these libraries for everyone to see if they contain anything which might be of interest, or use to them.  Since @madscijr asked about this one in particular, let me start here with it and explain what it is and what it can do for folks.

---

First thing to keep in mind is this is an old library, and some of the parts of it would be obsoleted for folks using the modern versions of QB64.  The reason?  I'm also one of those guys who help develop QB64 itself, and often you'll find portions of my libraries end up becoming part of QB64 itself, once they've been tested and enough people have decided they want to make the features permanent.  With Steve's Extended Toolset, that holds true in more than one place -- features that we have in here are now standard in QB64 itself. 

For instance, the color constants that a lot of folks enjoy the simplicity of using, originated here first, before being partially implemented into QB64.  If you've ever used $COLOR:32 or $COLOR:0, then you've used code which originated from this library....


But have you ever wondered why there isn't a $COLOR:256??

There is!  At least, here, there is.  It's just more of a two step process, rather than a simple one step command, so it never got migrated over to QB64 proper.

Code: (Select All)

$Let KOLOR = 256
'$INCLUDE:'SET.BI'

Screen _NewImage(640, 480, 256)
Set256Palette 0

Line (100, 100)-(300, 300), Peach, BF
Sleep
Line (100, 100)-(300, 300), Gold, BF
Sleep
Line (100, 100)-(300, 300), Silver, BF
Sleep
Line (100, 100)-(300, 300), SkyBlue, BF


'$INCLUDE:'SET.BM'

Notice that we have a couple of things to do here to set up the color names to work with a 256 color screen:

First, $LET KOLOR = 256.  This is a flag which says we want to use the 256 color values and not the screen 0 or 32-bit screen color values.  This needs to come before the $INCLUDE for the library.

Then we set the SCREEN to become a 256 color image with Screen _NewImage(640,480,256)

And then we set the image that we want to use the color named palette with Set256Palette (image handle), which is 0 in this case for the current screen.

And that's it!  You can now use the color names for Red, Blue, Green, Yellow, Midnight, White, Black, Purple, and whatnot, rather than having to try and remember the color codes for them with your program!

(Further demos and explanations to follow.)

[SMcNeill]

Starting from the top of the function list and working our way down slowly, let's begin with the BinarySearch routines:

Code: (Select All)

'$INCLUDE:'SET.BI'

Dim Words(370099) As String
Open "word lists\370099 Word List.txt" For Binary As #1
Print "Attempting to load 370,099 words into memory..."
Do Until EOF(1)
    Line Input #1, Words(count)
    count = count + 1
Loop
Print "Successfully Loaded"; count; "words into memory."
Print
Do
    Input "Give me a word =>", word$
    If word$ = "" Then System
    search$ = LCase$(word$)
    position = BinaryStringSearch(search$, Words())
    If position >= LBound(Words) Then
        Print "Your word was found in position #"; position
        If position > LBound(Words) Then Print position - 1, Words(position - 1)
        Print position, Words(position)
        If position < UBound(Words) Then Print position + 1, Words(position + 1)
    Else
        Print "Your word was not found in this data set."; position
        Print "If it would have been found, it would have been between:"
        Print LastIndex, Words(LastIndex)
        Print LastIndex, Words(LastIndex + 1)
    End If
Loop

'$INCLUDE:'SET.BM'

There's 4 of these routines in the library, but I'm just going to demo one of them, and then I'll explain what the rest do, as they're all similar in functionality.

BinaryMemSearch
BinaryMemSearchSome
BinaryStringSearch
BinaryStringSearchSome

What these four functions do is simply implement a quick binary search method for sorted data, such as the wordlist which I'm using here.  (Grab it from the common resource files download here, if you need it: Samples and Resources (qb64phoenix.com))

With the above, we load a word list which has 370,099 words in it.  We then ask the user to give us a word, and we search the wordlist to see if the word exists in it, or not...

Now, one way we could do this search is to simply start at the top of the list, and then move one entry at a time, comparing to see if our word matches any in the list.  A simple FOR i = 0 to 370099: IF search$ = Words(i) Then Exit For: Next would do that job...

BUT...  That means we'd end up having to check 370099 words to see if we had a match or not!!  Can you imagine doing this for a whole list of say 1000 words, and checking to see if they're in the dictionary, or not?  How long would all that take to process for us??

Instead of going such a slow route to find our answer, we instead do a binary search pattern to look for our word's place in the list.  We start in the middle of the list... If that word is less than our search word, we then can ignore the whole first half of the list.  If that word is greater than our search word, we can then ignore the whole second left of the list.  Divide the search area by half every pass!

2 ^ 19 = 524,288...  We can search 524,288 items in 19 or fewer passes, if we divide the search area in half with every pass!  And that makes a huge difference in how long it takes to find your index for an item, when you're doing the search multiple times.  (19,000 max passes to find out if the 1000 words in the list I mentioned above are in our dictionary, rather than 370,099,000 passes if we check for the existence against every word in the list.)

I think everyone should be able to see the performance gain in the differences described above. 

---

The differences for the four routines break down to simply matching our data types.  For anything that we can point a _MEM variable at, we can use the BinaryMem searching.  Since variable length strings don't work with _MEM, we have the BinaryString search routines.  

The SearchSome routines let us specify a range of our data set that we want to search for the result, rather than having to search the whole list.  For example, if we know "A" words start at 0 and end at 50,000 entries, we could BinaryStringSearchSome(search$ , Array(), 0, 50000), and not have to worry about the rest of the word list at all.

Binary Searching of just about anything we need to do a search with!   Just be certain your data array is sorted properly before using these, or else you're not going to get the result you're looking for.