// //------------------ DOK FILE -------------------------------------------------- +Header hashmapLib =pkg bios =title Hashmaps =short a (key,value) construction =desc Hashmaps let you associate a key of any type with a value of any type. They are very useful to search efficiently in a set of data. // // //------------------ PROTO ----------------------------------------------------- hashmap +Proto hashmap =type hashmap a1 -> a2 =mode type =pkg language =impl mcy =link =desc A hashmap has type 'hashmap a1 -> a2'. For example you may associate a floating number to a string: hashmap Float -> Str The implementation is quite simple: the hashmap is an array of lists of couple (key,value). A kind of hash function is applied to the key to determine in which list of the array the key will be added. Therefore it is necessary to specify the length of this array. This length is always a power of 2. // // //------------------ PROTO ----------------------------------------------------- hashmapCount +Proto hashmapCount =type fun (hashmap a1 -> a2) -> Int =mode function =pkg bios =impl native =link =desc This function returns the number of elements in the hashmap. Be aware that couples (key, nil) are not stored in the hashmap. // +arg src =type hashmap a1 -> a2 =desc An hashmap // +arg result =type Int =desc The number of elements in the hashmap // // //------------------ PROTO ----------------------------------------------------- hashmapCreate +Proto hashmapCreate =type fun Int -> (hashmap a1 -> a2) =mode function =pkg bios =impl native =link =desc This function creates a new hashmap. The internal implementation of hashmaps is an array of lists of couples (key, value). The length of the array is expressed by bitSize. The actual length is 2 power bitSize. When bitSize is 4, the internal array has length 2**4 = 16. The higher the bitSize, the faster the hashmap will be. // +arg bitSize =type Int =desc A number of bits // +arg result =type hashmap a1 -> a2 =desc A new hashmap // // //------------------ PROTO ----------------------------------------------------- hashmapFind +Proto hashmapFind =type fun (hashmap a1 -> a2) (fun a1 a2 -> Bool) -> a1 =mode function =pkg bios =impl mcy =link =desc This function runs through the hashmap and calls the fSearch function for each couple (key, value). When this function returns true, the search ends and the function returns the key. // +arg src =type hashmap a1 -> a2 =desc A hashmap of any type // +arg fSearch =type fun a1 a2 -> Bool =desc A lambda function which takes two parameters key and value and returns a boolean // +arg result =type a1 =desc The key // // //------------------ PROTO ----------------------------------------------------- hashmapGet +Proto hashmapGet =type fun (hashmap a1 -> a2) a1 -> a2 =mode function =pkg bios =impl native =link =desc This function searches for a couple (key, value) in the hashmap. When found, it returns the value. Otherwise it returns nil. // +arg src =type hashmap a1 -> a2 =desc A hashmap of any type // +arg key =type a1 =desc A key of this hashmap // +arg result =type a2 =desc The value associated to the key, or nil if this key is not found // // //------------------ PROTO ----------------------------------------------------- hashmapInit +Proto hashmapInit =type fun Int list [a1 a2] -> (hashmap a1 -> a2) =mode function =pkg bios =impl mcy =link =desc A new hashmap is created and filled with the couples (key, values) from the list lData. // +arg bitSize =type Int =desc A number of bits // +arg lData =type list [a1 a2] =desc A list of tuples [key value] // +arg result =type hashmap a1 -> a2 =desc A new hashmap // // //------------------ PROTO ----------------------------------------------------- hashmapMap +Proto hashmapMap =type fun (hashmap a1 -> a2) (fun a1 a2 -> a3) -> list a3 =mode function =pkg bios =impl mcy =link =desc This function runs through the hashmap src, and calls fMap for each couple (key, value) and makes a list of all its non nil results. // +arg src =type hashmap a1 -> a2 =desc A hashmap of any type // +arg fMap =type fun a1 a2 -> a3 =desc A lambda function that associates a couple (key,value) to another value of any type // +arg result =type list a3 =desc A list // // //------------------ PROTO ----------------------------------------------------- hashmapSet +Proto hashmapSet =type fun (hashmap a1 -> a2) a1 a2 -> a2 =mode function =pkg bios =impl native =link =desc This function adds a couple (key, value) into the hashmap. It removes the previous value associated to the key, if the key was already associated. On an implementation point of view, it is interesting to know that key are removed when associated to value nil. // +arg src =type hashmap a1 -> a2 =desc A hashmap of any type // +arg key =type a1 =desc A key // +arg value =type a2 =desc A value // +arg result =type a2 =desc The value // // //------------------ PROTO ----------------------------------------------------- hashmapTest +Proto hashmapTest =type fun (hashmap a1 -> a2) (fun a1 a2 -> Bool) -> Bool =mode function =pkg bios =impl mcy =link =desc This function runs through the hashmap and calls the fSearch function for each couple (key, value). When this function returns true, the search ends and the function returns true. // +arg src =type hashmap a1 -> a2 =desc A hashmap of any type // +arg fSearch =type fun a1 a2 -> Bool =desc A lambda function which takes two parameters key and value and returns a boolean // +arg result =type Bool =desc A boolean // // //------------------ PROTO ----------------------------------------------------- listFromHashmap +Proto listFromHashmap =type fun (hashmap a1 -> a2) -> list [a1 a2] =mode function =pkg bios =impl mcy =link =desc This function runs through the hashmap and build a list with all its couples (key, values). The order in the list is irrelevant, it cannot be anticipated. // +arg src =type hashmap a1 -> a2 =desc A hashmap of any type // +arg result =type list [a1 a2] =desc A list of tuples [key value]