especially advantageous by ingly digital. Digital cartography is letting users s

Question

especially advantageous by ingly digital. Digital cartography is letting users select the size and color of "event radii" les showing the area effected by some This ability, in turn, i enabled by data enable efficient searching-binary search structures which not only order data, but can trees. Onthis question, you will answering questions about using binary search trees to MapLoc instances, where MapLoc is a class used to represent a single location on a map. is: public class MapLoc private double K: Location on the map's horizontal axis Private doubly y: Location on the map's vertical axis Public Mal (double nx, double nr) x nx i y nY: Public double diatance (MapLoc aourc.) source. 2)) return Math.sqrt CMath -pov Cx source 2) Math. Pov cy .y. A) 10 pointsl Because MapLoc instances are NOT comparable, our binary search tree will need to use a Compar ator Diatcomp compare two Map using their distance from origin (the location where an event occurred Complete the Dietcomp class so that it performs this comparison. public class Dist comp implements comparator private MapLoc origin eli public Dist conp (Maploe el) origin t a rare da ble "if m is deser to orkeim return return turn 0.

Explanation / Answer

MapLoc.java:


public class MapLoc {
   private double x;
   private double y;
   public MapLoc(double x, double y) {
       this.x = x;
       this.y = y;
   }
  
   public double distance(MapLoc source) {
       return Math.sqrt(Math.pow(source.x - x, 2) + Math.pow(source.y - y, 2));
   }
}

DistComp.java:

import java.util.Comparator;

public class DistComp implements Comparator<MapLoc> {

   @Override
   public int compare(MapLoc m1, MapLoc m2) {
       MapLoc origin = new MapLoc(0, 0);
       return m1.distance(origin) > m2.distance(origin) ? 1 : (m1
               .distance(origin) == m2.distance(origin)) ? 0 : -1;
   }
}

BST.java:

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

public class BST {
   private BTNode root;
   private Comparator<MapLoc> comp;
   private MapLoc origin;
  
  
   public BST(Comparator<MapLoc> comp) {
       this.root = null;
       this.comp = comp;
       this.origin = new MapLoc(0, 0);;
   }

   private class BTNode {
       protected MapLoc element;
       protected BTNode parent, left, right;
      
       public boolean inRad(double dist) {
           double d = element.distance(origin);
           if(d < dist)
               return true;
           else
               return false;
       }
   }
  
   public MapLoc closest() {
       // if tree is empty
       if(root == null){
           return null;
       }
      
       BTNode closest = root;
       double minDistFormOrigin = root.element.distance(origin);
      
       // doing a breadth first search on the whole tree
       Queue<BTNode> queue = new LinkedList<BTNode>();
      
       // initialize queue with root element
       queue.add(root);
      
       while(!queue.isEmpty()) {
           // get the node from front of queue
           BTNode node = queue.poll();
          
           // if this node has got minimum distance.. update
           if(node.element.distance(origin) < minDistFormOrigin) {
               closest = node;
               minDistFormOrigin = node.element.distance(origin);
           }
          
           // insert this node's child to queue
           if(node.left != null)
               queue.add(node.left);
           if(node.right != null)
               queue.add(node.right);
          
       }
      
       return closest.element;
   }
  
  
   public int numInRadius(double maxDist) {
       return numInRadius(root, maxDist);
   }
  
   private int numInRadius(BTNode node, double maxDist) {
       if(node==null)
           return 0;
       int count = 0;
       if(node.inRad(maxDist)) {
           count++;
       }
       count += numInRadius(node.left, maxDist);
       count += numInRadius(node.right, maxDist);
       return count;
   }
}

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.