/*
    Course: Programming Fundamentals COIT11222 2014 Term2
    Purpose: Assignment two -- Motorcity Car Insurance GUI application
    Programmer: Bernard Li
    File: CarInsuranceGUI.java
    Date: 14 August 2014
*/

/*
    Enter your header comment here
*/
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JTextField;
import javax.swing.JButton;
import javax.swing.JTextArea;
import javax.swing.JScrollPane;
import javax.swing.JComboBox;
import javax.swing.JCheckBox;
import javax.swing.JOptionPane;
import java.awt.FlowLayout;
import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;
import java.awt.Font;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.util.ArrayList;

public class CarInsuranceGUI extends JFrame
{
    ///////////////////////////////////////////////////////////
    // declare your data structures and class variables here //
    ///////////////////////////////////////////////////////////
    // information of car registrations (four parallel lists)
    private ArrayList<String>  regNumbers;
    private ArrayList<Integer> ages;
    private ArrayList<Boolean> hasAccidents;
    private ArrayList<Double>  fees;

    // total number of cars limitation
    private static final int LIMIT = 10;
    // constant in calculation of fee
    private static final int AGE_THRESHOLD = 5;
    private static final int FEE1 = 200;
    private static final int FEE2 = 350;
    private static final double DISCOUNT = 0.25;

    // GUI components
    JLabel registrationLabel;       // label for registration field
    JTextField registrationField;   // field to enter the cars's registration
    JLabel ageLabel;                // label for selecting the car's age from drop-down combo box
    JComboBox<String> ageCombo;     // drop-down combo box for selecting the car's age
    JCheckBox accidentCheckBox;     // check box for selecting if car has been in an accident or not
    JButton enterButton;            // button for entering car's detail
    JButton displayAllButton;       // button to display all cars entered so far
    JButton sortButton;             // button to sort the car records by name
    JButton searchButton;           // button to search for a car using it's registration
    JButton exitButton;             // button to exit the program
    JTextArea textArea;             // text area for displaying the data
    JScrollPane scrollPane;         // scoll pane for text area scrolling

    // Constructor
    public CarInsuranceGUI()
    {
        super("Motorcity Car Insurance");               // invoke JFrame constructor
        setLayout(new FlowLayout());                    // set the layout to flow layout

        registrationLabel = new JLabel("Registration"); // create registration label
        add(registrationLabel);                         // add the label to the JFrame
        registrationField = new JTextField(15);         // create registration field
        add(registrationField);                         // add the registration field to the JFrame

        ageLabel = new JLabel("Age");                   // create age label
        add(ageLabel);                                  // add the name label
        ageCombo = new JComboBox<String>();             // create the age combo box
        for (int i = 0; i <= 30; i++)                   // populate the age combo box with numbers 0-30
        {
            ageCombo.addItem(i + "");                   // add number as a string
        }
        add(ageCombo);                                  // add the age combo

        accidentCheckBox = new JCheckBox("Accident?");  // create accident checkbox
        add(accidentCheckBox);                          // add accident checkbox

        enterButton = new JButton("Enter");             // create enter button
        add(enterButton);                               // add enter button

        displayAllButton = new JButton("Display All");  // create display all button
        add(displayAllButton);                          // add display all button

        sortButton = new JButton("Sort");               // create sort button
        add(sortButton);                                // add sort button

        searchButton = new JButton("Search");           // create search button
        add(searchButton);                              // add search button

        exitButton = new JButton("Exit");               // create exit button
        add(exitButton);                                // add exit button

        textArea = new JTextArea(16, 52);               // create text area
        // set text area to a monospaced font so the columns can be aligned using a format string
        textArea.setFont(new Font("Monospaced", Font.PLAIN, 12));
        textArea.setEditable(false);                    // set the text area to be read only
        scrollPane = new JScrollPane(textArea);         // put the text area into the scroll pane
        add(scrollPane);                                // add the scroll pane

        // add the ActionListener objects to all of the buttons and the name field
        ButtonHandler buttonEvent = new ButtonHandler();    // create event handler object

        enterButton.addActionListener(buttonEvent);
        registrationField.addActionListener(buttonEvent);
        displayAllButton.addActionListener(buttonEvent);
        sortButton.addActionListener(buttonEvent);
        searchButton.addActionListener(buttonEvent);
        exitButton.addActionListener(buttonEvent);

        // when the user pushes the system close (X top right corner)
        addWindowListener( // override window closing method
            new WindowAdapter()
            {
                public void windowClosing(WindowEvent e)
                {
                    exit(); // Attempt to exit application
                }
            }
        );

        ////////////////////////////////////////////////////////////////////////
        // contruct your data structures and set up your class variables here //
        ////////////////////////////////////////////////////////////////////////
        regNumbers = new ArrayList<String>();
        ages = new ArrayList<Integer>();
        hasAccidents = new ArrayList<Boolean>();
        fees = new ArrayList<Double>();
    } // end constructor

    // method used to enter that data for a car
    private void enterData()
    {
        // make sure the registration number is not empty
        String regNumber = this.registrationField.getText().trim();

        if ("".equals(regNumber)) {
            JOptionPane.showMessageDialog(this, 
                "Please enter a car's registration",
                "Error", JOptionPane.ERROR_MESSAGE);
            return;
        }
        // make sure have not reached the limit of cars
        if (this.regNumbers.size() >= LIMIT) {
            JOptionPane.showMessageDialog(this, 
                "You have reached the limit of cars to enter", 
                "Error", JOptionPane.ERROR_MESSAGE);
            return;
        }

        // add the current registration to the parallel arrays
        int age = Integer.parseInt((String)ageCombo.getSelectedItem());
        boolean hasAccident = accidentCheckBox.isSelected();
        // calculate the fee
        double fee = (age <= AGE_THRESHOLD ? FEE1 : FEE2);
        if (!hasAccident) {
            fee -= fee * DISCOUNT;
        }
        this.regNumbers.add(regNumber);
        this.ages.add(age);
        this.hasAccidents.add(hasAccident);
        this.fees.add(fee);

        // clear fields
        this.registrationField.setText("");
        this.ageCombo.setSelectedItem("0");
        this.accidentCheckBox.setSelected(false);

        // display the current car
        ArrayList<Integer> indices = new ArrayList<Integer>();
        indices.add(this.regNumbers.size() - 1);
        this.displayCars(indices);

        registrationField.requestFocus();
    }// enterData

    // display car information at the given indices
    private void displayCars(ArrayList<Integer> indices)
    {
        textArea.setText("");

        // display the table header
        String header = String.format("%-20s %-10s %-8s %11s\n", 
            "Registration", "Age", "Accident", "Fee");
        textArea.append(header);
        textArea.append("----------------------------------------------------\n");

        for (Integer i : indices) {
            String fee = String.format("$%.2f", this.fees.get(i));
            String line = String.format("%-20s %-10d %-8s %11s\n",
                this.regNumbers.get(i), 
                this.ages.get(i),
                this.hasAccidents.get(i) ? "Yes" : "No",
                fee);
            textArea.append(line);
        }
    }

    // method used to display the cars entered into the program
    private void displayAll()
    {
        // display cars
        ArrayList<Integer> indices = new ArrayList<Integer>();
        for (int i = 0; i < this.regNumbers.size(); i++) {
            indices.add(i);
        }
        this.displayCars(indices);

        textArea.append("----------------------------------------------------\n");

        // calculate total
        double total = 0;
        for (double fee : fees) {
            total += fee;
        }
        // display total fee
        String totalLine = String.format("Total fees: $%.2f", total);
        totalLine = String.format("%52s", totalLine);
        textArea.append(totalLine);

    }// displayAll

    // method used to sort the car arrays based on registration
    private void sort()
    {
        // insertion sort
        for (int i = 1; i < this.regNumbers.size(); i++) {
            String regNumber = this.regNumbers.get(i);
            Integer age = this.ages.get(i);
            Boolean hasAccident = this.hasAccidents.get(i);
            Double fee = this.fees.get(i);

            // find a proper position in [0, i) to insert
            int j = i - 1;
            while (j >= 0 && this.regNumbers.get(j).compareTo(regNumber) > 0) {
                // shift this one right
                this.regNumbers.set(j + 1, regNumbers.get(j));
                this.ages.set(j + 1, ages.get(j));
                this.hasAccidents.set(j + 1, hasAccidents.get(j));
                this.fees.set(j + 1, fees.get(j));
                j --;
            }
            // insert
            this.regNumbers.set(j + 1, regNumber);
            this.ages.set(j + 1, age);
            this.hasAccidents.set(j + 1, hasAccident);
            this.fees.set(j + 1, fee);
        }

        // display again
        this.displayAll();

    }// sort

    // method used to search for a car by registration
    private void search()
    {
        String regNumber = JOptionPane.showInputDialog(this, 
            "Enter registration of the car to search",
            "Input", JOptionPane.OK_OPTION);

        if (regNumber == null) {
            // user canceled, do nothing
            return;
        }

        ArrayList<Integer> indices = new ArrayList<Integer>();

        // linear search the regnumber ignoring case
        for (int i = 0; i < this.regNumbers.size(); i++) {
            if (regNumber.equalsIgnoreCase(this.regNumbers.get(i))) {
                indices.add(i);
            }
        }

        if (indices.isEmpty()) {
            // not found
            JOptionPane.showMessageDialog(this, 
                String.format("%s car not found", regNumber), 
                "Message", JOptionPane.WARNING_MESSAGE);
            return;
        } else {
            this.displayCars(indices);
        }

    }// search

    // method used to exit the program
    // a confirmation dialog should be shown to the user before exiting
    private void exit()
    {
        // display the confirmation dialog
        int option = JOptionPane.showConfirmDialog(this, 
            "Do you really want to exit?",
            "Exit Confirmation", JOptionPane.YES_OPTION);

        if (option == JOptionPane.YES_OPTION) {
            System.exit(0);
        }

    }// exit

    public static void main(String [] args)
    { // main method to create an instance of the class
        CarInsuranceGUI carInsurance = new CarInsuranceGUI();           // create instance of class

        carInsurance.setDefaultCloseOperation(JFrame.DO_NOTHING_ON_CLOSE);  // let the code close the program
        carInsurance.setSize(440, 390);                                     // dimensions of the JFrame
        carInsurance.setVisible(true);                                      // make the application visible
    } // main

    // private class used as an action listener for the buttons
    private class ButtonHandler implements ActionListener
    {
        public void actionPerformed(ActionEvent e)
        {
            if (e.getSource() == enterButton || e.getSource() == registrationField) // enter button or return hit in registration field
                enterData();
            else if (e.getSource() == displayAllButton)                     // display all button hit
                displayAll();
            else if (e.getSource() == sortButton)                           // sort button hit
                sort();
            else if (e.getSource() == searchButton)                         // search button hit
                search();
            else if (e.getSource() == exitButton)                           // exit button hit
                exit();
        }
    }// end ButtonHandler

}// end class

class Balance {
    private double balance = 1000.0;

    public double getBalance() {
        return balance;
    }

    public void deposit(double amount) {
        balance += amount;
    }

    public void withdraw(double amount) {
        balance -= amount;
    }
}

class BrokenDepositThread extends Thread {
    private Balance balance;

    public BrokenDepositThread(Balance b) {
        this.balance = b;
    }

    public void run() {
        System.out.println("Deposit: old balance = " + balance.getBalance());

        try {
            Thread.sleep(1000);
        } catch (InterruptedException ex) {
            ex.printStackTrace();
        }

        balance.deposit(100);
        System.out.println("Deposit: amount = 100");
        System.out.println("Deposit: new balance = " + balance.getBalance());        
    }
}

class BrokenWithdrawThread extends Thread {
    private Balance balance;

    public BrokenWithdrawThread(Balance b) {
        this.balance = b;
    }

    public void run() {
        System.out.println("Withdraw: old balance = " + balance.getBalance());

        try {
            Thread.sleep(1000);
        } catch (InterruptedException ex) {
            ex.printStackTrace();
        }

        balance.withdraw(100);
        System.out.println("Withdraw: amount = 100");
        System.out.println("Withdraw: new balance = " + balance.getBalance());        
    }
}

public class DriverATM_broken {

    public static void main(String args[]) {
        Balance balance = new Balance();

        new BrokenDepositThread(balance).start();
        new BrokenWithdrawThread(balance).start();
    }
}

class DepositThread extends Thread {
    private Balance balance;

    public DepositThread(Balance b) {
        this.balance = b;
    }

    public void run() {
        synchronized(balance) {
            System.out.println("Deposit: old balance = " + balance.getBalance());

            try {
                Thread.sleep(1000);
            } catch (InterruptedException ex) {
                ex.printStackTrace();
            }

            balance.deposit(100);
            System.out.println("Deposit: amount = 100");
            System.out.println("Deposit: new balance = " + balance.getBalance());        
        }
    }
}

class WithdrawThread extends Thread {
    private Balance balance;

    public WithdrawThread(Balance b) {
        this.balance = b;
    }

    public void run() {
        synchronized(balance) {
            System.out.println("Withdraw: old balance = " + balance.getBalance());

            try {
                Thread.sleep(1000);
            } catch (InterruptedException ex) {
                ex.printStackTrace();
            }

            balance.withdraw(100);
            System.out.println("Withdraw: amount = 100");
            System.out.println("Withdraw: new balance = " + balance.getBalance());        
        }
    }
}

public class DriverATM {

    public static void main(String args[]) {
        Balance balance = new Balance();

        new DepositThread(balance).start();
        new WithdrawThread(balance).start();
    }
}

import java.math.BigDecimal;

public class Temperature {

    // temperature in degress Kelvin
    private double degrees;

    public Temperature() {
        this(0);
    }

    public Temperature(double degrees) {
        this(degrees, 'K');
    }

    // construct a temperature instance
    // for the given temperature and scale
    public Temperature(double temp, char scale) {
        set(temp, scale);
    }

    // set the temperature of the given scale to this instance
    public void set(double temp, char scale) {
        this.degrees = revert(temp, scale);
    }

    // convert the internal temperature in Kelvin to the given scale
    private double convert(double degrees, char scale) {
        BigDecimal value = new BigDecimal(degrees);

        switch (scale) {
            case 'F':
            case 'f':
                return degrees * 9 / 5 - 459.67;

            case 'C':
            case 'c':
                return degrees - 273.15;

            case 'R':
            case 'r':
                return degrees * 9 / 5;

            case 'K':
            case 'k':
                return degrees;

            default:
                throw new IllegalArgumentException("unknown scale");
        }
    }

    // revert the given scaled temperature to Kelvin
    private double revert(double degrees, char scale) {
        BigDecimal value;

        switch (scale) {
            case 'F':
            case 'f':
                // since double is not accurate enough to handle division
                // test103-test114 failed if we do this directly.
                // return (degrees + 459.67) * 5 / 9;
                // thus, use BigDecimal instead
                value = new BigDecimal((degrees + 459.67) * 5);
                // divide by 9 and round up
                value = value.divide(new BigDecimal(9), 10, BigDecimal.ROUND_HALF_DOWN);
                return value.doubleValue();

            case 'C':
            case 'c':
                return degrees + 273.15;

            case 'R':
            case 'r':
                return degrees / (9.0 / 5.0);

            case 'K':
            case 'k':
                return degrees;

            default:
                throw new IllegalArgumentException("unknown scale");
        }    
    }

    // return temperature in Kelvin
    public double get() {
        return this.degrees;
    }

    // return temperature in the given scale
    public double get(char scale) {
        return convert(this.degrees, scale);
    }

    // return true if temperature < t
    public boolean isLessThan(Temperature t) {
        return get() < t.get();
    }

    // return true if temperature <= t
    public boolean isLessThanOrEqual(Temperature t) {
        return get() <= t.get();
    }

    // return true if temperature == t
    public boolean isEqual(Temperature t) {
        return get() == t.get();
    }

    // return true if temperature >= t
    public boolean isGreaterThanOrEqual(Temperature t) {
        return get() >= t.get();
    }

    // return true if temperature > t
    public boolean isGreaterThan(Temperature t) {
        return get() > t.get();
    }

    // return true if temperature != t
    public boolean isNotEqualTo(Temperature t) {
        return get() != t.get();
    }
}

public class TemperatureTester {
    // errorCount is a class variable so all methods can access it.
    static int errorCount = 0;

    public static void main(String[] args) {
        Temperature t = new Temperature();
        check(t.get(), 0, "Test 1");
        check(t.get('K'), 0, "Test 2");
        check(t.get('k'), 0, "Test 3");
        check(t.get('F'), -459.67, "Test 4");
        check(t.get('f'), -459.67, "Test 5");
        check(t.get('C'), -273.15, "Test 6");
        check(t.get('c'), -273.15, "Test 7");
        check(t.get('R'), 0, "Test 8");
        check(t.get('r'), 0, "Test 9");

        t = new Temperature(373.15);
        check(t.get(), 373.15, "Test 10");
        check(t.get('K'), 373.15, "Test 11");
        check(t.get('k'), 373.15, "Test 12");
        check(t.get('F'), 212, "Test 13");
        check(t.get('f'), 212, "Test 14");
        check(t.get('C'), 100, "Test 15");
        check(t.get('c'), 100, "Test 16");
        check(t.get('R'), 671.67, "Test 17");
        check(t.get('r'), 671.67, "Test 18");

        t.set(212, 'F');
        check(t.get(), 373.15, "Test 19");
        check(t.get('K'), 373.15, "Test 20");
        check(t.get('k'), 373.15, "Test 21");
        check(t.get('F'), 212, "Test 22");
        check(t.get('f'), 212, "Test 23");
        check(t.get('C'), 100, "Test 24");
        check(t.get('c'), 100, "Test 25");
        check(t.get('R'), 671.67, "Test 26");
        check(t.get('r'), 671.67, "Test 27");

        t.set(212, 'f');
        check(t.get(), 373.15, "Test 28");
        check(t.get('K'), 373.15, "Test 29");
        check(t.get('k'), 373.15, "Test 30");
        check(t.get('F'), 212, "Test 31");
        check(t.get('f'), 212, "Test 32");
        check(t.get('C'), 100, "Test 33");
        check(t.get('c'), 100, "Test 34");
        check(t.get('R'), 671.67, "Test 35");
        check(t.get('r'), 671.67, "Test 36");

        t.set(100, 'C');
        check(t.get(), 373.15, "Test 37");
        check(t.get('K'), 373.15, "Test 38");
        check(t.get('k'), 373.15, "Test 39");
        check(t.get('F'), 212, "Test 40");
        check(t.get('f'), 212, "Test 41");
        check(t.get('C'), 100, "Test 42");
        check(t.get('c'), 100, "Test 43");
        check(t.get('R'), 671.67, "Test 44");
        check(t.get('r'), 671.67, "Test 45");

        t.set(100, 'c');
        check(t.get(), 373.15, "Test 46");
        check(t.get('K'), 373.15, "Test 47");
        check(t.get('k'), 373.15, "Test 48");
        check(t.get('F'), 212, "Test 49");
        check(t.get('f'), 212, "Test 50");
        check(t.get('C'), 100, "Test 51");
        check(t.get('c'), 100, "Test 52");
        check(t.get('R'), 671.67, "Test 53");
        check(t.get('r'), 671.67, "Test 54");

        t.set(373.15, 'K');
        check(t.get(), 373.15, "Test 55");
        check(t.get('K'), 373.15, "Test 56");
        check(t.get('k'), 373.15, "Test 57");
        check(t.get('F'), 212, "Test 58");
        check(t.get('f'), 212, "Test 59");
        check(t.get('C'), 100, "Test 60");
        check(t.get('c'), 100, "Test 61");
        check(t.get('R'), 671.67, "Test 62");
        check(t.get('r'), 671.67, "Test 63");

        t.set(373.15, 'k');
        check(t.get(), 373.15, "Test 64");
        check(t.get('K'), 373.15, "Test 65");
        check(t.get('k'), 373.15, "Test 66");
        check(t.get('F'), 212, "Test 67");
        check(t.get('f'), 212, "Test 68");
        check(t.get('C'), 100, "Test 69");
        check(t.get('c'), 100, "Test 70");
        check(t.get('R'), 671.67, "Test 71");
        check(t.get('r'), 671.67, "Test 72");

        t.set(671.67, 'R');
        check(t.get(), 373.15, "Test 73");
        check(t.get('K'), 373.15, "Test 74");
        check(t.get('k'), 373.15, "Test 75");
        check(t.get('F'), 212, "Test 76");
        check(t.get('f'), 212, "Test 77");
        check(t.get('C'), 100, "Test 78");
        check(t.get('c'), 100, "Test 79");
        check(t.get('R'), 671.67, "Test 80");
        check(t.get('r'), 671.67, "Test 81");

        t.set(671.67, 'r');
        check(t.get(), 373.15, "Test 82");
        check(t.get('K'), 373.15, "Test 83");
        check(t.get('k'), 373.15, "Test 84");
        check(t.get('F'), 212, "Test 85");
        check(t.get('f'), 212, "Test 86");
        check(t.get('C'), 100, "Test 87");
        check(t.get('c'), 100, "Test 88");
        check(t.get('R'), 671.67, "Test 89");
        check(t.get('r'), 671.67, "Test 90");

        // t1 and t2 are different
        Temperature t1 = new Temperature(1);
        Temperature t2 = new Temperature(2);

        // <
        check(t1.isLessThan(t2), true, "Test 91");
        check(t2.isLessThan(t1), false, "Test 92");

        // <=
        check(t1.isLessThanOrEqual(t2), true, "Test 93");
        check(t2.isLessThanOrEqual(t1), false, "Test 94");

        // ==
        check(t1.isEqual(t2), false, "Test 95");
        check(t2.isEqual(t1), false, "Test 96");

        // >=
        check(t1.isGreaterThanOrEqual(t2), false, "Test 97");
        check(t2.isGreaterThanOrEqual(t1), true, "Test 98");

        // >
        check(t1.isGreaterThan(t2), false, "Test 99");
        check(t2.isGreaterThan(t1), true, "Test 100");

        // !=
        check(t1.isNotEqualTo(t2), true, "Test 101");
        check(t2.isNotEqualTo(t1), true, "Test 102");

        // t1 and t2 are equal, but not exactly
        t1.set(671.67, 'r');
        t2.set(212, 'f');

        // <
        check(t1.isLessThan(t2), false, "Test 103");
        check(t2.isLessThan(t1), false, "Test 104");

        // <=
        check(t1.isLessThanOrEqual(t2), true, "Test 105");
        check(t2.isLessThanOrEqual(t1), true, "Test 106");

        // ==
        check(t1.isEqual(t2), true, "Test 107");
        check(t2.isEqual(t1), true, "Test 108");

        // >=
        check(t1.isGreaterThanOrEqual(t2), true, "Test 109");
        check(t2.isGreaterThanOrEqual(t1), true, "Test 110");

        // >
        check(t1.isGreaterThan(t2), false, "Test 111");
        check(t2.isGreaterThan(t1), false, "Test 112?");

        // !=
        check(t1.isNotEqualTo(t2), false, "Test 113");
        check(t2.isNotEqualTo(t1), false, "Test 114");

        // Print summary
        if(errorCount == 0){
            System.out.println("\nNo Errors Found");
        } else {
            System.out.println("\n" + errorCount + " test(s) failed");
        }
    }

    public static void check(boolean value, boolean expected, String message){
        if(value != expected){
            errorCount++;
            System.out.println(message + ": got " + value + " expected " + expected);
        }
    }

    public static void check(double value, double expected, String message ){
        if (!approxEqual(value, expected)){
            errorCount++;
            System.out.println(message + ": got " + value + " expected " + expected);
        }

    }

    public static boolean approxEqual(double x, double y){
        return Math.abs(x - y) < 10E-12;
    }

}

A B 0.5
A E 1.5
A D 1.2
B A 0.5
B C 0.7
C B 0.7
C E 0.5
C F 2.5
D A 1.2
D F 4.5
E A 1.5
E C 0.5
E F 0.5
F C 2.5
F D 4.5
F E 0.5

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.io.IOException;
import java.io.FileInputStream;

public class MappingApp {
  public static void main(String[] args) {
    String filename = null;

    // use Scanner to let user input the file name to load
    Scanner scanner = new Scanner(System.in);
    while (filename == null || filename.length() == 0) {
      System.out.print("Input the name of the file to load: ");
      filename = scanner.nextLine();
    }

    // load the graph from the file
    Graph graph = new Graph();
    graph.loadFromFile(filename);

    // display the graph
    System.out.println(graph);

    // ask the user to input two vertices to calculate the shortest path
    String start = null, end = null;
    while (start == null || start.length() == 0) {
      System.out.print("Input the start vertex: ");
      start = scanner.nextLine();
    }
    while (end == null || end.length() == 0) {
      System.out.print("Input the end vertex: ");
      end = scanner.nextLine();
    }

    System.out.println();
    // run dijkstra's algorithm to display the shorted distance
    graph.dijkstra(start, end);
  }
}

class Vertex {
  private String name;

  // the edges that start from this vertex
  private List<Edge> edges;

  // these are for dijkstra's algorithm
  private double distance;
  private boolean visited;
  private Vertex previous;

  public Vertex(String name) {
    this.name = name;
    this.edges = new ArrayList<Edge>();
  }

  public double getDistance() {
    return this.distance;
  }

  public Vertex getPrevious() {
    return this.previous;
  }

  // update the distance and set the previous vertex to the parameter
  public void updateDistance(Vertex previous, double value) {
    this.previous = previous;
    this.distance = value;
  }

  public String getName() {
    return this.name;
  }

  // add an edge for this vertex. if such an edge already exist, 
  // then update the old weight with the
  // weight in the parameter.
  public boolean addEdge(Edge e) {
    for (int i = 0; i < edges.size(); i++) {
      Edge old = this.edges.get(i);
      if (old.getEnd().getName().equals(e.getEnd().getName())) { // found
        this.edges.set(i, e); // update the weight
        return false;
      }
    }

    this.edges.add(e); // not found
    return true;
  }

  public List<Edge> getEdges() {
    return this.edges;
  }

  public void setVisited(boolean v) {
    this.visited = v;
  }

  public boolean visited() {
    return this.visited;
  }
}

class Edge {
  private Vertex start;
  private Vertex end;
  private double weight;

  public Edge(Vertex start, Vertex end, double weight) {
    this.start = start;
    this.end = end;
    this.weight = weight;
  }

  public Vertex getStart() {
    return this.start;
  }

  public Vertex getEnd() {
    return this.end;
  }

  public double getWeight() {
    return this.weight;
  }
}

class Graph {
  private List<Vertex> vertices;
  private List<Edge> edges;

  public Graph() {
    vertices = new ArrayList<Vertex>();
    edges = new ArrayList<Edge>();
  }

  public void dijkstra(String start, String end) {
    // check whether start and end are in the graph
    Vertex startVertex = findVertex(start, false);
    Vertex endVertex = findVertex(end, false);

    if (startVertex == null || endVertex == null) {
      System.out.printf("Vertex %s or %s does not exist in the graph!\n", start, end);
      return;
    }

    // prepare the data for dijktra algorithm
    for (Vertex v : this.vertices) {
      v.setVisited(false);
      v.updateDistance(null, Double.POSITIVE_INFINITY);
    }

    startVertex.updateDistance(null, 0);
    Vertex curr;

    while ((curr = closest()) != null) {
      curr.setVisited(true);
      if (curr == endVertex) { // already found
        break;
      }

      // otherwise, update the vertices that this vertex has edges with
      for (Edge e : curr.getEdges()) {
        Vertex next = e.getEnd();
        if (curr.getDistance() + e.getWeight() < next.getDistance()) {
          // smaller distance, update
          next.updateDistance(curr, curr.getDistance() + e.getWeight());
        }
      }
    }

    // now dijkstra is done, display the path
    if (endVertex.visited()) {
      System.out.printf("Shortest distance from %s to %s: %.1f\n", start, end, endVertex.getDistance());
      displayPath(startVertex, endVertex);
      System.out.println();
    } else {
      System.out.printf("%s cannot reach %s.\n", start, end);
    }
  }

  // recursively display the path
  private void displayPath(Vertex start, Vertex end) {
    if (start == end) {
      System.out.print(end.getName());
    } else {
      displayPath(start, end.getPrevious());
      System.out.printf(" -> %s", end.getName());
    }
  }

  // find the vertex that has the smallest distance but still not visited
  private Vertex closest() {
    Vertex close = null;
    double distance = Double.POSITIVE_INFINITY;
    for (Vertex v : this.vertices) {
      if (!v.visited() && v.getDistance() < distance) {
        distance = v.getDistance();
        close = v;
      }
    }
    return close;
  }

  public void loadFromFile(String filename) {
    // load the graph information from the given file
    // use a scanner to scan the file
    Scanner scanner = null;
    try {
      scanner = new Scanner(new FileInputStream(filename));
      while (scanner.hasNext()) { // process line by line
        String start = scanner.next();

        if (start.length() == 0) {
          // End of file: this is the last empty line in the file
          break;
        }

        // read end vertex and weight
        String end = scanner.next();
        double weight = scanner.nextDouble();

        // add the edge to this graph
        addEdge(start, end, weight);
      }
    } catch (IOException e) {
      System.out.println("Could not read file: " + filename);
      System.exit(0);
    } finally {
      if (scanner != null) { // close the file
        scanner.close();
      }
    }
  }

  // add the edge to this graph
  private void addEdge(String start, String end, double weight) {
    Vertex startVertex = findVertex(start, true);
    Vertex endVertex = findVertex(end, true);

    Edge edge = new Edge(startVertex, endVertex, weight);
    if (startVertex.addEdge(edge)) { // new edge
      this.edges.add(edge);
    }
  }

  // find the vertex with the given name in the graph
  // if this name does not exist yet and addNew is true, append a new vertex into the list of vertices
  private Vertex findVertex(String name, boolean addNew) {
    for (Vertex v : vertices) {
      if (v.getName().equals(name)) {
        return v; // found
      }
    }
    if (addNew) {
      // not found, construct one
      Vertex v = new Vertex(name);
      this.vertices.add(v);
      return v;
    }

    return null;
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder();

    builder.append("------------------ Vertices ------------------\n");
    for (Vertex v : this.vertices) {
      builder.append(v.getName() + "\n");
    }

    builder.append("------------------   Edges  ------------------\n");
    for (Edge e : this.edges) {
      builder.append(e.getStart().getName() + " " + e.getEnd().getName() + " " + e.getWeight() + "\n");
    }

    return builder.toString();
  }
}