/*=======================================================================
   Berikut ini adalah kerangka program untuk tugas ke 4 struktur data
   kerangka ini tidak perlu diikuti 100% (anda boleh berkreasi sendiri).
   Kerangka ini dituliskan untuk membantu anda dalam:
   - membuat applet minimal
   - merancang kelas-kelas dalam tugas anda

   Misalkan dalam kerangka ini kelas-kelas dibagi dalam
      kelas utama : Tugas4.class
      kelas untuk graph: Graph.class
      kelas untuk linked-list vertex: VertexList.class
      kelas untuk vertex-nya sendiri: VertexNode.class
      kelas untuk adjacent list: AdjacentList.class
      kelas untuk edge-nya sendiri: EdgeNode.class
     (ingat, nama-nama kelas ini hanya contoh....)

=======================================================================*/

import java.awt.*;
import java.applet.*;
import java.awt.event.*;

public class Tugas4 extends Applet { // misalnya namanya Tugas4.java
    // misalkan kelas obyek Graph anda adalah Graph
    Graph graf;
    // metoda init untuk menginisialisasi applet, layout,
    // dan load datanya tentu

    public void init()    {
        this.setBackground(Color.white);
        defineLayout();
        graf = new Graph();

        // misalnya file data dideklarasikan dalam parameter
        // applet dengan nama parameter "filename"
        String fn = getParameter("filename");

        // load data dalam graph dengan metoda loadData(String)
        graf.loadData(fn);
    }

    // dalam metoda paint anda tuliskan penggambaran graph (termasuk
    // peragaan Shortestpath yang telah anda temukan
    public void paint(Graphics g) {
        graf.draw(g);
    }

    // metoda berikut ini merupakan private method untuk mendefinisikan
    // layout interaksi dari applet anda
    private void defineLayout() {

        this.setLayout(new BorderLayout());

        // supaya rapih, buttonBar digunakan untuk menempatkan 
        // komponen-komponen interaksi anda
        Panel buttonBar = new Panel();
        buttonBar.setBackground(Color.gray);
        this.add(buttonBar,"South");
        buttonBar.setLayout(new FlowLayout());

        // contoh button pada buttonBar
        contohButton = new Button("cari shortest path");
        buttonBar.add(contohButton);
    
        // mengkaitkan dengan Listenernya
        contohButton.addActionListener(
            new ActionListener() {
                public void actionPerformed(ActionEvent event) {
                    // anda tuliskan disini proses apa yang
                    // terjadi jika button tsb. ditekan
		    // misalnya jika ini untuk mengaktifkan
		    // pencarian shortest path maka pemanggilan
		    // dilakukan disini
		    graf.shortestPath(asal, tujuan);
                    repaint();
                }
            }
        ); 

        // Berikut ini contoh TextField (di depannya ada label)
        // yang berada pada buttonBar setelah button1
        // nanti mengaksesnya dengan contohInput.getText()
        contohLabel = new Label("   Nama Anda");
        buttonBar.add(contohLabel);
        contohInput = new TextField("     ");
        buttonBar.add(contohInput);

        // Berikut ini contoh choice menu
        // nanti mengaksesnya dengan colorCHoice.getSelectedItem()
        colorChoice = new Choice();
        colorChoice.addItem("Hitam");
        colorChoice.addItem("Merah");
        colorChoice.addItem("Kuning");
        buttonBar.add(colorChoice);

        // ini contoh mengimplementasikan MouseListener

        this.addMouseListener(
            new MouseAdapter() {
                public void mousePressed(MouseEvent e) {
                    Graphics g = getGraphics();
                    xold = e.getX();
                    yold = e.getY();
                }
            }
        );

        this.addMouseMotionListener(
            new MouseMotionAdapter() {
                public void mouseDragged(MouseEvent e) {
                    Graphics g = getGraphics();
                    int x = e.getX();
                    int y = e.getY();
                    g.drawLine(xold,yold,x,y);
                    xold = x;
                    yold = y;
                }
            }
        );
    }

}

//========================================================================

public class Graph {
    // misalnya anda sudah punya class LinkedList untuk vertex
    VertexList v;

    public Graph(){
        v = new VertexList();
    }

    public loadData(String fname) {
        // disini anda menuliskan program membaca data ke dalam
        // struktur data Graphnya
        
        // setelah membaca nama-nama verteks maka anda akan menginsert
        // verteks baru dalam v dengan metoda v.insertVertex(namaverteks, x, y)

        // setelah membaca nama-nama verteks maka anda akan menginsert
        // kedua edge baru dalam v dengan metoda 
        // v.insertEdge(A, B, bobot)

    }

    // mencari shortestPath

    shortestPath(String asal, String tujuan){
     ..........
    }

    // menggambarkan graph serta shortest pathnya ika telah dicari
    public draw() {
     .........
    }
}

// =======================================================================
// pada dasarnya VertexList adalah suatu linked list
// dengan masing-masing verteks menyimpan data (x,y)
// serta linked-list dari adjacent edge
public class VertexList {
    VertexNode vertices;
    public VertexList() {
	vertices = null; // saat dicreate linked list kosong
    }

    void insertVertex(String namaVertex, int x, int y) {
	// disini anda mencari dalam list apakah sudah ada
	// verteks yang bernama namaVertex (untuk menghindari
	// duplikasi, jika sudah ada maka reject data

	// kemudian create VertexNode
	VertexNode newVertex = new VertexNode(namaVertex, x, y)

	// akhirnya insert newVertex dalam linked list vertices
    }


    void insertEdge(String asal, String tujuan, double bobot) {
	// anda mencari dalam linked list vertices dengan nama asal
	// misalnya v1, lalu verteks dengan nama tujuan misalnya v2,
	// lalu lalu lakukan insert pada masing-masing adjacent list

	v1.insertAdjacentList(v2, bobot);
	v2.insertAdjacentList(v1, bobot); // hmm. bolak-balik kan?
    }
}

// =======================================================================
// ini kelas elemen linked list VertexList (kelas verteksnya sendiri)

public class VertexNode {
    String id;
    int x,
    int y;
    VertexNode next;
    AdjacentList adj;

    public VertexNode(String id, int x, int y) {
	this.id = id;
	this.x  = x;
	this.y  = y;
	this.next = null;
	this.adj = new AdjacentList();
    }

    public insertAdjacentList(VertexNode v, double weight) {
	// insert dalam linked list adj
	adj.insert(v, weight);

    }
}


// =======================================================================
// ini kelas untuk adjacent list dari edge
public class AdjacentList {
    EdgeNode header;

    public AdjacentList() {
	header = null;
    }


    public insert(VertexNode v, double w) {
	// create EdgeNode lalu melakukan insert pada linked list ini
	EdgeNode newEdge = new EdgeNode(v,w);
	header.insert(newEdge);
    }

}
// =======================================================================
// ini kelas elemen linked list adjacent list (untuk edgenya sendiri)
public class EdgeNode {
    double weight;
    NertexNode v;
    EdgeNode next;
    public EdgeNode( NertexNode v, double weight){
	this.v = v;
	this.weight = weight;
	this.next = null;
    }
}