©2007 Felleisen, Proulx, et. al.

3  Methods for Complex Class Hierarchies; Libraries

Portfolio Problems

• Methods for a grocery store

  Work out the problem 14.7 in the textbook.

• Sorting the runner’s log

  Work out the problem 15.4 (page 156) in the textbook.

• Methods for FEDEX shipping

  The shipping company from the previous assignment keeps a list of all packages ready to be shipped. Design the data definition for a list of packages and then design the methods to solve the following problems:

  • Find out if the total weight of all packages exceeds the truck weight limit. (Method name withinWeight)

  • Produce a list of all packages going to a given customer. (Method name packagesFor)

  • Produce a list of URLs for all customers for the packages in today’s shipment. Every customer’s URL should be in the list only once. (Method name customerList)

  • Sort the packages by their weight. (Method name sortByWeight)

• Methods for a Soccer Team Phone Tree

  Design the following methods for the soccer team phone tree classes:

  • Count the number of players a coach has on a team. (Method name countPlayers)

  • Produce the name of the player with the given phone number. If the phone number does not appear in the phone tree, produce an empty String. (Method name whosePhone)

  • Does one player (the caller) call another player (the callee) directly? (Method name isCallee)

    Note: If the caller is not in the phone tree, the answer is false.

Pair Programming Assignment

Binary Search Trees

3.1  Problem

Here is an HtDP data definition:

;; A Binary Search Tree (BST) is one of
;; --- empty
;; --- Node

;; A Node is (make-node Number BST BST)
(define-struct node (value left right))

;; we expect the value to be a whole number

The BST (the binary search tree) has the property that all values in the left sub-tree are smaller than the value of the node, and all values of the right subtree are larger than the value of the node. (We will not allow the same number to be a value of more than one node in the tree.)

1. Define the Java class hierarchy that represents a BST.

2. Design the method that counts the number of Nodes in a BST. (Method name count)

3. Design the method that adds the values of all nodes in the BST. (Method name totalValue)

4. Design the method that determines whether a given number is one of the node values in the BST. (Method name contains)

5. Design the method that inserts a new node with the given value into the right place in the BST. If there already exists a node with the given value, the method produces the BST that looks the same as the original one. (Method name insert)

6. Design the method that produces the smallest number recorded in the BST. (Method name first)

7. Design the method that removes the node with the smallest value from the BST. The method produces a new BST. (Method name rest)