Debian Codegraph @

src-testing/Futhark/Optimise/MemoryBlockMerging/GreedyColoringTests.hs

raw
1 module Futhark.Optimise.MemoryBlockMerging.GreedyColoringTests
2 ( tests,
3 )
4 where
5
6 import Control.Arrow ((***))
7 import Data.Function ((&))
8 import Data.Map qualified as M
9 import Data.Set qualified as S
10 import Futhark.Optimise.MemoryBlockMerging.GreedyColoring qualified as GreedyColoring
11 import Test.Tasty
12 import Test.Tasty.HUnit
13
14 tests :: TestTree
15 tests =
16 testGroup
17 "GreedyColoringTests"
18 [psumTest, allIntersect, emptyGraph, noIntersections, differentSpaces]
19
20 psumTest :: TestTree
21 psumTest =
22 testCase "psumTest"
23 $ assertEqual
24 "Color simple 1-2-3 using two colors"
25 ( [(0, "shared"), (1, "shared")] :: [(Int, String)],
26 [(1 :: Int, 0), (2, 1), (3, 0)]
27 )
28 $ (M.toList *** M.toList)
29 $ GreedyColoring.colorGraph
30 (M.fromList [(1, "shared"), (2, "shared"), (3, "shared")])
31 $ S.fromList [(1, 2), (2, 3)]
32
33 allIntersect :: TestTree
34 allIntersect =
35 testCase "allIntersect"
36 $ assertEqual
37 "Color a graph where all values intersect"
38 ( [(0, "shared"), (1, "shared"), (2, "shared")] :: [(Int, String)],
39 [(1 :: Int, 2), (2, 1), (3, 0)]
40 )
41 $ (M.toList *** M.toList)
42 $ GreedyColoring.colorGraph
43 (M.fromList [(1, "shared"), (2, "shared"), (3, "shared")])
44 $ S.fromList [(1, 2), (2, 3), (1, 3)]
45
46 emptyGraph :: TestTree
47 emptyGraph =
48 testCase "emptyGraph"
49 $ assertEqual
50 "Color an empty graph"
51 ([] :: [(Int, Char)], [] :: [(Int, Int)])
52 $ (M.toList *** M.toList)
53 $ GreedyColoring.colorGraph M.empty
54 $ S.fromList []
55
56 noIntersections :: TestTree
57 noIntersections =
58 GreedyColoring.colorGraph
59 (M.fromList [(1, "shared"), (2, "shared"), (3, "shared")])
60 (S.fromList [])
61 & M.toList *** M.toList
62 & assertEqual
63 "Color nodes with no intersections"
64 ( [(0, "shared")] :: [(Int, String)],
65 [(1, 0), (2, 0), (3, 0)] :: [(Int, Int)]
66 )
67 & testCase "noIntersections"
68
69 differentSpaces :: TestTree
70 differentSpaces =
71 GreedyColoring.colorGraph
72 (M.fromList [(1, "a"), (2, "b"), (3, "c")])
73 (S.fromList [])
74 & M.toList *** M.toList
75 & assertEqual
76 "Color nodes with no intersections but in different spaces"
77 ( [(0, "c"), (1, "b"), (2, "a")] :: [(Int, String)],
78 [(1, 2), (2, 1), (3, 0)] :: [(Int, Int)]
79 )
80 & testCase "differentSpaces"