· 10 years ago · Sep 21, 2016, 08:32 AM
1using System;
2using System.Collections.Concurrent;
3using System.Collections.Generic;
4using System.Threading;
5using QuickGraph;
6using QuickGraph.Algorithms.Observers;
7
8namespace DataStructures_Algorithms
9{
10 public class BackendService
11 {
12 //TODO: Declare LocationServiceQueue (public property & field)
13 //This is where device messages will be enqueued.
14 //The type of this data structure need to be ConcurrentQueue<DeviceMessage>
15 private ConcurrentQueue<DeviceMessage> _LocationServiceQueue;
16 public ConcurrentQueue<DeviceMessage> LocationServiceQueue
17 {
18 get
19 {
20 return _LocationServiceQueue;
21 }
22 set
23 {
24 _LocationServiceQueue = value;
25 }
26 }
27 //TODO: Declare POIsTable (public property & field), this table is used to maintain POI information
28 //Key is string (POI Name), and value is POI object
29 //The type of this data structure need to be Dictionary<string, POI>
30 private Dictionary<string, POI> _POIsTable;
31 public Dictionary<string, POI> POIsTable
32 {
33 get
34 {
35 return _POIsTable;
36 }
37 set
38 {
39 _POIsTable = value;
40 }
41 }
42
43 //TODO: Declare POIsGraph (public property & field), this is a Bidirectional Graph between all POIs in the shopping center
44 //Nodes of type POI, and Edges of type Edge<POI>
45 //The type of this data structure need to be BidirectionalGraph<POI, Edge<POI>>
46 private BidirectionalGraph<POI, Edge<POI>> _POIsGraph;
47 public BidirectionalGraph<POI, Edge<POI>> POIsGraph
48 {
49 get
50 {
51 return _POIsGraph;
52 }
53 set
54 {
55 _POIsGraph = value;
56 }
57 }
58
59 //TODO: Declare ActiveDevicesTable (public property & field), this is a dictionary of active devices and their navigation details
60 //The type of this data structure needs to be ConcurrentDictionary<string, NavigationDetails>
61 private ConcurrentDictionary<string, NavigationDetails> _ActiveDevicesTable;
62 public ConcurrentDictionary<string, NavigationDetails> ActiveDevicesTable
63 {
64 get
65 {
66 return _ActiveDevicesTable;
67 }
68 set
69 {
70 _ActiveDevicesTable = value;
71 }
72 }
73
74
75
76 public int NumberOfPOIs
77 {
78 get { return POIsTable.Count; }
79
80 }
81
82 public bool ShoppingCenterIsOpen { get; set; }
83
84
85 public bool FindPOI(string DeviceId, POI Source, POI Target)
86 {
87 Stack<Edge<POI>> path = GetShortestPath(Source, Target);
88 if (path == null) return false;
89
90 //TODO: Please complete the FindPOI method - add navigation details to the ActiveDevicesTable.
91 //This might be the first time the user asks for a navigation path or
92 //He might have asked before, and changed his mind
93 //So we need to use AddOrUpdate method which exists in the ConccurentDictionary class.
94 //Please read here for details & example: https://msdn.microsoft.com/en-us/library/ee378665(v=vs.110).aspx
95 //You may want to do it manually? then check if the key does not exist using ContainsKey, then call TryAdd
96 //and if it does exist, then do ActiveDevicesTable[deviceId] = your new NavigationDetails object
97
98 var nav = new NavigationDetails { CurrentPOI = Source, DestinationPOI = Target, PathToDestination = path };
99 ActiveDevicesTable.AddOrUpdate(DeviceId, nav, (k, v) => nav);
100 return true;
101
102 }
103 public BackendService()
104 {
105
106 }
107 public void Init()
108 {
109 //TODO: Initialise your POIsTable
110 _POIsTable = new Dictionary<string, POI>();
111 //TODO: Intialise your POIsGraph
112 _POIsGraph = new BidirectionalGraph<POI, Edge<POI>>();
113 //TODO: Add a list of POI locations (at least 10 POIs) to the POIsTable & to the POIsGraph
114 //Many lines here for POIs
115 POI Myer = new POI
116 {
117 POIName = "Myer",
118 POIDescription = "Fashion clothing",
119 Services = new List<string>
120 {
121 "Mens clothing",
122 "Womens clothing",
123 "Accessories",
124 }
125 };
126 _POIsTable.Add("Myer",Myer);
127 _POIsGraph.AddVertex(Myer);
128 POI Coles = new POI
129 {
130 POIName = "Coles",
131 POIDescription = "Supermarket",
132 Services = new List<string>
133 {
134 "Vegetable",
135 "Deli",
136 "Liquor",
137 }
138 };
139 _POIsTable.Add("Coles", Coles);
140 _POIsGraph.AddVertex(Coles);
141 POI JBHifi = new POI
142 {
143 POIName = "JB-Hifi",
144 POIDescription = "Electronic store",
145 Services = new List<string>
146 {
147 "Computers",
148 "Phones",
149 "Gadgets",
150 }
151 };
152 _POIsTable.Add("JB-Hifi", JBHifi);
153 _POIsGraph.AddVertex(JBHifi);
154 POI GoodGuys = new POI
155 {
156 POIName = "The Good Guys",
157 POIDescription = "Kitchen wares",
158 Services = new List<string>
159 {
160 "Microwave",
161 "Oven",
162 }
163 };
164 _POIsTable.Add("The Good Guys", GoodGuys);
165 _POIsGraph.AddVertex(GoodGuys);
166 POI AmartSport = new POI
167 {
168 POIName = "Amart Sport",
169 POIDescription = "Sport equipment",
170 Services = new List<string>
171 {
172 "footware",
173 "apparel",
174 "Accessories",
175 }
176 };
177 _POIsTable.Add("AmartSport", AmartSport);
178 _POIsGraph.AddVertex(AmartSport);
179 POI Apple = new POI
180 {
181 POIName = "Apple Store",
182 POIDescription = "Electronic store",
183 Services = new List<string>
184 {
185 "Warranty services",
186 "Apple devices",
187 "Accessories",
188 }
189 };
190 _POIsTable.Add("Apple", Apple);
191 _POIsGraph.AddVertex(Apple);
192 POI Adidas = new POI
193 {
194 POIName = "Adidas",
195 POIDescription = "Sport clothing",
196 Services = new List<string>
197 {
198 "Footware",
199 "Apparel",
200 "Accessories",
201 }
202 };
203 _POIsTable.Add("Adidas", Adidas);
204 _POIsGraph.AddVertex(Adidas);
205 POI AuPost = new POI
206 {
207 POIName = "Australia Post",
208 POIDescription = "post offer",
209 Services = new List<string>
210 {
211 "post office",
212 }
213 };
214 _POIsTable.Add("Aupost", AuPost);
215 _POIsGraph.AddVertex(AuPost);
216 POI Optus = new POI
217 {
218 POIName = "Optus",
219 POIDescription = "Mobile services",
220 Services = new List<string>
221 {
222 "Mobile phones",
223 "Sim plans",
224 "Phone accessories",
225 }
226 };
227 _POIsTable.Add("Optus", Optus);
228 _POIsGraph.AddVertex(Optus);
229 //TODO: Add edges to your POIsGraph (20 edges? more? up to you)
230 //Many lines here for edge
231 POIsGraph.AddEdge(new Edge<POI>
232 {
233 Source = Myer,
234 Target = JBHifi,
235 Description = "1 minute",
236 Distance = 5,
237 });
238 POIsGraph.AddEdge(new Edge<POI>
239 {
240 Source = Myer,
241 Target = AuPost,
242 Description = "3 minute",
243 Distance = 30,
244 });
245 POIsGraph.AddEdge(new Edge<POI>
246 {
247 Source = JBHifi,
248 Target = Adidas,
249 Description = "2 minute",
250 Distance = 43,
251 });
252 POIsGraph.AddEdge(new Edge<POI>
253 {
254 Source = JBHifi,
255 Target = Coles,
256 Description = "2 minute",
257 Distance = 40,
258 });
259 POIsGraph.AddEdge(new Edge<POI>
260 {
261 Source = Adidas,
262 Target = Optus,
263 Description = "5 minute",
264 Distance = 100,
265 });
266 POIsGraph.AddEdge(new Edge<POI>
267 {
268 Source = Adidas,
269 Target = AuPost,
270 Description = "6 minute",
271 Distance = 120,
272 });
273 POIsGraph.AddEdge(new Edge<POI>
274 {
275 Source = Coles,
276 Target = Apple,
277 Description = "4 minute",
278 Distance = 62,
279 });
280 POIsGraph.AddEdge(new Edge<POI>
281 {
282 Source = Coles,
283 Target = AuPost,
284 Description = "2 minute",
285 Distance = 35,
286 });
287 POIsGraph.AddEdge(new Edge<POI>
288 {
289 Source = AuPost,
290 Target = AmartSport,
291 Description = "7 minute",
292 Distance = 145,
293 });
294 POIsGraph.AddEdge(new Edge<POI>
295 {
296 Source = AuPost,
297 Target = GoodGuys,
298 Description = "2 minute",
299 Distance = 32,
300 });
301 POIsGraph.AddEdge(new Edge<POI>
302 {
303 Source = GoodGuys,
304 Target = JBHifi,
305 Description = "1 minute",
306 Distance = 16,
307 });
308 POIsGraph.AddEdge(new Edge<POI>
309 {
310 Source = GoodGuys,
311 Target = Apple,
312 Description = "2 minute",
313 Distance = 35,
314 });
315 POIsGraph.AddEdge(new Edge<POI>
316 {
317 Source = AuPost,
318 Target = Myer,
319 Description = "3 minute",
320 Distance = 58,
321 });
322 //TODO: Initialise your ActiveDevicesTable, this is an empty table - to be filled automatically
323 _ActiveDevicesTable = new ConcurrentDictionary<string, NavigationDetails>();
324 _LocationServiceQueue = new ConcurrentQueue<DeviceMessage>();
325 //Now let's open the shopping center and create a queue handling thread.
326 //You do not need to modify this code
327 ShoppingCenterIsOpen = true;
328 Thread queueHandler = new Thread(() => this.WatchLocationServiceQueue());
329 queueHandler.Start();
330 }
331 void WatchLocationServiceQueue()
332 {
333 DeviceMessage message = null;
334 while (ShoppingCenterIsOpen == true && LocationServiceQueue.TryDequeue(out message) == false) { }
335 if (ShoppingCenterIsOpen == false) return;
336
337 //TODO: Complete the WatchLocationServiceQueue method
338 //At this point (line), you have a message you retrieved from the queue - this is the message object
339 //If the message is sent by a known device exists in the ActiveDevicesTable, then we need to update route & give directions
340 //Otherwise -else skip the message, in a future version, you may track people movement in the shoppping center (not now)
341 //If the device known - exists in the ActiveDevicesTable, then we need to check if there is any step left in
342 //the PathToDestination stack - you can use count > 0
343 //If yes then we need to Pop an edge from the stack
344 // and then set the CurrentPOI of this device entry in the ActiveDevicesTable
345 // to either Source or Target (based on route direction)
346 //This step is important, because I wait for the value of the CurrentPOI to change
347 //in the Walk method (see the Runner class)
348 //To tell the user that there is a new direction
349 if(_ActiveDevicesTable.ContainsKey(message.DeviceId))
350 {
351 if (_ActiveDevicesTable[message.DeviceId].PathToDestination.Count > 0)
352 {
353 if (_ActiveDevicesTable[message.DeviceId].PathToDestination.Pop().Source == _ActiveDevicesTable[message.DeviceId].CurrentPOI)
354 {
355 _ActiveDevicesTable[message.DeviceId].CurrentPOI = _ActiveDevicesTable[message.DeviceId].PathToDestination.Pop().Target;
356 }
357 else
358 {
359 _ActiveDevicesTable[message.DeviceId].CurrentPOI = _ActiveDevicesTable[message.DeviceId].PathToDestination.Pop().Source;
360 }
361 }
362 }
363
364
365 //This will make sure that we process the next item in the LocationServiceQueue
366 WatchLocationServiceQueue();
367 }
368
369
370 public Stack<Edge<POI>> GetShortestPath(POI Source, POI Target)
371 {
372 QuickGraph.Algorithms.ShortestPath.DijkstraShortestPathAlgorithm<POI, Edge<POI>> algo =
373 new QuickGraph.Algorithms.ShortestPath.DijkstraShortestPathAlgorithm<POI, Edge<POI>>(POIsGraph, (Edge<POI> arg) => arg.Distance);
374
375
376 // creating the observer & attach it
377 var vis = new VertexPredecessorRecorderObserver<POI, Edge<POI>>();
378 vis.Attach(algo);
379
380 // compute and record shortest paths
381 algo.Compute(Target);
382
383 // vis can create all the shortest path in the graph
384 IEnumerable<Edge<POI>> path = null;
385 vis.TryGetPath(Source, out path);
386 Stack<Edge<POI>> pathStack = new Stack<Edge<POI>>();
387 if (path == null) return null;
388
389 foreach (Edge<POI> e in path)
390 pathStack.Push(e);
391 return pathStack;
392 }
393
394
395
396 }
397}