1/*
2 * Copyright 2015 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "SkRandom.h"
9#include "SkTTopoSort.h"
10#include "Test.h"
11
12#include "sk_tool_utils.h"
13
14typedef void (*CreateGraphPF)(SkTDArray<sk_tool_utils::TopoTestNode*>* graph);
15
16/* Simple diamond
17 *       3
18 *     /   \
19 *    1     2
20 *     \   /
21 *       0
22 */
23static void create_graph0(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
24    sk_tool_utils::TopoTestNode::AllocNodes(graph, 4);
25
26    (*graph)[0]->dependsOn((*graph)[1]);
27    (*graph)[0]->dependsOn((*graph)[2]);
28    (*graph)[1]->dependsOn((*graph)[3]);
29    (*graph)[2]->dependsOn((*graph)[3]);
30}
31
32/* Simple chain
33 *     3
34 *     |
35 *     2
36 *     |
37 *     1
38 *     |
39 *     0
40 */
41static void create_graph1(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
42    sk_tool_utils::TopoTestNode::AllocNodes(graph, 4);
43
44    (*graph)[0]->dependsOn((*graph)[1]);
45    (*graph)[1]->dependsOn((*graph)[2]);
46    (*graph)[2]->dependsOn((*graph)[3]);
47}
48
49/* Loop
50 *       2
51 *     /   \
52 *    0 --- 1
53 */
54static void create_graph2(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
55    sk_tool_utils::TopoTestNode::AllocNodes(graph, 3);
56
57    (*graph)[0]->dependsOn((*graph)[1]);
58    (*graph)[1]->dependsOn((*graph)[2]);
59    (*graph)[2]->dependsOn((*graph)[0]);
60}
61
62/* Double diamond
63 *       6
64 *     /   \
65 *    4     5
66 *     \   /
67 *       3
68 *     /   \
69 *    1     2
70 *     \   /
71 *       0
72 */
73static void create_graph3(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
74    sk_tool_utils::TopoTestNode::AllocNodes(graph, 7);
75
76    (*graph)[0]->dependsOn((*graph)[1]);
77    (*graph)[0]->dependsOn((*graph)[2]);
78    (*graph)[1]->dependsOn((*graph)[3]);
79    (*graph)[2]->dependsOn((*graph)[3]);
80
81    (*graph)[3]->dependsOn((*graph)[4]);
82    (*graph)[3]->dependsOn((*graph)[5]);
83    (*graph)[4]->dependsOn((*graph)[6]);
84    (*graph)[5]->dependsOn((*graph)[6]);
85}
86
87/* Two independent diamonds
88 *       3           7
89 *     /   \       /   \
90 *    1     2     5     6
91 *     \   /       \   /
92 *       0           4
93 */
94static void create_graph4(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
95    sk_tool_utils::TopoTestNode::AllocNodes(graph, 8);
96
97    (*graph)[0]->dependsOn((*graph)[1]);
98    (*graph)[0]->dependsOn((*graph)[2]);
99    (*graph)[1]->dependsOn((*graph)[3]);
100    (*graph)[2]->dependsOn((*graph)[3]);
101
102    (*graph)[4]->dependsOn((*graph)[5]);
103    (*graph)[4]->dependsOn((*graph)[6]);
104    (*graph)[5]->dependsOn((*graph)[7]);
105    (*graph)[6]->dependsOn((*graph)[7]);
106}
107
108DEF_TEST(TopoSort, reporter) {
109    SkRandom rand;
110
111    struct {
112        CreateGraphPF fCreate;
113        bool          fExpectedResult;
114    } tests[] = {
115        { create_graph0, true  },
116        { create_graph1, true  },
117        { create_graph2, false },
118        { create_graph3, true  },
119        { create_graph4, true  },
120    };
121
122    for (size_t i = 0; i < SK_ARRAY_COUNT(tests); ++i) {
123        SkTDArray<sk_tool_utils::TopoTestNode*> graph;
124
125        (tests[i].fCreate)(&graph);
126
127        sk_tool_utils::TopoTestNode::Shuffle(&graph, &rand);
128
129        bool actualResult = SkTTopoSort<sk_tool_utils::TopoTestNode>(&graph);
130        REPORTER_ASSERT(reporter, actualResult == tests[i].fExpectedResult);
131
132        if (tests[i].fExpectedResult) {
133            for (int j = 0; j < graph.count(); ++j) {
134                REPORTER_ASSERT(reporter, graph[j]->check());
135            }
136        }
137
138        //SkDEBUGCODE(print(graph);)
139        sk_tool_utils::TopoTestNode::DeallocNodes(&graph);
140    }
141}
142
143