Coursework 2000

Unit Organiser :  P.S.Williams

Below are the positions of various cities  on the surface of the earth.  These positions are given as latitude and longitude, expressed in degrees. 

 Place             Latitude Longitude (Don't type these headings in!)

London                        51.50                -0.08

Bombay                   18.92               72.83

Singapore          1.17    103.67

Sydney                  -33.88   151.17

Auckland               -36.86   174.77

Vancouver        49.33  -123.17

NewYork         40.75  -74.00

Kingston           18.00  -76.83

Brasilia                -15.92    -47.67

NorthPole         90.00                  0.00

SouthPole              -90.00       0.00

Berlin               52.53                13.40

Moscow           55.75                37.58

Athens              37.97                23.77

Rome                41.90                12.50

Tokyo               35.75                39.45

Nairobi             -1.33      36.83

Capetown                -33.92     18.37

Perth                   -31.95               115.87

Winnipeg          59.83               -97.35

You are required to do the following :

(a)       Enter the name and position data into a ASCII text file using a suitable text editor. The format must be as shown. Give the file a suitable name.

(b)       We will wish to read each line as a string then break up the string into a string variable for the name of the place, a double variable for the latitude and a double variable for the longitude. In order to split the input string into its constituent parts, you are recommended to use a Tokenizer - see the section on Tokenizing strings with a StringTokenizer object in  the chapter on Strings and Characters in Deitel's book. (Alternatively you may be able to use substring methods - also in the same chapter).

 (c)        Using the ASCII file for the place names and their latitudes and longitudes write a Java program to

            (i) Read the entries as before (splitting them up into three components) into  a binary search tree (BST). You will have to modify the definition of the node's data field to now hold three data items. The name field should be the key - i.e the choice of where you insert the data will be the result of an  alphabetical comparison. (Note : you must not use arrays)

            (ii) Using the BST output the list of entries in alphabetical order using the name field as key.

            (iii) For a given input name place (either from the keyboard or within the main part of the program), your program must output the distance in miles between the place chosen and London. (You will have to write a search method - the city name is either in the root node or in the left or right subtree or not there at all. Which subtree to look in can be done on the basis of comparing the given name with the name in the current root node).

            How far from London is Singapore ?  How far is Llanfairpwllgwyngyll ?

import java.io.*;
import java.util.*;
import java.text.*;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import java.net.*;

public class CityDistance extends JApplet implements ActionListener
{
private String city,filename="WorldData.txt";
private cityTree tree;
private JTextField cityTextField,answertextfield;
private JTextArea textarea;
private DecimalFormat precisionTwo = new DecimalFormat("0.00");

public void init()
{
textarea=new JTextArea(17,20);
city="";
tree=new cityTree();
JLabel question=new JLabel("For which of these cities do you want to know the distance from London?");
JLabel answer=new JLabel("The distance in miles is:");
cityTextField=new JTextField("");
answertextfield=new JTextField("");
cityTextField.addActionListener(this);
answertextfield.setEditable(false);
Container contentPane=getContentPane();
this.setSize(700,400);
GridBagLayout gridbag = new GridBagLayout();
GridBagConstraints c=new GridBagConstraints();
c.fill = GridBagConstraints.BOTH;
c.weightx=0.1;
contentPane.setLayout(gridbag);
gridbag.setConstraints(question,c);
contentPane.add(question);
c.gridwidth=GridBagConstraints.REMAINDER; 
c.weightx=1.0;
contentPane.add(cityTextField,c);
c.weightx=0.1;
c.gridwidth = GridBagConstraints.RELATIVE; 
gridbag.setConstraints(answer, c);
contentPane.add(answer);
c.gridwidth = GridBagConstraints.REMAINDER;
c.weightx=1.0;
gridbag.setConstraints(answertextfield, c);
contentPane.add(answertextfield);
JScrollPane scroller=new JScrollPane(textarea,JScrollPane.VERTICAL_SCROLLBAR_AS_NEEDED,JScrollPane.HORIZONTAL_SCROLLBAR_AS_NEEDED);
c.weighty = 1.0;
gridbag.setConstraints(scroller, c);
contentPane.add(scroller);
}

public void start()
{
String latit,longit,place,inorder;
Double lat, lon;
double lati, longi;
String text;
StringTokenizer allinorder; 

try
{
URL u=new URL(getDocumentBase(),filename);
text=readFile(u);
StringTokenizer allcities=new StringTokenizer(text);
int noCities=allcities.countTokens()/3;
for(int i=0;i<noCities;i++)
{
place=allcities.nextToken();
latit=allcities.nextToken();
longit=allcities.nextToken();
lat= new Double(latit); 
lon= new Double(longit);
lati=lat.doubleValue(); 
longi=lon.doubleValue(); 
tree.insert(place, lati, longi);
}
inorder=tree.toInOrderString();
textarea.append("The cities (in the file of data) in alphabetical order are:\n");
if(inorder=="") textarea.append("The file of cities is empty\n");
else
{
allinorder=new StringTokenizer(inorder);
for(int j=0;j<tree.getNumberOfCities();j++)
{
textarea.append("CITY:\t"+allinorder.nextToken()+"\tLATITUDE:\t"+allinorder.nextToken()+"\tLONGITUDE:\t"+allinorder.nextToken()+"\n");
}
}
}
catch(Exception e)
{
JOptionPane.showMessageDialog(null,e.toString());
}
}

public void actionPerformed(ActionEvent e)
{
city=cityTextField.getText();
if(tree.isMember(city))answertextfield.setText(""+precisionTwo.format(tree.Distance(tree.getLatitude(city),tree.getLongitude(city),tree.getLatitude("London"),tree.getLongitude("London"))));
else 
{
cityTextField.setText("");
answertextfield.setText(city+" is not in the list");
}
} 

public String readFile(URL url)
{
BufferedReader bReader;
String data="";
try
{
URLConnection uc=url.openConnection();
uc.setUseCaches(false); // set caches false for Netscape browsers
uc.setDoInput(true); // we are going to read from this url
uc.setDoOutput(false); // we do not want to transmit data through this url
uc.setAllowUserInteraction(false);// make the connection if not made already
uc.connect();// get the InputStream
InputStream in=uc.getInputStream();
InputStreamReader inReader=new InputStreamReader(in); // with default encoding scheme
bReader=new BufferedReader(inReader);
// get the data
String read=null;
do
{
read=bReader.readLine();
if (read!=null) data=data+read+"\n";
} while (read!=null);
if (bReader!=null) bReader.close();
} 
catch (Exception e)
{
JOptionPane.showMessageDialog(null,"An IO error occurred: "+e.toString());
data=null;
}
return data;
}

}

//********************************************************************************************
class city
{
private String Place;
private double Latitude, Longitude;

public city(String p, double lat, double longit)
{
Place=p;
Latitude=lat;
Longitude=longit;
}

public String getPlace()
{
return Place;
}

public double getLatitude()
{
return Latitude;
}

public double getLongitude()
{
return Longitude;
}

}

//********************************************************************************************
class cityTreeNode 
{
cityTreeNode left; 
city data;
cityTreeNode right;

cityTreeNode(String place, double latitude, double longitude)
{
data=new city(place, latitude, longitude); 
left=right=null;
}

public String getPlace()
{
return data.getPlace();
}

public double getLatitude()
{
return data.getLatitude();
}

public double getLongitude()
{
return data.getLongitude();
}
} 

//********************************************************************************************
class cityTree 
{
private cityTreeNode root;
private boolean ismember;
private double latitude, longitude;
private String inorder, preorder, postorder;
private int numberOfCities;

cityTree()
{
root=null;
ismember=false;
inorder="";
preorder="";
postorder="";
numberOfCities=0;
}

private static boolean issmaller(String s1, String s2)
// returns true if s1<s2, i.e. s1 before s2 alphabetically
{
int s1length=s1.length(), s2length=s2.length(), shortestlength;
int i=0;
boolean isbefore=false;
if(s1length<s2length)shortestlength=s1length;
else shortestlength=s2length;
while(s1.charAt(i)==s2.charAt(i)&&(i<shortestlength))
{
i++;
}
if(s1.charAt(i)<s2.charAt(i)) isbefore=true;
return isbefore;
}

private static boolean isequal(String s1, String s2)
// returns true if s1=s2, i.e. s1 the same word as s2 n.b. case sensitive
{
return (s1.equals(s2));
}

public String toInOrderString()
{
inorder=""; 
inorderTraversal();
return inorder;
}

public String toPreOrderString()
{
preorder=""; 
preorderTraversal();
return preorder;
}

public String toPostOrderString()
{
postorder="";
postorderTraversal();
return postorder;
}

public int getNumberOfCities()
{
return numberOfCities;
}

private cityTreeNode insert(cityTreeNode city, String place, double latitude, double longitude)
{
if(city==null) return new cityTreeNode(place, latitude, longitude);
else if(issmaller(place,city.getPlace())) city.left=insert(city.left, place, latitude, longitude);
else city.right=insert(city.right, place, latitude, longitude);
return city;
}

public void insert(String place, double latitude, double longitude)
{
numberOfCities++;
root=insert(root, place, latitude, longitude);
}

public void preorderTraversal() 
{ 
preorderHelper(root);
}

private void preorderHelper(cityTreeNode node)
{
if(node==null) return;
preorder+=(node.data.getPlace()+" "+node.data.getLatitude()+" "+node.data.getLongitude()+" ");
preorderHelper(node.left); 
preorderHelper(node.right);
}

public void inorderTraversal() 
{
inorderHelper(root);
}

private void inorderHelper(cityTreeNode node)
{
if(node==null) return;
inorderHelper(node.left); 
inorder+=(node.getPlace()+" "+node.getLatitude()+" "+node.getLongitude()+" ");
inorderHelper(node.right);
}

public void postorderTraversal() 
{ 
postorderHelper(root); 
}

private void postorderHelper(cityTreeNode node)
{
if(node==null) return;
postorderHelper(node.left); 
postorderHelper(node.right); 
postorder+=(node.getPlace()+" "+node.getLatitude()+" "+node.getLongitude()+" ");
} 

public boolean isMember(String s)
{
ismember=false;
memberHelper(s,root);
if(ismember) return true;
else return false;
}

private void memberHelper(String s,cityTreeNode node)
{
if (node==null) ismember=false;
else if(isequal(s,node.getPlace())) ismember=true;
else if(issmaller(s,node.getPlace())) memberHelper(s,node.left);
else memberHelper(s,node.right);
}

public double getLatitude(String s) throws IsntaMemberException
{
if(!(isMember(s))) throw new IsntaMemberException();
else
{
getLatitudeHelper(s,root);
return latitude;
}
}

private void getLatitudeHelper(String s,cityTreeNode node)
{
if (node==null) ;
else if(isequal(s,node.getPlace())) latitude=node.getLatitude();
else if(issmaller(s,node.getPlace())) getLatitudeHelper(s,node.left);
else getLatitudeHelper(s,node.right);
}

public double getLongitude(String s) throws IsntaMemberException
{
if(!(isMember(s))) throw new IsntaMemberException();
else
{
getLongitudeHelper(s,root);
return longitude;
}
}

private void getLongitudeHelper(String s,cityTreeNode node)
{
if (node==null) ;
else if(isequal(s,node.getPlace())) longitude=node.getLongitude();
else if(issmaller(s,node.getPlace())) getLongitudeHelper(s,node.left);
else getLongitudeHelper(s,node.right);
}

public double Distance(double Lat1, double Long1, double Lat2, double Long2)
// calculates the distance in miles between two points of given 
// latitude and longitude in degrees. The first point has position
// (Lat1,Long1) while the second has position (Lat2,Long2)} 
{
final double PI = 3.14149265;
final double R = 3961.0; // radius of the earth in miles
double L1,L2,M1,M2,N1,N2,C,S,T,Angle;

Lat1 = Lat1*PI/180.0; Long1 = Long1*PI/180.0;
Lat2 = Lat2*PI/180.0; Long2 = Long2*PI/180.0; 
L1 = Math.cos(Lat1)*Math.cos(Long1); L2 = Math.cos(Lat2)*Math.cos(Long2);
M1 = Math.cos(Lat1)*Math.sin(Long1); M2 = Math.cos(Lat2)*Math.sin(Long2); 
N1 = Math.sin(Lat1); N2 = Math.sin(Lat2);
C = L1*L2 + M1*M2 + N1*N2; S = Math.sqrt(Math.abs(1.0 - C*C));
if(Math.abs(C) < 1.0E-6) Angle = PI/2.0;
else
{ 
T = Math.abs(S/C);
if(C > 0) Angle = Math.atan(T); else Angle = PI - Math.atan(T);
} 
return R*Angle;
}

}

//********************************************************************************************
class IsntaMemberException extends ArithmeticException
{
public IsntaMemberException()
{ 
super("This city isn't on the list.");
}
}
//********************************************************************************************