# bag union

Write three functions computing the union of two bags; one function should take O(n^2) time, one should take O(n log n) time, and the third should take linear time.

``` \$ cat bu.rkt
#lang racket

(define (bag-element-less? e1 e2)

; Return #t iff the key in e1 is less than the key in e2.

(< (car e1) (car e2)))

(define (bag-element-merge e1 e2)

; Return a bag element representing the merger of the
; given bag elements.  The keys are assumed to match.

(cons (car e1) (+ (cdr e1) (cdr e2))))

(define (bag-sort b)

; Return a copy of the given bag with the elements in
; increasing order by key.

(sort b bag-element-less?))

(define (bag-union-nsquared b1 b2)

; Return the union of the given bags in O(n^2) time.

(define (find e b)

(let ((e-key (car e)))
(let loop ((b-hd '()) (b-tl b))

(if (null? b-tl)

(values e b)

(let ((e2 (car b-tl))
(b-tl (cdr b-tl)))

(if (eq? e-key (car e2))
(values
(bag-element-merge e e2)
(append b-hd b-tl))

(loop (cons e2 b-hd) b-tl)))))))

(let loop ((b1 b1) (b2 b2) (u '()))
(if (null? b1)

(append b2 u)

(let ((e (car b1)))
(let-values (((e b2) (find e b2)))
(loop (cdr b1) b2 (cons e u)))))))

(define (bag-union-nlogn b1 b2)

; Return the union of the given bags in O(n log n) time.

(let loop ((b1 (bag-sort b1)) (b2 (bag-sort b2)) (u '()))
(cond

((null? b1)
(append u b2))

((null? b2)
(append u b1))

(#t
(let ((e1 (car b1))
(e2 (car b2)))

(cond

((bag-element-less? e1 e2)
(loop (cdr b1) b2 (cons e1 u)))

((bag-element-less? e2 e1)
(loop b1 (cdr b2) (cons e2 u)))

(#t
(loop (cdr b1) (cdr b2) (cons (bag-element-merge e1 e2) u)))
))))))

(define (bag-union-linear b1 b2)

; Return the union of the given bags in O(n) time.

(let*
((ht (make-hash))

(let ((key (car e)))
(hash-set! ht key (+ (cdr e) (hash-ref ht key 0))))))

(for-each (lambda (e) (ht-add e)) b))))

(for-each (lambda (b) (ht-add-bag b)) (list b1 b2))
(hash-map ht (lambda (k v) (cons k v)))))

(require rackunit)

(for-each

(lambda (f)
(let ((check-same? (lambda (a b c)
(let ((ub (bag-sort (f a b))))
(check-equal? ub (bag-sort c))
(check-equal? ub (bag-sort (f b a)))))))

(check-same? '((1 . 0)) '() '((1 . 0)))
(check-same? '((1 . 1)) '((1 . 1)) '((1 . 2)))
(check-same? '((1 . 1)) '((2 . 1)) '((1 . 1) (2 . 1)))
(check-same? '((1 . 3) (5 . 3) (18 . 3)) '((2 . 3) (18 . 3) (6 . 3))
'((5 . 3) (18 . 6) (1 . 3) (2 . 3) (6 . 3)))))

(list bag-union-nsquared bag-union-nlogn bag-union-linear))

\$ racket bu.rkt

\$
```