Add SkTTopoSort

tests/TopoSortTest.cpp

+/*
+ * 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"
+
+///////////////////////////////////////////////////////////////////////////////
+// Shared with TopoSortBench.cpp

[bsalomon, 2015/10/19 14:19:13]

Is there any place we could stick the test node class that'd be accessible to
both?

[robertphillips, 2015/10/19 16:21:07]

Done - although we might want to create a top-level utils directory sometime for
code shared between bench, gm & tests.

+///////////////////////////////////////////////////////////////////////////////
+
+// A helper object to test the topological sorting code
+class TopoTestNode {
+public:
+    TopoTestNode(int id) : fID(id), fOutputPos(-1), fTempMark(false) { }
+
+    void dependsOn(TopoTestNode* src) {
+        *fDependencies.append() = src;
+    }
+
+    int id() const { return fID; }
+    void reset() { fOutputPos = -1; }
+
+    int outputPos() const { return fOutputPos; }
+
+    // check that the topological sort is valid for this node
+    void check() {
+        SkASSERT(-1 != fOutputPos);
+
+        for (int i = 0; i < fDependencies.count(); ++i) {
+            SkASSERT(-1 != fDependencies[i]->outputPos());
+            // This node should've been output after all the nodes on which it depends
+            SkASSERT(fOutputPos > fDependencies[i]->outputPos());
+        }
+    }
+
+    // The following 7 methods are needed by the topological sort
+    static void SetTempMark(TopoTestNode* node) { node->fTempMark = true; }
+    static void ResetTempMark(TopoTestNode* node) { node->fTempMark = false; }
+    static bool IsTempMarked(TopoTestNode* node) { return node->fTempMark; }
+    static void Output(TopoTestNode* node, int outputPos) { 
+        SkASSERT(-1 != outputPos);
+        node->fOutputPos = outputPos; 
+    }
+    static bool WasOutput(TopoTestNode* node) { return (-1 != node->fOutputPos); }
+    static int NumDependencies(TopoTestNode* node) { return node->fDependencies.count(); }
+    static TopoTestNode* Dependency(TopoTestNode* node, int index) { 
+        return node->fDependencies[index];
+    }
+
+private:
+    int  fID;
+    int  fOutputPos;
+    bool fTempMark;
+
+    SkTDArray<TopoTestNode*> fDependencies;
+};
+
+static void alloc_nodes(SkTDArray<TopoTestNode*>* graph, int num) {
+    graph->setReserve(num);
+
+    for (int i = 0; i < num; ++i) {
+        *graph->append() = new TopoTestNode(i);
+    }
+}
+
+static void dealloc_nodes(SkTDArray<TopoTestNode*>* graph) {
+    for (int i = 0; i < graph->count(); ++i) {
+        delete (*graph)[i];
+    }
+}
+
+#ifdef SK_DEBUG
+static void print(const SkTDArray<TopoTestNode*>& graph) {
+    for (int i = 0; i < graph.count(); ++i) {
+        SkDebugf("%d, ", graph[i]->id());
+    }
+    SkDebugf("\n");
+}
+#endif
+
+// randomize the array
+static void shuffle(SkTDArray<TopoTestNode*>* graph, SkRandom* rand) {
+    for (int i = graph->count()-1; i > 0; --i) {
+        int swap = rand->nextU() % (i+1);
+
+        TopoTestNode* tmp = (*graph)[i];
+        (*graph)[i] = (*graph)[swap];
+        (*graph)[swap] = tmp;
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+///////////////////////////////////////////////////////////////////////////////
+
+typedef void (*CreateGraphPF)(SkTDArray<TopoTestNode*>* graph);
+
+// Simple diamond
+//       3
+//     /   \
+//    1     2
+//     \   /
+//       0
+static void create_graph0(SkTDArray<TopoTestNode*>* graph) {
+    alloc_nodes(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<TopoTestNode*>* graph) {
+    alloc_nodes(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<TopoTestNode*>* graph) {
+    alloc_nodes(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<TopoTestNode*>* graph) {
+    alloc_nodes(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<TopoTestNode*>* graph) {
+    alloc_nodes(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<TopoTestNode*> graph;
+        
+        (tests[i].fCreate)(&graph);
+
+        shuffle(&graph, &rand);
+
+        bool actualResult = SkTTopoSort<TopoTestNode>(&graph);
+        REPORTER_ASSERT(reporter, actualResult == tests[i].fExpectedResult);
+
+        if (tests[i].fExpectedResult) {
+            for (int j = 0; j < graph.count(); ++j) {
+                graph[j]->check();
+            }
+        }
+
+        //SkDEBUGCODE(print(graph);)
+        dealloc_nodes(&graph);
+    }
+}
+