Difference between revisions of "Chained Dictionary Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
Line 117: Line 117:
  
 
=Testing=
 
=Testing=
<!--{{SMLUnitTest|single_list_and_hashed|dictionary/single_list_and_hashed}}-->
+
<!--{{SMLUnitTest|chained_testing|dictionary/single_list_and_hashed}}-->
file: <code>sml renovated_unit_test_single_list_and_hashed.sml</code>
+
file: <code>sml run_chained_testing.sml</code>
  
in folder: <code>src/test/sml/dictionary/single_list_and_hashed</code>
+
in folder: <code>src/test/sml/dictionary/chained</code>
  
 
=Pledge, Acknowledgments, Citations=
 
=Pledge, Acknowledgments, Citations=
 
{{Pledge|studio-dictionary}}
 
{{Pledge|studio-dictionary}}

Revision as of 15:31, 28 February 2022

Motivation

In this and the follow up Sorted Dictionary studio, you will build three implementations of a dictionary. Each will be a persistent, mutable data structure, so you can expect to use the ref feature of SML, either directly or via the mutable Array structure.

Background

Refs and Arrays


fun get_value_at_reference(reference : 'a ref) : 'a = 
    !reference

fun set_value_at_reference(reference : 'a ref, next_value : 'a) : 'a = 
    let
        val previous_value = !reference
        val _ = reference := next_value
    in
        previous_value
    end

(* alternate version
fun set_value_at_reference(reference : 'a ref, next_value : 'a) : 'a = 
    let
        val previous_value = !reference
    in
        ( reference := next_value
        ; previous_value )
    end
*)

Dictionary

Signature

signature DICTIONARY = sig
    type (''k,'v) dictionary
    val get : ((''k,'v) dictionary *''k) -> 'v option
    val put : ((''k,'v) dictionary *''k *'v) -> 'v option
    val remove : ((''k,'v) dictionary *''k) -> 'v option
    val entries : (''k,'v) dictionary -> (''k*'v) list
    val keys : (''k,'v) dictionary -> ''k list
    val values : (''k,'v) dictionary -> 'v list
end

Spec

get

Behaves much like java.util.Map<K,V>'s get(key) method except instead of returning null or the associated value, it returns an option.

put

Behaves much like java.util.Map<K,V>'s put(key,value) method except instead of returning null or the previously associated value, it returns an option.

remove

Behaves much like java.util.Map<K,V>'s remove(key) method except instead of returning null or the previously associated value, it returns an option.

entries

Behaves much like java.util.Map<K,V>'s entrySet() method.

keys

Behaves much like java.util.Map<K,V>'s keySet() method.

values

Behaves much like java.util.Map<K,V>'s values() method.


DictionaryUtils

All three implementations of dictionary can reuse the same functions which given a list of entries produce the keys and values.

One of List's higher order functions can be useful here. Which one is it?

fun entries_to_keys(entries : (''k*'v) list) : ''k list = 
    raise NotYetImplemented

fun entries_to_values(entries : (''k*'v) list) : 'v list =
    raise NotYetImplemented

HasEntriesFn

functor HasEntriesFn (HasEntriesParameter : sig
	type (''k,'v) dictionary
	val entries : (''k,'v) dictionary -> (''k*'v) list
end) : HAS_ENTRIES = struct
	open HasEntriesParameter

    fun keys(dict : (''k,'v) dictionary) : ''k list = 
        (* <SOLUTION> *)
        if true
        then
	        List.map (fn(key,_)=>key) (entries(dict))
        else (* </SOLUTION> *)raise Fail "NotYetImplemented"

    fun values(dict : (''k,'v) dictionary) : 'v list = 
        (* <SOLUTION> *)
        if true
        then
	        List.map (fn(_,value)=>value) (entries(dict))
        else (* </SOLUTION> *)raise Fail "NotYetImplemented"
end

HasChainingFn

functor HasChainingFn (HasChainingParameter : sig
	type (''k,'v) dictionary
	val getChainOfEntriesForKey : ((''k,'v) dictionary * ''k) -> (''k*'v) list
	val setChainOfEntriesForKey : ((''k,'v) dictionary * ''k * (''k*'v) list) -> unit
end) : HAS_CHAINING = struct
	open HasChainingParameter

SingleChained Implementation

signature SINGLE_CHAINED_DICTIONARY = sig include DICTIONARY
    val create : unit -> (''k,'v) dictionary
end

Hashtable Implementation

Hash table

Hash table 5 0 1 1 1 1 1 LL.svg

SML Array Structure

signature HASHED_DICTIONARY = sig include DICTIONARY
    type ''k hash_function = ''k -> int
    val create_hashed : (int * ''k hash_function) -> (''k,'v) dictionary
end

Testing

file: sml run_chained_testing.sml

in folder: src/test/sml/dictionary/chained

Pledge, Acknowledgments, Citations

file: studio-dictionary-pledge-acknowledgments-citations.txt

More info about the Honor Pledge