package amphis;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

import graph.BFSPath;
import graph.DFSPath;
import graph.Graph;

class Page {
  final int id;
  final String title;
  
  public Page(int id, String title) {
    this.id = id;
    this.title = title;
  }
  
  @Override
  public int hashCode() {
    return this.id;
  }
  
  @Override
  public boolean equals(Object o) {
    Page that = (Page)o;
    return this.id == that.id;
  }
  
  @Override
  public String toString() { return this.title; }
  
}

public class Amphi9 { 
  
  public static void main(String[] args) throws IOException {
    Graph<Page> g = new Graph<Page>();
    
    HashMap<Integer, Page> pages = new HashMap<Integer, Page>();
    HashMap<String, Page> byName = new HashMap<String, Page>();
    
    File f = new File("../../wikipedia/simple-pages.txt");
    Scanner sc = new Scanner(f);
    int count = 0;
    while (sc.hasNext()) {
      int id = sc.nextInt();
      String s = sc.next();
      Page p = new Page(id, s);
      g.addVertex(p);
      pages.put(id, p);
      byName.put(s, p);
      count++;
    }
    System.out.println(count + " pages");
    sc.close();
    
    f = new File("../../wikipedia/simple-links.txt");
    BufferedReader r = new BufferedReader(new FileReader(f));
    count = 0;
    while (true) {
      String s = r.readLine();
      if (s == null) break;
      sc = new Scanner(s);
      Page p = pages.get(sc.nextInt());
      if (p == null) continue;
      while (sc.hasNext()) {
        Page q = pages.get(sc.nextInt());
        if (q == null) continue;
        g.addEdge(p, q);
        count++;
      }
      sc.close();
    }
    System.out.println(count + " links");
    
    r = new BufferedReader(new InputStreamReader(System.in));
    while (true) {
      Page source = readPage(r, "enter source:", byName);
      if (source == null) continue;
      DFSPath<Page> dfs = new DFSPath<Page>(g);
      dfs.dfsStack(source);
      BFSPath<Page> bfs = new BFSPath<Page>(g);
      bfs.bfs(source);
      
      while (true) {
        Page target = readPage(r, "enter target:", byName);
        if (target == null) break;
        if (dfs.isVisited(target)) {
        	System.out.println("DFS:");
          List<Page> path = dfs.getPath(target);
          printPath(source, path);
          System.out.println("BFS:");
          assert bfs.isVisited(target);
          path = bfs.getPath(target);
          printPath(source, path);
        } else
          System.out.println("  page '" + target + "' is not reachable");
      }
    }
  }
  
  static void printPath(Page source, List<Page> path) {
    System.out.print("  " + source);
    path.remove(0);
    int i = 0;
    for (Page p: path) {
      System.out.print(" -> " + p); if (++i % 8 == 0) System.out.print("\n  ");
    }
    System.out.println();  	
    System.out.println("  path of length " + path.size());
  }
  
  static Page readPage(BufferedReader r, String msg, Map<String, Page> byName) throws IOException {
    while (true) {
      System.out.print(msg + " ");
      String s = r.readLine();
      if (s.equals("")) return null;
      Page p = byName.get(s);
      if (p != null) {
        // System.out.println("  this is page " + p.id);
        return p;
      }
      System.out.println("  unknown page");
    }
  }
  
}