Sorted Dictionary Assignment

Background

ref

How to use ref

dictionary

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, 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 :> 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.

structure TypeHolder = struct
	(* TODO: replace unit with the type you decide upon *)
	type (''k,'v) dictionary = unit
end

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"

type (''k,'v) dictionary

We recall that BinarySearchTree.tree has two generic types 'a and 'k.

type ('a,'k) tree

'a represents the type of the contents of each node. 'k represents the type of the key for each node.

To implement a (''k,'v) SortedDictionary.dictionary with a BinarySearchTree.tree, what is the type of the contents at each node?

What is the type of the key for your BinarySearchTree.tree?

The answers to these questions will be instrumental in defining your type in the SortedDictionary structure:

(* TODO: replace unit with the type you decide upon *)
type (''k,'v) dictionary = unit

NOTE: the sorted dictionary is mutable.

create

fun create(cmp : ''k compare_function) : (''k,'v) dictionary
    raise NotYetImplemented

Testing

file: sml run_unit_test_sorted_dictionary.sml

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

Pledge, Acknowledgments, Citations

file:

studio-sorted-dictionary-pledge-acknowledgments-citations.txt

More info about the Honor Pledge