Dictionary data structure

Background

The struct that provides user access to dictionary data structure. This dictionary is actually an array of linked lists managed by a simple hash table.

Module structure

<source lang="fortran">

!!! Module for dictionary struct.

!
!     Note:
!     Use is made of a hash table with each table corresponding 
!     to a linked list. This should speed up most
!     operations.
!

MODULE dictionary_module

 USE list_data_module,ONLY: LIST_DATA
 USE linked_list_module,ONLY: linked_list_struct
 IMPLICIT NONE

 TYPE dictionary_struct
   INTEGER,PRIVATE :: hash_size  !! The size of hash_table.
   TYPE(linked_list_struct),PRIVATE,ALLOCATABLE :: table(:)
 CONTAINS
   PROCEDURE :: init !!! ([hash_size])
     !!!  Initialize the dictionary struct.
     !!!  "hash_size" determines the size of hash table.
     !!!  Default value of hash_size is 100.
   PROCEDURE,PRIVATE :: hashkey !!! RESULT(key) 
     !!!  Calculates the hashkey for the given key.

   PROCEDURE :: has !!! (key) RESULT(T/F)
     !!!  Check if the dict has term with given key.
     !!!  Return .TRUE. if the key exists.
     !!!  Return .FALSE. otherwise. 
   PROCEDURE :: get !!! (key) RESULT(DATA)
     !!!  Get the value of given key.
     !!!  If the key doesn't exist, give a warning message
     !!!  and return a value of "NaN".
   PROCEDURE :: add !!! (DATA) RESULT(T/F)
     !!!  Add new term to dictionary.
     !!!  If the key already exists, return .FALSE. 
     !!!  and overwrite the value as the new one.
     !!!  Otherwise, return .TRUE. and add the term. 
   PROCEDURE :: add_no_overwrite !!! (DATA) RESULT(T/F)
     !!!  Same as add, except no overwriting.
   PROCEDURE :: delete  !!! (key) RESULT(T/F)
     !!!  Delete a term with given key from the dictionary.
     !!!  Returns .TRUE. if the key is found and deleted.
   PROCEDURE :: dict2list !!!() RESULT(list)
     !!!  Converts the data stored in the dictionary into
     !!!  linked list. This kind of operation is needed if 
     !!!  you want to iterate through the dictionary to find
     !!!  something whose key is unknown.
     !!!  Beaware that the list here has to be initialized 
     !!!  before this function is called.
   PROCEDURE :: dict2list_sort_key !!!() RESULT(list)
     !!!  Same as dict2list,except that the list is sorted by the 
     !!!  value of data%val in ascending order. 
   PROCEDURE :: dict2list_sort_val !!!() RESULT(list)
     !!!  Same as dict2list,except that the list is sorted by the 
     !!!  value of data%val in ascending order. 

   FINAL :: destroy !!!() destructor.
 END TYPE dictionary_struct

CONTAINS

</source>

Hash key generation algorithm

<source lang="fortran"> ! Calculate the hash key for hash table. !

 INTEGER FUNCTION hashkey( self,key )
   IMPLICIT NONE
   CLASS(dictionary_struct),INTENT(IN) :: self    
   INTEGER, INTENT(in) :: key

   IF (.NOT.(ALLOCATED(self%table))) RETURN
   hashkey = MOD( key, self%hash_size ) + 1

 END FUNCTION hashkey

</source>