| 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" |