core/hash-sets/hash-sets.factor

   1 ! Copyright (C) 2010 Daniel Ehrenberg
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: accessors assocs hashtables kernel sets sets.private
   4 sequences parser ;
   5
   6 IN: hash-sets
   7
   8 ! In a better implementation, less memory would be used
   9 TUPLE: hash-set { table hashtable read-only } ;
  10
  11 : <hash-set> ( capacity -- hash-set )
  12     <hashtable> hash-set boa ; inline
  13
  14 : >hash-set ( members -- hash-set )
  15     unique hash-set boa ; inline
  16
  17 INSTANCE: hash-set set
  18 M: hash-set in? table>> key? ; inline
  19 M: hash-set adjoin table>> dupd set-at ; inline
  20 M: hash-set delete table>> delete-at ; inline
  21 M: hash-set members table>> keys ; inline
  22 M: hash-set set-like drop dup hash-set? [ ?members >hash-set ] unless ;
  23 M: hash-set clone table>> clone hash-set boa ;
  24 M: hash-set null? table>> assoc-empty? ;
  25 M: hash-set cardinality table>> assoc-size ;
  26 M: hash-set intersect small/large sequence/tester filter >hash-set ;
  27 M: hash-set union (union) >hash-set ;
  28 M: hash-set diff sequence/tester [ not ] compose filter >hash-set ;
  29
  30 M: sequence fast-set >hash-set ;
  31 M: f fast-set drop H{ } clone hash-set boa ;
  32
  33 M: sequence duplicates
  34     dup length <hash-set> [ ?adjoin not ] curry filter ;
  35
  36 <PRIVATE
  37
  38 : (all-unique?) ( elt hash -- ? )
  39     2dup in? [ 2drop f ] [ adjoin t ] if ; inline
  40
  41 PRIVATE>
  42
  43 M: sequence all-unique?
  44     dup length <hash-set> [ (all-unique?) ] curry all? ;