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.

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 [[Binary_Search_Tree_Assignment#Code_to_Implement|BinarySearchTree] should be useful here.

put

A function from [[Binary_Search_Tree_Assignment#Code_to_Implement|BinarySearchTree] should be useful here.

remove

A function from [[Binary_Search_Tree_Assignment#Code_to_Implement|BinarySearchTree] should be useful here.

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