# order.py -- order projects in dependency order
#
# Copyright 2012  Lars Wirzenius
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.


def _traverse(project, result):
    for dep in project['_']:
        _traverse(dep, result)
    if project not in result:
        result.append(project)
    return result


def _roots(projects):
    '''Return list of projects that are not build dependencies of anyone.'''

    roots = projects[:]
    for project in projects:
        roots = [r for r in roots if r not in project['_']]
    return roots


def order(projects):
    by_name = {}
    for project in projects:
        by_name[project['name']] = project

    for project in projects:
        project['_'] = [by_name[dep]
                        for dep in project.get('build-depends', [])]

    roots = _roots(projects)

    linear = []
    for project in roots:
        _traverse(project, linear)

    result = []
    while linear:
        project = linear.pop(0)
        if project not in linear:
            result.append(project)

    return result