The Net: Ultimate Internet Guide/WWLCD1.ISO/pc/java/ingzp26a/route.java

Java Source | 1996-08-14 | 4.8 KB | 159 lines

/* $Id: Route.java,v 1.2 1996/03/31 11:43:02 djun Exp djun $

   File: Route.java

   Defines the class Route.   A route is a sequence of Carriers.

   Author: Djun M. Kim
   Copyright (c) 1996 Djun M. Kim.  All rights reserved.


*/

import Carrier;
import java.util.*;


// A Route is a sequence of Carriers
class Route {

    private Map parent;

    public static final int MAXINT = 2147483647;    // largest "int"

    private Vector segments;    // the carriers comprising the route.
    private String name;
    private int length;
    private String description;

    // Constructor - returns an empty route.
    Route(Map parent) {
    this.parent = parent;
    segments = new Vector();
    name = new String("");
    description = new String("");
    length = 0;
    }

    public String print(Route r) {
    String routestr = new String();
    for (Enumeration e = segments.elements(); e.hasMoreElements(); ) {
        routestr = routestr + ((Carrier) e.nextElement()).getName();
        }
    return routestr;
    }

    public void addSegment(Carrier c) {
    length = length + c.getLength().intValue();
    segments.addElement(c);
    }

    public String getName() {
    return name;
    }

    public int length() {
    return length;
    }


    /*------------------------------------------------------------
            Routing/Shortest Path
      ------------------------------------------------------------*/

    // Get the minimum distance between two locations.
    // Returns MAXINT if there is no carrier between the locations.
    // At the moment this assumes that there is only one type of carrier.
    // But the locations can be connected by multiple carriers.
    public int dist(Location v, Location u) {
    int distance = MAXINT;
    for (Enumeration e = v.exits.elements(); e.hasMoreElements();) {
        Carrier c = (Carrier)e.nextElement();
        if (c.sink == u) {
        distance = java.lang.Math.min(distance, c.length.intValue());
        }
    }
    return distance;
    }


    // Get the shortest carrier between two locations.
    // Returns null if there is no carrier between the locations.
    // At the moment this assumes that there is only one type of carrier.
    // But the locations can be connected by multiple carriers.
    public Carrier minCarrier(Location v, Location u) {
    Carrier min_c = new Carrier(parent, null, null, MAXINT, 0);
    for (Enumeration e = v.exits.elements(); e.hasMoreElements();) {
        Carrier c = (Carrier)e.nextElement();
        if (c.sink == u) {
        if (c.getLength().intValue() < min_c.getLength().intValue()) {
            min_c = c;
        }
        }
    }
    return min_c;
    }

    // Get shortest route between two locations on map.  Returns an
    // empty route if no route exists.  Uses Dijkstra's algorithm...
    public Route shortestPath(Location source, Location dest, Hashtable Locations) {
    Hashtable length = new Hashtable();    // upper bound on length of shortest path
    Hashtable shortest = new Hashtable();    // shortest path found so far - indexed by loc
    Vector Examined = new Vector();        // locations examined so far
    Vector Unexamined = new Vector();
    Route r = new Route(parent);
    Location ux = new Location(parent, 0, 0);    // unexamined location
    int lux = 0;                // length of path to ux.
    if (source != null && dest != null) {
        // Initialize length of "known" paths; unexamined locations
        for (Enumeration enum = Locations.elements();
           enum.hasMoreElements(); ) {
        Location loc = (Location) enum.nextElement();
        if (loc.getName() != "Carrier") {
            length.put(loc, new Integer(dist(source, loc)));
            Route s = new Route(parent);
            s.addSegment(minCarrier(source, loc));
            shortest.put(loc, s);
            Unexamined.addElement(loc);
        }
        }
        length.put(source, new Integer(0));
        shortest.put(source, new Route(parent));
        Examined.addElement(source);
        Unexamined.removeElement(source);
        while (!Unexamined.isEmpty()) {
    found_least:for (Enumeration unex = Unexamined.elements(); unex.hasMoreElements(); ) {
            ux = (Location)unex.nextElement();
    next:        for (Enumeration ex = Examined.elements(); ex.hasMoreElements(); ) {
            boolean found = true;
            Location x = (Location)ex.nextElement();
            lux = ((Integer)length.get(ux)).intValue();
            int lx =  ((Integer)length.get(x)).intValue();
            if (lux >= lx) {
                found = false;
                break next;
            }
            if (found) break found_least;
            }
        }
            Examined.addElement(ux);
        Unexamined.removeElement(ux);
        for (Enumeration unex = Unexamined.elements(); unex.hasMoreElements(); ) {
            Location v = (Location)unex.nextElement();
            int lv = ((Integer)length.get(v)).intValue();
            int testlen = ((Integer)length.get(ux)).intValue() + dist(ux, v);
            if (testlen < lv) {
            length.put(v, new Integer(testlen));
            Route s = (Route)shortest.get(ux);
            s.addSegment(minCarrier(ux, v));
            shortest.put(v, s);            // update shortest path to v
            }
        }
        }
        }
        return r;
    }

}