CS 136 Assignment 8

Due Wednesday November 14, 2012, 11:59am. Half marks for late submissions. No hand-marking.

For this assignment you will use an ordered set ADT ordered-set.rkt which is supplied to you. You will not modify ordered-set.rkt, but you will modify total-order.rkt, which is required by ordered-set.rkt and defines the total order for the ADT. By altering total-order.rkt, you are able to store different types of elements in an ordered set, as well as define how they should be ordered. We make one restriction to your modification: If you choose to modify the to-elem struct inside total-order.rkt, you must make sure it still has a field called data.

Remember that for a total order, we need a set of items and an operation that allows us to order all the items maintaining the properties of totality, antisymmetry, and transitivity. As an example, here is a trivial (i.e. inadequate) test program that requires total-order.rkt and ordered-set.rkt.

The file ordered-set.rkt provides the following functions:

;; In all functions below, e must be a to-elem struct
;; os-empty         the empty set
;; (os-empty? s)    produces true if s is empty, false otherwise
;; (os-singleton e) produces a set with one element e.
;; (os-member? s e)  produces true if e is a member of s; false otherwise
;; (os-union s t)   produces union of s and t in time 
;;                                  O(min(|s|,|t|) log max(|s|,|t|))
;; (os-intersection s t) produces intersection of s and t in time 
;;                                  O(min(|s|,|t|) log max(|s|,|t|))
;; (os-difference s t)   produces difference  s \ t in time 
;;                                  O(min(|s|,|t|) log max(|s|,|t|))
;; (os-min s)       produces the to-min element of s, 
;;                        or to-min-ident if s is empty
;;                        running time:  O(log |s|)
;; (os-max s)       produces the to-max element of s,
;;                        or to-max-ident if s is empty
;;                        running time:  O(log |s|)
;; (os-after s e)   produces the to-min element of s which is to> than e,
;;                        or to-min-ident if there is no such element
;;                        running time:  O(log |s|)
;; (os-before s e)  produces the to-max element of s which is to< than e
;;                        or to-max-ident if there is no such element
;;                        running time:  O(log |s|)
;; (os-op s)          produces the result of applying the binary operator
;;                        to-op to all e in s. If s is empty, returns the to-op-ident
;;                        similar idea to foldl
;;                        running time:  O(1)

You will also need to write a main program that will read from input. Recall that in Racket, we use tail recursion to do repetition (instead of iteration) and will need to use (read). Here is some sample code to get you started. To submit multiple files to Marmoset, you must combine them using zip. For example, to submit total-order.rkt and also main.rkt, execute the following command:

   zip submit.zip main.rkt total-order.rkt

Assignment 8 Problem 1 [10 marks]. Files: total-order.rkt, main.rkt

Sample Input

1
3
2
1

Output for Sample Input

1
2
3
3
2
1

Assignment 8 Problem 2 [10 marks]. Files: total-order.rkt, main.rkt

Sample Input 1

1
3
2
1

Output for Sample Input 1

2
1
3
3
1
2

Sample Input 2

2
4
6

Output for Sample Input 2

4
2
6
6
2
4

Assignment 8 Problem 3 [10 marks]. Files: total-order.rkt, main.rkt

Sample Input

1
3
2
1

Output for Sample Input

1 2
2 1
3 1

Assignment 8 Problem 4 [10 marks]. Files: total-order.rkt, scoreboard.rkt

• score symbol number
  Record number as the score for the player whose name is symbol. No output is produced. Assume number is an integer between -999999999 and 999999999.
• best symbol
  Output a line containing best symbol number where number is the best score recorded so far for the player whose name is symbol.
  Output ? instead of number if no score has been recorded for the player.
• highscore
  Output a line containing highscore number where number is the highest score recorded for any player so far. Output highscore ? if no score has been recorded.

Sample Input

score Fred 10
score Wilma 20
score Fred 20
highscore
score Betty 30
highscore
best Fred
score Fred 25
best Fred
best Barney

Output for Sample Input

highscore 20
highscore 30
best Fred 20
best Fred 25
best Barney ?

Assignment 8 Problem 5 [10 marks]. Files: total-order.rkt scoreboard.rkt

• disqualify symbol
  Remove all scores for the player whose name is symbol. Subsequent highscore commands will exclude the scores achieved by this player. A disqualified player is not banned from the game but will have to start over.

Sample Input

score Fred 10
score Wilma 20
score Fred 20
highscore
score Betty 30
highscore
best Fred
score Fred 25
best Fred
disqualify Betty
highscore
best Betty

Output for Sample Input

highscore 20
highscore 30
best Fred 20
best Fred 25
highscore 25
best Betty ?

Assignment 8 Problem 6 [10 marks]. Files: total-order.rkt, scoreboard.rkt

• leaders
  Output a line containing leaders followed by the names of all players tied for the highest score. Output a single space before each player's name. The names should be in lexicographic order according to their ASCII representation. If there are no leaders, output leaders ?.

Sample Input

score Fred 10
score Wilma 20
score Fred 20
leaders

Output for Sample Input

leaders Fred Wilma