Add fromDescList and fromDistinctDescList
[packages/containers.git] / tests / set-properties.hs
index 56e0b70..029110d 100644 (file)
@@ -16,6 +16,10 @@ main = defaultMain [ testCase "lookupLT" test_lookupLT
                    , testCase "lookupGT" test_lookupGT
                    , testCase "lookupLE" test_lookupLE
                    , testCase "lookupGE" test_lookupGE
+                   , testCase "lookupIndex" test_lookupIndex
+                   , testCase "findIndex" test_findIndex
+                   , testCase "elemAt" test_elemAt
+                   , testCase "deleteAt" test_deleteAt
                    , testProperty "prop_Valid" prop_Valid
                    , testProperty "prop_Single" prop_Single
                    , testProperty "prop_Member" prop_Member
@@ -27,7 +31,7 @@ main = defaultMain [ testCase "lookupLT" test_lookupLT
                    , testProperty "prop_InsertValid" prop_InsertValid
                    , testProperty "prop_InsertDelete" prop_InsertDelete
                    , testProperty "prop_DeleteValid" prop_DeleteValid
-                   , testProperty "prop_Join" prop_Join
+                   , testProperty "prop_Link" prop_Link
                    , testProperty "prop_Merge" prop_Merge
                    , testProperty "prop_UnionValid" prop_UnionValid
                    , testProperty "prop_UnionInsert" prop_UnionInsert
@@ -37,15 +41,13 @@ main = defaultMain [ testCase "lookupLT" test_lookupLT
                    , testProperty "prop_Diff" prop_Diff
                    , testProperty "prop_IntValid" prop_IntValid
                    , testProperty "prop_Int" prop_Int
-                   , testCase "lookupIndex" test_lookupIndex
-                   , testCase "findIndex" test_findIndex
-                   , testCase "elemAt" test_elemAt
-                   , testCase "deleteAt" test_deleteAt
                    , testProperty "prop_Ordered" prop_Ordered
+                   , testProperty "prop_DescendingOrdered" prop_DescendingOrdered
                    , testProperty "prop_List" prop_List
                    , testProperty "prop_DescList" prop_DescList
                    , testProperty "prop_AscDescList" prop_AscDescList
                    , testProperty "prop_fromList" prop_fromList
+                   , testProperty "prop_fromListDesc" prop_fromListDesc
                    , testProperty "prop_isProperSubsetOf" prop_isProperSubsetOf
                    , testProperty "prop_isProperSubsetOf2" prop_isProperSubsetOf2
                    , testProperty "prop_isSubsetOf" prop_isSubsetOf
@@ -64,6 +66,7 @@ main = defaultMain [ testCase "lookupLT" test_lookupLT
                    , testProperty "prop_minView" prop_minView
                    , testProperty "prop_split" prop_split
                    , testProperty "prop_splitMember" prop_splitMember
+                   , testProperty "prop_splitRoot" prop_splitRoot
                    , testProperty "prop_partition" prop_partition
                    , testProperty "prop_filter" prop_filter
                    ]
@@ -95,6 +98,32 @@ test_lookupGE = do
    lookupGE 6 (fromList [3, 5]) @?= Nothing
 
 {--------------------------------------------------------------------
+  Indexed
+--------------------------------------------------------------------}
+
+test_lookupIndex :: Assertion
+test_lookupIndex = do
+    isJust   (lookupIndex 2 (fromList [5,3])) @?= False
+    fromJust (lookupIndex 3 (fromList [5,3])) @?= 0
+    fromJust (lookupIndex 5 (fromList [5,3])) @?= 1
+    isJust   (lookupIndex 6 (fromList [5,3])) @?= False
+
+test_findIndex :: Assertion
+test_findIndex = do
+    findIndex 3 (fromList [5,3]) @?= 0
+    findIndex 5 (fromList [5,3]) @?= 1
+
+test_elemAt :: Assertion
+test_elemAt = do
+    elemAt 0 (fromList [5,3]) @?= 3
+    elemAt 1 (fromList [5,3]) @?= 5
+
+test_deleteAt :: Assertion
+test_deleteAt = do
+    deleteAt 0 (fromList [5,3]) @?= singleton 5
+    deleteAt 1 (fromList [5,3]) @?= singleton 3
+
+{--------------------------------------------------------------------
   Arbitrary, reasonably balanced trees
 --------------------------------------------------------------------}
 instance (Enum a) => Arbitrary (Set a) where
@@ -189,10 +218,10 @@ prop_DeleteValid k = forValidUnitTree $ \t -> valid (delete k (insert k t))
 {--------------------------------------------------------------------
   Balance
 --------------------------------------------------------------------}
-prop_Join :: Int -> Property
-prop_Join x = forValidUnitTree $ \t ->
+prop_Link :: Int -> Property
+prop_Link x = forValidUnitTree $ \t ->
     let (l,r) = split x t
-    in valid (join x l r)
+    in valid (link x l r)
 
 prop_Merge :: Int -> Property
 prop_Merge x = forValidUnitTree $ \t ->
@@ -236,38 +265,17 @@ prop_Int xs ys = toAscList (intersection (fromList xs) (fromList ys))
                  == List.sort (nub ((List.intersect) (xs)  (ys)))
 
 {--------------------------------------------------------------------
-  Indexed
---------------------------------------------------------------------}
-
-test_lookupIndex :: Assertion
-test_lookupIndex = do
-    isJust   (lookupIndex 2 (fromList [5,3])) @?= False
-    fromJust (lookupIndex 3 (fromList [5,3])) @?= 0
-    fromJust (lookupIndex 5 (fromList [5,3])) @?= 1
-    isJust   (lookupIndex 6 (fromList [5,3])) @?= False
-
-test_findIndex :: Assertion
-test_findIndex = do
-    findIndex 3 (fromList [5,3]) @?= 0
-    findIndex 5 (fromList [5,3]) @?= 1
-
-test_elemAt :: Assertion
-test_elemAt = do
-    elemAt 0 (fromList [5,3]) @?= 3
-    elemAt 1 (fromList [5,3]) @?= 5
-
-test_deleteAt :: Assertion
-test_deleteAt = do
-    deleteAt 0 (fromList [5,3]) @?= singleton 5
-    deleteAt 1 (fromList [5,3]) @?= singleton 3
-
-{--------------------------------------------------------------------
   Lists
 --------------------------------------------------------------------}
 prop_Ordered :: Property
 prop_Ordered = forAll (choose (5,100)) $ \n ->
     let xs = [0..n::Int]
-    in fromAscList xs == fromList xs
+    in fromAscList xs === fromList xs
+
+prop_DescendingOrdered :: Property
+prop_DescendingOrdered = forAll (choose (5,100)) $ \n ->
+    let xs = [n,n-1..0::Int]
+    in fromDescList xs === fromList xs
 
 prop_List :: [Int] -> Bool
 prop_List xs = (sort (nub xs) == toList (fromList xs))
@@ -279,13 +287,22 @@ prop_AscDescList :: [Int] -> Bool
 prop_AscDescList xs = toAscList s == reverse (toDescList s)
   where s = fromList xs
 
-prop_fromList :: [Int] -> Bool
-prop_fromList xs
-  = case fromList xs of
-      t -> t == fromAscList sort_xs &&
-           t == fromDistinctAscList nub_sort_xs &&
-           t == List.foldr insert empty xs
-  where sort_xs = sort xs
+prop_fromList :: [Int] -> Property
+prop_fromList xs =
+           t === fromAscList sort_xs .&&.
+           t === fromDistinctAscList nub_sort_xs .&&.
+           t === List.foldr insert empty xs
+  where t = fromList xs
+        sort_xs = sort xs
+        nub_sort_xs = List.map List.head $ List.group sort_xs
+
+prop_fromListDesc :: [Int] -> Property
+prop_fromListDesc xs =
+           t === fromDescList sort_xs .&&.
+           t === fromDistinctDescList nub_sort_xs .&&.
+           t === List.foldr insert empty xs
+  where t = fromList xs
+        sort_xs = reverse (sort xs)
         nub_sort_xs = List.map List.head $ List.group sort_xs
 
 {--------------------------------------------------------------------
@@ -359,6 +376,16 @@ prop_splitMember :: Set Int -> Int -> Bool
 prop_splitMember s i = case splitMember i s of
     (s1,t,s2) -> all (<i) (toList s1) && all (>i) (toList s2) && t == i `member` s && i `delete` s == union s1 s2
 
+prop_splitRoot :: Set Int -> Bool
+prop_splitRoot s = loop ls && (s == unions ls)
+ where
+  ls = splitRoot s
+  loop [] = True
+  loop (s1:rst) = List.null
+                  [ (x,y) | x <- toList s1
+                          , y <- toList (unions rst)
+                          , x > y ]
+
 prop_partition :: Set Int -> Int -> Bool
 prop_partition s i = case partition odd s of
     (s1,s2) -> all odd (toList s1) && all even (toList s2) && s == s1 `union` s2