In this assignment, you must implement a **sorted list** abstract
data type that maintains a sorted list of keys of type `ComparisonKey`.
Your implementation must use a binary search tree to represent the list.

Implement the ADT by defining a class `SortedList` that provides
the following public methods:

Name | Returns | Purpose |
---|---|---|

SortedList() |
SortedList |
A constructor; returns an empty sorted list. |

empty() |
boolean |
Determines whether the sorted list is empty. |

length() |
int |
Returns the length of the list, i.e. how many keys it contains. |

insert(ComparisonKey k) |
void |
Inserts the key k in the list; the key must not already be
in the list. |

remove(ComparisonKey k) |
void |
Removes the key k from the list; the key must be in
the list. |

findKey(ComparisonKey k) |
int |
Searches the list to see if the given key k is in it. If it is, it returns its index, otherwise it returns -1. |

keyAt(int n) |
ComparisonKey |
Returns the key that is at index n in the sorted list.
It must be the case that 1 <= n <= length(). |

print() |
void |
Prints the sorted list. Each key is on a separate line with its index. |

The index of a sorted list item is assigned as follows: index `1`
to the first item, index `2` to the second item, and so on, up to
index `length()` for the last item. For example, if we have
inserted the keys `ORY`, `JFK`, and `ZRH` in the sorted
list, then assuming that the string keys are compared in the normal way,
the sorted list will be `(JFK, ORY, ZRH)`, and the index of `JFK`
is `1, `the index of `ORY` is 2`, `and the index of
`ZHR` is 3`.`

By using a binary search tree to implement the ADT, it is possible to
perform insertion, deletion, and search in O(log n) in the average case.
Make sure your implementation achieves this. You may implement your
`SortedList` class my modifying the binary search tree implementation
discussed in class; it is available in the `a4` subdirectory of
the course directory.

Note that the `findKey` method required is different from the
one in the binary search tree implementation discussed in class; it must
return the index of the key (or `-1` if it is not found).
The `keyAt` method can be used to retrieve the key at a given index
position in the sorted list. Both methods have to search the binary
search tree. You can implement them efficiently by adding a new attribute
to tree nodes that contains `1 + `the number of nodes in the left
subtree of the node.

For debugging purposes, your class should also provide the following
methods:

Name | Returns | Purpose |
---|---|---|

printTree() |
void |
Prints the binary search tree in infix order. It indents 4 spaces for every level past the root. For each node, it prints the key, its index, and the count of nodes in its left subtree plus 1. |

main() |
void |
A test driver for the class. |

Here is an example of a run of the test driver:

`tiger 78 % java SortedList`
`Commands are:`
`e check whether the list
is empty`
`l print the length`
`i key insert the given key`
`r key remove the given key`
`f key search for key & return index`
`k index return the key at the given index`
`p print as a list`
`t print as a tree`
`q quit``
`

`? l`
`0`
`? i ORY`
`? i ZRH`
`? i JFK`
`? i MEX`
`? i BRU`
`? l`
`5`
`? p`
`1-BRU`
`2-JFK`
`3-MEX`
`4-ORY`
`5-ZRH`
`? t`
` 1-BRU-1`
` 2-JFK-2`
` 3-MEX-1`
`4-ORY-4`
` 5-ZRH-1`
`? f MEX`
`3`
`? f MAA`
`-1`
`? k 5`
`ZRH`
`? q`
`tiger 79 %`

Note that assignments are supposed to represent your own individual work. Do not misrepresent another's work as your own; it will be considered academic dishonesty if you do. If you have any questions about this please ask your course instructor.

Remember to include a copy of the marking sheet supplied as the cover
page of your report.