bit-sets: efficient bitwise operations on bit-arrays

diff --git a/basis/bit-sets/authors.txt b/basis/bit-sets/authors.txt
new file mode 100644 (file)
index 0000000..1901f27
--- /dev/null
+++ b/basis/bit-sets/authors.txt
@@ -0,0 +1 @@
+Slava Pestov

diff --git a/basis/bit-sets/bit-sets-tests.factor b/basis/bit-sets/bit-sets-tests.factor
new file mode 100644 (file)
index 0000000..e77bb43
--- /dev/null
+++ b/basis/bit-sets/bit-sets-tests.factor
@@ -0,0 +1,17 @@
+IN: bit-sets.tests
+USING: bit-sets tools.test bit-arrays ;
+
+[ ?{ t f t f t f } ] [
+    ?{ t f f f t f }
+    ?{ f f t f t f } bit-set-union
+] unit-test
+
+[ ?{ f f f f t f } ] [
+    ?{ t f f f t f }
+    ?{ f f t f t f } bit-set-intersect
+] unit-test
+
+[ ?{ t f t f f f } ] [
+    ?{ t t t f f f }
+    ?{ f t f f t t } bit-set-diff
+] unit-test

diff --git a/basis/bit-sets/bit-sets.factor b/basis/bit-sets/bit-sets.factor
new file mode 100644 (file)
index 0000000..0e97968
--- /dev/null
+++ b/basis/bit-sets/bit-sets.factor
@@ -0,0 +1,29 @@
+! Copyright (C) 2009 Slava Pestov.
+! See http://factorcode.org/license.txt for BSD license.
+USING: kernel accessors sequences byte-arrays bit-arrays math hints ;
+IN: bit-sets
+
+<PRIVATE
+
+: bit-set-map ( seq1 seq2 quot -- seq )
+    [ 2drop length>> ]
+    [
+        [
+            [ [ length ] bi@ assert= ]
+            [ [ underlying>> ] bi@ ] 2bi
+        ] dip 2map
+    ] 3bi bit-array boa ; inline
+
+PRIVATE>
+
+: bit-set-union ( seq1 seq2 -- seq ) [ bitor ] bit-set-map ;
+
+HINTS: bit-set-union bit-array bit-array ;
+
+: bit-set-intersect ( seq1 seq2 -- seq ) [ bitand ] bit-set-map ;
+
+HINTS: bit-set-intersect bit-array bit-array ;
+
+: bit-set-diff ( seq1 seq2 -- seq ) [ bitnot bitand ] bit-set-map ;
+
+HINTS: bit-set-diff bit-array bit-array ;
\ No newline at end of file

diff --git a/basis/bit-sets/summary.txt b/basis/bit-sets/summary.txt
new file mode 100644 (file)
index 0000000..d27503b
--- /dev/null
+++ b/basis/bit-sets/summary.txt
@@ -0,0 +1 @@
+Efficient bitwise operations on bit arrays