- Renamed lux/data/coll/ordered to lux/data/coll/ordered/set.

- Created ordered dictionary implementation, and based the set implementation upon it.

2 files changed, 122 insertions, 11 deletions

diff --git a/stdlib/test/test/lux/data/coll/ordered/dict.lux b/stdlib/test/test/lux/data/coll/ordered/dict.lux
new file mode 100644
index 000000000..8793be9c2
--- /dev/null
+++ b/stdlib/test/test/lux/data/coll/ordered/dict.lux
@@ -0,0 +1,86 @@
+(;module:
+  lux
+  (lux [io]
+       (control monad
+                eq)
+       (data [product]
+             [number]
+             (coll (ordered ["&" dict])
+                   ["s" set]
+                   ["d" dict]
+                   [list "L/" Functor<List>]))
+       ["r" math/random])
+  lux/test)
+
+(context: "Dict"
+  [size (|> r;nat (:: @ map (n.% +100)))
+   keys (r;set number;Hash<Nat> size r;nat)
+   values (r;set number;Hash<Nat> size r;nat)
+   extra-key (|> r;nat (r;filter (|>. (s;member? keys) not)))
+   extra-value r;nat
+   #let [pairs (list;zip2 (s;to-list keys)
+                          (s;to-list values))
+         sample (&;from-list number;Order<Nat> pairs)
+         sorted-pairs (list;sort (function [[left _] [right _]]
+                                   (n.< left right))
+                                 pairs)
+         sorted-values (L/map product;right sorted-pairs)
+         (^open "&/") (&;Eq<Dict> number;Eq<Nat>)]]
+  ($_ seq
+      (test "Can query the size of a dictionary."
+            (n.= size (&;size sample)))
+
+      (test "Can query value for minimum key."
+            (case [(&;min sample) (list;head sorted-values)]
+              [#;None #;None]
+              true
+
+              [(#;Some reference) (#;Some sample)]
+              (n.= reference sample)
+
+              _
+              false))
+
+      (test "Can query value for maximum key."
+            (case [(&;max sample) (list;last sorted-values)]
+              [#;None #;None]
+              true
+
+              [(#;Some reference) (#;Some sample)]
+              (n.= reference sample)
+
+              _
+              false))
+
+      (test "Converting dictionaries to/from lists cannot change their values."
+            (|> sample
+                &;entries (&;from-list number;Order<Nat>)
+                (&/= sample)))
+
+      (test "Order is preserved."
+            (let [(^open "L/") (list;Eq<List> (: (Eq [Nat Nat])
+                                                 (function [[kr vr] [ks vs]]
+                                                   (and (n.= kr ks)
+                                                        (n.= vr vs)))))]
+              (L/= (&;entries sample)
+                   sorted-pairs)))
+
+      (test "Every key in a dictionary must be identifiable."
+            (list;every? (function [key] (&;contains? key sample))
+                         (&;keys sample)))
+
+      (test "Can add and remove elements in a dictionary."
+            (and (not (&;contains? extra-key sample))
+                 (let [sample' (&;put extra-key extra-value sample)
+                       sample'' (&;remove extra-key sample')]
+                   (and (&;contains? extra-key sample')
+                        (not (&;contains? extra-key sample''))
+                        (case [(&;get extra-key sample')
+                               (&;get extra-key sample'')]
+                          [(#;Some found) #;None]
+                          (n.= extra-value found)
+
+                          _
+                          false)))
+                 ))
+      ))
diff --git a/stdlib/test/test/lux/data/coll/ordered.lux b/stdlib/test/test/lux/data/coll/ordered/set.lux
index 0ee02dea6..40b448f1e 100644
--- a/stdlib/test/test/lux/data/coll/ordered.lux
+++ b/stdlib/test/test/lux/data/coll/ordered/set.lux
@@ -2,31 +2,56 @@
   lux
   (lux [io]
        (control monad)
-       (data (coll ["&" ordered]
-                   ["S" set]
+       (data (coll (ordered ["&" set])
+                   ["s" set]
                    [list "" Fold<List>])
              [number]
              text/format)
-       ["R" math/random])
+       ["r" math/random])
   lux/test)
 
 (def: gen-nat
-  (R;Random Nat)
-  (|> R;nat
-      (:: R;Monad<Random> map (n.% +100))))
+  (r;Random Nat)
+  (|> r;nat
+      (:: r;Monad<Random> map (n.% +100))))
 
 (context: "Sets"
   [sizeL gen-nat
    sizeR gen-nat
-   setL (|> (R;set number;Hash<Nat> sizeL gen-nat)
-            (:: @ map (|>. S;to-list (&;from-list number;Order<Nat>))))
-   setR (|> (R;set number;Hash<Nat> sizeR gen-nat)
-            (:: @ map (|>. S;to-list (&;from-list number;Order<Nat>))))
-   #let [(^open "&/") &;Eq<Set>]]
+   listL (|> (r;set number;Hash<Nat> sizeL gen-nat) (:: @ map s;to-list))
+   listR (|> (r;set number;Hash<Nat> sizeR gen-nat) (:: @ map s;to-list))
+   #let [(^open "&/") &;Eq<Set>
+         setL (&;from-list number;Order<Nat> listL)
+         setR (&;from-list number;Order<Nat> listR)
+         sortedL (list;sort n.< listL)
+         minL (list;head sortedL)
+         maxL (list;last sortedL)]]
   ($_ seq
       (test "I can query the size of a set."
             (n.= sizeL (&;size setL)))
 
+      (test "Can query minimum value."
+            (case [(&;min setL) minL]
+              [#;None #;None]
+              true
+
+              [(#;Some reference) (#;Some sample)]
+              (n.= reference sample)
+
+              _
+              false))
+
+      (test "Can query maximum value."
+            (case [(&;max setL) maxL]
+              [#;None #;None]
+              true
+
+              [(#;Some reference) (#;Some sample)]
+              (n.= reference sample)
+
+              _
+              false))
+
       (test "Converting sets to/from lists can't change their values."
             (|> setL
                 &;to-list (&;from-list number;Order<Nat>)