Graph Class Reference

Public Member Functions
	Graph (int numNodesToReserve, skiatest::Reporter *reporter)
Node *	addNode (uint32_t id)
void	addEdge (Node *dependedOn, Node *dependent)
void	addEdges (SkTDArray< Node * > *dependedOn, Node *dependent)
void	getActual (SkString *actual) const

Detailed Description

Definition at line 93 of file IncrTopoSortTest.cpp.

Constructor & Destructor Documentation

Graph()

Graph::Graph ( int  numNodesToReserve, skiatest::Reporter *  reporter  )

inline

Definition at line 95 of file IncrTopoSortTest.cpp.

            : fNodes(numNodesToReserve)
            , fReporter(reporter) {
    }

Member Function Documentation

addEdge()

void Graph::addEdge ( Node *  dependedOn, Node *  dependent  )

inline

Definition at line 111 of file IncrTopoSortTest.cpp.

                                                    {
        // TODO: this would be faster if all the SkTDArray code was stripped out of
        // addEdges but, when used in MDB sorting, this entry point will never be used.
        SkTDArray<Node*> tmp(&dependedOn, 1);
        this->addEdges(&tmp, dependent);
    }

addEdges()

void Graph::addEdges ( SkTDArray< Node * > *  dependedOn, Node *  dependent  )

inline

Definition at line 133 of file IncrTopoSortTest.cpp.

                                                                 {
        this->validate();
 
        // remove any of the new dependencies that are already satisfied
        for (int i = 0; i < dependedOn->size(); ++i) {
            if ((*dependedOn)[i]->indexInSort() < dependent->indexInSort()) {
                dependent->addDependency((*dependedOn)[i]);
                dependedOn->removeShuffle(i);
                i--;
            } else {
                dependent->addDependency((*dependedOn)[i]);
            }
        }
 
        if (dependedOn->empty()) {
            return;
        }
 
        // Sort the remaining dependencies into descending order based on their indices in the
        // sort. This means that we will be proceeding from right to left in the sort when
        // correcting the order.
        // TODO: QSort is waaay overkill here!
        SkTQSort<Node*>(dependedOn->begin(), dependedOn->end(), Node::CompareIndicesGT);
 
        // TODO: although this is the general algorithm, I think this can be simplified for our
        // use case (i.e., the same dependent for all the new edges).
 
        int lowerBound = fNodes.size();  // 'lowerBound' tracks the left of the affected region
        for (int i = 0; i < dependedOn->size(); ++i) {
            if ((*dependedOn)[i]->indexInSort() < lowerBound) {
                this->shift(lowerBound);
            }
 
            if (!dependent->visited()) {
                this->dfs(dependent, (*dependedOn)[i]->indexInSort());
            }
 
            lowerBound = std::min(dependent->indexInSort(), lowerBound);
        }
 
        this->shift(lowerBound);
 
        this->validate();
    }

addNode()

Node * Graph::addNode ( uint32_t  id )

inline

Definition at line 100 of file IncrTopoSortTest.cpp.

                               {
        this->validate();
        sk_sp<Node> tmp(new Node(id));
 
        fNodes.push_back(tmp);       // The graph gets the creation ref
        tmp->setIndexInSort(fNodes.size()-1);
        this->validate();
        return tmp.get();
    }

getActual()

void Graph::getActual ( SkString *  actual ) const

inline

Definition at line 179 of file IncrTopoSortTest.cpp.

                                           {
        this->validate();
 
        for (int i = 0; i < fNodes.size(); ++i) {
            (*actual) += fNodes[i]->id();
            if (i < fNodes.size()-1) {
                (*actual) += ',';
            }
        }
    }

---

The documentation for this class was generated from the following file:

• third_party/skia/tests/IncrTopoSortTest.cpp