Assignment 4

Due: Oct 16

1.(2 points) Create a BinaryTreeKeyNotFoundError exception.

2. (8 points) Implement a BinarySearchTree class. In some implementations people use at least two classes, a Node class and a BinarySearchTree class. The requirements of this problem are small enough that one class will be enough, but you are free to use more. Make the class a subclass of Collection. Each node in your tree contains a key and a value. This makes the tree act like a dictionary. The keys must be objects that respond to the operations <, >, <=, >=. In any single tree all the keys have to be comparable with each other. Your BinarySearchTree code does not enforce this constraint, this is the responsibility of the user of your code. The key orders the nodes in your tree. The tree does not have to be balanced. You must implement the following methods:

do: aBlock – Evaluates the block with the value from each node in the tree.

size – returns the number of nodes in the tree

at: aKey – returns the value at the node with the given key. Raises BinaryTreeKeyNotFoundError if the key is not in the tree.

at: aKey ifAbsent: aBlock - returns the value at the node with the given key. Evaluate aBlock if the key is not in the tree.

at: aKey put: anObject – Adds a new node to the tree with aKey is key and anObject as the value. The node is of course placed in the correct location in the tree.

While it is possible to implement a binary search tree using an array or ordered collection (or various other collections) this is not allowed in this assignment. Nor are you allowed to keep a parallel structure of the tree in another collection. You are to implement your own do: method without using the do: of another collection class.

3. (3 points) Write SUnit tests for the methods in problem 2.

4. (4 points) Write Smalltalk code that reads a file named ‘start’ and copies the contents to a file name ‘end’ and replaces each comma ($,) with a period ($.). So if start contains:

cat,mat

sat,bat,

rat

end will end up with:

cat.mat

sat.bat.

rat

Uses streams to parse the file contents rather than using methods like replaceAll:with: on a string.

5. (4 points) Let ‘data’ be a file that contains rows of numbers. In each row the numbers are separated by commas. Write Smalltalk code that reads the file ‘data’, sums the numbers in each row, and writes out the row sums in a file called ‘result’. Each row sum in on a separate row in the file result. So if data contained:

1,2,3

2,4,2

result would contain:

6. (8 points) Create an HtmlTable class and SUnit tests for it. An HtmlTable object holds an N*K matrix of strings. The class needs to have the following operations:

HtmlTable class>>rows: numberOfRows columns: numberOfColumns

Returns an HtmlTable object that has the given number of rows and columns.

HtmlTable>>row: rowIndex column: columnIndex

Returns the string in the given location

HtmlTable>>row: rowIndex column: columnIndex put: aString

Puts aString in the given location.

HtmlTable>>asHtml

Returns a string containing the html representation of the table.

For example:

| table |

table := HtmlTable rows: 2 columns: 2.

table

row: 1 column:1 put: ‘hi’;

row: 1 column: 2 put: ‘mom’;

row: 2 column: 1 put: ‘how’;

row: 2 column: 2 put: ‘are you’.

table asHtml

the last statement will return the string

<table>

<tr>

</tr>

<tr>

</tr>

</table>

You might find the method CharacterArray>>match: useful in your unit test(s).

7. (5 points) Create a WordStream class a subclass of ReadStream. The next method of the WordStream is to return the next word in the stream. Words are separated by space, tab, carriage return, line feed, null, form feed, period (.), comma (,) , semicolon (;), question mark (?), or the exclamation point (!). Do not return the separators. The following test shows the behavior of WordStream. Provide a better unit test(s).

testWordStream

| word |

word := WordStream on: 'cat dog,,mom'.

self

assert: word next = 'cat';

assert: word next = 'dog';

assert: word next = 'mom';

assert: word next = nil

Style

In addition to the points assigned to the problems above there will be 7 points for code style and code quality. This includes:

Using names that follow Smalltalk convention and are meaningful

Reasonable and consistent code formating

Reasonable use of Smalltalk constructs

Properly using OO and design ideas covered in class