2023年11月25日

Scala代写 | TreeMap Data Structure

本次Scala代写要求学生自己实现TreeMap数据结构。
# Homework 10 (20 Points)
The deadline for Homework 10 is Thursday, December 13, 6pm. The late submission deadline is Monday, December 17, 6pm.
The purpose of this homework assignment is to practice the use of generics.
The code template is provided in the file
src/main/scala/pl/hw10/hw10.scala
relative to the root directory of the repository. Follow the instructions in the notes for Class 2 to import the project into
InteliJ (or use your other favorite IDE or editor to work on the assignment).
The file
src/test/scala/pl/hw10/hw10Spec.scala
contains unit tests that help you to ensure that the code that you write is correct. You can run the unit tests directly from within
InteliJ: right-click on the file in the “Project” overview and choose “Run ‘hw10Spec’”. After running the test suite, the IDE will show you a summary indicating which tests failed (if any).
Alternatively, you can run the tests by executing the command `test` in the sbt shell. You can do the latter either from within the IDE or on the command line: open a terminal in the project directory and execute `sbt`. When the prompt of the sbt shell appears type `test`.
Feel free to add additional test cases to the file `hw10Spec.scala`.
## Problem 1: Generic Functional Maps (20 Points)
The goal of this homework is to implement a generic functional map data structure `TreeMap` that stores key/value pairs using binary search trees. We want our data structure to be consistent with the interface of functional maps in Scala’s standard API. This interface is described by the trait `Map[K,+A]` whose documentation you can find [here](https://www.scala-lang.org/api/current/scala/collection/Map.html). The trait takes two type parameters: `K` stands for the type of the keys stored in the map and `A` stands for the type of the associated values. Note that this trait is covariant in the value type `A`. To
simplify matters a bit, we fix the type of keys to be `Int` in our tree map implementation. That is, we will implement a class
`TreeMap[+A]` that extends `Map[Int,A]`.
The `Map` trait provides a large number of methods to interact with map data structures including complex higher-order methods to iterate over maps such as `foldLeft` and `foldRight`. Rather than implementing all of these methods from scratch, we build upon a *skeleton implementation* of a map data structure that is already provided by the Scala standard library. This skeleton implementation is given by the abstract class `AbstractMap[K,+A]` whose documentation you can
find [here](https://www.scala-lang.org/api/current/scala/collection/immutable/AbstractMap.html).
`AbstractMap` implements all of the methods of `Map` in terms of four basic methods that every concrete map data structure needs to provide:
* Adding a given key/value pair `(key, value)` into the map: this operation returns the new map with the pair `(key, value)`
inserted. If the old map already contained a binding `(key, value1)` for some other value `value1`, then `value1` is replaced by `value`.
* Deleting the key/value pair associated with a given key `key` from the map: this operation returns the new map where the pair `(key, value)` in the map has been removed if such a pair exists. Otherwise, the map is returned unchanged.
* Retrieving the value associated with a given key `key` from the map: if a pair `(key, value)` exists in the map, this operation returns `Some(value)`, otherwise `None`.
* Obtaining an *iterator* object from the map that abstractly describes a traversal over all key/value pairs stored in the map.
Your task will be to implement the first two of these methods. The other two are already implemented for you.
We implement the binary search trees that we use for our `TreeMap` data structure as an algebraic data type. In Scala, algebraic data types are implemented using so-called *case classes*.
The instances of the case class `Leaf` are the leaf nodes of the tree. That is, these objects describe empty maps. The instances of the case class `Node` are the inner nodes of the tree. They store the left and right subtrees as well as a key/value pair. The type `TreeMap` is similar to the OCaml ADT `’a tree` that we used in [Class 9](https://github.com/nyu-pl-fa18/class09#polymorphic-adts). The only difference is that `TreeMap` is covariant in its value type `A`.
Note that `Leaf` nodes extend `TreeMap[Nothing]`. The type `Nothing` is the smallest type in Scala’s type hierarchy. That is, it is a subtype of all other types. This means that `Leaf` instances are also instances of `TreeMap[A]` for any type `A`.
Similar to ADTs in OCaml, we can pattern match on instances of case classes using Scala’s match expressions, similar to match expressions in OCaml. The code template contains some examples (see methods `TreeMap.get` and `TreeMap.toList`.