From 024d9990d005971e5c9a238bda8de620cd3b2fc1 Mon Sep 17 00:00:00 2001 From: Eduardo Julian Date: Fri, 23 Jun 2017 19:48:16 -0400 Subject: - Renamed lux/data/coll/ordered to lux/data/coll/ordered/set. - Created ordered dictionary implementation, and based the set implementation upon it. --- stdlib/test/test/lux/data/coll/ordered.lux | 67 ------------------ stdlib/test/test/lux/data/coll/ordered/dict.lux | 86 +++++++++++++++++++++++ stdlib/test/test/lux/data/coll/ordered/set.lux | 92 +++++++++++++++++++++++++ 3 files changed, 178 insertions(+), 67 deletions(-) delete mode 100644 stdlib/test/test/lux/data/coll/ordered.lux create mode 100644 stdlib/test/test/lux/data/coll/ordered/dict.lux create mode 100644 stdlib/test/test/lux/data/coll/ordered/set.lux (limited to 'stdlib/test') diff --git a/stdlib/test/test/lux/data/coll/ordered.lux b/stdlib/test/test/lux/data/coll/ordered.lux deleted file mode 100644 index 0ee02dea6..000000000 --- a/stdlib/test/test/lux/data/coll/ordered.lux +++ /dev/null @@ -1,67 +0,0 @@ -(;module: - lux - (lux [io] - (control monad) - (data (coll ["&" ordered] - ["S" set] - [list "" Fold]) - [number] - text/format) - ["R" math/random]) - lux/test) - -(def: gen-nat - (R;Random Nat) - (|> R;nat - (:: R;Monad map (n.% +100)))) - -(context: "Sets" - [sizeL gen-nat - sizeR gen-nat - setL (|> (R;set number;Hash sizeL gen-nat) - (:: @ map (|>. S;to-list (&;from-list number;Order)))) - setR (|> (R;set number;Hash sizeR gen-nat) - (:: @ map (|>. S;to-list (&;from-list number;Order)))) - #let [(^open "&/") &;Eq]] - ($_ seq - (test "I can query the size of a set." - (n.= sizeL (&;size setL))) - - (test "Converting sets to/from lists can't change their values." - (|> setL - &;to-list (&;from-list number;Order) - (&/= setL))) - - (test "Order is preserved." - (let [listL (&;to-list setL) - (^open "L/") (list;Eq number;Eq)] - (L/= listL - (list;sort n.< listL)))) - - (test "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)))) - - (test "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)))) - - (test "Union with the empty set leaves a set unchanged." - (&/= setL - (&;union (&;new number;Order) - setL))) - - (test "Intersection with the empty set results in the empty set." - (let [empty-set (&;new number;Order)] - (&/= empty-set - (&;intersection empty-set setL)))) - - (test "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))))) - - (test "Every member of a set must be identifiable." - (list;every? (&;member? setL) (&;to-list setL))) - )) 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])) + ["r" math/random]) + lux/test) + +(context: "Dict" + [size (|> r;nat (:: @ map (n.% +100))) + keys (r;set number;Hash size r;nat) + values (r;set number;Hash 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 pairs) + sorted-pairs (list;sort (function [[left _] [right _]] + (n.< left right)) + pairs) + sorted-values (L/map product;right sorted-pairs) + (^open "&/") (&;Eq number;Eq)]] + ($_ 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) + (&/= sample))) + + (test "Order is preserved." + (let [(^open "L/") (list;Eq (: (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/set.lux b/stdlib/test/test/lux/data/coll/ordered/set.lux new file mode 100644 index 000000000..40b448f1e --- /dev/null +++ b/stdlib/test/test/lux/data/coll/ordered/set.lux @@ -0,0 +1,92 @@ +(;module: + lux + (lux [io] + (control monad) + (data (coll (ordered ["&" set]) + ["s" set] + [list "" Fold]) + [number] + text/format) + ["r" math/random]) + lux/test) + +(def: gen-nat + (r;Random Nat) + (|> r;nat + (:: r;Monad map (n.% +100)))) + +(context: "Sets" + [sizeL gen-nat + sizeR gen-nat + listL (|> (r;set number;Hash sizeL gen-nat) (:: @ map s;to-list)) + listR (|> (r;set number;Hash sizeR gen-nat) (:: @ map s;to-list)) + #let [(^open "&/") &;Eq + setL (&;from-list number;Order listL) + setR (&;from-list number;Order 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) + (&/= setL))) + + (test "Order is preserved." + (let [listL (&;to-list setL) + (^open "L/") (list;Eq number;Eq)] + (L/= listL + (list;sort n.< listL)))) + + (test "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)))) + + (test "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)))) + + (test "Union with the empty set leaves a set unchanged." + (&/= setL + (&;union (&;new number;Order) + setL))) + + (test "Intersection with the empty set results in the empty set." + (let [empty-set (&;new number;Order)] + (&/= empty-set + (&;intersection empty-set setL)))) + + (test "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))))) + + (test "Every member of a set must be identifiable." + (list;every? (&;member? setL) (&;to-list setL))) + )) -- cgit v1.2.3