////////////////// class VMGraf //////////////////////////////

package hjelpeklasser;

import java.util.*;
import java.io.*;
import java.net.URL;

public final class VMGraf           // final: skal ikke arves
{
  private final byte IKKE_KANT = -128;      // minst byte-verdi

  private byte[][] graf;                    // en todimensjonal tabell
  private int antall;                       // antall noder
  private String[] navn;                    // nodenavn - usortert
  private String[] snavn;                   // nodenavn - sortert
  private int[] indeks;                     // indekser

  private int[] avstand;                    // for senere bruk
  private int[] forrige;                    // for senere bruk

  public VMGraf(int dimensjon)                // konstruktør
  {
    graf = new byte[dimensjon][dimensjon];    // grafmatrisen
    antall = 0;                               // foreløpig ingen noder
    navn = new String[dimensjon];             // nodenavn - usortert

    snavn = new String[dimensjon];            // nodenavn - sortert
    indeks = new int[dimensjon];              // indekstabell

    for (int i = 0; i < dimensjon; i++)
    {
      Arrays.fill(graf[i], IKKE_KANT);        // setter IKKE-KANT på alle plasser
    }
  }

  public VMGraf()                             // standardkonstruktør
  {
    this(10);                                 // bruker 10 som startdimensjon
  }

  public VMGraf(String url) throws IOException // konstruktør - henter fra fil
  {
    this();

    BufferedReader inn = new BufferedReader  // leser fra fil
        (new InputStreamReader((new URL(url)).openStream()));

    String linje;
    while ((linje = inn.readLine()) != null)
    {
      String[] s = linje.split(" ");            // deler opp linjen

      String fra = s[0];                        // franode kommer først
      leggInnNode(fra);

      for (int i = 1; i < s.length; i += 2)     // går gjennom kantene
      {
        String til = s[i];                      // noden kanten går til
        int vekt = Integer.parseInt(s[i + 1]);  // kantens vekt

        leggInnNode(til);                       // legger inn tilnode
        leggInnKant(fra, til, vekt);            // legger inn kanten
      }
    }
  }

  private void utvid()
  {
    int nydimensjon = graf.length == 0 ? 1 : 2*graf.length;  // dobler

    navn = Arrays.copyOf(navn, nydimensjon);       // usortert navnetabell
    snavn = Arrays.copyOf(snavn, nydimensjon);     // sortert navnetabell
    indeks = Arrays.copyOf(indeks, nydimensjon);   // indekstabell

    byte[][] gammelgraf = graf;
    graf = new byte[nydimensjon][nydimensjon];     // grafmatrisen

    for (int i = 0; i < antall; i++)
    {
      System.arraycopy(gammelgraf[i], 0, graf[i], 0, antall);
      Arrays.fill(graf[i], antall, nydimensjon, IKKE_KANT);  // resten av raden
    }

    for (int i = antall; i < nydimensjon; i++)
    {
      Arrays.fill(graf[i], IKKE_KANT);  // hele raden
    }
  }

  public boolean leggInnNode(String nodenavn)     // ny node
  {
    if (navn == null || nodenavn.length() == 0)
      throw new IllegalArgumentException("Noden må ha et navn!");

    int rad = finn(nodenavn);    // raden i den sorterte navnetabellen
    if (rad >= 0) return false;  // finnes fra før!

    if (antall >= graf.length) utvid();  // sjekker om det er fullt

    rad = -(rad + 1);  // for å få innsettingspunktet

    for (int i = antall; i > rad; i--)
    {
      snavn[i] = snavn[i - 1];    // forskyver i snavn[]
      indeks[i] = indeks[i - 1];  // forskyver i infeks[]
    }

    snavn[rad] = nodenavn;      // på rett sortert plass i snavn[]
    navn[antall] = nodenavn;    // på neste ledige plass
    indeks[rad] = antall;       // antall blir indeks i navn[] 

    antall++;  // en ny node

    return true;  // vellykket innlegging
  }

  public void leggInnKant(String franode, String tilnode, int vekt)
  {
    if (franode.equals(tilnode)) throw    // sjekker om de er like
      new IllegalArgumentException(franode + " er lik " + tilnode + "!");

    int i = finn(franode);   // indeks i den sorterte navnetabellen
    if (i < 0) throw new NoSuchElementException(franode + " er ukjent!");
    i = indeks[i];           // indeks i den usorterte navnetabellen

    int j = finn(tilnode);   // indeks i den sorterte navnetabellen
    if (j < 0) throw new NoSuchElementException(tilnode + " er ukjent!");
    j = indeks[j];           // indeks i den usorterte navnetabellen

    if (graf[i][j] != IKKE_KANT)
      throw new IllegalArgumentException("Kanten finnes fra før!");

    if (vekt < -127 || vekt > 127)
      throw new IllegalArgumentException(vekt + " er ulovlig som vekt!");

    graf[i][j] = (byte)vekt;  // fra int til byte
  }

  public String kanterFra(String node)
  {
    int i = finn(node);  // indeks i den sorterte navnetabellen
    if (i < 0) return null;
    i = indeks[i];       // indeks i den usorterte navnetabellen

    StringJoiner sj = new StringJoiner(", ", "[", "]");

    for (int j = 0; j < antall; j++)
    {
      if (graf[i][j] != IKKE_KANT)
        sj.add('(' + navn[j] + ',' + graf[i][j] + ')');
    }

    return sj.toString();
  }

  public int antallNoder()    // antall noder i grafem 
  {
    return antall;
  }

  public int dimensjon()      // dimensjonen til tabellene
  {
    return graf.length;
  }

  public String[] nodenavn()  // navn på alle nodene
  {
    return Arrays.copyOf(snavn, antall);
  }

  private int finn(String nodenavn)  // privat hjelpemetode
  {
    return Arrays.binarySearch(snavn, 0, antall, nodenavn);
  }

  public boolean nodeFinnes(String nodenavn)  // finnes denne noden?
  {
    return finn(nodenavn) >= 0;
  }

  public void kortestVeiFra(String nodenavn)  // Dijkstras metode
  {
    int i = finn(nodenavn);  // indeks i den sorterte navnetabellen
    if (i < 0) throw new NoSuchElementException(nodenavn + " er ukjent!");
    i = indeks[i];           // indeks i den usorterte navnetabellen   

    class Avstand  // lokal hjelpeklasse
    {
      int node;
      int avstand;

      Avstand(int node, int avstand)
      {
        this.node = node; this.avstand = avstand;
      }
    }

    Queue<Avstand> aktiv = new PriorityQueue<>((a,b) -> a.avstand - b.avstand);

    avstand = new int[antall];           // oppretter tabellen
    Arrays.fill(avstand, 0x7fffffff);    // setter verdiene til "uendelig"

    forrige = new int[antall];           // oppretter tabellen
    Arrays.fill(forrige, -1);            // setter verdiene til -1

    boolean[] ferdig = new boolean[antall];  // lokal hjelpetabell

    avstand[i] = 0;                      // avstand i startnoden settes til 0
    aktiv.offer(new Avstand(i, 0));      // startnoden er nå aktiv

    while (!aktiv.isEmpty())             // så lenge det er aktive noder
    {
      Avstand minst = aktiv.poll();      // den "minste" noden
      int denne = minst.node;            // hjelpevariabel
      int avst = minst.avstand;          // hjelpevariabel

      ferdig[denne] = true;              // denne er ferdig

      for (int neste = 0; neste < antall; neste++)  // går gjennom matriseraden
      {
        if (graf[denne][neste] != IKKE_KANT) // en kant fra denne til neste
        {
          if (ferdig[neste]) continue;  // hopper over neste siden den er ferdig

          int vekt = graf[denne][neste];     // hjelpevariabel

          if (avst + vekt < avstand[neste])  // sammenligner
          {
            avstand[neste] =  avst + vekt;
            aktiv.offer(new Avstand(neste, avstand[neste]));
            forrige[neste] = denne;   // veien går fra denne til neste
          }
        }
      } // for
    } // while
  }

  public int avstand(String nodenavn)
  {
    int i = finn(nodenavn);  // indeks i den sorterte navnetabellen
    if (i < 0) throw new NoSuchElementException(nodenavn + " er ukjent!");
    i = indeks[i];           // indeks i den usorterte navnetabellen   

    return avstand[i];
  }

  public String veiTil(String node)
  {
    int i = finn(node);  // indeks i den sorterte navnetabellen
    if (i < 0) throw new IllegalArgumentException(node + " er ukjent!");
    i = indeks[i];       // indeks i den usorterte navnetabellen

    int avst = avstand[i];

    if (forrige[i] == -1) return "[], 0";  // ingen vei til denne noden

    Deque<String> stakk = new ArrayDeque<>();  // bruker en deque som stakk

    while (i != -1)
    {
      stakk.push(navn[i]);                 // legger nodenavnet på stakken
      i = forrige[i];                      // går til forrige node på veien
    }

    return stakk.toString() + ", " + avst;
  }

}  // VMGraf