001package org.eclipse.aether.util.graph.visitor;
002
003/*
004 * Licensed to the Apache Software Foundation (ASF) under one
005 * or more contributor license agreements.  See the NOTICE file
006 * distributed with this work for additional information
007 * regarding copyright ownership.  The ASF licenses this file
008 * to you under the Apache License, Version 2.0 (the
009 * "License"); you may not use this file except in compliance
010 * with the License.  You may obtain a copy of the License at
011 * 
012 *  http://www.apache.org/licenses/LICENSE-2.0
013 * 
014 * Unless required by applicable law or agreed to in writing,
015 * software distributed under the License is distributed on an
016 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
017 * KIND, either express or implied.  See the License for the
018 * specific language governing permissions and limitations
019 * under the License.
020 */
021
022import org.eclipse.aether.graph.DependencyNode;
023
024/**
025 * Generates a sequence of dependency nodes from a dependeny graph by traversing the graph in postorder. This visitor
026 * visits each node exactly once regardless how many paths within the dependency graph lead to the node such that the
027 * resulting node sequence is free of duplicates.
028 */
029public final class PostorderNodeListGenerator
030    extends AbstractDepthFirstNodeListGenerator
031{
032
033    private final Stack<Boolean> visits;
034
035    /**
036     * Creates a new postorder list generator.
037     */
038    public PostorderNodeListGenerator()
039    {
040        visits = new Stack<>();
041    }
042
043    @Override
044    public boolean visitEnter( DependencyNode node )
045    {
046        boolean visited = !setVisited( node );
047
048        visits.push( visited );
049
050        if ( visited )
051        {
052            return false;
053        }
054
055        return true;
056    }
057
058    @Override
059    public boolean visitLeave( DependencyNode node )
060    {
061        Boolean visited = visits.pop();
062
063        if ( visited )
064        {
065            return true;
066        }
067
068        if ( node.getDependency() != null )
069        {
070            nodes.add( node );
071        }
072
073        return true;
074    }
075
076}