Add SkTTopoSort

BUG=skia:4094

Review URL: https://codereview.chromium.org/1414503003

1 files changed, 142 insertions, 0 deletions

diff --git a/tests/TopoSortTest.cpp b/tests/TopoSortTest.cpp
new file mode 100644
index 0000000000..358cd8dbad
--- /dev/null
+++ b/tests/TopoSortTest.cpp
@@ -0,0 +1,142 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkRandom.h"
+#include "SkTTopoSort.h"
+#include "Test.h"
+
+#include "sk_tool_utils.h"
+
+typedef void (*CreateGraphPF)(SkTDArray<sk_tool_utils::TopoTestNode*>* graph);
+
+/* Simple diamond
+ *       3
+ *     /   \
+ *    1     2
+ *     \   /
+ *       0
+ */
+static void create_graph0(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+    sk_tool_utils::TopoTestNode::AllocNodes(graph, 4);
+
+    (*graph)[0]->dependsOn((*graph)[1]);
+    (*graph)[0]->dependsOn((*graph)[2]);
+    (*graph)[1]->dependsOn((*graph)[3]);
+    (*graph)[2]->dependsOn((*graph)[3]);
+}
+
+/* Simple chain
+ *     3
+ *     |
+ *     2
+ *     |
+ *     1
+ *     |
+ *     0
+ */
+static void create_graph1(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+    sk_tool_utils::TopoTestNode::AllocNodes(graph, 4);
+
+    (*graph)[0]->dependsOn((*graph)[1]);
+    (*graph)[1]->dependsOn((*graph)[2]);
+    (*graph)[2]->dependsOn((*graph)[3]);
+}
+
+/* Loop
+ *       2
+ *     /   \
+ *    0 --- 1
+ */
+static void create_graph2(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+    sk_tool_utils::TopoTestNode::AllocNodes(graph, 3);
+
+    (*graph)[0]->dependsOn((*graph)[1]);
+    (*graph)[1]->dependsOn((*graph)[2]);
+    (*graph)[2]->dependsOn((*graph)[0]);
+}
+
+/* Double diamond
+ *       6
+ *     /   \
+ *    4     5
+ *     \   /
+ *       3
+ *     /   \
+ *    1     2
+ *     \   /
+ *       0
+ */
+static void create_graph3(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+    sk_tool_utils::TopoTestNode::AllocNodes(graph, 7);
+
+    (*graph)[0]->dependsOn((*graph)[1]);
+    (*graph)[0]->dependsOn((*graph)[2]);
+    (*graph)[1]->dependsOn((*graph)[3]);
+    (*graph)[2]->dependsOn((*graph)[3]);
+
+    (*graph)[3]->dependsOn((*graph)[4]);
+    (*graph)[3]->dependsOn((*graph)[5]);
+    (*graph)[4]->dependsOn((*graph)[6]);
+    (*graph)[5]->dependsOn((*graph)[6]);
+}
+
+/* Two independent diamonds
+ *       3           7
+ *     /   \       /   \
+ *    1     2     5     6
+ *     \   /       \   /
+ *       0           4
+ */
+static void create_graph4(SkTDArray<sk_tool_utils::TopoTestNode*>* graph) {
+    sk_tool_utils::TopoTestNode::AllocNodes(graph, 8);
+
+    (*graph)[0]->dependsOn((*graph)[1]);
+    (*graph)[0]->dependsOn((*graph)[2]);
+    (*graph)[1]->dependsOn((*graph)[3]);
+    (*graph)[2]->dependsOn((*graph)[3]);
+
+    (*graph)[4]->dependsOn((*graph)[5]);
+    (*graph)[4]->dependsOn((*graph)[6]);
+    (*graph)[5]->dependsOn((*graph)[7]);
+    (*graph)[6]->dependsOn((*graph)[7]);
+}
+
+DEF_TEST(TopoSort, reporter) {
+    SkRandom rand;
+
+    struct {
+        CreateGraphPF fCreate;
+        bool          fExpectedResult;
+    } tests[] = {
+        { create_graph0, true  },
+        { create_graph1, true  },
+        { create_graph2, false },
+        { create_graph3, true  },
+        { create_graph4, true  },
+    };
+
+    for (size_t i = 0; i < SK_ARRAY_COUNT(tests); ++i) {
+        SkTDArray<sk_tool_utils::TopoTestNode*> graph;
+        
+        (tests[i].fCreate)(&graph);
+
+        sk_tool_utils::TopoTestNode::Shuffle(&graph, &rand);
+
+        bool actualResult = SkTTopoSort<sk_tool_utils::TopoTestNode>(&graph);
+        REPORTER_ASSERT(reporter, actualResult == tests[i].fExpectedResult);
+
+        if (tests[i].fExpectedResult) {
+            for (int j = 0; j < graph.count(); ++j) {
+                REPORTER_ASSERT(reporter, graph[j]->check());
+            }
+        }
+
+        //SkDEBUGCODE(print(graph);)
+        sk_tool_utils::TopoTestNode::DeallocNodes(&graph);
+    }
+}
+