////////////////// 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;
  }

}  // VMGraf