Answer Happy

1 Introduction Vehicle hiring companies such as Uber, Careem, and Joeny rely on fast localization of available vehicles near potential customers. Such efficient localization requires specialized data structures, and the goal of this project is to implement and use one such data structure. 2 Storing vehicles locations Vehicles and customers are localized using GPS devices available in mobile phones, and these devices determine the longitude and latitude coordinates as floating-point numbers. To simplify the task, however, we will divide the geographical area under consideration into small cells and use integers to identify ench location on the map (see Figure 1). w ol O DO o Figure 1: The city is divided into small cells so that a location is identified by two integer coordinates rund y. Note that a single cell may contain several vehicles and customers, When a customer request a ride, only vehicles within a certain range of this customer will be contacted (see Figure
20 8 @ 0 I 20 @ 8 o COD 09 COD @ King o Figure 2: Only vehicles lying within a square of side er centered at the customer are contacted (shown in green). To store locations for efficient search, we use a tree structure similar to a BST. In addition to data, cach node of this tree contains a location (u, v) and has up to four children (see Figure 3): • The nodes in the sub-tree rooted at Child 1 (shown in red in Figure 3) contain locations (x,y) satisfying: I <u and y su • The nodes in the sub-tree rooted at Child 2 (shown in green in Figure 3) contain locations (x,y) satisfying: *Su and y>u. • The nodes in the sub-tree rooted at Child 3 (shown in blue in Figure 3) contain locations (x,x) satisfying: > u and y2u. • The nodes in the sub-tree rooted at Child 4 (shown in yellow in Figure 3) contain locations (my) satisfying 2 u and y < 0.
U V V al c2 04 за уу. I Figure 3: Data structure used to store locations. Example 1. If we insert the following data at the specified locations in an empty tree: F- (4.7) V + (5,7) R (61) D (4.3) 0 (4,8) U + (8.4) V - (8.2) Y(29) S (6, 1) B (63) then, we obtain the free shown in Figure 4: T (47) 22 4.8) (5.7 (1) KS o PA D
+ 1. ID Page view A Read aloud | Add text V Draw S Highlight V (82) Y (29) S (6, 1) B (63) then, we obtain the tree shown in Figure 43 (4.7) V I (2, 2) 22 (4) 0 (5,7) V (6.1) K (43) D (4) U null SK (82) V mull (63) B null 0 1 2 Figure 4: Example tree.
0 (6,3) B null null null (82) V null Figure 4: Example tree. 3 Requirements The requirements for this assignment are incremental, that is, you will get partial points for implementing each class, Note however that • Your code must be compatible with Java 1.7. In Eclipse, go to: Project > Properties > Java Compiler, and set Compiler compliance level to 1.7. • If your code contains compilation errors, you will get O even if some classes are implemented correctly. Thus you should upload all classes even those you did not implement (classes that are not fully implemented should have default implementations of all methods specified in the interface). • If your code contains too many infinite loops and exceeds the time limit set for the tests, it will be interrupted by the system and assigned the grade 0. The code for this assignments consists of the following classes (details are included below): . Two basic class Location and Pair used to represent locations and pairs of elements respectively: The class VehicleliringManager, which stores the locations of vehicles and allows to add, remove and move vehicles to a new position. Vehicles are identified by a key of type String. An important functionality of this class is finding all vehicles within a square centered at the customer's location • The class linkedlist used to store data when needed. • The class as used to map vehicle IDs to their locations, The class Trelocator, which is used to store the vehicles available at every location using the method explained in Section 2 . The class Treet.ocatorMap which is used to store the locations of vehicles by combining rst and Treatocator to guarantee that vehicle IDs are unique (unlike the class Trelocater, which only guarantees the uniqueness of the locations but not the data). 3.1 Class Location (Given) 20 location
10s are unique (unlike the class Treelocator, which only locations but not the data). 3.1 Class Location (Given) 11 Represents a 20 location public class Location public int x; public int y public Location (int n, int y){ I this.x - X this.y - y } @Override public String toString() { return (+*+.+ y + ": 3.2 Class Pair (Given) / Stores a pair of elements public class Paircu. V> { public u first: public V second; public Pair (u first. V second) { this.first - first; this.second - second; } @Override publie String toString() { return" (" + first + ". > + second + ");
3.3 Class Linkedlist (3pt) Implement the class Linkedlist that has a no-argument constructor and implements the following interface: public interface List <T> ( public boolean empty(); public boolean full(); public void findFirst(); public void findNext(); public boolean last): public Tretrieve(): public void update (T): public void insert (T ): I public void remove(): > 3.4 Class ast (5pt) Implement the class set that has a no-argument constructor and implements the following interface: puble Interface Map< extends Comparable<K», T>( Return to the treenpty. Must be 001) boolean empty(): // Return true the trutul. Must be 0(1) boolean full(); W Return the key and date of the current lesent T retrieve() 11 update the data of current element. void update (Te): Wakes the element with key the current lost 11 t exist and it was 1/ not it. the current 1 unchanged the first close to the returned pair 11 indicates whether ist, od the second the number of comparison made Pair<Boolean, Integer > find (K key);
1/ Inserts no element if it does not exist and makes it the current element. WIf the already exists, the current does not change. The first lesent of V the returned pair indicates whether as inserted, and the second to the W number of key comparisons made Pair<Boolean, Integer > insert (K key. T data); 17 Remove the element with key kif it exists. The position of current is un pecified after calling this method. The first element of the returned pair 1 indicates whether kwas removed, and the second is the number ot key W comparisons made Pair<Boolean, Integer > remove(key): 1/ Returns all keys of the map as a list sorted in increasing order. List<> getall); > 3.5 Class Treelocator (Tpt) Implement the class Treelocator that has a no-argument constructor and implements the following interface using the storage scheme explained in Section 2: public interface Locator <T> Wissertat location to and returns the number of comparinade when 1 senrching for loc int add (T., Location loc): W The first chonest of the returned pairit contain 11 lenents w located at loc. It loe does not exist or has no closest the returned list yapty. The second lesent of the pain the suber of comparisosade 1/ when warching for loc Pair<List<T>. Integer > get (Location loc): 1 ve 11 OCT sent from location to the first en Wetteratursed pair troved and tailoc does sotetut 17 do not exist in to the second last of the pair the but 17 compare and when searching for 10 Pair<Boolean, Integer> remove(T.. Location loc); Retensilete and the tesents they contain List<Pair location. List<T>>>getAll(); // The title of the red part of 11 and their at they lo within the rectan peribylower left with Crimeve the boundaries The second lanet of the 77 pair the hero compared Pair Pair tocation. List<T>>>. Integer) Intang (Location loverloft, location upper right) > Remark 1. The number of comparisons in the method toge must be minimal 9
3.6 Class Treelocator Map (5pt) Implement the class TreelocatorMap that has a no-argument constructor and implements the following interface by usin the two classes RST and Trelocator! public interface LocatorMap<K extends Comparable<K>> // Returns map with the location of every key Map<, Location > getMap(): // Returns locator that contains all keyn. Locator <K>getLocator(): 1/ Insert the key at location loc if it does not exist. The first element of 11 the returned pair indicates whether varierted, and the second in the 17 number of key comparisons made Pair<Boolean, Integer > add( k, Location loc); 17 Moves the key to location locit k exists. The first element of W the returned pair indicates whether exits, and the second is the 17 number of key comparisons made Pair<Boolean. Integer > move (X k. Location loc): I W The first wesent of the returned pair contain the location of my 17 at all other the necond set in the number of key comparison y required to find Pair Location. Integer > getLoc CX ) 1 RAROV the element with kay if It is The first element of the y returned pair Teates whether was renova and the second the ber 1 of key cosparsons required to find Pair<Boolean. Integer renove (X k) Return 11 key in the sported in increder List<) ct11(); The Twent of the returned pair of all toys located within 17 the totale specified by a lovet upper right corners (inclusiv The boundaries. The second of the partner of COMPATIOS unde Pairchit<>, Integer > InRange (Location loverteft, location upperlicht)
3.7 Class VehicleHiringManager (3pt) Implement the class VehicleHiringManager by using the class TreelocatorMap: public class VehicleHiring Manager { public VehicleHiringManager () { // Return the locator nap public Locator Map<String> get locator Map() { return null; } I 1 Sets the locator nap public void setLocator Map (Locator Map<String> locator Map) { > Insert the vehicle id at location loc if it does not exist and returns true // It id already exists. the method return false publie boolean addVehicle(String id. Location loc) { return false; > // Moves the vehicle id to location loc if id exists and return true. If id not 1/ exist, the method return false publie boolean move Vehicle (String id, location loc) { return false; > 1 Remove the vehicle id if it exists and return truet id does not exist. the method return false publie boolean renovaVehicle(String id) { return false: 3 1/ Returns the location of vehicle ditt existul otherwise publie Location set Vehicleloc (string 10) return null; > Returns all vehicle located within Ure of 127 contered at loc Vinclusive of the boundaries) publie 1.1nt<string> getVehicles in Range(location loc, int n) { return null; > Remark 2. In the implementation of the class VehiclellingManager, do not call the method getalt of the interface LocatorMap
public class BST<K extends Comparable<K>, T> implements Map<K, T> { @Override public boolean empty() { // TODO Auto-generated method stub return false; } @Override public boolean full() { // TODO Auto-generated method stub return false; } @Override public T retrieve() { // TODO Auto-generated method stub return null; } @Override public void update(Te) { // TODO Auto-generated method stub } @Override public Pair<Boolean, Integer> find(K key) { // TODO Auto-generated method stub return null; } @Override public PaircBoolean, Integer> insert(k key, T data) { // TODO Auto-generated method stub return null; 3 @Override public Pair<Boolean, Integer> remove(K key) { // TODO Auto-generated method stub return null; ) Override public List<K> getAll() { // TODO Auto-generated method stub
@Override public List<K> getAll() { // TODO Auto-generated method stub return null; }
public class LinkedList<T> implements List<T> { @Override public boolean empty() { // TODO Auto-generated method stub return false; } @Override public boolean full() { // TODO Auto-generated method stub return false; } @Override I public void findFirst() { // TODO Auto-generated method stub } @Override public void findNext() { // TODO Auto-generated method stub } @Override public boolean last() { // TODO Auto-generated method stub return false; }
@Override public boolean last() { // TODO Auto-generated method stub return false; } @Override public T retrieve() { // TODO Auto-generated method stub return null; } @Override public void update(t e) { // TODO Auto-generated method stub } @Override public void insert(Te) { // TODO Auto-generated method stub } @Override public void remove() { // TODO Auto-generated method stub } }
Size Password pr... List - Notepad File Edit Format View Help public interface List<T> { public boolean empty(); public boolean full(); public void findFirst(); public void findNext(); public boolean last(); public T retrieve(); public void update(Te); public void insert(Te); I public void remove(); }
Location - Notepad File Edit Format View Help 17 Represents a 2D location. public class Location { public int x; public int y; public Location(int x, int y) { this.x = x; this.y = y; y; I } @Override public String toString() { return "(" + x + } + y + ")"; }
File Edit Format View Help public interface Locator<T> { // Inserts e at location loc and returns the number of comparisons made when // searching for loc. int add(T e, Location loc); // The first element of the returned pair is a list containing all elements // located at loc. If loc does not exist or has no elements, the returned list // is empty. The second element of the pair is the number of comparisons made // when searching for loc. Pair<List<T>, Integer> get (Location loc); // Removes all occurrences of element e from location loc. The first element // of the returned pair is true if e is removed and false if loc does not exist // or e does not exist in loc. The second element of the pair is the number of // comparisons made when searching for loc. Pair<Boolean, Integer> remove(Te, Location loc); // Returns all locations and the elements they contain. List<Pair<Location, List<T>>> getA110); // The first element of the returned pair is a list of all locations and their // data if they are located within the rectangle specified by its lower left and /upper right corners (inclusive of the boundaries). The second element of the // pair is the number of comparisons made. Pair<List<Pair<Location, List<T>>>, Integer> inRange(Location lower left, Location upperRight);
Compressed size Password pe Sure Ratio Date modified Locator Map - Notepad File Edit Format View Help public interface LocatorMap<K extends comparable<K>> { // Returns a map with the location of every key. Map<K, Location> getMap(; // Returns a locator that contains all keys. Locator<K> getLocator(); // Inserts the key k at location loc if it does not exist. The first element of // the returned pair indicates whether k was inserted, and the second is the // number of key comparisons made. Pair<Boolean, Integer> add(K k, Location loc); // Moves the key k to location loc if k exists. The first element of // the returned pair indicates whether k exists, and the second is the Il number of key comparisons made. Pair<Boolean, Integer> move(K k, Location loc); // The first element of the returned pair contains the location of key k if it 1/ exists, null otherwise. The second element is the number of key comparisons // required to find k. Pair<Location, Integer> getLoc(kk); // Removes the element with key k if it exists. The first element of the 1/ returned pair indicates whether k was removed, and the second is the number // of key comparisons required to find k. Pair<Boolean, Integer> remove(K K);
// Moves the key k to location loc if k exists. The first element of // the returned pair indicates whether k exists, and the second is the // number of key comparisons made. Pair<Boolean, Integer> move(K k, Location loc); // The first element of the returned pair contains the location of key k if it // exists, null otherwise. The second element is the number of key comparisons // required to find k. Pair Location, Integer> getLoc(KK); // Removes the element with key k if it exists. The first element of the 1/ returned pair indicates whether K was removed, and the second is the number // of key comparisons required to find k. Pair<Boolean, Integer> remove(K k); // Returns all keys in the map sorted in increasing order. List<K> getAll(); // The first element of the returned pair is a list of all keys located within // the rectangle specified by its lower left and upper right corners (inclusive // of the boundaries). The second element of the pair is the number of // comparisons made. Pair<List<K>, Integer> get InRange(Location lowerLeft, Location upperRight);
туре Date modified **"); Compressed size Password pr. Size Ratio Main - Notepad File Edit Format View Help public class Main { public static void main(String[] args) { testVM(); System.out.println("** testlocator(); } private static void testVM() { VehicleHiringManager vhm = new VehicleHiringManager(); vhm. addVehicle("F", new location (4, 7)); vhm.addVehicle"V", new Location(5, 7)); vhm.addVehicle("K", new Location(6, 1)); vhm.addVehicle("D", new Location (4, 3)); vhm.addVehicle("0", new Location (4, 8)); vhm.addVehicle("U", new Location(8, 4)); vhm. addVehicle("V", new Location(8, 2)); vhm.addVehicle("Y", new Location(2, 2)); vhm.addVehicle("S", new Location(6, 1)); vhm.addVehicle("B", new Location(6, 3)); System.out.println(".. -"); System.out.println(vhm.getVehicleloc("E")); System.out.println(vhm.getVehicleLoc("S")); System.out.println(vhm.getVehicleLoc("F")); System.out.println("---- --"); print(vhm.getVehiclesInRange(new Location(5, 5), 2)); print(vhm.getVehiclesInRange(new Location(3, 3), 1)); print(vhm.getVehiclesInRange(new Location(e, e), 10)); System.out.println("--- ----"); Map<String, Location> map = vhm.getLocatorMap().getMap();
System.out.println("-- "); Map<String, Location map = vhm.getLocatorMap().getMap(); System.out.println(map.find("U")); System.out.println(map.find("K")); System.out.println(map.find("X")); System.out.println("-- --------"); Locator<String> locator = vhm.getLocatorMap().getLocator(); System.out.println(locator.get(new Location(3, 5)). second); System.out.println(locator.get(new Location (2, 6)). second); System.out.priſtin(locator.get(new Location (8, 3)). second); System.out.println(locator.get(new Location(5, 1)).second); System.out.println(locator.get(new Location (4, 2)).second), System.out.println(locator.get(new Location(e, e)). second); System.out.println(locator.inRange(new Location (2, 2), new Location(8, 8)). Second); System.out.println(locator.inRange(new Location (4, 4), new Location (6, 6)). second); System.out.println(locator.inRange(new Location(e, e), new Location (2, 3)). second); } private static void testLocator() { Treelocator<String> locator = new TreeLocator<String>(); locator.add("F", new Location (4, 7)); locator.add("V", new Location(5, 7)); locator.add("K", new Location(6, 1)); locator.add("D", new Location (4, 3)); locator.add("0", new Location (4, 8)); locator.add("U", new Location(8, 4)); locator.add("V", new Location(8, 2)); locator.add("Y", new Location (2, 2)); locator.add("S", new Location(6, 1)); locator.add("B", new Location(6, 3));
edste Password Sure Ratio Date modified Main - Notepad File Edit Format View Help locator.add("S", new Location(6, 1)); locator.add("B", new location(6, 3)); System.out.println(locator.get(new Location(3, 5)). second); System.out.println(locator.get(new Location (2, 6)). second); System.out.println(locator.get(new Location (8, 3)). second); System.out.println(locator.get(new Location (5, 1)). second); System.out.println(locator.get(new Location(4, 2)).second); System.out.println(locator.get(new Location(e, e)).second); System.out.println(locator.inRange(new Location(2, 2), new Location(8, 8)).second); System.out.println(locator.inRange(new Location(4, 4), new Location (6, 6)). second); System.out.priiſtin(locator.inRange(new location(e, e), new Location (2, 3)). second); } private static <T> void print(List<T> 1) { if (1 == null) { System.out.println("[null]"); return; if (1.empty() { System.out.println("(emptyl"); return; } 1. findFirst(); while (11.last() { System.out.print(1.retrieve() + ", "); 1.findNext(); System.out.println(1.retrieve()); }
Main-Output - Notepad File Edit Format View Help null (6,1) (4,7) F, V, D, B [Y, F, Y, O, V, K, S, D, B, U troVKSBE (true, 5) (true, 3) (false, 3) 2 3 2 3 8 4 2 NNMNM N 00N NNNNN 2 2 4 2 3 2 9 4 2
Map - Notepad File Edit Format View Help public interface Map<K extends Comparable<K>, T> { // Returns true if the tree is empty. Must be 0(1). boolean empty(); // Returns true if the tree is full. Must be 0(1). boolean full(); // Returns the key and data of the current element T retrieve(); // Updates the data of current element. void update(t e); // Makes the element with key k the current element if it exists, and if k does 1/ not exist, the current is unchanged. The first element of the returned pair // indicates whether k exists, and the second is the number of key comparisons // made. Pair<Boolean, Integer> find(K key); // Inserts a new element if it does not exist and makes it the current element. // If the k already exists, the current does not change. The first element of // the returned pair indicates whether k was inserted, and the second is the // number of key comparisons made. Pair<Boolean, Integer> insert(k key, T data); // Removes the element with key k if it exists. The position of current is // unspecified after calling this method. The first element of the returned pair // indicates whether k was removed, and the second is the number of key // comparisons made. Pair<Boolean, Integer> remove(K key); // Returns all keys of the map as a list sorted in increasing order. List<K> getA110);
Pair - Notepad File Edit Format View Help V/ Stores a pair of elements. I public class Pair<U, V> { public U first; public V second; public Pair(U first, V second) { this.first = first; this.second = second; } @Override public String toString() { return "(" + first + ", } + second + ")"; }
Treelocator Notepad File Edit Format View Help public class Treelocator<T> implements Locator<T> { moverride public int add(Te, Location loc) { // TODO Auto-generated method stub return; > @Override public Pair<List<T>, Integer> get(Location loc) // TODO Auto-generated method stub return null; 1 @Override public Pair<Boolean, Integer> remove(t e, Location loc) // TODO Auto-generated method stub return null; } @Override public List<Pair<Location, List<T>>>getAllo { // TODO Auto-generated method stub return null; } @Override public Pair<List<Pair Location, List<T>>>, Integer> inRange(Location lowerLeft, Location upperRight) { // TODO Auto-generated method stub return null; } I
hle Edit Format View Help public class TreeLocatorMapck extends Comparable<K>> implements LocatorMap<K> { @Override public Map<K, Location> getMap() { // TODO Auto-generated method stub return null; ) @Override public Locator<K> getLocator() { // TODO Auto-generated method stub return null; } @Override public Pair<Boolean, Integer> add(K k, Location loc) { // TODO Auto-generated method stub return null; ) @Override public Pair<Boolean, Integer> move(K k, Location loc) { // TODO Auto-generated method stub I return null; } @Override public Pair<Location, Integer> getLoc(kk) { // TODO Auto-generated method stub return null; } @Override public Pair<Boolean, Integer> remove(K ) { // TODO Auto-generated method stub return null:
@Override public Pair<Location, Integer> getLoc(KK) { I // TODO Auto-generated method stub return null; } @Override public Pair<Boolean, Integer> remove(KK) { // TODO Auto-generated method stub return null; } @Override public List<K> getAll() { // TODO Auto-generated method stub return null; @Override public Pair<List<K>, Integer> get InRange(Location lowerLeft, Location upperRight) { // TODO Auto-generated method stub return null; } }
Vehicle Hiring Manager - Notepad File Edit Format View Help public class VehicleHiringManager { public VehicleHiringManager() { } // Returns the locator map. public LocatorMap<String> getLocatorMap() { return null; } // Sets the locator map. public void setLocatorMap (LocatorMap<String> locatorMap) { } 1/ Inserts the vehicle id at location loc if it does not exist and returns true. // If id already exists, the method returns false. public boolean addvehicle(String id, Location loc) { return false; } // Moves the vehicle id to location loc if id exists and returns true. If id not // exist, the method returns false. public boolean moveVehicle(String id, location loc) { return false; } // Removes the vehicle id if it exists and returns true. If id does not exist, // the method returns false. public boolean removeVehicle(String id) { return false; } I // Returns the location of vehicle id if it exists, null otherwise. public Location getVehicleLoc(String id) { return null; } // Returns all vehicles located within a square of side 2*r centered at loc // (inclusive of the boundaries). public List<String> getVehicles InRange(Location loc, int r) { return null; }