// DirectedGraph.java
// Copyright (C) 2000 Linyuan Lu
// Code based on David Binger's Graph.java 
// Copyright (C) 1997 David Binger
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, 
// Boston, MA  02111-1307, USA.

// Version 0.1

import java.io.*;
import java.awt.*;

public class DirectedGraph
extends Selectable
	//implements Serializable
{
  public List vertices = new List();
  public List edges = new List();
  public List discs = new List();
  public List faces = new List();
  public List outsideVerticies = new List();

  public int getE(){
	int sum=0;
	int n=vertices.length;
	Object a[]=vertices.elements;
	for(int i=0;i<n;i++){
	    sum=sum+((DirectedVertex) a[i]).inDegree();
	}
	return sum;
    }


  // Serializable
  //  private void writeObject(ObjectOutputStream out)
//    throws IOException { 
//  //      out.writeObject(version);
//  //      out.writeObject(vertices);
//  //      out.writeObject(edges);
//    }


  // Serializable
  //  private void readObject(ObjectInputStream in)
//    throws IOException, ClassNotFoundException {
//      String v = (String)in.readObject();
//      if (!(v.equals(version))) {
//        System.err.println("Attempting to read version "+v);
//        System.err.println("file with version "+version+" software.");
//        System.err.println("Expect failure.");
//      }
//      vertices=(List)in.readObject();
//      edges=(List)in.readObject();
//    }

  public DirectedGraph() {}

 //   public Graph(String filename) {
//      try {
//        FileInputStream  f = new FileInputStream(filename);
//        ObjectInputStream s = new ObjectInputStream(f);
//        Graph g = (Graph)s.readObject();
//        f.close();
//        vertices = g.vertices;
//        edges = g.edges;
//      } catch (Exception ex) {
//        System.out.println(ex);
//        ex.printStackTrace();
//      }
//    }

  public final DirectedVertex vertex(int n) {
    return ((DirectedVertex)(vertices.elements[n]));
  }

  public final DirectedEdge edge(int n) {
    return ((DirectedEdge)(edges.elements[n]));
  }

  public final DirectedEdge disc(int n) {
    return ((DirectedEdge)(discs.elements[n]));
  }

  public final DirectedVertex addVertex(DirectedVertex v) {
    vertices.push(v);
    return v;
  }

  public final DirectedVertex addVertex() {
    DirectedVertex v = new DirectedVertex();
    vertices.push(v);
    return v;
  }

  public final DirectedVertex addVertex(int x,int y) {
    DirectedVertex v = new DirectedVertex(x,y);
    vertices.push(v);
    return v;
  }

  public final Disc addDisc(double x, double y, double r) {
    Disc d = new Disc(x,y,r);
    discs.push(d);
    return d;
  }

  public final Disc addDisc(Disc d) {
    discs.push(d);
    return d;
  }

  public final Disc deleteDisc(Disc d) {
    discs.delete(d);
    return d;
  }

  public final void delEdge(DirectedEdge e) {
    e.start.delOutEdge(e);
    e.end.delInEdge(e);
    edges.delete(e);
  }

  public final void delVertex(DirectedVertex v) {
     int n = v.inedges.length;
    Object a[] = v.inedges.elements;
    for (int j=0;j<n;j++) {
      DirectedEdge e = (DirectedEdge)a[j];
      edges.delete(e);
      e.start.delOutEdge(e);
    }
    n = v.outedges.length;
    Object b[] = v.outedges.elements;
    for (int j=0;j<n;j++) {
      DirectedEdge e = (DirectedEdge)b[j];
      edges.delete(e);
      e.end.delInEdge(e);
    }

  //      int n=edges.length;
//        Object x[]=edges.elements;
//        for(int i=0;i<n;i++){
//  	  DirectedEdge ed=(DirectedEdge) x[i];
//  	  if(v.equals(ed.start)||v.equals(ed.end))
//  	      delEdge(ed);
//  	  n--;
//  	  i--;
//        }

    vertices.delete(v);
  }

  public final DirectedEdge addEdge(DirectedVertex a, DirectedVertex b) {
    DirectedEdge e = new DirectedEdge(a,b);
    int n=edges.length;
    Object x[]=edges.elements;

    for(int i=0;i<n;i++){
	    if(e.start.equals(((DirectedEdge)x[i]).start)&&
	        e.end.equals(((DirectedEdge)x[i]).end)){
	      ((DirectedEdge)x[i]).multi+=e.multi;
	      a.addOutEdge(e);
	      b.addInEdge(e);
	      return ((DirectedEdge)x[i]);
	    }
    }
    edges.push(e);
    a.addOutEdge(e);
    b.addInEdge(e);
    return e;
  }

  public final DirectedEdge addEdge(int a,int b) {
   DirectedVertex v1 = (DirectedVertex)vertices.elements[a];
    DirectedVertex v2 = (DirectedVertex)vertices.elements[b];
    return addEdge(v1,v2);
  }    

  public String toString() {
    String s = "(graph\n";
    s += vertices.toString() +"\n";
    s += edges.toString();
    s = s +"\n)";
    return s;
  }
  
  public final void paint(Graphics g) {
    int n = edges.length;
    Object x[] = edges.elements;
    int j;

    for (j=0;j<n;j++)
      ((DirectedEdge)x[j]).paint(g);

    n = vertices.length;
    x = vertices.elements;

    for (j=0;j<n;j++)
      ((DirectedVertex)x[j]).paint(g);

    for (j=0;j<n;j++)
      ((DirectedVertex)x[j]).paintLabel(g);

    n = edges.length;
    x = edges.elements;

    for (j=0;j<n;j++)
      ((DirectedEdge)x[j]).paintLabel(g);

    n = discs.length;
    x = discs.elements;
    
    for (j=0;j<n;j++)
      ((Disc)x[j]).paint(g);
  }



  // Move vertices and edges.
  public final void moveRelative(double x,double y) {
    int n = edges.length;
    Object a[] = edges.elements;
    int j;
    for (j=0;j<n;j++)
      ((DirectedEdge)a[j]).moveRelative(x,y);
    n = vertices.length;
    a = vertices.elements;
    for (j=0;j<n;j++)
      ((DirectedVertex)a[j]).moveRelative(x,y);
  }

  /*public List ListAdjEdges(DirectedVertex vertex)
  {
    List adjEdgeList = new List();
    for(int i=0; i<edges.length; i++) {
      if ( ((DirectedEdge)(edges.elements[i])).start == vertex ||
          ((DirectedEdge)(edges.elements[i])).start == vertex)
        adjEdgeList.push((DirectedEdge)(edges.elements[i]));
    }
    return  adjEdgeList;
  }*/

  //checking if two edges are crossing
  public boolean isCrossing(DirectedEdge e1, DirectedEdge e2){
      if(e1.start==e2.start
         || e1.start==e2.end
         || e1.end==e2.start
         || e1.end==e2.end) return false;

      double s,t; //the affine coordinates respect to e1=AB and e2=CD.
      double e1x=e1.start.position.x - e1.end.position.x; // e1x is x coodinates of A-B.
      double e1y=e1.start.position.y - e1.end.position.y; // e1y is y coodinates of A-B.
      double e2x=e2.start.position.x - e2.end.position.x; // e2x is x coodinates of C-D.
      double e2y=e2.start.position.y - e2.end.position.y; // e2y is y coodinates of C-D.
      
      double dbx=e2.end.position.x-e1.end.position.x; // dbx is x coodinates of D-B.
      double dby=e2.end.position.y-e1.end.position.y; // dby is y coodinates of D-B.

      double determint=e1x * e2y - e1y * e2x;
      if(determint <0.001 && determint >0.001)
          return false; // e1 and e2 are parallel.
      s = (dbx * e2y -dby * e2x)/determint;
      t = (dbx * e1y -dby * e1x)/determint;
      if(0<s && s<1 && 0<t && t<1) return true;
      else return false;
  }

}