www

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs | README | LICENSE

dset.rkt (1250B)

      1 #lang racket/base
      2 
      3 ;; A dset is an `equal?`-based set, but it preserves order based on
      4 ;; the history of additions, so that if items are added in a
      5 ;; deterministic order, they come back out in a deterministic order.
      6 
      7 (provide dset
      8          dset-empty?
      9          dset->list
     10          dset-add
     11          dset-union
     12          dset-subtract
     13          dset-filter)
     14 
     15 (define dset
     16   (case-lambda
     17     [() (hash)]
     18     [(e) (hash e 0)]))
     19 
     20 (define (dset-empty? ds)
     21   (zero? (hash-count ds)))
     22 
     23 (define (dset->list ds)
     24   (map cdr
     25        (sort (for/list ([(k v) (in-hash ds)])
     26                (cons v k))
     27              <
     28              #:key car)))
     29 
     30 (define (dset-add ds e)
     31   (if (hash-ref ds e #f)
     32       ds
     33       (hash-set ds e (hash-count ds))))
     34 
     35 (define (dset-union ds1 ds2)
     36   (cond
     37    [((hash-count ds1) . > . (hash-count ds2))
     38     (dset-union ds2 ds1)]
     39    [else
     40     (for/fold ([ds2 ds2]) ([e (dset->list ds1)])
     41       (dset-add ds2 e))]))
     42 
     43 (define (dset-subtract ds1 ds2)
     44   ;; ! takes O(size(ds2)) time !
     45   (for/fold ([r (dset)]) ([e (in-list (dset->list ds1))])
     46     (if (hash-ref ds2 e #f)
     47         r
     48         (dset-add r e))))
     49 
     50 (define (dset-filter ds pred)
     51   (for/fold ([r (dset)]) ([e (in-list (dset->list ds))])
     52     (if (pred e)
     53         (dset-add r e)
     54         r)))