min missing max


Write a function accepting an integer list l and returning a triple (a b c) such that a is the smallest element in l, c is the largest element in l, and b is the smallest element not in l such that a < b < c.

 $ cat mmm.rkt 
 #lang racket 
  
 (require rnrs/sorting-6 rackunit "utl.rkt" "priority-queue.rkt") 
  
 (define (ht-min-missing-max l) 
  
   ; Given the unsorted list of integers l, return the 
   ; triple (mn sm mx) such that mn is the smallest 
   ; integer in l, mx is the largest integer in l and 
   ; sm is the smallest integer strictly between mn and mx 
   ; not in l.  If there's no such integer, sm is undefned. 
   ; If there's no such triple, return is undefined. 
  
   (define (smallest-missing mn mx ht) 
  
     ; Given the sorted integer vector v, return the 
     ; smallest integer strictly between v's min and max 
     ; elements not in v.  Return undefined if there's 
     ; no such integer. 
  
     (let loop ((i (+ mn 1))) 
       (when (< i mx) 
         (if (hash-has-key? ht i) 
           (loop (+ i 1)) 
           i)))) 
    
   (let* 
  
     ((e (car l)) 
      (ht (make-hash (list (cons e #t))))) 
  
     (let loop ((l (cdr l)) (mn e) (mx e)) 
       (if (null? l) 
         (list mn (smallest-missing mn mx ht) mx) 
         (let ((e (car l))) 
           (hash-set! ht e #t) 
           (loop (cdr l) (min mn e) (max mx e))))))) 
  
            
 (define (pq-min-missing-max l) 
  
   ; Given the unsorted list of integers l, return the 
   ; triple (mn sm mx) such that mn is the smallest 
   ; integer in l, mx is the largest integer in l and 
   ; sm is the smallest integer strictly between mn and mx 
   ; not in l.  If there's no such integer, sm is undefned. 
   ; If there's no such triple, return is undefined. 
  
   (define (smallest-missing-element! min-q) 
  
     ; Given the minimum priority queue min-q, return the 
     ; smallest integer strictly between min-q's min and max 
     ; elements not in min-q.  Code assumes such an integer 
     ; exists. 
  
     (let loop ((min-e (pq-dq! min-q))) 
       (let ((next-min-e (+ min-e 1))) 
         (if (= next-min-e (pq-dq! min-q)) 
           (loop next-min-e) 
           next-min-e)))) 
    
   (define (largest-element! min-q) 
  
     ; Return the largest element in the given the minimum 
     ; priority queue min-q Code assumes such an element 
     ; exists. 
  
     (let loop ((le (pq-dq! min-q))) 
       (if (pq-empty? min-q) 
         le 
         (loop (pq-dq! min-q))))) 
    
  
   (let* 
  
     ((min-q (pq-new < l)) 
      (min (pq-top min-q)) 
      (sme (smallest-missing-element! min-q))) 
  
     (list min sme (largest-element! min-q)))) 
  
  
 (define (sorted-min-missing-max l) 
  
   ; Given the unsorted list of integers l, return the 
   ; triple (mn sm mx) such that mn is the smallest 
   ; integer in l, mx is the largest integer in l and 
   ; sm is the smallest integer strictly between mn and mx 
   ; not in l.  If there's no such integer, sm is undefned. 
   ; If there's no such triple, return is undefined. 
            
   (define (missing-min v) 
  
     ; Given the sorted integer vector v, return the 
     ; smallest integer strictly between v's min and max 
     ; elements not in v.  Return undefined if there's 
     ; no such integer. 
      
     (let ((n (vector-length v))) 
       (let loop ((i 1) (mm (+ (vector-ref v 0) 1))) 
         (when (< i n) 
           (let ((e (vector-ref v i))) 
             (if (= e mm) 
               (loop (+ i 1) (+ e 1)) 
               mm)))))) 
  
  
   (unless (null? l) 
     (let ((v (vector-sort < (list->vector l)))) 
       (list (vector-ref v 0) 
             (missing-min v) 
             (vector-ref v (- (vector-length v) 1)))))) 
  
  
 (let ((in '(-1 4 5 -23 24)) 
       (out '(-23 -22 24))) 
   (for-each 
     (lambda (f) (check-equal? (f in) out)) 
     (list sorted-min-missing-max ht-min-missing-max pq-min-missing-max))) 
  
  
 (define (chopped-permuted-iota n) 
   (let loop () 
       (let* ((l (permuted-iota n)) 
              (a (car l)) 
              (b (cadr l)) 
              (min-ab (min a b))) 
         (if (or (= min-ab 0) (= (max a b) (- n 1))) 
           (loop) 
           (values min-ab (cddr l)))))) 
  
 (define (run-test iters l-size f) 
   (let loop ((i 0)) 
     (when (< i iters) 
       (let-values (((mn l) (chopped-permuted-iota l-size))) 
         (check-equal? (f l) (list 0 mn (- l-size 1))) 
         (loop (+ i 1)))))) 
  
 (run-test 100 20 sorted-min-missing-max) 
 (run-test 100 20 ht-min-missing-max) 
 (run-test 100 20 pq-min-missing-max) 
  
  
 (define (time-it f N l) 
   (let loop ((t 0) (n N)) 
     (if (= n 0) 
       (round (/ t N)) 
       (let-values 
         (((a b c d) (time-apply f (list l)))) 
         (loop (+ t b) (- n 1)))))) 
  
 (define (time n l) 
   (printf "~a  ~a  ~a  ~a\n" 
     (length l) 
     (time-it sorted-min-missing-max n l) 
     (time-it ht-min-missing-max n l) 
     (time-it pq-min-missing-max n l) 
     )) 
  
 (define N 20) 
  
 (printf "n  sorted  hash table  priority queue\n" ) 
 (do ((i 100002 (+ i 100000))) ((> i 500002)) 
   (let-values (((mn l) (chopped-permuted-iota i))) 
     (time N l))) 
  
 $ mzscheme mmm.rkt 
 n  sorted  hash table  priority queue 
 100000  54  50  200 
 200000  120  121  421 
 300000  191  187  661 
 400000  257  327  917 
 500000  333  404  1174 
  
 $