#lang racket
(require rackunit)

(define (setof type?)
  (λ (seq) (sequence-andmap type? seq)))

(provide (contract-out
          [epsilon char?]
          [powerset (-> set? (setof set?))]
          [dfa-transitions->function
           (-> (setof list?) (-> any/c any/c any/c))]
          [nfa-transitions->function
           (-> (setof list?) (-> any/c any/c any/c))]
          [set-disjoint? (-> set? set? boolean?)])
         [struct-out 5-tuple]
         group-by

         set-grab)


#|;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

    These are used in several modules so I have collected them here for
    convenience.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;|#

;;;;;;;;;;;
;;; UTILITY
;;;;;;;;;;;

;Implementation of Haskells' "groupBy"
(define (group-by pred xs)
  (match `(,pred ,xs)
    [(list _ '()) '()]
    [(list pred (cons x xs))
     (let-values ([(ys zs) (partition (curry pred x) xs)])
       (cons (cons x ys) (group-by pred zs)))]))

(define epsilon #\ε) ;Avoding a "magic character"

(define (powerset ss)
  (for/fold ([accum (set(set))]) ([s ss])
    (set-union accum
               (for/set ([a accum])
                        (set-add a s)))))

(check-equal? (powerset (set))
              (set (set)))

(check-equal? (powerset (set 1 2 3))
              (set
               (set) (set 1) (set 2) (set 3) (set 1 2) (set 1 3) (set 2 3) (set 1 2 3)))

;"We say that A and B are disjoint if A does not intersect B"
(define (set-disjoint? s1 s2)
  (equal? (set-intersect s1 s2) (set)))

(check-equal? (set-disjoint? (set 1 2) (set 3 4))
              #t)
(check-equal? (set-disjoint? (set 1 2) (set 3 1))
              #f)

;Used to get some arbitrary element from a set
(define (set-grab ss)
  (car (set->list ss)))

;These use the standard "5 tuple" order, which is different from the order used
;in the DFA files
(struct 5-tuple
  (states alphabet transitions start-state accept-states) #:transparent)

;;;;;;;;;;;;;;;;
;;;; TRANSITIONS
;;;;;;;;;;;;;;;;

(define (transitions->table ts)
  (define (transform t) (cons (cons (first t) (second t)) (third t)))
  (make-immutable-hash (map transform [sequence->list ts])))

(check-equal? (transitions->table '((1 2 3)))
              #hash([(1 . 2) . 3]) '(1 . 2))

;;;Not meant to be used directly - helper function for the two below it
;;;Takes a list of transitions, outputs a function
(define (fa-transitions->function error ts)
  (let ([table (transitions->table ts)])
    (λ (state input-symbol)
      (hash-ref table (cons state input-symbol) error))))

(define (dfa-transitions->function ts)
  (fa-transitions->function "" ts))

(define (nfa-transitions->function ts)
  (fa-transitions->function (set) ts))

(check-equal? [(dfa-transitions->function '((a b c))) 'a 'b]
              'c)

(check-equal? [(nfa-transitions->function `((a b ,(set 'c)))) 'a 'b]
              (set 'c))