Difference between revisions of "Sorted Dictionary Assignment"
(34 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
− | |||
=Code To Use= | =Code To Use= | ||
− | [[Binary_Tree_Assignment|Binary Tree | + | ==Binary Search Tree== |
+ | You will undoubtedly want to use the tree you implemented in the [[Binary_Tree_Assignment|Binary Search Tree]] assignment. | ||
+ | ==DictionaryFn== | ||
+ | The structure SortedDictionary has been setup to re-use [[Chained_Dictionary_Assignment#functor_DictionaryFn|functor DictionaryFn]] from the [[Chained_Dictionary_Assignment|Chained Dictionary]] exercise. | ||
=Code To Implement= | =Code To Implement= | ||
− | == | + | ==structure SortedDictionary== |
− | + | SortedDictionary must: | |
− | + | * have O(lg N) expected performance for <code>get</code>, <code>put</code>, and <code>remove</code>. | |
− | + | * produce <code>entries</code> and <code>keys</code> in sorted order based on the provided <code>compare_function</code>. | |
− | + | * produce <code>values</code> in the sorted order of each value's key based on the provided <code>compare_function</code>. | |
− | + | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | structure SortedDictionary = DictionaryFn(struct | ||
+ | type ''k compare_function = (''k*''k) -> order | ||
+ | |||
+ | |||
+ | (* TODO: replace unit with the type you decide upon *) | ||
+ | type (''k,'v) dictionary = unit | ||
+ | |||
+ | |||
+ | type ''k create_parameter_type = ''k compare_function | ||
+ | |||
+ | fun create(cmp : ''k compare_function) : (''k,'v) dictionary = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | |||
+ | fun get(dict : (''k,'v) dictionary, key:''k) : 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | |||
+ | fun put(dict : (''k,'v) dictionary, key:''k, value:'v) : (''k,'v) dictionary * 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | |||
+ | fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | |||
+ | fun entries(dict : (''k,'v) dictionary) : (''k*'v) list = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | |||
+ | end) | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | [[File:Sorted dictionary.svg]] | ||
+ | |||
+ | ===type dictionary=== | ||
+ | Change the definition of <nowiki>type (''k,'v) dictionary</nowiki> to support SortedDictionary. | ||
+ | |||
+ | <syntaxhighlight lang="sml"> | ||
+ | (* TODO: replace unit with the type you decide upon *) | ||
+ | type (''k,'v) dictionary = unit | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | ===type create_parameter_type=== | ||
+ | Leave create_parameter_type unchanged. SortedDictionary's create method accepts a single compare_function parameter, so <nowiki>''k compare_function</nowiki> is the correct type. | ||
+ | |||
+ | <syntaxhighlight lang="sml"> | ||
+ | type ''k create_parameter_type = ''k compare_function | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | === create === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun create(cmp : ''k compare_function) : (''k,'v) dictionary = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | === get === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun get(dict : (''k,'v) dictionary, key : ''k) : 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | A function from [[Binary_Search_Tree_Assignment#Code_to_Implement|BinarySearchTree]] should be useful here. | ||
+ | |||
+ | === put === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun put(dict : (''k,'v) dictionary, key : ''k , value : 'v) : (''k,'v) dictionary * 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | A function from [[Binary_Search_Tree_Assignment#Code_to_Implement|BinarySearchTree]] should be useful here. | ||
+ | |||
+ | === remove === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | A function from [[Binary_Search_Tree_Assignment#Code_to_Implement|BinarySearchTree]] should be useful here. | ||
+ | |||
+ | === entries === | ||
+ | <syntaxhighlight lang="sml"> | ||
+ | fun entries(dict : (''k,'v) dictionary) : (''k*'v) list = | ||
+ | raise Fail "NotYetImplemented" | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | A function from [[Binary_Search_Tree_Assignment#Code_to_Implement|BinarySearchTree]] should be useful here. | ||
=Testing= | =Testing= | ||
− | {{ | + | ==Complete== |
+ | {{SMLUnitTesting|run_sorted_testing|dictionary/sorted}} | ||
+ | ==Without Remove== | ||
+ | sml -Ccm.verbose=false run_sorted_testing.sml --remove=false | ||
+ | |||
+ | sml run_sorted_testing.sml --remove=false | ||
=Pledge, Acknowledgments, Citations= | =Pledge, Acknowledgments, Citations= | ||
{{Pledge|studio-sorted-dictionary}} | {{Pledge|studio-sorted-dictionary}} |
Latest revision as of 19:39, 14 July 2023
Contents
Code To Use
Binary Search Tree
You will undoubtedly want to use the tree you implemented in the Binary Search Tree assignment.
DictionaryFn
The structure SortedDictionary has been setup to re-use functor DictionaryFn from the Chained Dictionary exercise.
Code To Implement
structure SortedDictionary
SortedDictionary must:
- have O(lg N) expected performance for
get
,put
, andremove
. - produce
entries
andkeys
in sorted order based on the providedcompare_function
. - produce
values
in the sorted order of each value's key based on the providedcompare_function
.
structure SortedDictionary = DictionaryFn(struct
type ''k compare_function = (''k*''k) -> order
(* TODO: replace unit with the type you decide upon *)
type (''k,'v) dictionary = unit
type ''k create_parameter_type = ''k compare_function
fun create(cmp : ''k compare_function) : (''k,'v) dictionary =
raise Fail "NotYetImplemented"
fun get(dict : (''k,'v) dictionary, key:''k) : 'v option =
raise Fail "NotYetImplemented"
fun put(dict : (''k,'v) dictionary, key:''k, value:'v) : (''k,'v) dictionary * 'v option =
raise Fail "NotYetImplemented"
fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option =
raise Fail "NotYetImplemented"
fun entries(dict : (''k,'v) dictionary) : (''k*'v) list =
raise Fail "NotYetImplemented"
end)
type dictionary
Change the definition of type (''k,'v) dictionary to support SortedDictionary.
(* TODO: replace unit with the type you decide upon *)
type (''k,'v) dictionary = unit
type create_parameter_type
Leave create_parameter_type unchanged. SortedDictionary's create method accepts a single compare_function parameter, so ''k compare_function is the correct type.
type ''k create_parameter_type = ''k compare_function
create
fun create(cmp : ''k compare_function) : (''k,'v) dictionary =
raise Fail "NotYetImplemented"
get
fun get(dict : (''k,'v) dictionary, key : ''k) : 'v option =
raise Fail "NotYetImplemented"
A function from BinarySearchTree should be useful here.
put
fun put(dict : (''k,'v) dictionary, key : ''k , value : 'v) : (''k,'v) dictionary * 'v option =
raise Fail "NotYetImplemented"
A function from BinarySearchTree should be useful here.
remove
fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option =
raise Fail "NotYetImplemented"
A function from BinarySearchTree should be useful here.
entries
fun entries(dict : (''k,'v) dictionary) : (''k*'v) list =
raise Fail "NotYetImplemented"
A function from BinarySearchTree should be useful here.
Testing
Complete
source folder: | src/test/sml/dictionary/sorted |
how to run with CM.make verbosity off: | sml -Ccm.verbose=false run_sorted_testing.sml |
how to run with CM.make verbosity on: | sml run_sorted_testing.sml |
note: ensure that you have removed all printing to receive credit for any assignment.
Without Remove
sml -Ccm.verbose=false run_sorted_testing.sml --remove=false
sml run_sorted_testing.sml --remove=false
Pledge, Acknowledgments, Citations
file: | studio-sorted-dictionary-pledge-acknowledgments-citations.txt |
More info about the Honor Pledge