FreeBasic containers (map , vector , list , queue , stack , hashtable)
FreeBasic containers (map , vector , list , queue , stack , hashtable)
Hi All!
Implementation of dynamic data types for Freebasic. This implementation is built on the basis of templates (macros), which makes it possible to use it for almost any data type.
In stock:
1) MAP - dictionary (associative array), created on the basis of a balanced tree
2) VECTOR - dynamic array, with the ability to insert and delete any number of cells and much more useful opportunities
3) LIST - doubly linked list
4) QUEUE
5) STACK
6) HashTable - dictionary (unordered data).
Full description, examples and possibilities are described in the help.
License: MIT
Download
Implementation of dynamic data types for Freebasic. This implementation is built on the basis of templates (macros), which makes it possible to use it for almost any data type.
In stock:
1) MAP - dictionary (associative array), created on the basis of a balanced tree
2) VECTOR - dynamic array, with the ability to insert and delete any number of cells and much more useful opportunities
3) LIST - doubly linked list
4) QUEUE
5) STACK
6) HashTable - dictionary (unordered data).
Full description, examples and possibilities are described in the help.
License: MIT
Download
Last edited by VANYA on Jan 15, 2022 12:20, edited 2 times in total.
Re: FreeBasic containers (map , vector , list , queue , stack)
@Vanya,
Thanks for the much needed library.
I just download it and started reading the chm file. When I read about the list, I found this.
Thanks for the much needed library.
I just download it and started reading the chm file. When I read about the list, I found this.
Can I use my own UDT ?list_type - List Type (Data Type to save in List) . Data type can be: any standart type , including pointers, except (any ptr)
Re: FreeBasic containers (map , vector , list , queue , stack)
Hi kcvinu!Can I use my own UDT ?
Code: Select all
#include "LIST.bi"
type Q
i as Long
s as Zstring*10
End Type
type PQ as Q ptr ' pseudonym Q ptr
MListTemplate(PQ) ' macro for PQ
Dim p As TLISTPQ ' create list with Q ptr
'fill list
For i As Long = 0 To 10
dim qTemp as PQ = new Q ' alloc memory for type Q ptr
qTemp->i = i
qTemp->s = "value" & i
p.Add(qTemp)
Next
' print values
For i As Long = 0 To 10
? (p.GetValueIndex(i))->i , (p.GetValueIndex(i))->s
Next
' delete nodes from list
For i As Long = 10 To 0 step -1
delete p.GetValueIndex(i) ' delete memory for type Q ptr
p.DeleteItemIndex(i) ' delete nodes
Next
? "Size list=" , p.GetSize()
sleep
Code: Select all
#include "VECTOR.bi"
type Q
i as Long
s as Zstring*10
End Type
type pQ as Q ptr
MVectorTemplate(pQ , 1 )
dim V as TVECTORPQ
for i as Long = 0 to 10
dim t as Q
t.i = i
t.s = "value" & i
V.push_back(@t)
Next
for i as Long = 0 to V.size()-1
? V[i]->i , V[i]->s
Next
V.clear()
Sleep
Re: FreeBasic containers (map , vector , list , queue , stack)
What about more data structures? Before your library, I tried to use klib with FreeBASIC but always failed:
https://attractivechaos.github.io/klib/#About
https://attractivechaos.github.io/klib/#About
Re: FreeBasic containers (map , vector , list , queue , stack)
Update:
1) Optimization of work VECTOR , MAP
2) Fix VECTOR (operator [] + type string , thanks fxm)
1) Optimization of work VECTOR , MAP
2) Fix VECTOR (operator [] + type string , thanks fxm)
Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)
Update , added hash table.
Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)
Update:
1) fix bug in linked list
2) linked list indexing optimization.
1) fix bug in linked list
2) linked list indexing optimization.
-
- Posts: 232
- Joined: Apr 10, 2010 11:41
- Location: Japan
- Contact:
Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)
Dear VANYA
Thank you for adding HashTable to your Containers.
I like HashTable because it can be used to prevent duplicate keys and to count the number of duplicate keys in the registered data.
I made a sample program because WSTRING (Japanese characters) can be used for key_type in MHashTemplate(key_type , data_type).
This program outputs the expected result.
However, in this case of this program, I got the same result even if I specified ZSTRING for key_type........
P.S.
It's trivial, but I think the description "Declare Sub DeleteNode (nKey As key_type)" on the DeleteItem page in the CHM help is "Declare Sub DeleteItem (nKey As key_type)".
https://makoto-watanabe.main.jp/freebas ... sterJP.csv
Thank you for adding HashTable to your Containers.
I like HashTable because it can be used to prevent duplicate keys and to count the number of duplicate keys in the registered data.
I made a sample program because WSTRING (Japanese characters) can be used for key_type in MHashTemplate(key_type , data_type).
This program outputs the expected result.
However, in this case of this program, I got the same result even if I specified ZSTRING for key_type........
P.S.
It's trivial, but I think the description "Declare Sub DeleteNode (nKey As key_type)" on the DeleteItem page in the CHM help is "Declare Sub DeleteItem (nKey As key_type)".
https://makoto-watanabe.main.jp/freebas ... sterJP.csv
Code: Select all
'HashTable Test0
'日本語漢字(県名)をキーにしてデータを集計する
'Data aggregation using Japanese characters (prefecture name) as a key
'pTable -> insert("Key", "Value") '辞書項目を登録
'pTable -> deleteitem("Key") '項目を個別に消去
'*pTable-> find("Key") '設定済の索引のデータ取得。未登録のキーを検索すると空白を返します
'pTable -> cleartable() '辞書データをまとめて消去
'pTable -> freetable() '辞書を削除
#Include "HashTable.bi"
MHashTemplate(WString , Zstring)
Dim As THASHTABLEwstringzstring Ptr MasterItemIDpTable = New THASHTABLEwstringzstring
Dim STARTT As Long
Dim ENDTIME As Long
Dim Minut As Integer
Dim Shared ItemID As String
Dim Shared Region As String
Dim Shared Price As String
Dim Shared Weight As String
Dim Shared Counter As Integer
Dim i As Integer
Dim BoolVar As String
Dim QuantityString As String
Dim Amount As String
Dim Dimension As Integer
Dim cellString As String
Dim file_name As String
Dim file_num As Integer
Dim CharacterString As String
Dim Shared RegionArray(100,2) As String 'Region, weight
'****************************************************************
'****************************************************************
'Print "Read ""ItemMasterJP.csv"" and store each line in RegionArray, indexing Region."
Print """ItemMasterJP.csv"" を読み込んで、県名単位に重量項目を集計"
'****************************************************************
STARTT=Val(Left(Time,2))*3600+Val(Mid(Time,4,2))*60+Val(Right(Time,2))
Print
file_name = "ItemMasterJP.csv"
file_num = FreeFile( ) '' 有効なファイル番号を検索します
'' ファイルを開きます。そして、ファイル番号をそれに結び付けます。エラーが有れば、抜けます。
If( Open( file_name For Input As #file_num ) ) Then
Print "ERROR: 開こうとしたファイル名 " ; file_name
Sleep
End -1
End If
Counter = 0
Do Until Eof( file_num ) '' ファイルの端に達するまで、繰り返します。
ItemID ="": Region ="": Price ="" : Weight =""
Line Input #file_num, CharacterString '' テキストの行を読みます。
ItemID = Left(CharacterString,3)
Region = Mid(CharacterString,6,InStrRev(CharacterString,"""")-6)
Price = Mid(CharacterString,InStrRev(CharacterString,"""")+2,InStrRev(CharacterString,",")-InStrRev(CharacterString,"""")-2)
Weight = Right(CharacterString,Len(CharacterString)-InStrRev(CharacterString,","))
BoolVar = *MasterItemIDpTable -> find(Region) '★★★★ キーの存在チェック ★★★★★★★★
If BoolVar = "" Then ' New Key
Counter = Counter + 1
MasterItemIDpTable -> insert(Region, Str(Counter)) '★★★★ 辞書項目を登録
RegionArray(Counter,1)=Region
RegionArray(Counter,2)=Str(Weight)
Else
'Print CharacterString '' キー重複を画面に出力します。
'Print ItemID , Region , Price , Weight
'Print "Counter", Counter
'Print "BoolVar", BoolVar
'Print "Region", RegionArray(Val(BoolVar),1)
'Print "OldVar", RegionArray(Val(BoolVar),2)
RegionArray(Val(BoolVar),2)=Str(Val(RegionArray(Val(BoolVar),2))+Val(Weight)) '値を累積
''Print "NewVar", RegionArray(Val(BoolVar),2)
''Print
'Sleep
End If
Loop
'Print "Number of Regions = ";Counter
Print "県名の件数 = ";Counter
Print
Print "品目マスタの最後のデータの内容 : ";CharacterString ' 画面に最終行を出力します。
Print ItemID , Region , Price , Weight
Print
Close #file_num '' ファイル番号を通したファイルを閉じます。
'****************************************************************
'****************************************************************
'Print "Out put the results to ""RegionArray.csv"""
Print "集計結果を ""RegionArray.csv"" として出力します。"
'****************************************************************
Print
'RegionArray(100,2) 'Region, Weight
Open "RegionArray.csv" For Output As #1
For i = 1 To Counter
CharacterString = ""
For Dimension =1 To 2
cellString = RegionArray(i,Dimension)
If Dimension = 1 Then
cellString = """" & cellString & """"
EndIf
If Dimension > 1 Then
cellString = "," & cellString
EndIf
CharacterString = CharacterString & cellString
Next Dimension
Print #1, CharacterString
Next i
Close #1
ENDTIME = Val(Left(Time,2))*3600+Val(Mid(Time,4,2))*60+Val(Right(Time,2))
Minut=(ENDTIME-STARTT)\60
'Print Using "processing time: ## minutes ## seconds"; Minut; (ENDTIME-STARTT)-Minut*60
Print Using "処理時間: ## 分 ## 秒"; Minut; (ENDTIME-STARTT)-Minut*60
Print
'****************************************************************
'****************************************************************
'Print "Output of the sorted order aggregate has been completed."
Print "集計結果のリスト出力が完了しました。"
Print "*******************************************************"
'Print "Please enter any key to exit."
Print "何かキー入力すると終了します。"
MasterItemIDpTable -> cleartable() '★★★★ 連想配列を消去
MasterItemIDpTable -> freetable() '★★★★ 連想配列を開放
Sleep
Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)
Hi Makoto!Makoto WATANABE wrote: ↑Jan 29, 2022 6:36 However, in this case of this program, I got the same result even if I specified ZSTRING for key_type........
There is a difference and it is that a different amount of memory is allocated.
Zstring allocated 1 byte * number of characters
Wstring is allocated 2 bytes * number of characters (for Windows) or 4 bytes * number of characters (for Linux)
The result should be the same, because HASH is calculated for the key_type value. Inside the HASH keys for the WSTRING and ZSTRING strings is different, but when filling and comparing, the situation will be the same. For instance:
For ZSTRINGKEY:
1) Add a row with the QQQ key to the table and when calculating it HASH = 111
2) Check if there is a line with the key QQQ. But before checking, HASH is calculated for the key and it will also be equal to 111 , so there is such a key.
For WSTRINGKEY:
1) Add a row to the table with the key QQQ and when calculating it HASH = 222
2) Check if there is a line with the key QQQ. But before checking, HASH is calculated for the key and it will also be equal to 222 , which means that there is such a key.
As you can see, it doesn't matter what HASH the key has internally, the main thing is that the result for the same string will be the same.
Thanks, everything is fixed now. Archive updated.It's trivial, but I think the description "Declare Sub DeleteNode (nKey As key_type)" on the DeleteItem page in the CHM help is "Declare Sub DeleteItem (nKey As key_type)".
-
- Posts: 232
- Joined: Apr 10, 2010 11:41
- Location: Japan
- Contact:
Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)
Dear VANYA
Thank you for letting me know immediately.
I did a test to register a huge number of keys, 11,881,376.
Interestingly, on my Win10 computer, MHashTemplate(WString , ZString) took 33 seconds and MHashTemplate(ZString , ZString) took 39 seconds, slightly more time.
In either case, I'm thrilled that your HashTemplate runs fast.
Edited on Feb. 01.
Thank you for letting me know immediately.
I did a test to register a huge number of keys, 11,881,376.
Interestingly, on my Win10 computer, MHashTemplate(WString , ZString) took 33 seconds and MHashTemplate(ZString , ZString) took 39 seconds, slightly more time.
In either case, I'm thrilled that your HashTemplate runs fast.
Code: Select all
'HashTableTest1
'Check for interference in hash generation
'キーに対する Hash 生成での干渉の有無チェック
'Data collation check by Hash
'Hash によるデータの照合チェック
'pTable -> insert("Key", "Value") '辞書項目を登録
'pTable -> deleteitem("Key") '項目を個別に消去
'*pTable-> find("Key") '設定済の索引のデータ取得。未登録のキーを検索すると空白を返します
'pTable -> cleartable() '辞書データをまとめて消去
'pTable -> freetable() '辞書を削除
'pTable-> Count() '登録データ件数
'pTable-> Size() '使用メモリサイズ
#Include "HashTable.bi"
'W:33
MHashTemplate(WString , ZString)
Dim As THASHTABLEwstringzstring Ptr pTable = New THASHTABLEwstringzstring
'Z:39
'MHashTemplate(ZString , ZString)
'Dim As THASHTABLEzstringzstring Ptr pTable = New THASHTABLEzstringzstring
Dim ItemID As String
Dim As Integer Counter, i, j, k, l, m
Dim BoolVar As String
Dim As Single t1,t2,t3
'****************************************************************
'キーに対する Hash 生成と、生成した Hash の干渉有無チェック
'Generate Hashes for keys and check for interference with the generated Hash
'****************************************************************
t1=Timer
Counter = 0
For i = Asc("A") To Asc("Z")
Print Chr(i)+Space(1);
For j = Asc("A") To Asc("Z")
For k = Asc("A") To Asc("Z")
For l = Asc("A") To Asc("Z")
For m = Asc("A") To Asc("Z")
ItemID = Chr(i) + Chr(j) + Chr(k) + Chr(l) + Chr(m)
BoolVar = *pTable-> find(ItemID) ' ItemIDの存在を確認
If BoolVar = "" Then '***********
Counter += 1
pTable-> insert(ItemID, ItemID) '★★ データ追加★★★★★★★★★★
Else
'キーの重複が発生したら表示する
Print
Print "Key Duplicate", Counter, ItemID
Sleep
End If
Next m
Next l
Next k
Next j
Next i
Print
Print
Print "データ登録を終了しました。 ItemID = "; ItemID
Print " Counter = 26^5(11,881,376) = "; Counter
t2=Timer
Print "登録所要秒数 = ";t2 - t1
Print
Print "*******************************************************"
'****************************************************************
'データ項目を削除して再登録する
'Deleting and re-registering data items
'****************************************************************
Print "26 個のキーを削除します。"
Print
For i = Asc("A") To Asc("Z")
ItemID = Chr(i) + "AAAA"
pTable -> deleteitem(ItemID) 'キーを指定して、データ項目を個別に消去
Print ItemID,
Next i
Print
Print "Count ="; pTable-> Count()
Print "Size ="; pTable-> Size()
Print
Print "26 個のキーを追加します。"
Print
For i = Asc("A") To Asc("Z")
ItemID = Chr(i) + "AAAA"
BoolVar = *pTable-> find(ItemID) ' ItemIDの存在を確認
If BoolVar = "" Then '***********
Counter += 1
pTable-> insert(ItemID, ItemID) '★★ データ追加★★★★★★★★★★
Print ItemID,
Else
'キーの重複が発生したら表示する
Print
Print "Key Duplicate", Counter, ItemID
Sleep
End If
Next i
Print
Print "Count ="; pTable-> Count()
Print "Size ="; pTable-> Size()
Print
Print "*******************************************************"
'****************************************************************
'Hash によるデータの照合チェック
'Data collation check by Hash
'****************************************************************
For i = Asc("A") To Asc("Z")
Print Chr(i)+Space(1);
For j = Asc("A") To Asc("Z")
For k = Asc("A") To Asc("Z")
For l = Asc("A") To Asc("Z")
For m = Asc("A") To Asc("Z")
ItemID = Chr(i) + Chr(j) + Chr(k) + Chr(l) + Chr(m)
If ItemID <> *pTable -> find(ItemID) Then ' Hash を使ってデータを照合
'データの不整合が発生したら表示する
Print
Print "Inconsistent data", ItemID, *pTable -> find(ItemID)
Sleep
End If
Next m
Next l
Next k
Next j
Next i
Print
t3=Timer
Print "照合所要秒数 = ";t3 - t2
Print
Print "合計所要秒数 = ";t3 - t1
pTable -> cleartable()
pTable -> freetable()
Print "*******************************************************"
'Print "Please enter any key to exit."
Print "何かキー入力すると終了します。"
Sleep
Last edited by Makoto WATANABE on Feb 01, 2022 14:50, edited 1 time in total.
Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)
Makoto, thanks for testing!
-
- Posts: 237
- Joined: Jul 15, 2021 7:23
- Location: Greece
- Contact:
Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)
Please can you update the English documentation for hashtable ?
Thnaks !!!
Thnaks !!!
Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)
Greetings!
This container library is easy to understand and use to me.When I tried to run the examples from the chm documents,I noticed the Vector insert and push_back behavior is not as I expected.Can anybody help on this?
As mentioned above,my confusion is focused on the vector.
1.In testvector(),Dim As TVECTORLONG Ptr pv = New TVECTORLONG(2),does this mean the vector size is 2?or 3?([0],[1],[2]) Please see below output screenshot for further information regarding why I was confused.
2.I can call at() assignment again and again and the compiler won't say anything when compiling,but the result is not as expected.part of the at() assignment doen't insert the value to the vector.
3.Does insert() and push_back always resize the vector?
Regarding teststack(),Inserting asian characters got a out of range result-->
This container library is easy to understand and use to me.When I tried to run the examples from the chm documents,I noticed the Vector insert and push_back behavior is not as I expected.Can anybody help on this?
As mentioned above,my confusion is focused on the vector.
1.In testvector(),Dim As TVECTORLONG Ptr pv = New TVECTORLONG(2),does this mean the vector size is 2?or 3?([0],[1],[2]) Please see below output screenshot for further information regarding why I was confused.
2.I can call at() assignment again and again and the compiler won't say anything when compiling,but the result is not as expected.part of the at() assignment doen't insert the value to the vector.
3.Does insert() and push_back always resize the vector?
Code: Select all
#include "LIST.bi"
#include "HashTable.bi"
#include "MAP.bi"
#include "QUEUE.bi"
#include "STACK.bi"
#include "VECTOR.bi"
Type CATALOG
iAge As Long
sGender As Zstring*30
sStatus As Zstring*30
sCountry As Zstring*30
End Type
Type pCATALOG As CATALOG Ptr
declare sub printInfo(sKey as string)
declare sub testhashtable()
declare sub testmap()
declare sub testqueue()
declare sub teststack()
declare sub testvector()
MListTemplate(String)
MHashTemplate(Zstring , Zstring)
MMapTemplate(String , pCATALOG , , 1 )
MQueueTemplate(String)
MStackTemplate(String)
MVectorTemplate(Long)
Dim shared sMap As TMAPSTRINGpCATALOG ' TMAP+STRING+pCATALOG
sub testlist()
Dim p As TLISTSTRING
For i As Long = 0 To 10
p.Add(Str(i))
Next
' print values
For i As Long = 0 To 10
? p.GetValueIndex(i)
Next
sleep
end sub
testlist()
testhashtable()
testmap()
testqueue()
teststack()
testvector()
sub testhashtable()
Dim As THASHTABLEzstringzstring Ptr pTable = New THASHTABLEzstringzstring
?
For i As Long = 0 To 10
pTable->insert("Key" & i , "Value" & i)
Next
? "Items count="; pTable->Count()
?
For i As Long = 0 To 10
? *pTable->find("Key" & i)
Next
?
? "delete Key5"
pTable->deleteitem("Key5")
?
? "Items count="; pTable->Count()
?
For i As Long = 0 To 10
? *pTable->find("Key" & i)
Next
pTable->cleartable()
pTable->freetable()
Sleep
end sub
sub testmap()
'Dim sMap As TMAPSTRINGpCATALOG ' TMAP+STRING+pCATALOG
'Add data
Dim t As CATALOG
t.iAge = 18
t.sCountry = "USA"
t.sGender = "Female"
t.sStatus = "Daughter"
sMap.insert("Kristina" , @t)
t.iAge = 50
t.sCountry = "USA"
t.sGender = "Male"
t.sStatus = "Father"
sMap.insert("Robert" , @t)
' find data:
printInfo("Kristina")
printInfo("Robert")
printInfo("Den")
sleep
end sub
Sub printInfo(sKey as string)
'Dim sMap As TMAPSTRINGpCATALOG ' TMAP+STRING+pCATALOG
? "Data for " & sKey & ":"
Dim As CATALOG Ptr pPointer = (sMap.find(sKey))
If pPointer Then
? "Age = ", pPointer->iAge
? "Country = ", pPointer->sCountry
? "Gender = ", pPointer->sGender
? "Status = ", pPointer->sStatus
Else
? "There is no such thing in the catalog"
Endif
?
End Sub
sub testqueue()
Dim As TQUEUESTRING ps
ps.push("String1")
ps.push("String2")
? ps.size()
? ps.front()
? ps.back()
? ps.size()
sleep
end sub
sub teststack()
Dim ps As TSTACKSTRING
ps.push("字符串1")
ps.push("字符串2")
ps.push("字符串3")
? "Size stack="; ps.size()
? ps.pop()
? ps.pop()
? ps.pop()
? "Size stack="; ps.size()
sleep
end sub
sub testvector()
' We declare the vector c 2 cells
Dim As TVECTORLONG Ptr pv = New TVECTORLONG(2)
' Let us come at once a symbolic links to use the vectors as convenient as possible:
Dim Byref As TVECTORLONG V = *pv
' assign values
V[0] = 1
V[1] = 2
pv->insert(2,3)
pv->at(3)=4
pv->at(4)=5
pv->at(5)=6
pv->at(6)=7
pv->at(7)=8
pv->at(8)=9
v.push_back(10)
?
?
? "Size of v is :",v.size()
'print values
?
? "print vector"
for i as integer =0 to v.size()-1
? v.at(i)
next i
Sleep
end sub
Code: Select all
Size stack= 3
瀛楃涓?
瀛楃涓?
瀛楃涓?
Size stack= 0
out of range!
out of range!
out of range!
out of range!
out of range!
out of range!
Size of v is : 4
print vector
1
2
3
10
Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)
Maybe one day...demosthenesk wrote: ↑Aug 31, 2022 11:52 Please can you update the English documentation for hashtable ?
Thnaks !!!
TVECTORLONG(2) = 21.In testvector(),Dim As TVECTORLONG Ptr pv = New TVECTORLONG(2),does this mean the vector size is 2?or 3?([0],[1],[2]) Please see below output screenshot for further information regarding why I was confused.
at() - replaces or assigns a value to existing cells. This function does not insert a value!I can call at() assignment again and again and the compiler won't say anything when compiling,but the result is not as expected.part of the at() assignment doen't insert the value to the vector.
No not always. As needed.3.Does insert() and push_back always resize the vector?
I can't tell how the STRING type works with Chinese characters. Try using the WSTRING PTR type with manual memory allocation. By the way, what will this code return for you? :Regarding teststack(),Inserting asian characters got a out of range result-->
Code: Select all
sub adds(psz as zstring ptr)
? Len(*psz)
? *psz
End Sub
dim as string s
s = "字符串1"
? Len(s)
? s
adds(strptr(s))
sleep
Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)
But why v.size=4?This is what I was confused.TVECTORLONG(2) = 2
output---
Code: Select all
Size of v is : 4
print vector
1
2
3
10
Output:I can't tell how the STRING type works with Chinese characters. Try using the WSTRING PTR type with manual memory allocation. By the way, what will this code return for you? :
Code: Select all
sub adds(psz as zstring ptr) ? Len(*psz) ? *psz End Sub dim as string s s = "字符串1" ? Len(s) ? s adds(strptr(s)) sleep
Code: Select all
7
字符串1
7
字符串1