#lang racket
(require csc151)
(require rackunit)
(require racket/undefined)

;; CSC-151-01 (Spring 2021, Term 1)
;; Lab: Hash Tables (Side A)
;;   https://rebelsky.cs.grinnell.edu/Courses/CSC151/2021SpT1/labs/hash-tables
;; Authors: YOUR NAMES HERE
;; Date: THE DATE HERE
;; Acknowledgements:
;;   ACKNOWLEDGEMENTS HERE

; +---------------+--------------------------------------------------
; | Provided code |
; +---------------+

;;; (common-form str) -> string?
;;;   str : string?
;;; Convert `str` to a common form for use as, say, a key in
;;; a hash table.
;;;   If provided with a non-string, just returns the value.
(define common-form
  (lambda (str)
    (if (string? str)
        (string-downcase (list->string (filter (lambda (ch)
                                                 (or (char-numeric? ch)
                                                     (char-alphabetic? ch)))
                                               (string->list str))))
        str)))

;;; (new-make-hash pairs) -> hash?
;;;   pairs : list-of pair?
;;; Create a hash table that uses the common form of the keys in pairs.
(define new-make-hash
  (lambda (pairs)
    (make-hash (map (lambda (pair)
                      (cons (common-form (car pair))
                            (cdr pair)))
                    pairs))))

;;; (new-hash-set! hash key value) -> void?
;;;   hash : hash?
;;;   key : any?
;;;   value : any?
;;; Sets a value in a hash using the common form of string keys.
(define new-hash-set!
  (lambda (hash key value)
    (hash-set! hash (common-form key) value)))

;;; (new-hash-ref! hash key) -> any?
;;;   hash : hash?
;;;   key : any?
;;; Look up a value using the common form of key.
(define new-hash-ref
  (lambda (hash key)
    (hash-ref hash (common-form key))))

;;; (new-hash-has-key? hash key) -> boolean?
;;;   hash : hash
;;;   key : any?
;;; Determine if hash has the common form of key.
(define new-hash-has-key?
  (lambda (hash key)
    (hash-has-key? hash (common-form key))))

;;; (new-directory) -> hash?
;;; Creates a directory of students usable by the following procedures.
;;; (DrRacket has a `make-directory` procedure with a different meaning,
;;; so we call this `new-directory` instead.
(define new-directory
  make-hash)

;;; (directory-add-entry! dir name phone username address) -> void?
;;;   dir : hash?
;;;   name : string?
;;;   phone : string?
;;;   address : string?
;;; Add an entry to our global student directory.
(define directory-add-entry!
  (lambda (dir name phone username address)
    (new-hash-set! dir name (vector phone username address))))

;;; (directory-lookup-phone dir name) -> string?
;;;   name : string?
;;; Look up the phone number associated with a student in our global
;;; student directory.
(define directory-lookup-phone
  (lambda (dir name)
    (and (new-hash-has-key? dir name)
         (vector-ref (new-hash-ref dir name) 0))))

;;; (directory-lookup-username dir name) -> string?
;;;   name : string?
;;; Look up the username associated with a student in our global
;;; student directory.
(define directory-lookup-username
  (lambda (dir name)
    (and (new-hash-has-key? dir name)
         (vector-ref (new-hash-ref dir name) 1))))

;;; (directory-lookup-address dir name) -> string?
;;;   name : string?
;;; Look up the address associated with a student in our global 
;;; student directory.
(define directory-lookup-address
  (lambda (dir name)
    (and (new-hash-has-key? dir name)
         (vector-ref (new-hash-ref dir name) 2))))

;;; (new-table) -> hash?
;;; Creates a table of student contact info usable by the following
;;; procedures.
(define new-table
  make-hash)

;;; (table-add-entry! table name phone username address) -> void?
;;;   table : hash?
;;;   name : string?
;;;   phone : string?
;;;   address : string?
;;; Add an entry to our global student table.
(define table-add-entry!
  (lambda (table name phone username address)
    (new-hash-set! table (string-append name "000" "phone") phone)
    (new-hash-set! table (string-append name "000" "username") username)
    (new-hash-set! table (string-append name "000" "address") address)))

;;; (table-lookup table name attribute) -> string?
;;;   table : hash?
;;;   name : string?
;;;   attribute : string?
;;; Look up the attribute (column name) for a particular name.
;;; Returns the attribute, if found, or #f if not found.
(define table-lookup
  (lambda (table name attribute)
    (let ([key (string-append name "000" attribute)])
      (and (new-hash-has-key? table key)
           (new-hash-ref table key)))))

;;; (table-lookup-phone table name) -> string?
;;;   name : string?
;;; Look up the phone number associated with a student in table.
(define table-lookup-phone
  (section table-lookup <> <> "phone"))

;;; (table-lookup-username dir name) -> string?
;;;   name : string?
;;; Look up the username associated with a student in our global
;;; student table.
(define table-lookup-username
  (section table-lookup <> <> "username"))

;;; (table-lookup-address dir name) -> string?
;;;   name : string?
;;; Look up the address associated with a student in our global
;;; student table.
(define table-lookup-address
  (section table-lookup <> <> "address"))

#| AB |#

; +-------------------------+----------------------------------------
; | Exercise 0: Preparation |
; +-------------------------+

#|
a. If you have not already done so, do the normal start-of-lab
discussion: Introduce yourselves, indicate strengths and areas to
improve, decide what to do at 4:30, etc.
|#

#|
b. Check the double dagger questions with each other.
|#

#|
c. Review the helper procedures above to ensure you understand what
they are supposed to do.  *Note that it will often be helpful for
the navigator to have those at hand.*
|#

#| A |#

; +---------------------------+--------------------------------------
; | Exercise 1: A basic table |
; +---------------------------+

#|
In the reading, we created a simple hash table of book authors.
Here are the commands we used.

    > (define book-authors (make-hash))
    > (hash-set! book-authors "The Princess Bride" "William Goldman")
    > (hash-set! book-authors "Homegoing" "Yaa Gasi")
    > (hash-set! book-authors "Moo" "Jane Smiley")
    > (hash-set! book-authors "Moo, Baa, La La La!" "Sandra Boynton")

Transfer those commands to the interactions pane.  You should
eliminate the prompts.
|#

#|
a. Add a few more book/author pairs.

<TODO: Enter the commands you used to add book/author pairs>
|#

#|
b. In the interactions pane, confirm that you can get the author
of "Moo" and "Homegoing".

<TODO: Enter the results from the interactions pane>
|#

#|
c. What do you expect as the result of the following expression?

    > (hash-ref book-authors "homegoing")

Check your answer experimentally.

<TODO: Enter the results from the interactions pane>
|#

#|
d. In the reading, we claimed that you can use `hash-set!` to change
the author associated with a title.  Verify that claim.

<TODO: Enter the results from the interactions pane>
|#

#|
e. Although we did not mention it in the reading, there is also a
procedure, `(hash-remove! hash key)` that removes a value from a
hash table.  Determine by experiment how this procedure works.

<TODO: Enter the results from the interactions pane>
|#

#|
f. What do you think happens if you try to remove a key from a hash
table that is not in the hash table?  

<TODO: Enter  your answer>

Check your answer experimentally.

<TODO: Enter the results of your experiment>
|#

; +-------------------------------------+----------------------------
; | Exercise 2: An immutable hash table |
; +-------------------------------------+

#|
Recall that you define *immutable* hash tables with a command like
the following.  (Note the period in between the key and value.)

    > (define sidekicks 
        '#hash(("Peabody" . "Sherman")
               ...))
|#

#|
a. Finish defining an immutable hash table, `sidekicks`, that associates the
names of some famous cartoon protagonists (as strings) with the
names of their sidekicks (again, as strings).

    Protagonist          Sidekick
    -----------          --------
    Peabody              Sherman 
    Yogi                 Booboo 
    Secret Squirrel      Morocco Mole 
    Tennessee Tuxedo     Chumley 
    Quick Draw McGraw    Baba Looey 
    Dick Dastardly       Muttley 
    Bullwinkle           Rocky 
    Bart Simpson         Milhouse Van Houten 
    Asterix              Obelix 
    Strong Bad           The Cheat 
|#

(define sidekicks
  '#hash(("Peabody" . "Sherman")
         ("Yogi" . "Booboo")
         ("Secret Squirrel" . "Morrocco Mole")
         ("Tennessee Tuxedo" . "Chumley")
         ("Quick Draw McGraw" . "Baba Looey")
         ("Dick Dastardly" . "Muttley")
         ("Bullwinkle" . "Rocky")
         ("Bart Simpson" . "Milhouse Van Houten")))

#|
b. Verify that you can look up a few characters in the table,
such as "Asterix" or "Yogi".

<TODO: Enter your code from the interactions pane>
|#

#|
c. Determine what happens if you try to look something up by
sidekick (e.g., "Sherman") rather than protagonist.

<TODO: Enter your code from the interactions pane>
|#

#|
d. We claimed that it is not possible to change an immutable
hash table.  Verify that claim by trying to set a value in
the table (e.g., to make "Homestar Runner" a sidekick of "Strong
Bad") and by trying to remove an entry.

<TODO: Enter the code from the interactions pane>
|#

#|
e. We claimed that the order of the key/value pairs in the table
might change from the order in which we created the table.  Check
that claim by looking at the contents of `sidekicks`.

<TODO: Enter the contents of `sidekicks` as DrRacket prints it out>
|#

; +---------------------------------------------------------+--------
; | Exercise 3: More experiments with immutable hash tables |
; +---------------------------------------------------------+

#|
a. What do you expect to happen if we try to put two values with
identical keys in an immutable hash table?

    (define more-sidekicks
      '#hash(("Scooby Doo" . "Shaggy")
             ("Scooby Doo" . "Scrappy Doo")))

<TODO: Enter your answer here>

Check your answer experimentally.  Make sure that in one of your
experiments is to look at what `more-sidekicks` looks like.

<TODO: Enter the experiments from the interactions pane>
|#

#|
b. Although we cannot use `hash-set!` and `hash-remove!` with immutable
hash tables, there are related procedures, called `hash-set` and 
`hash-remove`, that we can use.  For example,

    > (hash-set sidekicks "Strong Bad" "Homestar Runner")
    ?
    > (hash-ref sidekicks "Strong Bad")
    ?
    > (hash-remove sidekicks "Strong Bad")
    ?
    > (hash-ref sidekicks "Strong Bad")
    ?
    > sidekicks
    ?

What do you expect these two procedures to do?  What do you expect
the value of `sidekicks` to be when we're done?

<TODO: Enter your answers here>

Check your answer experimentally.

<TODO: Enter your experiments from the interactions pane>
|#

#|
c. What do you expect as the final result of the second of the
following two expressions?  (You should assume that both expressions
are evaluated and that `sidekicks` is defined as in the previous
exercise.)

    > (hash-set sidekicks "Scooby Doo" "Shaggy")
    > (hash-ref sidekicks "Scooby Doo")

<TODO: Enter your answer here>

Check your answer experimentally.

<TODO: Enter your experiment from the interactions pane>
|#

#|
d. What do you expect as the result of the following expression?

    > (hash-ref (hash-set sidekicks "Scooby Doo" "Shaggy")
                "Scooby Doo")

<TODO: Enter your answer here>

Check your answer experimentally.

<TODO: Enter your experiment from the interactions pane>
|#


#|
e. What do you expect as the final result of the second of the
following two expressions?

    > (hash-remove sidekicks "Strong Bad")
    > (hash-ref sidekicks "Strong Bad")

<TODO: Enter your answer here>

Check your answer experimentally.

<TODO: Enter your experiment from the interactions pane>
|#

#|
f. What do you expect as the result of the following expression?

    > (hash-ref (hash-remove sidekicks "Strong Bad") "Strong Bad")

<TODO: Enter your answer here>

Check your answer experimentally.

<TODO: Enter your experiment from the interactions pane>
|#

#|
g. Summarize what you've learned about immutable hash tables.

<TODO: Enter your answer here>
|#

#| B |#

; +---------------------------------------------+--------------------
; | Exercise 4: A return to mutable hash tables |
; +---------------------------------------------+

; +-----------------------------------------------+------------------
; | Exercise 5: Mutable vs. immutable hash tables |
; +-----------------------------------------------+

; +----------------------------+-------------------------------------
; | Exercise 6: Counting words |
; +----------------------------+

#| A |#

; +--------------------------+---------------------------------------
; | Exercise 7: Strange code |
; +--------------------------+

#|
a. What does the following procedure do?  For example, what do
you expect for `(seven-eh word-counts "window")`?
|#

(define seven-eh
  (lambda (hash str)
    (list str (hash-ref hash str))))

#|
b. The procedure `hash-keys` takes a hash table as input and returns
a list of all of the keys in that hash table.  Use `hash-keys` and
`length` to determine how many entries there are in `word-counts`.
|#

(define num-words
  undefined)

#|
c. What do you expect the following expression to produce?

    > (map (section seven-eh word-counts <>) 
           (sort (hash-keys word-counts) string<=?))

<TODO: Enter your answer here>

Check your answer experimentally.

<TODO: Enter your experiment from the interactions pane>
|#

#|
d. What does the following `seven-dee?` procedure do?

<TODO: Enter your answer here>
|#

(define seven-dee?
  (lambda (entry1 entry2)
    (>= (list-ref entry1 1) (list-ref entry2 1))))

#|
f. What do you expect as the result of the following?

    > (sort (map (section seven-eh word-counts <>)
                 (hash-keys word-counts))
            seven-dee?)

<TODO: Enter your answer here>

Check your answer experimentally.

<TODO: Enter your experiment from the interactions pane>
|#

#| AB |#

; +---------------------------+--------------------------------------
; | For those with extra time |
; +---------------------------+

#|
If you find that you have extra time, you might consider one or more
of the following exercises.
|#

; +------------------------------------+-----------------------------
; | Extra 1: Counting words, revisited |
; +------------------------------------+

#|
Write a procedure, `(count-words fname)`, that returns a hash table
of the word frequencies in the file named by `fname`.  As you've
likely figured out from the previous exercises, your procedure
should probably,

* Create a new hash table (most likely, with a `let`).
* Read all of the words in the file (most likely, with `file->words`).
* Use the hash table to count the words in the file (using `for-each`
  and `add-word!`).
* Return the hash table.
|#

; +----------------------------+-------------------------------------
; | Extra 2: Most common words |
; +----------------------------+

#|
Write a procedure `(most-common-words fname n)`, that reads all of
the words in the file and returns the `n` most common words in
the file.  You will likely want to create a hash table for all
of the word counts (see extra 1), turn that into a list of
word/count lists, sort that list, and take the first `n` elements.
|#