NewsForumsCodeLogsGallerySpecsSearch

CollLib v2.0 (userlib) is released

Blitz3D Forums/Blitz3D Userlibs/CollLib v2.0 (userlib) is released

Mahan(Posted 2009) [#1]
The free collection lib is now better than ever.

It expands Blitz3D and BlitzPlus is several ways that makes life in these languages much nicer.

Now with the powerful debug-dll in version 2.0 you don't have to be a resource-management-guru to find illegal usages etc. (Full internal handle and bounds checking in debug-mode with popups that tells you what went wrong)

Freeware for use in any (even commercial) projects:

D/L link: http://download.ecma.webfactional.com/CollLib_v2.03.zip

from README.txt:

****************************************************************************
*                                                                          *
*                               CollLib v2.0                               *
*                                                                          *
*               Collection Library for Blitz3D and BlitzPlus               *
*                                (userlib)                                 *
*                                                                          *
* Lib author: Mattias Hansson (aka MaHan)                                  *
* (Safe)Wrapped FreePascal functionality.                                  *
****************************************************************************

What does it do?

+ Provides lists (yes, several lists of the same Type's!)
+ Manages strings (Lots of strings, very fast!)
+ Provides a hashed lookup-list. (find a string among millions in <1ms!)
  (full HashMap).
+ Haves a utility function to convert a locale ANSI string to a valid UTF-8
  string.


What is new in v2.0?

+ A debug-mode dll that helps you find errors in your program (regarding
  calls to CollLib). (The debug-dll trades speed for instance-validation
  and range-checking.)
+ New function CollLibClear() to: 
    1) Clean up stray resources.
    2) Ability to check if your program cleans up after itself
       (not necessary but recommended)


I hope you find it as useful as me :-)

EDIT: Forgot the ListDelete() function in 2.0. Added in 2.01

EDIT2: Today I found quite a rare bug in the TStringHashList-implementation (yes in the library code of fpc!). Fixed in 2.02.

EDIT3: Added reverse StringListSort()


Mahan(Posted 2009) [#2]
If anyone uses the StringHashList in this lib, re-download the new version, as I found a nasty bug while programming today.

The bug affected the functions:

StringHashRemoveValue%(shlHandle%, key$)
StringHashGetValue%(shlHandle%, key$)
StringHashExists%(shlHandle%, key$)

Sometimes in rare cases these functions can fail in the old version.


GIB3D(Posted 2009) [#3]
Why exactly would you need this lib?

1)Clean up stray resources.
Isn't that what FreeEntity, FreeImage, etc... are for?

What is this thing supposed to help with?


Mahan(Posted 2009) [#4]
This lib adds collections to the Blitz3D and BlitzPlus languages.

It does not help with FreeImage and FreeEntity, but it provides 3 new list-types.

Short descrption:
1. List: Similar to a normal integer array (dim), except its fully dynamic, blazingly fast in both modifications (add/delete) and access.

I use Lists all the time since the normal type-lists (first, last, each etc.) are limited to only 1 list per type, and I often want to use several lists of the same type.

Example of usage: I'm right now writing a dynamic tile-map that consists of a List of Lists of TTile (my tile type), so I'm "simulating" a two dimensional array. Tried it without any problems on a map with 1000x1000 tiles so far, and the only limit seems to be the memory.


2. StringList: A insanely fast list of strings, where each string additionally has a optional integer value attached, that of course can be used to hold handles to Blitz entities.

3. StringHashList: A HashMap/Associative table.

Easiest explained like a (very fast) phone book. You pass a name (key-string) and you get the number (integer value) associated with this string.

There is a sacrifice in modification speed (adding new values is not as fast as in the two first lists) but TStringHashList can find a string among millions in fractions of a millisecond. (using binary search)

Since it (similar to the stringlist) matches strings to integers this list again is very nifty when used with Blitz-object handles.

Example: I used this to write a cached text-command (since the one built in is so slow). It renders Text to a new Image and stores the image with the passed string (for screen output) as key. Next time the function is called the StringHashList is called and checked if this string is already pre-rendered. If so it just calls DrawImage on the associated image, which is much faster.

EDIT: added example of list usage


GIB3D(Posted 2009) [#5]
Ok I see it's usefulness now :) I see that you can sort strings which is really useful for things like player lists and server lists.




Mahan(Posted 2009) [#6]
;) Yeah, thats a possibility.

Or if you got a TUser type you could do this:
;Add a new user
local newUser.TUser = new TUser
StringListAddValue(mysl, "Cake", handle(newUser))

;Then have the user accessible on the same index as the string in the StringList:
local user.TUser = Object.TUser(StringListGetValue(mysl, someUserIndex%))
; do stuff with the user here
user\posX = user\posX + 1 ; etc



Beaker(Posted 2009) [#7]
Cool. I like em!


GIB3D(Posted 2009) [#8]
Mmk how about this... StringListSort only sorts things in forward order. Can you make it so you can choose which way you want to order things? So instead of

A
B
C

you get

C
B
A


Mahan(Posted 2009) [#9]
@GIA_Green_Fire_ I'll look into it. A single reversed sort on the StringList is probably easy to add since iirc it's built into the underlying TStringList component.

If you need it like "right now" you could use the normal "sort" and then write an own routine reversing the list fast with the function StringListSwap%(slHandle%, idx1%, idx2%).


Possible future plan: I was thinking of making a user customizable sort. Since Blitz+ and Blitz3D does not have callbacks I'll though about trying to make a "call sequence" of it, something in the lines of (for List example):

//Compare func returns -1 if item1 < item2, 0 if item1 = item2 and 1 if item1 > item2
function MyCompareFunc(item1%, Item2%)
  local user1.TUser = Object.TUser(item1)
  local user2.TUser = Object.TUser(item2)
  local result = 0
  If user1\name < user2\name then result = -1
  if user1\name > user2\name then result = 1
  Return result
end function

local mySort=CreateSort(myList)

While not SortFinished(mySort)
  SortCompare(mySort, MyCompareFunc(SortValue1(mySort), SortValue2(mySort))
Wend

FreeSort(mySort)


This would enable total user customizable sorts and that could be nice to have maybe?


Mahan(Posted 2009) [#10]
@GIA_Green_Fire_: Ok I added reverse sort to the lib. (download in first post above).

Note the new param reverse. If you pass false the sort is done as it has been. If you pass true you get reverse sort order.

Changes:
v2.03:

* Added reverse param to StringListSort(slHandle%, reverse%). False = normal. True = Reverse alphabetic order.
* Added StringHashCount%(shlHandle%)
* Added StringListSortDemo.bb
* Updated the StringHashLists demos to use the new StringHashCount function.



GIB3D(Posted 2009) [#11]
If you need it like "right now"
Nah, I was just telling you that because it seemed like it would be useful later on if someone needed it. Like if you had a server list that scrolls and the servers are in order of abc, over 1000 servers, and the one you're looking for is in the Z section, you would want to reverse the order so you can get to the Z's faster. It's cool that you put it in there though ;)


Charrua(Posted 2009) [#12]
thank's

here a simple example using types

;
; simple code to see if I get the point!
;
; 100 myType objects are created and their handles stored in 4 diferent list based on some
; conditions of the Random field.
;
; so, we end with 4 lists that has some objects in comon, but when we need an object with one attribute
; we only has to search on the apropiate list, not the entire collection of objets (with for each..)

Graphics 800,600

Type myType
	Field Number
	Field Random
End Type

mylist_1=CreateList()	;Random > 10
mylist_2=CreateList()	;Random < 30
mylist_3=CreateList()	;(Random > 40) and (Random < 60)
mylist_4=CreateList()	;(Random Mod 2) = 0

For i=1 To 100
	temp.myType = New myType
	temp\Number = i
	temp\Random = Rand(1,100)
	If temp\Random > 70 Then ListAdd(mylist_1,Handle(temp))
	If temp\Random < 20 Then ListAdd(mylist_2,Handle(temp))
	If (temp\Random > 40) And (temp\Random < 60) Then ListAdd(mylist_3,Handle(temp))
	If (temp\Random Mod 2)=0 Then ListAdd(mylist_4,Handle(temp))
Next

Cls

Print "Items in list 1: "+ListCount(myList_1)
Print "Items in list 2: "+ListCount(myList_2)
Print "Items in list 3: "+ListCount(myList_3)
Print "Items in list 4: "+ListCount(myList_4)
Print

Print "Random > 10"
DumpList(myList_1)

Print "Random < 30"
DumpList(myList_2)

Print "(Random > 40) And (Random < 60)"
DumpList(myList_3)

Print "(Random Mod 2) = 0"
DumpList(myList_4)




WaitKey()

FreeList(myList_1)
FreeList(myList_2)
FreeList(myList_3)
FreeList(myList_4)

End

Function DumpList(list)
	Text$ = ""
	j=0
	For i=0 To ListCount(list)-1
		temp.myType = Object.myType(ListGet(list,i))
		Text$ = Text$ + "("+temp\Number + ":" + temp\Random + ")  "
		j=j+1
		If j=10 Then
			Print Text
			j=0
			Text$ = ""
		End If
	Next
	If Text <> "" Then Print Text
	
	Print 
	Print

End Function


Juan


Mahan(Posted 2009) [#13]
Yes, Juan you got the point exactly. This is imo the single most valuable use of the List in the Blitz3D and Blitz+ languages, even if there are lots of other nifty things that can be done. :-)

Just wanted to point out 2 minor details in the example:

#1
These two lines ...
mylist_1=CreateList()	;Random > 10


Print "Random > 10"

... do not correspond with this one:
If temp\Random > 70 Then ListAdd(mylist_1,Handle(temp))


#2
And also a ...
SeedRnd(MilliSecs())

... in the top of the program, would enhance the demo =)


Charrua(Posted 2009) [#14]
you are right (and so much more like the <30 etc!

when i firs test it, i was using two list's and the rule to be in one or the other was the value 10, then i tihink that 4 list with overlaped references to objets should give more sense, and when i expand the idea to 4 list i change the rule but not the text displayed!
And of course SeedRnd would be good to force the pseudorandomic generator to generate a diferent sequence of values in every try.

rewrite:



btw

is there a function to get an idx in the list based on the value stored?.
(as i see, the idx isn't asociated to an element on the list: if i delete the element 3 of the list, then the element 3 of the list is asigned to the next in the list (exept that only three elementes were in the list), isn't it?)
say, i have some list's, some blitz entities (or types..) ho's handles are stored on the list's but if one entity has to be deleted, i have to delete that item from the list,or the various list's in which it could be. I could do a search for all the list until i found the handle and with the idx i delete that item.

Is it posible to do it better?

thank's

Juan


Mahan(Posted 2009) [#15]
I'd recommend you to look at the StringHashList if you want to have a static assigned key (or index) for a value.



I rewrote your code a bit to show you how StringHashLists may be used to check correlations between sets of values in a fairly efficient way.

Just an additional note (you may already know this): Blitz type instances do not magically disappear if you delete a CollLib-List, -StringList or -StringHashList that holds its handle.


Charrua(Posted 2009) [#16]
than's for your fast response

the question was in this direction.
i didn't test the string and hash functions, based on the fact that i only need to store handles, but, the way you use it is very ilustrative (don`t know if that word exists in english, but hope you understand).

Juan


Mahan(Posted 2009) [#17]
Yes, I can see how the leap from integer handles to strings may firstly seem a little inefficient for a programmer, but the StringHashList hashes the strings so they actually become small integer values themselves.

So when you use the function StringHashAddValue() it actually:

1. Calculates a hash (an integer-value) based of the key-string.
2. Inserts the hash into the right place in a sorted table.

When you use the function StringHashExists() (or *GetValue etc.) internally the StringHashList does this:

1. Calculates a hash based of only the search-key-string (that is sent in to the function).
2. Binary searches the sorted hash-table for a matching hash.

Thinking this way it's very logical to use a StringHashList even when you fill the keys with string representations of the handles.

Example:

StringHashAddValue(myShl, Hex(Handle(myTypeInstance)), <whatever handle you need to lookup fast>)

or

StringHashAddValue(myShl, Str(Handle(myTypeInstance)), <whatever handle you need to lookup fast>)

This way you can use Blitz Type instances as "keys" to map other handles. (or images, or cubes, or <you get it> ... :-)