FreeBasic containers (map , vector , list , queue , stack , hashtable)

Headers, Bindings, Libraries for use with FreeBASIC, Please include example of use to help ensure they are tested and usable.
Post Reply
VANYA
Posts: 1683
Joined: Oct 24, 2010 15:16
Location: Ярославль
Contact:

FreeBasic containers (map , vector , list , queue , stack , hashtable)

Post by VANYA »

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
Last edited by VANYA on Jan 15, 2022 12:20, edited 2 times in total.
kcvinu
Posts: 222
Joined: Oct 07, 2015 16:44
Location: Keralam, India

Re: FreeBasic containers (map , vector , list , queue , stack)

Post by kcvinu »

@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.
list_type - List Type (Data Type to save in List) . Data type can be: any standart type , including pointers, except (any ptr)
Can I use my own UDT ?
VANYA
Posts: 1683
Joined: Oct 24, 2010 15:16
Location: Ярославль
Contact:

Re: FreeBasic containers (map , vector , list , queue , stack)

Post by VANYA »

Can I use my own UDT ?
Hi kcvinu!

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
You can work with a type using vectors (in my opinion, this is more convenient):

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
In addition, vectors have the same data access speed as arrays, that is, faster than in a linked list.
Cretin Ho
Posts: 182
Joined: Feb 04, 2021 13:01

Re: FreeBasic containers (map , vector , list , queue , stack)

Post by Cretin Ho »

What about more data structures? Before your library, I tried to use klib with FreeBASIC but always failed:

https://attractivechaos.github.io/klib/#About
VANYA
Posts: 1683
Joined: Oct 24, 2010 15:16
Location: Ярославль
Contact:

Re: FreeBasic containers (map , vector , list , queue , stack)

Post by VANYA »

Update:

1) Optimization of work VECTOR , MAP
2) Fix VECTOR (operator [] + type string , thanks fxm)
VANYA
Posts: 1683
Joined: Oct 24, 2010 15:16
Location: Ярославль
Contact:

Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)

Post by VANYA »

Update , added hash table.
VANYA
Posts: 1683
Joined: Oct 24, 2010 15:16
Location: Ярославль
Contact:

Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)

Post by VANYA »

Update:
1) fix bug in linked list
2) linked list indexing optimization.
Makoto WATANABE
Posts: 215
Joined: Apr 10, 2010 11:41
Location: Japan
Contact:

Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)

Post by Makoto WATANABE »

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

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
VANYA
Posts: 1683
Joined: Oct 24, 2010 15:16
Location: Ярославль
Contact:

Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)

Post by VANYA »

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........
Hi Makoto!

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.
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)".
Thanks, everything is fixed now. Archive updated.
Makoto WATANABE
Posts: 215
Joined: Apr 10, 2010 11:41
Location: Japan
Contact:

Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)

Post by Makoto WATANABE »

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.

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
Edited on Feb. 01.
Last edited by Makoto WATANABE on Feb 01, 2022 14:50, edited 1 time in total.
VANYA
Posts: 1683
Joined: Oct 24, 2010 15:16
Location: Ярославль
Contact:

Re: FreeBasic containers (map , vector , list , queue , stack , hashtable)

Post by VANYA »

Makoto, thanks for testing!
Post Reply