names = ["Pathways", "Pather", "Cheap Ways"];
suffixes = ["Inc.", "Co.", "S.A.", "Corps"]

cityCargoClasses = [
    AICargo.CargoClass.CC_PASSENGERS,
    AICargo.CargoClass.CC_MAIL
];

function pick(arr)
{
    return arr[1.0 * arr.len() * rand() / RAND_MAX];
}

function checkMoney(money, func)
{
    if ( AICompany.GetBankBalance(AICompany.CompanyID.COMPANY_SELF) > money )
        func(AICompany.GetBankBalance(AICompany.CompanyID.COMPANY_SELF));
}

function ClosestDepotToRoad(begin)
{
    neighbors = AITileList();
    neighbors.Add(begin, 0);

    costs = {
        [begin] = 0
    };

    cameFrom = {
        [begin] = null;
    };

    function CostFor(current, tile)
    {
        return GetSlope(tile) != AITile.Slope.SLOPE_FLAT ? 2 : 1;
    }

    function CostForBridge(tile)
    {
        return	  AIBridge.GetMinLength(AIBridge.GetBridgeID(tile))
                / AIBridge.GetMaxSpeed(AIBridge.GetBridgeID(tile));
    }

    function CostForTunnel(tile)
    {
        return	  AITile.GetManhattanDistance(tile, AITunnel.GetOtherTunneEnd(tile))
                / AIEngine.GetMaxSpeed(
                    AIEngineList(AIVehicle.VehicleType.VT_RAIL)
                            .Valuate(AIEngine.GetPrice)
                            .End()
                );
    }

    function CalcCameFrom(tile, current)
    {
        if ( !cameFrom.HasItem(tile) || neighbors.GetValue(tile) < CostFor(current, tile) )
            cameFrom[tile] <- current;
    }

    function AddNeighbor(tile, current)
    {
        if ( AIRail.IsRailTile(tile) && AIRail.AreTilesConnected(tile, current) )
        {
            CalcCameFrom(tile, current);

            neighbors.SetValue(tile, CostFor(current, tile));
        }
    }

    function AddBridge(tile)
    {
        if ( !AIRail.IsRailTile(tile) )
            return;

        if ( AIBridge.IsBridgeTile(tile) )
        {
            CalcCameFrom(AIBridge.GetOtherBridgeEnd(tile), tile);

            neighbors.SetValue(tile, CostForBridge(tile));
        }

        else if ( AITunnel.IsTunnelTile(tile) )
        {
            CalcCameFrom(AITunnel.GetOtherTunneEnd(tile), tile);

            neighbors.SetValue(tile, CostForTunnel(tile));
        }
    }

    while ( neighbors.Count() > 0 )
    {
        t = neighbors.Begin();
        neighbors.RemoveTop(1);

        // orthogonals
        AddNeighbor(tile - AIMap.GetTileIndex(1,0));
        AddNeighbor(tile - AIMap.GetTileIndex(0,1));
        AddNeighbor(tile - AIMap.GetTileIndex(-1,0));
        AddNeighbor(tile - AIMap.GetTileIndex(0,-1));

        // diagonals
        AddNeighbor(tile - AIMap.GetTileIndex(-1,1));
        AddNeighbor(tile - AIMap.GetTileIndex(1,1));
        AddNeighbor(tile - AIMap.GetTileIndex(1,-1));
        AddNeighbor(tile - AIMap.GetTileIndex(-1,-1));
        
        AddBridge(t);
    }

    return function(depot)
    {
        if ( cameFrom.HasItem(depot) )
            return costs[depot];

        return 0x7FFF;
    };
}

function TilesInCity(city)
{
    tiles = AITileList();
    neighbors = AITileList();

    function AddNeighbor(tile)
    {
        if ( AITown.IsWithinTownInfuence(city, tile) )
        {
            neighbors.AddTile(tile);
            tiles.AddTile(tile);
        }
    }

    while ( neighbors.Count() > 0 )
    {
        t = neighbors.Begin();
        neighbors.RemoveTop(1);

        // orthogonals
        AddNeighbor(tile - AIMap.GetTileIndex(1,0));
        AddNeighbor(tile - AIMap.GetTileIndex(0,1));
        AddNeighbor(tile - AIMap.GetTileIndex(-1,0));
        AddNeighbor(tile - AIMap.GetTileIndex(0,-1));
    }

    return tiles;
}

function CityOutletRoads(city)
{
    outlets = AITileList();

    function IsOutlet(tile)
    {
        if ( !AIRoad.IsRoadTile(tile) )
            return false;

        neighbors = OrthoNeighbors(tile);

        neighboringRoads = 0;

        foreach ( tile in neighbors )
        {
            if ( !AITile.IsBuildable(tile) )
                return false;

            if ( AIRoad.IsRoadTile(tile) )
                neighboringRoads++;
        }

        return neighboringRoads == 1;
    }

    foreach ( tile, val in TilesInCity(city) )
    {
        if ( IsOutlet(tile) )
            outlets.AddTile(tile);
    }

    return outlets;
}

function OrthoNeighbors(point)
{
    return [
        AddNeighbor(tile - AIMap.GetTileIndex(1,0)),
        AddNeighbor(tile - AIMap.GetTileIndex(0,1)),
        AddNeighbor(tile - AIMap.GetTileIndex(-1,0)),
        AddNeighbor(tile - AIMap.GetTileIndex(0,-1))
    ];
}

class RoadPath
{
    path = null;

    constructor(p)
    {
        path = p;
    }

    function BuildPath()
    {
        for ( local i = 0; i < path.len() - 1; i++ )
            if ( !AIRoad.BuildRoad(path[i], path[i] + 1) )
                return false;

        return true;
    }

    function BuildStations()
    {
        local done = false;
        local pos = 0;

        while ( AIRoad.BuildRoadStation(
            path[pos], path[pos] + 1,
            AIRoad.RoadVehicleType.ROADVEHTYPE_BUS,
            AIStation.STATION_JOIN_ADJACENT
        ) )
        {
            pos++;
            done = true;
        }

        if ( !done )
            return false;

        done = false;
        pos = path.len() - 1;

        while ( AIRoad.BuildRoadStation(
            path[pos], path[pos] - 1,
            AIRoad.RoadVehicleType.ROADVEHTYPE_BUS,
            AIStation.STATION_JOIN_ADJACENT
        ) )
        {
            pos--;
            done = true;
        }

        return done;
    }

    function RandomPoint()
    {
        return pick(path);
    }

    function RandomNeighboringPoint()
    {
        candidates = [];

        while ( candidates.len() < path.len() )
        {
            p = RandomPoint();

            if ( !(p in candidates) )
                candidates.push(p);
        }

        foreach ( p in candidates )
            foreach ( neighbor in OrthoNeighbors(p) )
                if ( !AIRoad.IsRoadTile(neighbor) && AITile.IsBuildable(neighbor) )
                    return {
                        pos = neighbor,
                        from = p
                    };

        return null;
    }

    function Begin()
    {
        return path[0];
    }

    function End()
    {
        return path[path.len() - 1];
    }
}

function CityPathes(city1, city2)
{
    paths = []
    pathCosts = AIList();

    destinations = CityOutletRoads(city2);

    function findOutletPath(outlet)
    {
        neighbors = AITileList();
        neighbors.Add(outlet, 0);

        costs = {
            [outlet] = 0
        };

        cameFrom = {
            [outlet] = null;
        };

        function CostFor(current, tile)
        {
            return GetSlope(tile) != AITile.Slope.SLOPE_FLAT ? 2 : 1;
        }

        function CostForBridge(tile)
        {
            return	  AIBridge.GetMinLength(AIBridge.GetBridgeID(tile))
                    / AIBridge.GetMaxSpeed(AIBridge.GetBridgeID(tile));
        }

        function CostForTunnel(tile)
        {
            return	  AITile.GetManhattanDistance(tile, AITunnel.GetOtherTunneEnd(tile))
                    / AIEngine.GetMaxSpeed(
                        AIEngineList(AIVehicle.VehicleType.VT_ROAD)
                                .Valuate(AIEngine.GetPrice)
                                .End()
                    );
        }

        function CalcCameFrom(tile, current)
        {
            if ( !cameFrom.HasItem(tile) || neighbors.GetValue(tile) < CostFor(current, tile) )
                cameFrom[tile] <- current;
        }

        function AddNeighbor(tile, current)
        {
            if ( AIRoad.IsRoadTile(tile) && AIRoad.AreRoadTilesConnected(tile, current) )
            {
                CalcCameFrom(tile, current);

                neighbors.SetValue(tile, CostFor(current, tile));
            }
        }

        function AddBridge(tile)
        {
            if ( !AIRoad.IsRoadTile(tile) )
                return;

            if ( AIBridge.IsBridgeTile(tile) )
            {
                CalcCameFrom(AIBridge.GetOtherBridgeEnd(tile), tile);

                neighbors.SetValue(tile, CostForBridge(tile));
            }

            else if ( AITunnel.IsTunnelTile(tile) )
            {
                CalcCameFrom(AITunnel.GetOtherTunneEnd(tile), tile);

                neighbors.SetValue(tile, CostForTunnel(tile));
            }
        }

        while ( neighbors.Count() > 0 )
        {
            t = neighbors.Begin();
            neighbors.RemoveTop(1);

            // orthogonals
            AddNeighbor(tile - AIMap.GetTileIndex(1,0));
            AddNeighbor(tile - AIMap.GetTileIndex(0,1));
            AddNeighbor(tile - AIMap.GetTileIndex(-1,0));
            AddNeighbor(tile - AIMap.GetTileIndex(0,-1));

            AddBridge(tile);
        }

        pathes = [];
        pcosts = AIList();

        foreach ( dest in destinations )
        {
            path = [];
            c = dest;

            while ( c != null && c in cameFrom )
            {
                path.push(c);

                c = cameFrom[c];

                if ( c == outlet )
                    break;
            }

            pcosts.SetValue(pathes.len(), costs[dest]);
            path.reverse();
            pathes.push(path);
        }

        return {
            "pathes" = pathes,
            "costs" = pcosts
        };
    }

    foreach ( outlet, _ in CityOutletRoads(city1) )
    {
        res = findOutletPath(outlet);

        paths.extend(RoadPath(res.pathes));
        pathCosts.AddList(res.costs);
    }

    return {
        "pathes": paths,
        "costs": pathCosts
    };
}

function ClosestCityPath(city1, city2)
{
    res = CityPathes(city1, city2);

    if ( res.costs.Count() == 0 )
        return null;

    return res.pathes[res.costs.Begin()];
}

function pollEvents()
{
    while (AIEventController.IsEventWaiting()) {
        local e = AIEventController.GetNextEvent();

        switch (e.GetEventType()) {
            case AIEvent.AI_ET_VEHICLE_CRASHED:
                local ec = AIEventVehicleCrashed.Convert(e);
                local v  = ec.GetVehicleID();
                AILog.Info("We have a crashed vehicle (" + v + ")");

                /* Handle the crashed vehicle */
                AIVehicle.StartStopVehicle( wAIVehicle.CloneVehicle(
                    AIDepotList()
                            .Valuate(ClosestDepotToRoad(
                                AIEventVehicleCrashed.Convert(e).GetCrashSite())
                            )
                            .End(),

                    AIEventVehicleCrashed.Convert(e).GetVehicleID();
                    true
                ) );

                break;
        }
    }
}

function max(a, b)
{
    return a > b ? a : b;
}

function EstimateNumVehicles(path, engine)
{
    return max(
        AITile.GetManhattanDistance(path.Begin(), path.End()) + 3) / AIEngine.GetMaxSpeed(engine)
                - AIEngine.GetCapacity(engine) / 8),

        1
    );
}

function linkGivenCities(engine, start, end)
{
    path = ClosestCityPath(start, end);

    if ( path == null )
    {
        AILog.Warning("Could not link " + AITown.GetName(start) + " to " + AITown.GetName(end) + ": No path found!");

        return false;
    }

    if ( !path.BuildPath() )
    {
        AILog.Warning("Could not link " + AITown.GetName(start) + " to " + AITown.GetName(end) + ": Road building failed!");

        return false;
    }

    else
    {
        depot = path.RandomNeighboringPoint();

        if ( depot == null )
        {
            AILog.Warning("Could not link " + AITown.GetName(start) + " to " + AITown.GetName(end) + ": No depot location found in pathway built!");

            return false;
        }

        if ( !AIRoad.BuildRoadDepot(depot.pos, depot.from) )
        {
            AILog.Warning("Could not link " + AITown.GetName(start) + " to " + AITown.GetName(end) + ": Depot building failed!");

            return false;
        }

        veh = BuildVehicle(depot.pos, engine);

        for ( i = 1; i <= EstimateNumVehicles(path, engine); i++ )
        {
            if ( veh == null )
            {
                AILog.Warning("Could not link " + AITown.GetName(start) + " to " + AITown.GetName(end) + " with vehicle #" + i + ": Vehicle buying failed!");

                return false;
            }

            if ( !path.BuildStations() )
            {
                AILog.Warning("Could not link " + AITown.GetName(start) + " to " + AITown.GetName(end) + " with vehicle #" + i + ": Could not build stations!");

                return false;
            }

            if ( AITile.GetManhattanDistance(depot, path.Begin()) < AITile.GetManhattanDistance(depot, path.End()) )
                locs = [path.Begin(), depot.pos, path.End()];

            else
                locs = [path.Begin(), path.End(), depot.pos];

            foreach ( l in locs )
            {
                if ( !AIOrder.AppendOrder(
                    veh,
                    l,
                    l == depot.pos ? AIOrder.AIOrderFlags.OF_SERVICE_IF_NEEDED : AIOrder.AIOrderFlags.OF_NONE
                ) )
                {
                    AILog.Warning("Could not link " + AITown.GetName(start) + " to " + AITown.GetName(end) + " with vehicle #" + i + ": Could not add vehicle orders!");

                    return false;
                }
            }

            if ( !AIVehicle.StartStopVehicle(veh) )
            {
                AILog.Warning("Could not link " + AITown.GetName(start) + " to " + AITown.GetName(end) + " with vehicle #" + i + ": Could not start vehicle!");

                return false;
            }
        }
    }

    return true;
}

function linkCities(engine)
{

}

class EdsgerMain extends AIController
{
    function Start();
}

function NameCompany()
{
    if ( AICompany.IsMine(AICompany.CompanyID.COMPANY_SELF) )
    {
        retries = 0;

        while ( !AICompany.SetName(pick(names) + " " + pick(suffixes)) && retries < 25 )
            retries++;

        if ( retries == 25 )
        {
            i = 0;

            while ( true )
            {
                retries = 0;

                while ( !AICompany.SetName(pick(names) + " " + pick(suffixes)) + " #" + i && retries < 25 )
                    retries++;

                if ( retries == 25 )
                    i++;

                else
                    break;
            }
        }

        AICompany.SetPresidentName("Edsger W. Dijkstra")
    }
}

function EdsgerMain::Start()
{
    NameCompany();

    while (true) {
        pollEvents();

        cheapVeh = AIEngineList(AIVehicle.VehicleType.VT_ROAD)
            .Valuate(function(engine) {
                AICargo.HasCargoClass(AIEngine.GetCargoType(engine), pick(cityCargoClasses))
            })
            .KeepValue(1)
            .Valuate(AIEngine.GetPrice)
            .End();

        checkMoney(12000 + AIEngine.GetPrice(cheapVeh), function(cost) {
            linkCities(cheapVeh);
        })

        this.Sleep(150);
    }
}