core/sets/sets.factor

   1 ! Copyright (C) 2008 Slava Pestov, Doug Coleman.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: assocs hashtables kernel sequences vectors ;
   4 IN: sets
   5
   6 : adjoin ( elt seq -- ) [ delete ] [ push ] 2bi ;
   7
   8 : conjoin ( elt assoc -- ) dupd set-at ;
   9
  10 : (prune) ( elt hash vec -- )
  11     3dup drop key? [ 3drop ] [
  12         [ drop conjoin ] [ nip push ] 3bi
  13     ] if ; inline
  14
  15 : prune ( seq -- newseq )
  16     [ ] [ length <hashtable> ] [ length <vector> ] tri
  17     [ [ (prune) ] 2curry each ] keep ;
  18
  19 : duplicates ( seq -- newseq )
  20     H{ } clone [ [ key? ] [ conjoin ] 2bi ] curry filter ;
  21
  22 : gather ( seq quot -- newseq )
  23     map concat prune ; inline
  24
  25 : unique ( seq -- assoc )
  26     [ dup ] H{ } map>assoc ;
  27
  28 : (all-unique?) ( elt hash -- ? )
  29     2dup key? [ 2drop f ] [ conjoin t ] if ;
  30
  31 : all-unique? ( seq -- ? )
  32     dup length <hashtable> [ (all-unique?) ] curry all? ;
  33
  34 : intersect ( seq1 seq2 -- newseq )
  35     unique [ key? ] curry filter ;
  36
  37 : diff ( seq1 seq2 -- newseq )
  38     unique [ key? not ] curry filter ;
  39
  40 : union ( seq1 seq2 -- newseq )
  41     append prune ;
  42
  43 : subset? ( seq1 seq2 -- ? )
  44     unique [ key? ] curry all? ;
  45
  46 : set= ( seq1 seq2 -- ? )
  47     [ unique ] bi@ = ;