SIT221 – PROJECT 2 1 SIT221 –DATA STRUCTURES AND ALGORITHMS PROJECT2 DUE WEK 10, FRIDAY 11:59PM SUBMISSION INSTRUCTIONS Please submit your BackendService.cs file to the project2 folder. PROJECT DESCRIPTION Have you used GPS before to travel from one place to another? Was it useful? What about indoor navigation in a shopping center, hospital, airport, or even university campus where GPS is not available? Do you usually get lost? What do you currently do? Try to find a map, and if not then you keep walking around until you find what you want, if you are lucky enough! In this project we want to build an indoor navigation system that can help visitors of indoor venues to easily find and navigate to their point-of-interest (POI) as soon as possible. Let's take a shopping center as our motivating example here. Imagine that we have mounted Bluetooth based devices in the key areas in the shopping center – e.g. shops, toilets, food court, etc. and we have developed mobile app that visitors can install and be able to use it to find the location of a POI. The app will use the device built-in Bluetooth capability and installed Bluetooth-based devices in the shopping center to send to a backend server its current location. The server will then send directions back to the app based on the current location and intended location of the POI. See the figure below. In this project we want to implement the backend server – we call it BackendService - using the data structures we have learned in this unit.SIT221 – PROJECT 2 2 The specifications of the backend server are as follows: 1. List of POI, we need to maintain the list of POIs that a user might be interested to search for – e.g. McDonald's, Nike, Myer, etc. for each POI we want to store information like name, description, key services available, etc. By default, this list would not change quite often. We want this to be as fast as possible. A Hashtable (name it: POIsTable) would fit these details. The key will be POI name, and the value will be POI object. 2. Venue Graph. This is a graph of all the POI in the shopping center and paths between them. Note: if two POIs are not directly connect (no path between them), we should not have an edge between both POIs. A graph of venue POIs (name it: POIsGraph) with vertices are POIs, and edges are paths (for each edge we need to have distance between both source and target POI, and description to the user – e.g. walk straight until Myer).SIT221 – PROJECT 2 3 3. Active Devices and their DestinationPOIs. The server should keep information about current active devices (one for each visitor) along with their current location, requested destination, and current location/POI. A Dictionary (name it: ActiveDevicesTable) would fit these requirements. The key should be Device Id, and the value should be NavigationDetails Object which has the following information (DestinationPOI, CurrentPOI, and PathToDestination). Note: If DestinationPOI is null, then PathToDestination will be null. Otherwise, the PathToDestination will be a Stack> of remaining steps until the destination. 4. Find a POI. The server should have a method called "FindPOI" that takes three parameters: Device Id, CurrentPOI, and DestinationPOI – both of type POI. The method should do the following: a. calls the GetShortestPath(CurrentPOI, DestinationPOI) method (implemented for you). The returned stack of steps (Path). b. Adds the Device Id and NavigationDetails to the ActiveDevicesTable if it does not exist. c. If the Device Id already exists in the table, it replaces the current NavigationDetails with the new requested DestinationPOI. d. Remember to store the Path details in the ActiveDevicesTable (NavigationDetails.PathToDestination). So we can walk through while the visitor is moving in the shopping center towards the DestinationPOI. 5. Current location information. Each user (with a mobile app), will send a message to the backend server, whenever it passes by a location or a POI, its current location. The format of this message is [Device Id, CurrentPOI, and a timestamp]. These details need to be maintained in a data structure until further processing. A queue would fit these needs (name it: LocationServiceQueue). All received messages from different mobile apps (different visitors) will be forwarded to this queue for processing.SIT221 – PROJECT 2 4 6. Directions. The server should send users directions as they are walking towards the DestinationPOI. Once a message is received in the LocationServiceQueue, you need to do the following – implementation in the WatchLocationServiceQueue: a. Read the message b. Check Device Id if it exists in the ActiveDevicesTable, has a DestinationPOI, and still has steps to reach its destination. If yes, move to the next step in the stack and return it to the mobile app – set the CurrentPOI to the next POI. The rest is implemented for you in the Walk method. HOW TO APPROACH THIS PROBLEM? * First, make sure to download the solution template from Project 2 folder. * Second, please note that I'm using QuickGraph library to help with the ShortestPath and graph representation. * Third, you can download it using Nuget package manager. You can find all the places where you need to add your code through the Task (TODO) panel. 1. In the Runner project, expects one parameter: numberOfVisitors. Do not enter too many because the current implementation creates thread for each visitor. The rest of the Runner project does not need to be changed, unless you want to add new features. 2. Most of your code will be in Project2 folder in the DataStructures_Algorithms project. 3. In the same project folder you will find the following classes, you do not need to modify any of them, unless you want to: a. POI: Class that maintain a point-of-interest and its information. b. Edge: Class to maintain venue Graph edges, and distances. c. DeviceMessage: Class to maintain device message data d. NavigationDetails: Class to maintain NavigationDetails for a given MobileDevice including DestinationPOI, CurrentPOI, and a stack of steps to follow to go from CurrentPOI to DestinationPOI. 4. In the same project folder you will also find BackendService class. This is what you will need to add most of your code, as follows: a. Field & Property declarations: At the top of the class, there is a list of //TODO tasks for you to complete. This includes: //TODO: Declare LocationServiceQueue (public property & field) //This is where device messages will be enqueued. //The type of this data structure need to be ConcurrentQueueSIT221 – PROJECT 2 5 //TODO: Declare POIsTable (public property & field), //This table is used to maintain POI information //Key is string (POI Name), and value is POI object //The type of this data structure need to be Dictionary //TODO: Declare POIsGraph (public property & field), //This is a Bidirectional Graph between all POIs in the shopping center //Nodes of type POI, and Edges of type Edge //The type of this data structure need to be //BidirectionalGraph> //TODO: Declare ActiveDevicesTable (public property & field), //This is a dictionary of active devices and their navigation details //The type of this data structure needs to be //ConcurrentDictionary b. Implement the Init method: public void Init() i. You need to do the following: //TODO: Initialise your POIsTable //TODO: Intialise your POIsGraph //TODO: Add a list of POI locations (at least 10 POIs) to the POIsTable & to the POIsGraph //TODO: Add edges to your POIsGraph (20 edges? more? up to you) //TODO: Initialise your ActiveDevicesTable, this is an empty table - to be filled automatically c. Implement FindPOI method: public bool FindPOI(string DeviceId, POI Source, POI Target) . i. I have already implemented the GetShortestPath for you, which returns Stack>, stored in path variable. ii. You need to create a new NavigationDetails object and try to add (or update) the ActiveDevicesTable. See comment below and in the method body. //TODO: Please complete the FindPOI method - add navigation details to the ActiveDevicesTable. //This might be the first time the user asks for a navigation path or //He might have asked before, and changed his mind //So we need to use AddOrUpdate method which exists in the ConccurentDictionary class. //Please read here for details & example: https://msdn.microsoft.com/en-us/library/ee378665(v=vs.110).aspx //You may want to do it manually?SIT221 – PROJECT 2 6 //Then check if the key does not exist using ContainsKey, then call TryAdd //and if it does exist, then do ActiveDevicesTable[deviceId] = your new NavigationDetails object d. Implement WatchLocationServiceQueue method: void WatchLocationServiceQueue() i. This method will read a Device Message from the LocationServiceQueue using TryDequeue method. ii. Then update CurrentPOI to be the next step in the navigation route (from the PathToDestination Stack), see below and in code. //TODO: Complete the WatchLocationServiceQueue method //At this line, you have a message you retrieved from the queue - message object //If the message is sent by a known device (exists in the ActiveDevicesTable, //Then we need to update route & give directions //Otherwise skip the message //If the device known, then we need to check if there is other steps left in //the PathToDestination stack - you can use count > 0 //If yes then we need to Pop the edge from the stack // and then set the CurrentPOI of this device entry in the ActiveDevicesTable // to either Source or Target (based on route direction) //This step is important, because I wait for the value of the CurrentPOI to change //in the Walk method (see the Runner class) //To tell the user that there is a new direction Project 2 Rubric Fields/Properties Declarations See step 4 (a) above 2 marks half for each Init method See step 4(b) 3 marks 1 for initializations 1 for vertices 1 for edges FindPOI See step 4(c) 4 marks WatchLocationServiceQueue See step 4(d) 6 marks