Difference between revisions of "Sorted Dictionary Assignment"
Line 60: | Line 60: | ||
=Testing= | =Testing= | ||
==Complete== | ==Complete== | ||
− | {{SMLUnitTesting| | + | {{SMLUnitTesting|run_sorted_testing|dictionary/sorted}} |
==Without Remove== | ==Without Remove== | ||
− | sml -Ccm.verbose=false | + | sml -Ccm.verbose=false run_sorted_testing.sml --remove=false |
− | sml | + | sml run_sorted_testing.sml --remove=false |
=Pledge, Acknowledgments, Citations= | =Pledge, Acknowledgments, Citations= | ||
{{Pledge|studio-sorted-dictionary}} | {{Pledge|studio-sorted-dictionary}} |
Revision as of 15:33, 1 April 2022
Contents
Background
ref
dictionary
signature Dictionary
Code To Use
Binary Search Tree
You will undoubtedly want to use the tree you implemented in the Binary Search Tree assignment.
HasEntriesFn
The structure SortedDictionary has been setup to re-use functor HasEntriesFn from the Chained Dictionary exercise.
Code To Implement
structure SortedDictionary
SortedDictionary must:
- have O(lg N) expected performance for
find
,insert
, 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 :> SORTED_DICTIONARY
<nowiki>signature SORTED_DICTIONARY = sig include DICTIONARY type ''k compare_function = (''k*''k) -> order val create : ''k compare_function -> (''k,'v) dictionary end
structure TypeHolder
Change the definition of type (''k,'v) dictionary to support SortedDictionary.
Recall that BinarySearchTree.tree has two generic types 'a and 'k.
structure TypeHolder = struct (* TODO: replace unit with the type you decide upon *) type (''k,'v) dictionary = unit end
NOTE: the sorted dictionary is mutable.
structure SortedHasEntries
structure SortedHasEntries = HasEntriesFn (struct type (''k,'v) dictionary = (''k,'v) TypeHolder.dictionary fun entries(dict : (''k,'v) dictionary) : (''k*'v) list = raise Fail "NotYetImplemented" end)
entries
Define the entries method so we can take advantage of the keys
and values
functions you implemented on functor HasEntriesFn
.
functions
create
fun create(cmp : ''k compare_function) : (''k,'v) dictionary = raise Fail "NotYetImplemented"
get
A function from BinarySearchTree should be useful here.
put
A function from BinarySearchTree should be useful here.
remove
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