There is a straight road with several towns along the road. Your program is given the distance between each pair of adjacent towns. You need to write a class to accept this input (as initialization) and has a method to calculate the distances between two arbitrary towns.

class Road - initialized with list of towns and distances between adjacent towns

Road(String[] towns, int[] distances)

Road.findDistance(String from, String to)

Road.findDistance - takes two towns and returns distance between them

A --- B ---- C --- D --- E

10 23 12 10

towns = {“A”, “B”, “C”, “D”, “E”}

distances = {10, 23, 12, 10}

findDistance(“C”, “E”) = 22 -> takes constant time.

import java.util.HashMap;

import java.util.Map;

public class Road {

static Map<String, Integer> map = new HashMap<String, Integer>();

int size;

static int distance_sum[];

public Road(String[] towns, int[] distances) {

if (towns.length < 2 || distances.length < 1

|| distances.length != towns.length - 1)

return;

distance_sum = new int[distances.length];

for (int i = 0; i < towns.length; i++) {

map.put(towns[i], i);

}

distance_sum[0] = 0;

for (int i = 1; i < distances.length + 1; i++) {

distance_sum[i] += distances[i - 1] + distance_sum[i - 1];

}

}

public static int findDistance(String from, String to) {

int startIndex = -1;

if (map.get(from) != null)

startIndex = map.get(from);

int toIndex = -1;

if (map.get(to) != null)

toIndex = map.get(to);

if (toIndex == -1 || startIndex == -1)

return -1;

if (startIndex == toIndex)

return 0;

if (startIndex > toIndex) {

return distance_sum[startIndex] - distance_sum[toIndex];

} else

return distance_sum[toIndex] - distance_sum[startIndex];

}

}

## No comments:

Post a Comment