#lang racket
(require loudhum)
(provide (all-defined-out))

;;; File:
;;;   analysis-lab.rkt
;;; Authors:
;;;   Charlie Curtsinger
;;;   Janet Davis
;;;   Fahmida Hamid
;;;   Titus Klinge
;;;   Samuel A. Rebelsky
;;;   Jerod Weinman
;;;   YOUR NAME HERE
;;; Summary:
;;;   Procedures for the lab on analyzing procedures

; +--------------------------------+----------------------------------
; | Generalized Counter Procedures |
; +--------------------------------+

;;; Struct:
;;;   counter
;;; Fields:
;;;   counts, a hash table
(struct counter (name counts))

;;; Procedure:
;;;   make-counter
;;; Parameters:
;;;   name, a string
;;; Purpose:
;;;   Create a set of counters
;;; Produces:
;;;   counter, a counter
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   counter can be used as a parameter to the various counter
;;;   procedures.
(define make-counter
  (lambda (name)
    (counter name (make-hash))))

;;; Procedure:
;;;   counter-increment!
;;; Parameters:
;;;   counter, a counter
;;;   procname, a symbol
;;; Purpose:
;;;   count a call to the given procedure
;;; Produces:
;;;   [Nothing; called for the side effect.]
;;; Preconditions:
;;;   counter was created by make-counter (or something similar) and
;;;   has only been modified by the counter procedures.
;;; Postconditions:
;;;   (counter-lookup counter procname) gives a number one higher than it
;;;   did before.
(define counter-increment!
  (lambda (counter procname)
    (let ([counts (counter-counts counter)])
      (hash-set! counts procname (+ 1 (hash-ref counts procname 0)))
      (hash-set! counts "" (+ 1 (hash-ref counts "" 0))))))

;;; Procedure:
;;;   counter-get
;;; Parameters:
;;;   counter, a counter
;;;   procname, a symbol
;;; Purpose:
;;;   Get the number of times that counter-increment! has been called
;;;   with this procedure name.
;;; Produces:
;;;   count, a non-negative integer
;;; Preconditions:
;;;   counter was created by make-counter and has only been modified
;;;   by the counter procedures.
;;; Postconditions:
;;;   count is the number of calls to counter-increment! for procname
;;;   since (a) the last call to counter-reset-all! or to counter-reset! for
;;;   procname or (b) since the counter was created, there have been no calls 
;;;   to counter-reset-all! or to counter-reset! for this procedure.
(define counter-get
  (lambda (counter procname)
    (hash-ref (counter-counts counter) procname 0)))

;;;   counter-reset!
;;; Parameters:
;;;   counter, a counter
;;;   procname, a symbol
;;; Purpose:
;;;   Reset the counter for the given procedure.
;;; Produces:
;;;   [Nothing; called for the side effect]
;;; Preconditions:
;;;   counter was created by make-counter (or something similar) and
;;;   has only been modified by the other counter procedures.
(define counter-reset!
  (lambda (counter procname)
    (let ([counts (counter-counts counter)])
      (hash-set! counts "" (- (hash-ref counts "" 0)
                              (hash-ref counts procname 0)))
      (hash-remove! counts procname))))

;;; Procedure:
;;;   counter-reset-all!
;;; Parameters:
;;;   counter, a counter
;;; Purpose:
;;;   reset the counters
;;; Produces:
;;;   [Nothing; called for the side effect]
;;; Preconditions:
;;;   counter was created by make-counter (or something similar) and
;;;   has only been modified by the other counter procedures.
;;; Postconditions:
;;;   (counter-get counter procname) gives 0 for all procedure names.
(define counter-reset-all!
  (lambda (counter)
    (hash-clear! (counter-counts counter))))

;;; Procedure:
;;;   counter-print
;;; Parameters:
;;;   counter, a counter
;;; Purpose:
;;;   Print out the information associated with the counter.
;;; Produces:
;;;   [Nothing; called for the side effect.]
;;; Preconditions:
;;;   counter was created by make-counter and has only been modified
;;;   by the various counter procedures.
;;; Postconditions:
;;;   * counter is unchanged.
;;;   * The output port now contains information on counter.
(define counter-print
  (lambda (counter)
    (let ([counts (counter-counts counter)])
      (display "Counts for ")
      (display (counter-name counter))
      (newline)
      (display "  Total: ")
      (display (hash-ref counts "" 0))
      (newline)
      (hash-for-each counts
                     (lambda (proc count)
                       (when (not (eq? proc ""))
                         (display "  ")
                         (display proc)
                         (display ": ")
                         (display count)
                         (newline)))))))

(define animals (list "armadillo" "badger" "capybara" "donkey" "emu"))

; +-------------------+-----------------------------------------------
; | Specific Counters |
; +-------------------+

(define AF (make-counter "experiments with alphabetically-first"))

; +--------------------------+----------------------------------------
; | Finding the first string |
; +--------------------------+

;;; Procedure:
;;;   first-of-two
;;; Parameters:
;;;   str1, a string
;;;   str2, a string
;;; Purpose:
;;;   Find the alphabetically first of two strings.
;;; Produces:
;;;   first, a string
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * first is either str1 or str2
;;;   * (string-ci<= first str1)
;;;   * (string-ci<= first str2)
(define first-of-two
  (lambda (str1 str2)
    (if (string-ci<=? str1 str2)
        str1
        str2)))

;;; Procedure:
;;;   alphabetically-first
;;; Parameters:
;;;   strings, a list of strings
;;; Purpose:
;;;   Finds the alphabetically first string in the list.
;;; Produces:
;;;   first, a string
;;; Preconditions:
;;;   strings contains at least one element
;;; Postconditions:
;;;   * first is an element of strings
;;;   * For any string, str, in strings

(define alphabetically-first-1
  (lambda (strings)
    (counter-increment! AF 'alphabetically-first-1)
    (cond
      [(null? (cdr strings))
       (car strings)]
      [(string-ci<=? (car strings) (alphabetically-first-1 (cdr strings)))
       (car strings)]
      [else
       (alphabetically-first-1 (cdr strings))])))

(define alphabetically-first-2
  (lambda (strings)
    (counter-increment! AF 'alphabetically-first-2)
    (if (null? (cdr strings))
        (car strings)
        (first-of-two (car strings)
                      (alphabetically-first-2 (cdr strings))))))


(define alphabetically-first-3
  (lambda (strings)
    (let kernel ([first-so-far (car strings)]
                 [remaining (cdr strings)])
      (if (null? remaining)
          first-so-far
          (kernel (first-of-two first-so-far (car remaining))
                  (cdr remaining))))))

(define alphabetically-first-4
  (lambda (strings)
    (when (not (all-string? strings))
      (error "alphabetically-first: expects a list strings; received" strings))
    (if (null? (cdr strings))
        (car strings)
        (first-of-two (car strings)
                      (alphabetically-first-4 (cdr strings))))))

(define alphabetically-first alphabetically-first-4)

;;; Procedure:
;;;   all-string?
;;; Parameters:
;;;   lst, a list
;;; Purpose:
;;;   Determine if all elements of lst are strings.
;;; Produces:
;;;   ok?, a Boolean
(define all-string?
  (lambda (lst)
    (or (null? lst)
        (and (string? (car lst))
             (all-string? (cdr lst))))))

; +-----------------+-------------------------------------------------
; | List Procedures |
; +-----------------+

;;; Procedure:
;;;   list-append
;;; Parameters:
;;;   front, a list of size n
;;;   back, a list of size m
;;; Purpose:
;;;   Put front and back together into a single list.
;;; Produces:
;;;   appended, a list of size n+m.
;;; Preconditions:
;;;   front is a list [Unverified]
;;;   back is a list [Unverified]
;;; Postconditions:
;;;   For all i, 0 <= i < n,
;;;    (list-ref appended i) is (list-ref front i)
;;;   For all i, n <= i < n+m
;;;;   (list-ref appended i) is (list-ref back (- i n))
(define list-append
  (lambda (front back)
    (if (null? front)
        back
        (cons (car front) (list-append (cdr front) back)))))

;;; Procedure:
;;;   list-reverse
;;; Parameters:
;;;   lst, a list
;;; Purpose:
;;;   Reverse the list
;;; Produces:
;;;   tsl, a list
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * (length tsl) = (length lst)
;;;   * For all i, 0 <= i < (length lst)
;;;     (list-ref tsl i) = (list-ref lst (- (length tsl) i 1))
(define list-reverse-1
  (lambda (lst)
    (if (null? lst)
        null
        (list-append (list-reverse-1 (cdr lst)) (list (car lst))))))

(define list-reverse-2
  (lambda (lst)
    (let kernel ([reversed null]
                 [remaining lst])
      (if (null? remaining)
          reversed
          (kernel (cons (car remaining) reversed)
                  (cdr remaining))))))

(define list-reverse list-reverse-2)