- Implemented ordered sets by means of red-black trees.

2 files changed, 69 insertions, 0 deletions

diff --git a/stdlib/test/test/lux/data/coll/ordered.lux b/stdlib/test/test/lux/data/coll/ordered.lux
new file mode 100644
index 000000000..213a568c1
--- /dev/null
+++ b/stdlib/test/test/lux/data/coll/ordered.lux
@@ -0,0 +1,68 @@
+(;module:
+  lux
+  (lux [io]
+       (control monad)
+       (data (coll ["&" ordered]
+                   ["S" set]
+                   [list "" Fold<List>])
+             [number]
+             text/format)
+       ["R" math/random]
+       pipe)
+  lux/test)
+
+(def: gen-nat
+  (R;Random Nat)
+  (|> R;nat
+      (:: R;Monad<Random> map (n.% +100))))
+
+(test: "Sets"
+  [sizeL gen-nat
+   sizeR gen-nat
+   setL (|> (R;set number;Hash<Nat> sizeL gen-nat)
+            (:: @ map (|>. S;to-list (&;from-list number;Ord<Nat>))))
+   setR (|> (R;set number;Hash<Nat> sizeR gen-nat)
+            (:: @ map (|>. S;to-list (&;from-list number;Ord<Nat>))))
+   #let [(^open "&/") &;Eq<Set>]]
+  ($_ seq
+      (assert "I can query the size of a set."
+              (n.= sizeL (&;size setL)))
+
+      (assert "Converting sets to/from lists can't change their values."
+              (|> setL
+                  &;to-list (&;from-list number;Ord<Nat>)
+                  (&/= setL)))
+
+      (assert "Order is preserved."
+              (let [listL (&;to-list setL)
+                    (^open "L/") (list;Eq<List> number;Eq<Nat>)]
+                (L/= listL
+                     (list;sort n.< listL))))
+
+      (assert "Every set is a sub-set of the union of itself with another."
+              (let [setLR (&;union setL setR)]
+                (and (&;sub? setLR setL)
+                     (&;sub? setLR setR))))
+
+      (assert "Every set is a super-set of the intersection of itself with another."
+              (let [setLR (&;intersection setL setR)]
+                (and (&;super? setLR setL)
+                     (&;super? setLR setR))))
+
+      (assert "Union with the empty set leaves a set unchanged."
+              (&/= setL
+                   (&;union (&;new number;Ord<Nat>)
+                            setL)))
+
+      (assert "Intersection with the empty set results in the empty set."
+              (let [empty-set (&;new number;Ord<Nat>)]
+                (&/= empty-set
+                     (&;intersection empty-set setL))))
+
+      (assert "After substracting a set A from another B, no member of A can be a member of B."
+              (let [sub (&;difference setR setL)]
+                (not (list;any? (&;member? sub) (&;to-list setR)))))
+
+      (assert "Every member of a set must be identifiable."
+              (list;every? (&;member? setL) (&;to-list setL)))
+      ))
diff --git a/stdlib/test/tests.lux b/stdlib/test/tests.lux
index c066e551e..ffe0628bf 100644
--- a/stdlib/test/tests.lux
+++ b/stdlib/test/tests.lux
@@ -45,6 +45,7 @@
                          [list]
                          [queue]
                          [set]
+                         [ordered]
                          [stack]
                          ## [vector]
                          (tree [rose]