private void sortNodes() {
        if (mNeedsSort) {
            mSortedNodes.clear();
            ArrayList<Node> roots = new ArrayList<Node>();
            int numNodes = mNodes.size();
            for (int i = 0; i < numNodes; ++i) {
                Node node = mNodes.get(i);
                if (node.dependencies == null || node.dependencies.size() == 0) {
                    roots.add(node);
                }
            }
            ArrayList<Node> tmpRoots = new ArrayList<Node>();
            while (roots.size() > 0) {
                int numRoots = roots.size();
                for (int i = 0; i < numRoots; ++i) {
                    Node root = roots.get(i);
                    mSortedNodes.add(root);
                    if (root.nodeDependents != null) {
                        int numDependents = root.nodeDependents.size();
                        for (int j = 0; j < numDependents; ++j) {
                            Node node = root.nodeDependents.get(j);
                            node.nodeDependencies.remove(root);
                            if (node.nodeDependencies.size() == 0) {
                                tmpRoots.add(node);
                            }
                        }
                    }
                }
                roots.clear();
                roots.addAll(tmpRoots);
                tmpRoots.clear();
            }
            mNeedsSort = false;
            if (mSortedNodes.size() != mNodes.size()) {
                throw new IllegalStateException("Circular dependencies cannot exist"
                        + " in AnimatorSet");
            }
        } else {
            // Doesn't need sorting, but still need to add in the nodeDependencies list
            // because these get removed as the event listeners fire and the dependencies
            // are satisfied
            int numNodes = mNodes.size();
            for (int i = 0; i < numNodes; ++i) {
                Node node = mNodes.get(i);
                if (node.dependencies != null && node.dependencies.size() > 0) {
                    int numDependencies = node.dependencies.size();
                    for (int j = 0; j < numDependencies; ++j) {
                        Dependency dependency = node.dependencies.get(j);
                        if (node.nodeDependencies == null) {
                            node.nodeDependencies = new ArrayList<Node>();
                        }
                        if (!node.nodeDependencies.contains(dependency.node)) {
                            node.nodeDependencies.add(dependency.node);
                        }
                    }
                }
                // nodes are 'done' by default; they become un-done when started, and done
                // again when ended
                node.done = false;
            }
        }
    }
private void sortNodes ( ) { if ( mNeedsSort ) { mSortedNodes . clear ( ) ; ArrayList < Node > roots = new ArrayList < Node > ( ) ; int numNodes = mNodes . size ( ) ; for ( int i = 0 ; i < numNodes ; ++ i ) { Node node = mNodes . get ( i ) ; if ( node . dependencies == null || node . dependencies . size ( ) == 0 ) { roots . add ( node ) ; } } ArrayList < Node > tmpRoots = new ArrayList < Node > ( ) ; while ( roots . size ( ) > 0 ) { int numRoots = roots . size ( ) ; for ( int i = 0 ; i < numRoots ; ++ i ) { Node root = roots . get ( i ) ; mSortedNodes . add ( root ) ; if ( root . nodeDependents != null ) { int numDependents = root . nodeDependents . size ( ) ; for ( int j = 0 ; j < numDependents ; ++ j ) { Node node = root . nodeDependents . get ( j ) ; node . nodeDependencies . remove ( root ) ; if ( node . nodeDependencies . size ( ) == 0 ) { tmpRoots . add ( node ) ; } } } } roots . clear ( ) ; roots . addAll ( tmpRoots ) ; tmpRoots . clear ( ) ; } mNeedsSort = false ; if ( mSortedNodes . size ( ) != mNodes . size ( ) ) { throw new IllegalStateException ( "Circular dependencies cannot exist" + " in AnimatorSet" ) ; } } else { int numNodes = mNodes . size ( ) ; for ( int i = 0 ; i < numNodes ; ++ i ) { Node node = mNodes . get ( i ) ; if ( node . dependencies != null && node . dependencies . size ( ) > 0 ) { int numDependencies = node . dependencies . size ( ) ; for ( int j = 0 ; j < numDependencies ; ++ j ) { Dependency dependency = node . dependencies . get ( j ) ; if ( node . nodeDependencies == null ) { node . nodeDependencies = new ArrayList < Node > ( ) ; } if ( ! node . nodeDependencies . contains ( dependency . node ) ) { node . nodeDependencies . add ( dependency . node ) ; } } } node . done = false ; } } }
This method sorts the current set of nodes, if needed. The sort is a simple
DependencyGraph sort, which goes like this:
- All nodes without dependencies become 'roots'
- while roots list is not null
-   for each root r
-     add r to sorted list
-     remove r as a dependency from any other node
-   any nodes with no dependencies are added to the roots list