<?php

    
/* build a array with test objects */
    
$packages = array();
    
$packages['early'] = array();
    
$packages['app-arch/bzip2'] = array('early');
    
$packages['media-libs/alsa-lib'] = array('media-sound/alsa-headers');
    
$packages['media-libs/libsdl'] = explode(',''x11-libs/libXt,x11-libs/libXext,x11-libs/libX11,x11-libs/libXrandr');
    
$packages['media-libs/mesa'] = array('x11-libs/libXext');
    
$packages['media-libs/openal'] = array('media-libs/alsa-lib');
    
$packages['media-video/mplayer'] = explode(',''x11-libs/libXxf86vm,sys-libs/ncurses,app-arch/bzip2,sys-libs/zlib,virtual/opengl,media-libs/openal,media-libs/libsdl');
    
$packages['sys-libs/ncurses'] = array();
    
$packages['sys-libs/zlib'] = array();
    
$packages['virtual/opengl'] = array('media-libs/mesa''early');

    
$packages['media-sound/alsa-headers'] = array();
    
$packages['x11-libs/libX11'] = array();
    
$packages['x11-libs/libXext'] = array();
    
$packages['x11-libs/libXrandr'] = array();
    
$packages['x11-libs/libXt'] = array();
    
$packages['x11-libs/libXxf86vm'] = array();

    
/* make list easier to work with, using value as key in lists */
    
foreach($packages as $package_name => $depenings)
    {
        if(
$depenings)
        {
            
sort($depenings);
            
$packages[$package_name] = array_combine($depenings$depenings);
        }
    }

    
/* define some useful funktions */

    /* list direcktly depening packages of a given package */
    
function list_dependings($package)
    {
        global 
$packages;
        
//if(!isset($packages[$package])) trigger_error("Invalid package: {$package}") AND die();
        
return $packages[$package];
    }

    
/* list all depening packages of a given package */
    
function list_all_dependings($package)
    {
        
$tested = array();
        
$not_tested = array($package => $package);

        while(
count($not_tested))
        {
            
reset($not_tested);
            
$next_package key($not_tested);

            if(!isset(
$tested[$next_package]))
            {
                
$not_tested += list_dependings($next_package);
                
$tested[$next_package] = $next_package;
            }

            unset(
$not_tested[$next_package]);
        }

        
$dependings $tested;
        unset(
$dependings[$package]);

        return 
$dependings;
    }

    
/* list direcktly reverse depening packages of a given package */
    
function list_reverse_depenings($package)
    {
        global 
$packages;

        
$reverse_dependings = array();
        foreach(
array_keys($packages) as $current_package)
        {
            if(isset(
$packages[$current_package][$package]))
            {
                
$reverse_dependings[$current_package] = $current_package;
            }
        }
        return 
$reverse_dependings;
    }

    
/* list all reverse depening packages of a given package */
    
function list_all_reverse_dependings($package)
    {
        global 
$packages;
        
$tested = array();
        
$not_tested = array($package => $package);

        while(
count($not_tested))
        {
            
reset($not_tested);
            
$next_package key($not_tested);

            if(!isset(
$tested[$next_package]))
            {
                
$not_tested += list_reverse_depenings($next_package);
                
$tested[$next_package] = $next_package;
            }

            unset(
$not_tested[$next_package]);
        }

        
$reverse_dependings $tested;
        unset(
$reverse_dependings[$package]);

        return 
$reverse_dependings;
    }

    
/* compare 2 packages */
    
function cmp_packages($package_a$package_b)
    {
        
/* create a (static) list of early packages, by using reverse depenings */
        
static $early;
        if(!isset(
$early)) $early list_all_reverse_dependings('early') + array('early' => 'early');

        
/* list depenings on the 2 given packages */
        
$dependings_a list_all_dependings($package_a);
        
$dependings_b list_all_dependings($package_b);

        
/* is A depending on B */
        
if(isset($dependings_a[$package_b]))
        {
            
/* is B also a depening on A */
            
if(isset($dependings_b[$package_a]))
            {
                
trigger_error("Loop dependecy between: '{$package_a}' and '{$package_b}'\n");
                return 
strcmp($package_a$package_b); // return list alphabeticly
                //return 0;
            
}
            else
            {
if(
$GLOBALS['debug']) trigger_error("build A: '{$package_a}' after B:'{$package_b} as A depneds on B");
                return 
1;
            }
        }
        
/* is B a depening on A */
        
else if(isset($dependings_b[$package_a]))
        {
if(
$GLOBALS['debug']) trigger_error("build A: '{$package_a}' before B:'{$package_b} as B depneds on A");
            return -
1;
        }
        
/* is A a early package */
        
else if(isset($early[$package_a]))
        {
            
/* is B also a early package */
            
if(isset($early[$package_b]))
            {
if(
$GLOBALS['debug']) trigger_error("build A: '{$package_a}' and B:'{$package_b} as both are early marked");
                return 
strcmp($package_a$package_b); // return list alphabeticly
                
return 0;
            }
            else
            {
if(
$GLOBALS['debug']) trigger_error("build A: '{$package_a}' before B:'{$package_b} as A is early marked");
                return -
1;
            }
        }
        
/* is B a early package */
        
else if(isset($early[$package_b]))
        {
if(
$GLOBALS['debug']) trigger_error("build A: '{$package_a}' after B:'{$package_b} as B is early marked");
            return 
1;
        }
        else
        {
if(
$GLOBALS['debug']) trigger_error("build A: '{$package_a}' and B:'{$package_b} as they don't interact");
            return 
strcmp($package_a$package_b); // return list alphabeticly
            
return 0;
        }
    }

//     /* print depenings lists */
//     foreach(array_keys($packages) as $current_package)
//     {
//         echo "\n";
//         echo $current_package . "\n";
//         echo " * direct dep: " . implode(",", list_dependings($current_package)) . "\n";
//         echo " * full dep:   " . implode(",", list_all_dependings($current_package)) . "\n";
//         echo " * direct reverse-dep: " . implode(",", list_reverse_depenings($current_package)) . "\n";
//         echo " * full reverse-dep:   " . implode(",", list_all_reverse_dependings($current_package)) . "\n";
//     }

    /* if webbroser, pretend to be a webpage */
    
if(isset($_SERVER['REMOTE_ADDR'])) echo "<html><body><pre>";

    
$debug FALSE;
    
$build_package 'media-video/mplayer';
    
$build_list = array($build_package => $build_package) + list_all_dependings($build_package);
    
uasort($build_list'cmp_packages');
    
print_r($build_list);
?>