package org.lucci.madhoc.network.util;

import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Vector;

import org.lucci.madhoc.network.Station;
import org.lucci.madhoc.network.Network;
import org.lucci.madhoc.network.net.NetworkInterface;
import org.lucci.madhoc.network.net.NetworkingTechnology;
import org.lucci.madhoc.network.net.NetworkingUnit;
import org.lucci.math.Utilities;
import org.lucci.util.assertion.Assertions;

/*
 * Created on Aug 26, 2004
 */

/**
 * @author luc.hogie
 */
public class Graph
{
    /**
     * @return a list in which the index is the hop index and the object at the given index is
     * the collection of stations at the given hop.
     */
    static public List<Collection<Station>> getHops(NetworkingUnit networkingUnit, int maxHop)
    {
        if (maxHop < 0)
            throw new IllegalArgumentException();
        
        List<Collection<Station>> hops = new Vector<Collection<Station>>();
        Collection<Station> hop0 = new HashSet<Station>();
        hop0.add(networkingUnit.getStation());
        hops.add(hop0);

        while (hops.size() - 1 < maxHop)
        {
            Collection<Station> newHop = new HashSet<Station>();

            {
                Collection<Station> previousHop = hops.get(hops.size() - 1);
                
                for (Station s : previousHop)
                {
                    newHop.addAll(s.getNetworkingUnit().getNeighborhood());
                }
            }

            Iterator hopIterator = hops.iterator();
            
            while (hopIterator.hasNext())
            {
                newHop.removeAll((Collection) hopIterator.next());
            }

            hops.add(newHop);
        }

        return hops;
    }

    public static int getMaximumDegree(Network net)
    {
        if (net.getStations().isEmpty())
            throw new IllegalArgumentException();

        int max = 0;
        
        for (Station station : net.getStations())
        {
            int degree = station.getNetworkingUnit().getNeighborhood().size();
            
            if (degree > max)
            {
                max = degree;
            }
        }
        
        return max;
    }

    public static int getMinimumDegree(Network net)
    {
        Assertions.ensure(!net.getStations().isEmpty(), "no station in the network, the min degree cannot be processed");

        int min = Integer.MAX_VALUE;

        for (Station station : net.getStations())
        {
            int degree = station.getNetworkingUnit().getNeighborhood().size();
            
            if (degree < min)
            {
                min = degree;
            }
        }
        
        return min;
    }

    
    public static double getAverageDegree(Network net)
    {
        Collection c = new Vector();
        Iterator stationsIterator = net.getStations().iterator();
        
        while (stationsIterator.hasNext())
        {
            Station station = (Station) stationsIterator.next();
            double degree = station.getNetworkingUnit().getNeighborhood().size();
            c.add(new Double(degree));
        }
        
        return Utilities.getAverage(c);
        
//      return net.getConnections().size() / (double) net.getComputers().size();
    }


    
    public static Collection getRedundantConnections(Network net)
    {
        Collection c = new HashSet();
        Iterator stationsIterator = net.getStations().iterator();
        
        while (stationsIterator.hasNext())
        {
            Station station = (Station) stationsIterator.next();
            Iterator neighborIterator = station.getNetworkingUnit().getNeighborhood().iterator();

            while (neighborIterator.hasNext())
            {
                Station neighbor = (Station) neighborIterator.next();
                Collection connectionsToNeighbors = station.getNetworkingUnit().getConnectionsTo(neighbor);
                int connectionCount = connectionsToNeighbors.size();
                
                if (connectionCount > 1)
                {
                    c.add(connectionsToNeighbors);
                }
            }
        }
        
        return c;
    }

    
    
    public static Collection<Collection<Station>> getPartitions(Network net)
    {
        Collection<Collection<Station>> partitions = new Vector<Collection<Station>>();
        Collection<Station> stationsNotYetAffected = new HashSet<Station>(net.getStations());

        while (!stationsNotYetAffected.isEmpty())
        {
            Station station = stationsNotYetAffected.iterator().next();
            Collection<Station> partition = getPartition(station);
            stationsNotYetAffected.removeAll(partition);
            partitions.add(partition);
        }
        
        return partitions;
    }

    public static Collection<Station> getGreatestConnectedComponent(Network net)
    {
        double max = 0;
        Collection<Station> greatestComponent = null;
        
        for (Collection<Station> partition : getPartitions(net))
        {
            if (greatestComponent == null)
            {
                greatestComponent = partition;
            }
            else
            {
                int ps = partition.size();
                
                if (ps > max)
                {
                    greatestComponent = partition;
                    max = ps;
                }
            }
        }
        
        return greatestComponent;
    }


    private static Collection<Station> getPartition(Station station)
    {
        List<Station> partition = new Vector<Station>();
        partition.add(station);
        
        for (int i = 0; i < partition.size(); ++i)
        {
            for (Station neighbor : partition.get(i).getNetworkingUnit().getNeighborhood())
            {
                if (!partition.contains(neighbor))
                {
                    partition.add(neighbor);
                }
            }
        }
        
        return partition;
    }

    public static Collection findNetworkTypes(Network network)
    {
        Collection networkTypes = new HashSet();
        Iterator stationIterator = network.getStations().iterator();
        
        while (stationIterator.hasNext())
        {
            Station station = (Station) stationIterator.next();
            Iterator networkInterfaceIterator = station.getNetworkingUnit().getNetworkInterfaces().iterator();
            
            while (networkInterfaceIterator.hasNext())
            {
                NetworkInterface networkInterface = (NetworkInterface) networkInterfaceIterator.next();
                networkTypes.add(networkInterface.getNetworkingTechnology());
            }
        }
        
        return networkTypes;
    }

    public static Collection findBridgesTowardsNetworkType(Network network, NetworkingTechnology networkType)
    {
        Collection bridges = new Vector();
        Iterator stationIterator = network.getStations().iterator();
        
        while (stationIterator.hasNext())
        {
            Station station = (Station) stationIterator.next();
            
            // if the station has several network interface, among whose one if compliant with the given network type
            if (station.getNetworkingUnit().getNetworkInterfaces().size() > 1 && station.getNetworkingUnit().getNetworkInterface(networkType) != null)
            {
                bridges.add(station);
            }
        }   
        
        return bridges;
    }
    
    
    public static Collection findBridgesBetween(Network network, NetworkingTechnology t1, NetworkingTechnology t2)
    {
        Collection bridges = new Vector();
        Iterator stationIterator = network.getStations().iterator();
        
        while (stationIterator.hasNext())
        {
            Station station = (Station) stationIterator.next();
            
            if (station.getNetworkingUnit().getNetworkInterface(t1) != null && station.getNetworkingUnit().getNetworkInterface(t2) != null)
            {
                bridges.add(station);
            }
        }   
        
        return bridges;
    }

    public static Collection findUnreachableNetworkTypes(Network network)
    {
        Collection isolatedNetworkTypes = new Vector();
        Collection networkTypesInvolved = findNetworkTypes(network);
        
        if (networkTypesInvolved.size() > 1)
        {
            Iterator networkTypeIterator = networkTypesInvolved.iterator();
            
            while (networkTypeIterator.hasNext())
            {
                NetworkingTechnology networkType = (NetworkingTechnology) networkTypeIterator.next();
                Collection bridges = findBridgesTowardsNetworkType(network, networkType);
                        
                if (bridges.isEmpty())
                {
                    isolatedNetworkTypes.add(networkType);
                }
            }
        }
        
        return isolatedNetworkTypes;
    }
}