Add SkTTopoSort

tools/sk_tool_utils.h

 /*
  * Copyright 2014 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef sk_tool_utils_DEFINED
 #define sk_tool_utils_DEFINED
 
 #include "SkColor.h"
 #include "SkImageEncoder.h"
 #include "SkImageInfo.h"
 #include "SkPixelSerializer.h"
+#include "SkRandom.h"
+#include "SkTDArray.h"
 #include "SkTypeface.h"
 
 class SkBitmap;
 class SkCanvas;
 class SkPaint;
 class SkPath;
 class SkShader;
 class SkTestFont;
 class SkTextBlobBuilder;
 
@@ skipping 108 matching lines @@
     void create_frustum_normal_map(SkBitmap* bm, const SkIRect& dst);
 
     void create_tetra_normal_map(SkBitmap* bm, const SkIRect& dst);
 
     void make_big_path(SkPath& path);
 
     // Return a blurred version of 'src'. This doesn't use a separable filter
     // so it is slow!
     SkBitmap slow_blur(const SkBitmap& src, float sigma);
 
+    // A helper object to test the topological sorting code (TopoSortBench.cpp & TopoSortTest.cpp)
+    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
+        bool check() {
+            if (-1 == fOutputPos) {
+                return false;
+            }
+
+            for (int i = 0; i < fDependencies.count(); ++i) {
+                if (-1 == fDependencies[i]->outputPos()) {
+                    return false;
+                }
+                // This node should've been output after all the nodes on which it depends
+                if (fOutputPos < fDependencies[i]->outputPos()) {
+                    return false;
+                }
+            }
+
+            return true;
+        }
+
+        // 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];
+        }
+
+        // Helper functions for TopoSortBench & TopoSortTest
+        static void AllocNodes(SkTDArray<TopoTestNode*>* graph, int num) {
+            graph->setReserve(num);
+
+            for (int i = 0; i < num; ++i) {
+                *graph->append() = new TopoTestNode(i);
+            }
+        }
+
+        static void DeallocNodes(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;
+            }
+        }
+
+    private:
+        int  fID;
+        int  fOutputPos;
+        bool fTempMark;
+
+        SkTDArray<TopoTestNode*> fDependencies;
+    };
+
 }  // namespace sk_tool_utils
 
 #endif  // sk_tool_utils_DEFINED