1 package com.pathfinder.internal;
2
3 import com.pathfinder.api.GraphTraversalService;
4 import com.pathfinder.api.TransitEdge;
5 import com.pathfinder.api.TransitPath;
6
7 import java.util.*;
8
9 public class GraphTraversalServiceImpl implements GraphTraversalService {
10
11 private GraphDAO dao;
12 private Random random;
13 private static final long ONE_MIN_MS = 1000 * 60;
14 private static final long ONE_DAY_MS = ONE_MIN_MS * 60 * 24;
15
16 public GraphTraversalServiceImpl(GraphDAO dao) {
17 this.dao = dao;
18 this.random = new Random();
19 }
20
21 public List<TransitPath> findShortestPath(final String originUnLocode,
22 final String destinationUnLocode,
23 final Properties limitations) {
24 Date date = nextDate(new Date());
25
26 List<String> allVertices = dao.listLocations();
27 allVertices.remove(originUnLocode);
28 allVertices.remove(destinationUnLocode);
29
30 final int candidateCount = getRandomNumberOfCandidates();
31 final List<TransitPath> candidates = new ArrayList<TransitPath>(candidateCount);
32
33 for (int i = 0; i < candidateCount; i++) {
34 allVertices = getRandomChunkOfLocations(allVertices);
35 final List<TransitEdge> transitEdges = new ArrayList<TransitEdge>(allVertices.size() - 1);
36 final String firstLegTo = allVertices.get(0);
37
38 Date fromDate = nextDate(date);
39 Date toDate = nextDate(fromDate);
40 date = nextDate(toDate);
41
42 transitEdges.add(new TransitEdge(
43 dao.getVoyageNumber(originUnLocode, firstLegTo),
44 originUnLocode, firstLegTo, fromDate, toDate));
45
46 for (int j = 0; j < allVertices.size() - 1; j++) {
47 final String curr = allVertices.get(j);
48 final String next = allVertices.get(j + 1);
49 fromDate = nextDate(date);
50 toDate = nextDate(fromDate);
51 date = nextDate(toDate);
52 transitEdges.add(new TransitEdge(dao.getVoyageNumber(curr, next), curr, next, fromDate, toDate));
53 }
54
55 final String lastLegFrom = allVertices.get(allVertices.size() - 1);
56 fromDate = nextDate(date);
57 toDate = nextDate(fromDate);
58 transitEdges.add(new TransitEdge(
59 dao.getVoyageNumber(lastLegFrom, destinationUnLocode),
60 lastLegFrom, destinationUnLocode, fromDate, toDate));
61
62 candidates.add(new TransitPath(transitEdges));
63 }
64
65 return candidates;
66 }
67
68 private Date nextDate(Date date) {
69 return new Date(date.getTime() + ONE_DAY_MS + (random.nextInt(1000) - 500) * ONE_MIN_MS);
70 }
71
72 private int getRandomNumberOfCandidates() {
73 return 3 + random.nextInt(3);
74 }
75
76 private List<String> getRandomChunkOfLocations(List<String> allLocations) {
77 Collections.shuffle(allLocations);
78 final int total = allLocations.size();
79 final int chunk = total > 4 ? 1 + new Random().nextInt(5) : total;
80 return allLocations.subList(0, chunk);
81 }
82
83 }