Difference between revisions of "Sorted Dictionary Assignment"

From CSE425S Wiki
Jump to navigation Jump to search
 
(17 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
=Background=
 
−
==ref==
 
−
[[SML_Mutable_Ref|How to use <code>ref</code>]]
 
−
 
−
{{:Chained_Dictionary_Assignment#Code_To_Investigate}}
 
−
 
 
=Code To Use=
 
=Code To Use=
 
==Binary Search Tree==
 
==Binary Search Tree==
 
You will undoubtedly want to use the tree you implemented in the [[Binary_Tree_Assignment|Binary Search Tree]] assignment.
 
You will undoubtedly want to use the tree you implemented in the [[Binary_Tree_Assignment|Binary Search Tree]] assignment.
−
==HasEntriesFn==
+
==DictionaryFn==
−
[[Chained_Dictionary_Assignment#functor_HasEntriesFn|functor HasEntriesFn]]
+
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=
Line 15: Line 9:
 
SortedDictionary must:
 
SortedDictionary must:
  
−
* have O(lg N) expected performance for find, insert, and remove.
+
* 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>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>.
 
* produce <code>values</code> in the sorted order of each value's key based on the provided <code>compare_function</code>.
  
−
<nowiki>structure SortedDictionary :> SORTED_DICTIONARY</nowiki>
+
<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"
  
−
<nowiki> <nowiki>signature SORTED_DICTIONARY = sig include DICTIONARY
+
end)
−
    type ''k compare_function = (''k*''k) -> order
+
</syntaxhighlight>
−
    val create : ''k compare_function -> (''k,'v) dictionary
+
 
−
end</nowiki>
+
[[File:Sorted dictionary.svg]]
  
−
=== structure TypeHolder ===
+
===type dictionary===
 
Change the definition of <nowiki>type (''k,'v) dictionary</nowiki> to support SortedDictionary.
 
Change the definition of <nowiki>type (''k,'v) dictionary</nowiki> to support SortedDictionary.
  
−
<nowiki>structure TypeHolder = struct
+
<syntaxhighlight lang="sml">
−
(* TODO: replace unit with the type you decide upon *)
+
(* TODO: replace unit with the type you decide upon *)
−
type (''k,'v) dictionary = unit
+
type (''k,'v) dictionary = unit
−
end</nowiki>
+
</syntaxhighlight>
  
−
=== structure SortedHasEntries ===
+
===type create_parameter_type===
−
  <nowiki>structure SortedHasEntries = HasEntriesFn (struct
+
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.
−
type (''k,'v) dictionary = (''k,'v) TypeHolder.dictionary
 
−
fun entries(dict : (''k,'v) dictionary) : (''k*'v) list =
 
−
raise Fail "NotYetImplemented"
 
−
end)</nowiki>
 
−
====entries====
 
−
Define the entries method so we can take advantage of the <code>keys</code> and <code>values</code> functions you implemented on <code>functor HasEntriesFn</code>.
 
  
−
=== create function ===
+
<syntaxhighlight lang="sml">
−
<nowiki>fun create(cmp : ''k compare_function) : (''k,'v) dictionary =
+
type ''k create_parameter_type = ''k compare_function
−
raise Fail "NotYetImplemented"</nowiki>
+
</syntaxhighlight>
  
−
===type <nowiki>(''k,'v)</nowiki> dictionary===
+
=== create ===
−
We recall that BinarySearchTree.tree has two generic types <code>'a</code> and <code>'k</code>. 
+
<syntaxhighlight lang="sml">
 +
fun create(cmp : ''k compare_function) : (''k,'v) dictionary =  
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
−
<nowiki>type ('a,'k) tree</nowiki>
+
=== get ===
 +
<syntaxhighlight lang="sml">
 +
fun get(dict : (''k,'v) dictionary, key : ''k) : 'v option =
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
−
<code>'a</code> represents the type of the contents of each node.  <code>'k</code> represents the type of the key for each node.
+
A function from [[Binary_Search_Tree_Assignment#Code_to_Implement|BinarySearchTree]] should be useful here.
  
−
To implement a <nowiki>(''k,'v) SortedDictionary.dictionary</nowiki> with a BinarySearchTree.tree, what is the type of the contents at each node?
+
=== put ===
 +
<syntaxhighlight lang="sml">
 +
fun put(dict : (''k,'v) dictionary, key : ''k , value : 'v) : (''k,'v) dictionary * 'v option =
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
−
What is the type of the key for your BinarySearchTree.tree?
+
A function from [[Binary_Search_Tree_Assignment#Code_to_Implement|BinarySearchTree]] should be useful here.
  
−
The answers to these questions will be instrumental in defining your type in the SortedDictionary structure:
+
=== remove ===
 +
<syntaxhighlight lang="sml">
 +
fun remove(dict : (''k,'v) dictionary, key : ''k) : (''k,'v) dictionary * 'v option =
 +
        raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
−
<nowiki>(* TODO: replace unit with the type you decide upon *)
+
A function from [[Binary_Search_Tree_Assignment#Code_to_Implement|BinarySearchTree]] should be useful here.
−
type (''k,'v) dictionary = unit</nowiki>
 
  
−
NOTE: the sorted dictionary is mutable.
+
=== entries ===
 +
<syntaxhighlight lang="sml">
 +
fun entries(dict : (''k,'v) dictionary) : (''k*'v) list =
 +
raise Fail "NotYetImplemented"
 +
</syntaxhighlight>
  
−
===create===
+
A function from [[Binary_Search_Tree_Assignment#Code_to_Implement|BinarySearchTree]] should be useful here.
−
<nowiki>fun create(cmp : ''k compare_function) : (''k,'v) dictionary
 
−
    raise NotYetImplemented</nowiki>
 
  
 
=Testing=
 
=Testing=
−
<!--{{SMLUnitTest|sorted_dictionary|dictionary}}-->
+
==Complete==
−
file: <code>sml run_unit_test_sorted_dictionary.sml</code>
+
{{SMLUnitTesting|run_sorted_testing|dictionary/sorted}}
 +
==Without Remove==
 +
sml -Ccm.verbose=false run_sorted_testing.sml --remove=false
  
−
in folder: <code>src/test/sml/dictionary/sorted</code>
+
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

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, and remove.
  • produce entries and keys in sorted order based on the provided compare_function.
  • produce values in the sorted order of each value's key based on the provided compare_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)

Sorted dictionary.svg

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.

SML Error Messages

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

Retrieved from "http://classes.engineering.wustl.edu/cse425s/index.php?title=Sorted_Dictionary_Assignment&oldid=2219"