IncrTopoSortTest.cpp File Reference

#include "include/core/SkRefCnt.h"
#include "include/core/SkString.h"
#include "include/core/SkTypes.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkTArray.h"
#include "include/private/base/SkTDArray.h"
#include "src/base/SkTSort.h"
#include "tests/Test.h"
#include <algorithm>
#include <cstdint>

Go to the source code of this file.

Classes
class	Node
class	Graph

Functions
static void	test_1 (skiatest::Reporter *reporter)
static void	test_2 (skiatest::Reporter *reporter)
static void	test_diamond (skiatest::Reporter *reporter)
static void	test_lopsided_binary_tree (skiatest::Reporter *reporter)
	DEF_TEST (IncrTopoSort, reporter)

Function Documentation

DEF_TEST()

DEF_TEST	(	IncrTopoSort	,
		reporter
	)

Definition at line 493 of file IncrTopoSortTest.cpp.

                                 {
    test_1(reporter);
    test_2(reporter);
    test_diamond(reporter);
    test_lopsided_binary_tree(reporter);
}

test_1()

static void test_1 ( skiatest::Reporter *  reporter )

static

Definition at line 327 of file IncrTopoSortTest.cpp.

                                               {
    Graph g(10, reporter);
 
    Node* nodeQ = g.addNode('q');
    Node* nodeY = g.addNode('y');
    Node* nodeA = g.addNode('a');
    Node* nodeZ = g.addNode('z');
    Node* nodeB = g.addNode('b');
    /*Node* nodeC =*/ g.addNode('c');
    Node* nodeW = g.addNode('w');
    Node* nodeD = g.addNode('d');
    Node* nodeX = g.addNode('x');
    Node* nodeR = g.addNode('r');
 
    // All these edge are non-invalidating
    g.addEdge(nodeD, nodeR);
    g.addEdge(nodeZ, nodeW);
    g.addEdge(nodeA, nodeB);
    g.addEdge(nodeY, nodeZ);
    g.addEdge(nodeQ, nodeA);
 
    {
        const SkString kExpectedInitialState("q,y,a,z,b,c,w,d,x,r");
        SkString actualInitialState;
        g.getActual(&actualInitialState);
        REPORTER_ASSERT(reporter, kExpectedInitialState == actualInitialState);
    }
 
    // Add the invalidating edge
    g.addEdge(nodeX, nodeY);
 
    {
        const SkString kExpectedFinalState("q,a,b,c,d,x,y,z,w,r");
        SkString actualFinalState;
        g.getActual(&actualFinalState);
        REPORTER_ASSERT(reporter, kExpectedFinalState == actualFinalState);
    }
}

test_2()

static void test_2 ( skiatest::Reporter *  reporter )

static

Definition at line 367 of file IncrTopoSortTest.cpp.

                                               {
    Graph g(10, reporter);
 
    Node* nodeY = g.addNode('y');
    /*Node* nodeA =*/ g.addNode('a');
    Node* nodeW = g.addNode('w');
    /*Node* nodeB =*/ g.addNode('b');
    Node* nodeZ = g.addNode('z');
    Node* nodeU = g.addNode('u');
    /*Node* nodeC =*/ g.addNode('c');
    Node* nodeX = g.addNode('x');
    /*Node* nodeD =*/ g.addNode('d');
    Node* nodeV = g.addNode('v');
 
    // All these edge are non-invalidating
    g.addEdge(nodeU, nodeX);
    g.addEdge(nodeW, nodeU);
    g.addEdge(nodeW, nodeZ);
    g.addEdge(nodeY, nodeZ);
 
    {
        const SkString kExpectedInitialState("y,a,w,b,z,u,c,x,d,v");
        SkString actualInitialState;
        g.getActual(&actualInitialState);
        REPORTER_ASSERT(reporter, kExpectedInitialState == actualInitialState);
    }
 
    // Add the first invalidating edge
    g.addEdge(nodeX, nodeY);
 
    {
        const SkString kExpectedFirstState("a,w,b,u,c,x,y,z,d,v");
        SkString actualFirstState;
        g.getActual(&actualFirstState);
        REPORTER_ASSERT(reporter, kExpectedFirstState == actualFirstState);
    }
 
    // Add the second invalidating edge
    g.addEdge(nodeV, nodeW);
 
    {
        const SkString kExpectedSecondState("a,b,c,d,v,w,u,x,y,z");
        SkString actualSecondState;
        g.getActual(&actualSecondState);
        REPORTER_ASSERT(reporter, kExpectedSecondState == actualSecondState);
    }
}

test_diamond()

static void test_diamond ( skiatest::Reporter *  reporter )

static

Definition at line 415 of file IncrTopoSortTest.cpp.

                                                     {
    Graph g(4, reporter);
 
    /* Create the graph (the '.' is the pointy side of the arrow):
     *        b
     *      .    \
     *     /      .
     *   a          d
     *     \      .
     *       .   /
     *         c
     * Possible topological orders are [a,c,b,d] and [a,b,c,d].
     */
 
    Node* nodeD = g.addNode('d');
    Node* nodeC = g.addNode('c');
    Node* nodeB = g.addNode('b');
 
    {
        SkTDArray<Node*> dependedOn;
        dependedOn.push_back(nodeB);
        dependedOn.push_back(nodeC);
 
        g.addEdges(&dependedOn, nodeD); // nodes B and C must come before node D
    }
 
    Node* nodeA = g.addNode('a');
    g.addEdge(nodeA, nodeB);            // node A must come before node B
    g.addEdge(nodeA, nodeC);            // node A must come before node C
 
    const SkString kExpected0("a,c,b,d");
    const SkString kExpected1("a,b,c,d");
    SkString actual;
    g.getActual(&actual);
 
    REPORTER_ASSERT(reporter, kExpected0 == actual || kExpected1 == actual);
}

test_lopsided_binary_tree()

static void test_lopsided_binary_tree ( skiatest::Reporter *  reporter )

static

Definition at line 453 of file IncrTopoSortTest.cpp.

                                                                  {
    Graph g(7, reporter);
 
    /* Create the graph (the '.' is the pointy side of the arrow):
     *        a
     *       /  \
     *      .    .
     *     b      c
     *           /  \
     *          .    .
     *         d      e
     *               /  \
     *              .    .
     *             f      g
     *
     * Possible topological order is: [a,b,c,d,e,f,g].
     */
 
    Node* nodeG = g.addNode('g');
    Node* nodeF = g.addNode('f');
    Node* nodeE = g.addNode('e');
    Node* nodeD = g.addNode('d');
    Node* nodeC = g.addNode('c');
    Node* nodeB = g.addNode('b');
    Node* nodeA = g.addNode('a');
 
    g.addEdge(nodeE, nodeG);
    g.addEdge(nodeE, nodeF);
    g.addEdge(nodeC, nodeE);
    g.addEdge(nodeC, nodeD);
    g.addEdge(nodeA, nodeC);
    g.addEdge(nodeA, nodeB);
 
    const SkString kExpected("a,b,c,d,e,f,g");
    SkString actual;
    g.getActual(&actual);
 
    REPORTER_ASSERT(reporter, kExpected == actual);
}