Dictionary Class

Source-code only - please, don't post questions here.
paul doe
Posts: 553
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 19, 2018 13:28

@fxm: the error is thrown during instantiation:

Code: Select all

type Dictionary
  dim as Integer I
  declare operator let( byref as Dictionary )
end type

type RegisterDictionary extends Dictionary
end type

dim as RegisterDictionary a = RegisterDictionary()

Which, to me, makes perfect sense. Why you're extending a class that doesn't extends Object? Isn't it supposed to work like a final class in languages like Java? And indeed, it does.
fxm
Posts: 8175
Joined: Apr 22, 2009 12:46
Location: Paris suburb, FRANCE

Re: Dictionary Class

Postby fxm » May 19, 2018 13:36

Same fbc versions.
Unbelievable !
Last edited by fxm on May 19, 2018 13:47, edited 1 time in total.
fxm
Posts: 8175
Joined: Apr 22, 2009 12:46
Location: Paris suburb, FRANCE

Re: Dictionary Class

Postby fxm » May 19, 2018 13:42

dim as RegisterDictionary a = RegisterDictionary()

'RegisterDictionary()' explicitly calls the default constructor of RegisterDictionary which does not exist !

dim as RegisterDictionary a
works !
fxm
Posts: 8175
Joined: Apr 22, 2009 12:46
Location: Paris suburb, FRANCE

Re: Dictionary Class

Postby fxm » May 19, 2018 14:00

Have you specific compile options when you are testing these very simple codes ?
fxm
Posts: 8175
Joined: Apr 22, 2009 12:46
Location: Paris suburb, FRANCE

Re: Dictionary Class

Postby fxm » May 19, 2018 14:14

I found:
-Wc -Ofast

with:
-Wc -O0
or no gcc option,
the error appears !
fxm
Posts: 8175
Joined: Apr 22, 2009 12:46
Location: Paris suburb, FRANCE

Re: Dictionary Class

Postby fxm » May 19, 2018 14:20

May be the gcc optimization removes some unused code (calling the let operator), but which would have caused this error (undefined Let operator call).
For example the copy-constructor / let-operator generated by the compiler ?
paul doe
Posts: 553
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 19, 2018 14:31

fxm wrote:I found:
-Wc -Ofast

with:
-Wc -O0
or no gcc option,
the error appears !

Ok, updated the repo now. Should work with any compiler switch.

@Makoto WATANABE: the reason why the previous examples worked and this one didn't, was that the older header and reference implementation DID have these operators defined in-code. Somewhere, I deleted them and didn't remembered to add them back. I'm very sorry for the inconvenience.

@fxm: MANY thanks for looking at this issue in depth. Seems like the -Ofast switch inhibits (or optimizes away) the implicit let operator and copy constructor that FB generates (will have to keep this in mind in the future).
paul doe
Posts: 553
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 19, 2018 14:33

fxm wrote:May be the gcc optimization removes some unused code (calling the let operator), but which would have caused this error (undefined Let operator call).
For example the copy-constructor / let-operator generated by the compiler ?

Indeed, that's what happened. As I explained above, the previous version did have them defined in-code, but for some reason I deleted them (most likely formatting) and forgot to put them back. However, it's an insidious issue that I better not forget. Thank you for your troubles, I hope everything is working now as expected.
fxm
Posts: 8175
Joined: Apr 22, 2009 12:46
Location: Paris suburb, FRANCE

Re: Dictionary Class

Postby fxm » May 19, 2018 14:52

For more safety, I would have put everywhere a definition (even empty) for each declaration.
paul doe
Posts: 553
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 19, 2018 14:59

fxm wrote:For more safety, I would have put everywhere a definition (even empty) for each declaration.

Yeah, but hindsight is always genius, don't you agree?
Makoto WATANABE
Posts: 103
Joined: Apr 10, 2010 11:41
Location: Japan
Contact:

Re: Dictionary Class

Postby Makoto WATANABE » May 20, 2018 14:21

Dear fxm;

Thank you for your professional support.
I am very grateful to you.

Dear paul doe;

Thanks for your update.
Now, "fb-dict-example-1.bas" works fine in my environment.

Then, please teach me how to get all dictionary registrations without using keys.
I want to store them in an array and sort by age.

20,"Shaiel Doe","Dreamland"
30,"Janet Doe","2st street"
36,"Paul Doe","1st street"
paul doe
Posts: 553
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 20, 2018 16:05

Makoto WATANABE wrote:Dear paul doe;

Thanks for your update.
Now, "fb-dict-example-1.bas" works fine in my environment.

Glad to hear that =D
Makoto WATANABE wrote:Then, please teach me how to get all dictionary registrations without using keys.
I want to store them in an array and sort by age.

20,"Shaiel Doe","Dreamland"
30,"Janet Doe","2st street"
36,"Paul Doe","1st street"

If you need linear indexing of sorted data, a Dictionary is not the right data structure to use. There are more efficient (and appropriate) methods to do so:

Code: Select all

/'
  Define a composite type, with all it's members public. This will
  represent the 'data' that our app will process.
'/
type Record
   public:
      declare constructor()
      declare constructor( _
         byref as const string, byref as const string, byval as integer )
     
      declare destructor()
     
      as string      name
      as string      address
      as integer   age
end type

constructor Record()
  name = "Unknown"
  address = "Unknown"
  age = 0
end constructor

constructor Record( _
   byref pName as const string, byref pAddress as const string, byval pAge as integer )

   name = pName
   address = pAddress
   age = pAge
end constructor

destructor Record()

end destructor

'' Sort an array of Records by age
sub sortArray( byval startIndex as integer, byval endIndex as integer, array() as Record ptr )
   dim as integer firstHalf, secondHalf
   dim as integer pivot
   
   firstHalf = startIndex
   secondHalf = endIndex
   
   '' Use the median value as pivot
   pivot = array( ( firstHalf + secondHalf ) \ 2 )->age

  do
    '' Find > pivot
    do while( array( firstHalf )->age < pivot )
      firstHalf = firstHalf + 1
    loop
     
      '' Find < pivot
      do while( array( secondHalf )->age > pivot )
         secondHalf = secondHalf - 1
      loop
     
      '' Swap if needed
      if( firstHalf <= secondHalf ) then
         swap array( firstHalf ), array( secondHalf )
         
         firstHalf = firstHalf + 1
         secondHalf = secondHalf - 1
      end if
   loop until( firstHalf > secondHalf )
 
  '' Repeate sort until each half is sorted
   if( secondHalf > startIndex ) then
      sortArray( startIndex, secondHalf, array() )
  end if
   
   if( firstHalf < endIndex ) then
      sortArray( firstHalf, endIndex, array() )
   end if
end sub

/'
  Main code
'/
dim as Record ptr records( 0 to 2 )

records( 0 ) = new Record( "Paul Doe", "1st Street", 36 )
records( 1 ) = new Record( "Jane Doe", "2st Street", 30 )
records( 2 ) = new Record( "Shaiel Doe", "Dreamland", 9 )

'' Sort the array of records
sortArray( 0, ubound( records ), records() )

for i as integer = 0 to ubound( records )
  ? records( i )->name
  ? records( i )->address
  ? records( i )->age
  ?
next

'' Cleanup
for i as integer = 0 to ubound( records )
  delete( records( i ) )
next

sleep()

But then, does this mean that we must totally forfeit accessing the data by key? Not exactly:

Code: Select all

#include once "fb-dictionary-src.bi"
#include once "fb-dict-reference.bas"

/'
  Define a composite type, with all it's members public. This will
  represent the 'data' that our app will process.
'/
type Record
   public:
      declare constructor()
      declare constructor( _
         byref as const string, byref as const string, byval as integer )
     
      declare destructor()
     
      as string      name
      as string      address
      as integer   age
end type

constructor Record()
  name = "Unknown"
  address = "Unknown"
  age = 0
end constructor

constructor Record( _
   byref pName as const string, byref pAddress as const string, byval pAge as integer )

   name = pName
   address = pAddress
   age = pAge
end constructor

destructor Record()

end destructor

/'
  A dictionary implementation to handle Records
'/
type RecordDictionary extends Dictionary
   public:
      declare constructor()
      declare destructor()
     
      declare function add( byref as const string, byval as Record ptr ) as boolean
      declare function item( byref as const string ) as Record ptr
      declare sub remove( byref as const string )
      declare function keyExists( byref as const string ) as boolean
end type

constructor RecordDictionary()
   base()
end constructor

destructor RecordDictionary()

end destructor

function RecordDictionary.add( _
   byref key as const string, byval value as Record ptr ) as boolean
   
   /'
     Note that we do NOT specify a disposal callback, for all we want to do is
     *index* data, not *store* it. This is really the original intent of this
     class (the disposal callback was provided in case one doesn't have a
     centralized data management mechanism).
   '/
   return( base.add( key, value ) )
end function

sub RecordDictionary.remove( byref key as const string )
   base.remove( key )
end sub

function RecordDictionary.item( byref key as const string ) as Record ptr
   return( cast( Record ptr, base.item( key ) ) )
end function

function RecordDictionary.keyExists( byref key as const string ) as boolean
   return( base.keyExists( key ) )
end function

'' Sort an array of Records by age
sub sortArray( byval startIndex as integer, byval endIndex as integer, array() as Record ptr )
   dim as integer firstHalf, secondHalf
   dim as integer pivot
   
   firstHalf = startIndex
   secondHalf = endIndex
   
   '' Use the median value as pivot
   pivot = array( ( firstHalf + secondHalf ) \ 2 )->age

  do
    '' Find < pivot
    do while( array( firstHalf )->age < pivot )
      firstHalf = firstHalf + 1
    loop
     
      '' Find > pivot
      do while( array( secondHalf )->age > pivot )
         secondHalf = secondHalf - 1
      loop
     
      '' Swap if needed
      if( firstHalf <= secondHalf ) then
         swap array( firstHalf ), array( secondHalf )
         
         firstHalf = firstHalf + 1
         secondHalf = secondHalf - 1
      end if
   loop until( firstHalf > secondHalf )
 
  '' Repeate sort until each half is sorted
   if( secondHalf > startIndex ) then
      sortArray( startIndex, secondHalf, array() )
  end if
   
   if( firstHalf < endIndex ) then
      sortArray( firstHalf, endIndex, array() )
   end if
end sub

/'
  Main code
'/
dim as Record ptr records( 0 to 2 )

records( 0 ) = new Record( "Paul Doe", "1st Street", 36 )
records( 1 ) = new Record( "Jane Doe", "2st Street", 30 )
records( 2 ) = new Record( "Shaiel Doe", "Dreamland", 9 )

'' Create a dictionary to *index* the data by key
dim as RecordDictionary ptr dic = new RecordDictionary()

'' Add the entries to the dictionary. We will use the name as key
for i as integer = 0 to ubound( records )
  dic->add( records( i )->name, records( i ) )
next

'' Sort the array of records
sortArray( 0, ubound( records ), records() )

/'
  Now, if we want to index the data sequentially (and ordered), we
  simply use the array directly.
'/
? "== Indexing data by array =="

for i as integer = 0 to ubound( records )
  ? records( i )->name
  ? records( i )->address
  ? records( i )->age
  ?
next

? "== Indexing data by key =="

/'
  And if we need to index the data by key (to avoid a linear search on the
  array), we use the dictionary.
'/
dim as string key = "Jane Doe"

if( dic->keyExists( key ) ) then
  ? dic->item( key )->name
  ? dic->item( key )->address
  ? dic->item( key )->age
else
  ? "That dictionary entry does not exists"
end if

'' Cleanup
for i as integer = 0 to ubound( records )
  delete( records( i ) )
next

delete( dic )

sleep()

You see, there's a common misconception about data. Our applications need to manipulate data (otherwise there's no point to writing them), and we use data structures to do so. However, data structures are not 'data'. Data just is. It can reside in memory, on a file, across a network, anywhere you like. Data structures, on the other hand, are representations (abstractions) of that data, to allow us to manipulate it more easily/conveniently.

This way of thinking allows you to effectively abstract data so you can index it using any data structure that's more appropriate for the task at hand, without needing to toss the data itself across your application. Ideally, data should reside in one and only one place (application wise), and every data structure that's coded in an abstract way can be used to index it without needing to worry about how the data is actually stored.

I hope that this makes at least some sense to you ;)
Makoto WATANABE
Posts: 103
Joined: Apr 10, 2010 11:41
Location: Japan
Contact:

Re: Dictionary Class

Postby Makoto WATANABE » May 21, 2018 10:35

Dear paul doe;

Thanks for your quick reply.
Your sortArray program that uses the pointer is a useful code that I can use as it is.
I am very grateful to you.

By the way, I want functions equivalent to "Keys Method" and "Items Method" of "Dictionary object".
I plan to complete the Dictionary first, then I'd like to register it in an array and sort it.
"Dictionary.Keys Method" returns an array containing all existing keys in a Dictionary object.
"Dictionary.Items Method" returns an array containing all the items in the specified Dictionary object.
paul doe
Posts: 553
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Dictionary Class

Postby paul doe » May 21, 2018 16:55

Makoto WATANABE wrote:...
Your sortArray program that uses the pointer is a useful code that I can use as it is.
I am very grateful to you.

You're welcome. Glad you find it useful.
Makoto WATANABE wrote:...
By the way, I want functions equivalent to "Keys Method" and "Items Method" of "Dictionary object".
I plan to complete the Dictionary first, then I'd like to register it in an array and sort it.

Didn't the previous example addressed this?
Makoto WATANABE wrote:...
"Dictionary.Keys Method" returns an array containing all existing keys in a Dictionary object.
"Dictionary.Items Method" returns an array containing all the items in the specified Dictionary object.

You can easily implement this yourself, if you want. However, do note that you can't return arrays in FreeBasic, so you'll have to somehow circumvent this. The code I provided is generic, thus allowing you to implement any features you miss/want on top of the IDictionary class. At least try to implement them, and if you can't, tell me and I'll provide one possible (there are many) implementation for it =D
Makoto WATANABE
Posts: 103
Joined: Apr 10, 2010 11:41
Location: Japan
Contact:

Re: Dictionary Class

Postby Makoto WATANABE » May 22, 2018 6:11

Count the appearance frequency of letters
Frequency analysis

One of the detective Sherlock Holmes story is "The Adventure of the Dancing Men".
https://en.wikipedia.org/wiki/The_Adventure_of_the_Dancing_Men
https://en.wikipedia.org/wiki/Frequency_analysis
http://archives.obs-us.com/obs/english/books/rawlins/moths/secrets/1.html

I used paul doe's program of using Dictionary Class and created a program to check the number of occurrences of characters in English text files.
I really appreciate paul doe.

Note:
This program uses "Open File Dialog OpenFileRequester" of "FBGUI library for windows Window 9".
https://www.freebasic.net/forum/viewtopic.php?f=14&t=17058&p=247087#p247087

P.S.
I want to translate the Dictionary Class and related programs into Japanese and publish them on my site with MIT License. I hope you will understand this.

Code: Select all

'Count the appearance frequency of letters

#Include Once "fb-dictionary-src.bi"
#Include Once "fb-dict-reference.bas"
#Include "window9.bi"

/'
   ******************************************
   Count the appearance frequency of letters
   ******************************************
   This program was modified based on "paul doe"s program below.
   https://www.freebasic.net/forum/viewtopic.php?f=7&p=247578&sid=1e219112395b8599409f858ab0d58029#p247578
   Dictionary Class
   by paul doe ≫ May 20, 2018 16:05
   
   '   name = pName→   Character = pCharacter
   '   address = pAddress→削除
   '   age = pAge   CountsOfCharacter = pCountsOfCharacter
   '   RegisterDictionary →RecordDictionary

   This code demonstrates an example of use for the Dictionary class.
   We're going to define a composite type (which we'll call Register, as in
   'database register'), and we're going to inherit a specific dictionary for
   this type.
   
   Also, since we'll be adding new registers to it, the garbage collection
   facilities of the base class will be used to dispose of the entries at
   instance deletion.
'/

/'
  Define a composite type, with all it's members public. This will
  represent the 'data' that our app will process.
'/
Type Record
   Public:
      Declare Constructor()
      Declare Constructor( _
         ByRef As Const String, ByVal As Integer )
     
      Declare Destructor()
     
      As String      Character
      As Integer   CountsOfCharacter
End Type

Constructor Record()
  Character = "Unknown"
  CountsOfCharacter = 0
End Constructor

Constructor Record( _
   ByRef pCharacter As Const String, ByVal pCountsOfCharacter As Integer )

   Character = pCharacter
   CountsOfCharacter = pCountsOfCharacter
End Constructor

Destructor Record()

End Destructor

/'
  A dictionary implementation to handle Records
'/
Type RecordDictionary extends Dictionary
   Public:
      Declare Constructor()
      Declare Destructor()
     
      Declare Function Add( ByRef As Const String, ByVal As Record Ptr ) As boolean
      Declare Function item( ByRef As Const String ) As Record Ptr
      Declare Sub remove( ByRef As Const String )
      Declare Function keyExists( ByRef As Const String ) As boolean
End Type

Constructor RecordDictionary()
   base()
End Constructor

Destructor RecordDictionary()

End Destructor

Function RecordDictionary.add( _
   ByRef key As Const String, ByVal value As Record Ptr ) As boolean
   
   /'
     Note that we do NOT specify a disposal callback, for all we want to do is
     *index* data, not *store* it. This is really the original intent of this
     class (the disposal callback was provided in case one doesn't have a
     centralized data management mechanism).
   '/
   Return( base.add( key, value ) )
End Function

Sub RecordDictionary.remove( ByRef key As Const String )
   base.remove( key )
End Sub

Function RecordDictionary.item( ByRef key As Const String ) As Record Ptr
   Return( Cast( Record Ptr, base.item( key ) ) )
End Function

Function RecordDictionary.keyExists( ByRef key As Const String ) As boolean
   Return( base.keyExists( key ) )
End Function

'' Sort an array of Records by CountsOfCharacter
Sub sortArray( ByVal startIndex As Integer, ByVal endIndex As Integer, array() As Record Ptr )
   Dim As Integer firstHalf, secondHalf
   Dim As Integer pivot
   
   firstHalf = startIndex
   secondHalf = endIndex
   
   '' Use the median value as pivot
   pivot = array( ( firstHalf + secondHalf ) \ 2 )->CountsOfCharacter

  Do
    '' Find < pivot
    Do While( array( firstHalf )->CountsOfCharacter < pivot )
      firstHalf = firstHalf + 1
    Loop
     
      '' Find > pivot
      Do While( array( secondHalf )->CountsOfCharacter > pivot )
         secondHalf = secondHalf - 1
      Loop
     
      '' Swap if needed
      If( firstHalf <= secondHalf ) Then
         Swap array( firstHalf ), array( secondHalf )
         
         firstHalf = firstHalf + 1
         secondHalf = secondHalf - 1
      End If
   Loop Until( firstHalf > secondHalf )
 
  '' Repeate sort until each half is sorted
   If( secondHalf > startIndex ) Then
      sortArray( startIndex, secondHalf, array() )
  End If
   
   If( firstHalf < endIndex ) Then
      sortArray( firstHalf, endIndex, array() )
   End If
End Sub

/'
   Dictionary usage example
'/

'' Create a dictionary of character and frequencies
   '' Create a dictionary to *index* the data by key
   Dim As RecordDictionary Ptr dic = New RecordDictionary()
 
   Dim As Record Ptr Records( 0 To 100 )
   Dim INPUTFILE As HANDLE
   Dim FullPass As String 
   Dim Filehandle As Integer
   Dim StringVariable As String
   Dim CountsOfCharacter As Integer
   Dim CountsOfLine As Integer
   Dim TotalCountOfCharacters As Integer
   Dim CharacterSymbol As String
   Dim Position As Integer
   Dim Counter As Integer
   Dim NumberOfCharacterTypes As Integer
   Dim Number As Integer
   
Counter = -1
   'Input a file containing the character string you want to check
'************************* Use Window 9 Open File Dialog *************************

FullPass = OpenFileRequester("Specify English text file",ExePath,"Text File(*.txt;*.csv;*.htm*)"_
+Chr(0)+"*.txt;*.csv;*.htm*"+Chr(0)+"All File(*.*)"+Chr(0)+"*.*"+Chr(0))

If FullPass<>"" Then

  '' Open the input text file.
   INPUTFILE = Read_File(FullPass)

   If INPUTFILE <> -1 Then 'Make sure the file is opened
      Close_File(INPUTFILE)
   EndIf
   
   ' Reading contents of text file
   CountsOfLine = 0
   TotalCountOfCharacters = 0

   Filehandle = FreeFile
   Open FullPass For Input As #Filehandle ' Open text file

   If Lof(Filehandle) > 0 Then
      Do Until EOF(Filehandle )     

         Line Input #Filehandle, StringVariable     ' Read 1 line
         StringVariable = Trim(StringVariable)
         CountsOfLine = Len(StringVariable)
         TotalCountOfCharacters = TotalCountOfCharacters + CountsOfLine
         
         If CountsOfLine >0 Then
            ?
            ? "CountsOfLine = " , CountsOfLine
            ? "TotalCountOfCharacters = ", TotalCountOfCharacters
            ? "StringVariable = " , StringVariable
            ?
            For Position = 1 To CountsOfLine
               CharacterSymbol = Mid(StringVariable, Position, 1)
               If Trim(CharacterSymbol) <> "" Then
                  '' We check if a key exists using the 'keyExists' method:
                  If( dic->keyExists(CharacterSymbol) = TRUE ) Then
                     'If existing, add the occurrence frequency of the character
                     Number = dic->item(CharacterSymbol)->CountsOfCharacter
                     Number = Number + 1
                     '? CharacterSymbol;
                     '? Number;
                     '? " ";
                     dic->item(CharacterSymbol)->CountsOfCharacter = Number
                  Else
                    ' This character is not registered in the dictionary. Add it to the dictionary.
                    Counter =Counter +1
                     '? Counter ;
                     '? CharacterSymbol ;
                    dic->Add( CharacterSymbol, New Record( CharacterSymbol, 1 ) )
                    Records( Counter ) = New Record( CharacterSymbol, 1 )
                  End If
                 
               End If
            Next Position
         End If

      Loop     
   Else
           GoTo HandleErrors
   End If
   
   Close #Filehandle           '' Close the file with the file number.
   
Else
   MessBox("メッセージ","ファイルが選択されませんでした!")
   End
EndIf
   
'Update frequency of occurrence of array   
NumberOfCharacterTypes = Counter

For Counter = 0 To NumberOfCharacterTypes
   CharacterSymbol = records( Counter )->Character
   Number = dic->item(CharacterSymbol)->CountsOfCharacter
   Records( Counter ) = New Record(CharacterSymbol ,Number )
Next
?
? "Input has ended . Continue with any key input."
?
Sleep()

For Counter = 0 To NumberOfCharacterTypes
  ? records( Counter )->Character ;
  ? records( Counter )->CountsOfCharacter;
  ? " " ;
Next

?
? "Updated array for sorting. Sorting will start with any key input."
?
Sleep()

'' Sort the array of records
sortArray( 0, NumberOfCharacterTypes, records() )

''Displays the number of occurrences and characters in the order of appearance frequency of characters.
For Counter= 0 To NumberOfCharacterTypes
  ? records( Counter )->Character ;
  ? records( Counter )->CountsOfCharacter
Next

' Total number of characters in input file
? "TotalCountOfCharacters = " & TotalCountOfCharacters
?
? "The number of occurrences and characters were displayed in order of appearance frequency of characters. "
? "Exit the program with any key input."
Sleep()

'' Cleanup
For Counter = 0 To UBound( Records )
  Delete( Records( Counter ) )
Next
   
Delete( dic )
End

HandleErrors:
Print "File not found"
Sleep

Image
Last edited by Makoto WATANABE on May 24, 2018 1:02, edited 1 time in total.

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 4 guests