1 files changed, 177 insertions, 0 deletions
diff --git a/stdlib/source/library/lux/data/collection/bits.lux b/stdlib/source/library/lux/data/collection/bits.lux
new file mode 100644
index 000000000..63e90f7c8
--- /dev/null
+++ b/stdlib/source/library/lux/data/collection/bits.lux
@@ -0,0 +1,177 @@
+(.module:
+  [library
+   [lux (#- not and or)
+    [abstract
+     [equivalence (#+ Equivalence)]]
+    [control
+     pipe]
+    [data
+     ["." maybe]
+     [collection
+      ["." array (#+ Array) ("#\." fold)]]]
+    [math
+     [number
+      ["n" nat]
+      ["." i64]]]]])
+
+(type: #export Chunk
+  I64)
+
+(def: #export chunk-size
+  i64.width)
+
+(type: #export Bits
+  (Array Chunk))
+
+(def: empty-chunk
+  Chunk
+  (.i64 0))
+
+(def: #export empty
+  Bits
+  (array.new 0))
+
+(def: #export (size bits)
+  (-> Bits Nat)
+  (array\fold (function (_ chunk total)
+                (|> chunk i64.count (n.+ total)))
+              0
+              bits))
+
+(def: #export (capacity bits)
+  (-> Bits Nat)
+  (|> bits array.size (n.* chunk-size)))
+
+(def: #export empty?
+  (-> Bits Bit)
+  (|>> size (n.= 0)))
+
+(def: #export (get index bits)
+  (-> Nat Bits Bit)
+  (let [[chunk-index bit-index] (n./% chunk-size index)]
+    (.and (n.< (array.size bits) chunk-index)
+          (|> (array.read chunk-index bits)
+              (maybe.default empty-chunk)
+              (i64.set? bit-index)))))
+
+(def: (chunk idx bits)
+  (-> Nat Bits Chunk)
+  (if (n.< (array.size bits) idx)
+    (|> bits (array.read idx) (maybe.default empty-chunk))
+    empty-chunk))
+
+(template [<name> <op>]
+  [(def: #export (<name> index input)
+     (-> Nat Bits Bits)
+     (let [[chunk-index bit-index] (n./% chunk-size index)]
+       (loop [size|output (n.max (inc chunk-index)
+                                 (array.size input))
+              output ..empty]
+         (let [idx|output (dec size|output)]
+           (if (n.> 0 size|output)
+             (case (|> (..chunk idx|output input)
+                       (cond> [(new> (n.= chunk-index idx|output) [])]
+                              [(<op> bit-index)]
+
+                              ## else
+                              [])
+                       .nat)
+               0
+               ## TODO: Remove 'no-op' once new-luxc is the official compiler.
+               (let [no-op (recur (dec size|output) output)]
+                 no-op)
+               
+               chunk
+               (|> (if (is? ..empty output)
+                     (: Bits (array.new size|output))
+                     output)
+                   (array.write! idx|output (.i64 chunk))
+                   (recur (dec size|output))))
+             output)))))]
+
+  [set   i64.set]
+  [clear i64.clear]
+  [flip  i64.flip]
+  )
+
+(def: #export (intersects? reference sample)
+  (-> Bits Bits Bit)
+  (let [chunks (n.min (array.size reference)
+                      (array.size sample))]
+    (loop [idx 0]
+      (if (n.< chunks idx)
+        (.or (|> (..chunk idx sample)
+                 (i64.and (..chunk idx reference))
+                 ("lux i64 =" empty-chunk)
+                 .not)
+             (recur (inc idx)))
+        #0))))
+
+(def: #export (not input)
+  (-> Bits Bits)
+  (case (array.size input)
+    0
+    ..empty
+
+    size|output
+    (loop [size|output size|output
+           output ..empty]
+      (let [idx (dec size|output)]
+        (case (|> input (..chunk idx) i64.not .nat)
+          0
+          (recur (dec size|output) output)
+
+          chunk
+          (if (n.> 0 size|output)
+            (|> (if (is? ..empty output)
+                  (: Bits (array.new size|output))
+                  output)
+                (array.write! idx (.i64 chunk))
+                (recur (dec size|output)))
+            output))))))
+
+(template [<name> <op>]
+  [(def: #export (<name> param subject)
+     (-> Bits Bits Bits)
+     (case (n.max (array.size param)
+                  (array.size subject))
+       0
+       ..empty
+
+       size|output
+       (loop [size|output size|output
+              output ..empty]
+         (let [idx (dec size|output)]
+           (if (n.> 0 size|output)
+             (case (|> (..chunk idx subject)
+                       (<op> (..chunk idx param))
+                       .nat)
+               0
+               (recur (dec size|output) output)
+
+               chunk
+               (|> (if (is? ..empty output)
+                     (: Bits (array.new size|output))
+                     output)
+                   (array.write! idx (.i64 chunk))
+                   (recur (dec size|output))))
+             output)))))]
+
+  [and i64.and]
+  [or  i64.or]
+  [xor i64.xor]
+  )
+
+(implementation: #export equivalence
+  (Equivalence Bits)
+  
+  (def: (= reference sample)
+    (let [size (n.max (array.size reference)
+                      (array.size sample))]
+      (loop [idx 0]
+        (if (n.< size idx)
+          (.and ("lux i64 ="
+                 (..chunk idx reference)
+                 (..chunk idx sample))
+                (recur (inc idx)))
+          #1)))))