MP6

cs497rej - Homework 6

Homework 6. Collections

Smalltalk neophytes only iterate over collections using do:. Veterans make full use of the Collection enumeration protocol, including

collect:

detect:

detect: ifNone:

select:

reject:

inject: into:

Dictionaries and SequenceableCollections have more enumeration messages, but this is the standard Collection enumeration protocol.

Part 1. Using the Collection protocol on strings

Exercise 1.1. Create a class category CS598rej-HW6. Add one class called StringManipulator. Using the richer set for enumarating over collections (String is a collection), implement the following methods as instance methods in StringManipulator:

collectToLowercase: Converts an argument string of alphabetic characters to entirely lowercase.

detectFirstLowercase: Finds the first lowercase character in an argument string.

selectCapitalLetters: Takes a string as an argument and returns a string consisting of all the capital letters in the argument (make use of select: message)

injectMinimumCharacter: Finds the minimum character in the String passed as argument (make use of inject: into: message)

dollarValue: Finds the "dollar value" of a string. The dollar value of a string is the sum of the dollar values of its characters. The dollar value of "a" (and "A") is 1, of "b" (and "B") is 2, ..., of "z" (and "Z") is 26, and all nonalphabetic characters are worth 0.

encode: Encodes the argument string using the first grade code, which is to replace "a" with "b", "b" with "c", etc "z" with "a", "Z" with "A". All non-alphabetic characters are unchanged.

Read class Character, especially the "accessing", "converting" and "testing" protocols.

We provided for you some test cases for this part (found in class StringManipulatorTestCase at the bottom of this page).

Part 2. Extending class Set

Class Set is one of the Collection classes, and it implements typical Collection protocol like do:, add:, remove:, and collect:. It also implements typical operations on sets like intersection and union. Study those methods in the image.

For this part, you will create a class MySet, subclass of Set that implements method setComplement. This method takes no arguments and returns the complement of the set. Note that a complement makes sense only if there exists a Universal set. Define a universal set for the class MySet that is common to all instances of that class. (This is an ambiguous statement inviting you to explore different ways of storing the universal set.)

Implement this method in a Test-Driven-Development style. Before writing the code of setComplement, write the test cases for it. Add a test case class called SetComplementTestCase. Add the following test case methods to it:

testSetComplement - tests method setComplement for a set that is a subset of the universal set.
testBadSetComplement - tests method setComplement with a set that is not a subset of the universal set (there are many error cases to consider here). No mathematician would ever consider this reasonable, but fortunately, this is CS.
testDeMorgansLaws - tests method setComplement along with union: and intersection: as used in DeMorgan's laws.

After you write your test cases, add a protocol 'set operations' to MySet, and define your new method there.

Here are some operations on sets that you might want to use:

Inherited from Object

copy - makes a copy of any object, including a Set

Inherited from Collection

addAll: - add all the elements of the argument to the receiver

select: - select the subset that cause the block-argument to evaluate true

Inherited from Set

add: - add the argument to the receiver

remove:ifAbsent: - remove the argument from the receiver

do: - evaluate the block that is the argument for each element in the receiver

includes: - returns true if the argument is an element of the receiver, else false

Part 3. Binary tree

Exercise 3.1. Build a BinaryTree class. A binary search tree is a collection that is made up of a set of nodes. Each node has two children and a value. The particular BinaryTree class that you will implement should be ordered so that the value stored in a node is greater than or equal to the values of its right-most child or any of its children. Likewise, the value stored in a node is less than or equal to the values of its left-most child or any of its children (notice that our BinaryTree is the mirror-image of the regular BinaryTree you might have implemented in other programming classes). The trick is to note that each node is itself a binary tree, so you only need to make one class, BinaryTree, which is also the class of your nodes. Make your binary tree class a subclass of Collection . Implement the following messages:

with: aValue - an 'instance creation' method (on the class side) that creates a brand new BinaryTree with a single node whose value is aValue.
add: aValue - add any object to the tree, as long as they are the same class and understand the '<' and' >' messages.
elementsInOrder - return a collection of the elements of the tree in ascending order.
do: - Note that do: should evaluate the block only for the values of the nodes, not the nodes themselves.

As with Part 2, build your test cases before writing the BinaryTree code. Make a test case for each of the methods in the list above.

Exercise 3.2. Having do: implemented in the binary tree, it should be able to understand size, addAll: , and inject: into: . Test it to make sure. It might be able to understand collect: and select: . If not, make sure you can explain why.

Deliverables

Try to use small methods described by an intention-revealing selector.

When you fileOut the classes, please just paste the text into the e-mail. Do not send as an attachment.

Part 1. fileOut the "StringManipulator" class that you created and I will look at that. Use the provided test case to verify your answers.

Part 2. fileOut the "MySet" class and also your test cases. For each test case (testSetComplemet, testBadSetComplement, testDeMorgansLaws) make sure that you test several different inputs (null set, etc).

Part 3. fileOut the BinaryTree class and also your test cases. As with part2, make sure that your tests cover different cases.
For part 3.2, you can create some more test cases just to show me that size, addAll, works.

Files

StringManipulatorTestCase.st

Link to this Page

Machine Problems last edited on 14 May 2008 at 4:25:53 pm by c-98-212-224-168.hsd1.il.comcast.net