(use-modules
     (ice-9 eval-string)
     (ice-9 common-list)
     (ice-9 hash-table)
     (srfi srfi-1)
     (ice-9 rdelim))


(define *obj-string-cache* (make-hash-table 500))
(define (fast-obj-string obj)
  (let ((entry (hashq-ref *obj-string-cache* obj #f)))
    (unless entry
        (set! entry (if (symbol? obj) (symbol->string obj) (object->string obj)))
        (hashq-set! *obj-string-cache* obj entry))
    entry))

(define (sort-tuples tuples)
  (sort-list tuples
      (lambda (x y)
          (string<? (fast-obj-string (car x))
                    (fast-obj-string (car y))))))

(define (report-diff type tuple1 tuple2)
  (let ((tuple (if tuple1 tuple1 tuple2)))
     (cond ((eq? type '-) `((- . (,tuple1))))
              ((eq? type '+) `((+ . (,tuple2))))
              ((eq? type '!) `((! . (,tuple1 . (,tuple2))))))))

(define (diff-sorted-tuples tuples1 tuples2 diff)
  (cond ((and (null? tuples1) (null? tuples2)) diff)
        ((null? tuples1) (append (map (lambda (x) (report-diff '+ #f x)) tuples2) diff))
        ((null? tuples2) (append (map (lambda (x) (report-diff '- x #f)) tuples1) diff))
        (else
         (let* ((tuple1 (car tuples1))
                (tuple2 (car tuples2)))
           (cond ((equal? (car tuple1) (car tuple2))
                  (diff-sorted-tuples (cdr tuples1) (cdr tuples2)
                                      (if (equal? tuple1 tuple2) diff (append! diff (report-diff '! tuple1 tuple2)))))
                 ((string<? (fast-obj-string (car tuple1))
                            (fast-obj-string (car tuple2)))
                  (diff-sorted-tuples (cdr tuples1) tuples2 (append! diff (report-diff '- tuple1 #f))))
                 (else
                  (diff-sorted-tuples tuples1 (cdr tuples2) (append! diff (report-diff '+ #f tuple2)))))))))

(define-inlinable (diff-tuples tuples1 tuples2)
  (diff-sorted-tuples (sort-tuples tuples1) (sort-tuples tuples2) '()))

(define compare
  (let ((count 0))
     (lambda (port)
           (let ((msg  (eval-string (read-line port))))
               (diff-tuples msg msg)
               (seek port 0 SEEK_SET)
               (set! count (1+ count))
               (if (< count 10000)
                  (compare port))))))

(compare (open-input-file "data.txt"))