package hjelpeklasser;
import java.util.*;
import java.io.*;
import java.net.URL;
public final class VMGraf
{
private final byte IKKE_KANT = -128;
private byte[][] graf;
private int antall;
private String[] navn;
private String[] snavn;
private int[] indeks;
private int[] avstand;
private int[] forrige;
public VMGraf(int dimensjon)
{
graf = new byte[dimensjon][dimensjon];
antall = 0;
navn = new String[dimensjon];
snavn = new String[dimensjon];
indeks = new int[dimensjon];
for (int i = 0; i < dimensjon; i++)
{
Arrays.fill(graf[i], IKKE_KANT);
}
}
public VMGraf()
{
this(10);
}
public VMGraf(String url) throws IOException
{
this();
BufferedReader inn = new BufferedReader
(new InputStreamReader((new URL(url)).openStream()));
String linje;
while ((linje = inn.readLine()) != null)
{
String[] s = linje.split(" ");
String fra = s[0];
leggInnNode(fra);
for (int i = 1; i < s.length; i += 2)
{
String til = s[i];
int vekt = Integer.parseInt(s[i + 1]);
leggInnNode(til);
leggInnKant(fra, til, vekt);
}
}
}
private void utvid()
{
int nydimensjon = graf.length == 0 ? 1 : 2*graf.length;
navn = Arrays.copyOf(navn, nydimensjon);
snavn = Arrays.copyOf(snavn, nydimensjon);
indeks = Arrays.copyOf(indeks, nydimensjon);
byte[][] gammelgraf = graf;
graf = new byte[nydimensjon][nydimensjon];
for (int i = 0; i < antall; i++)
{
System.arraycopy(gammelgraf[i], 0, graf[i], 0, antall);
Arrays.fill(graf[i], antall, nydimensjon, IKKE_KANT);
}
for (int i = antall; i < nydimensjon; i++)
{
Arrays.fill(graf[i], IKKE_KANT);
}
}
public boolean leggInnNode(String nodenavn)
{
if (navn == null || nodenavn.length() == 0)
throw new IllegalArgumentException("Noden må ha et navn!");
int rad = finn(nodenavn);
if (rad >= 0) return false;
if (antall >= graf.length) utvid();
rad = -(rad + 1);
for (int i = antall; i > rad; i--)
{
snavn[i] = snavn[i - 1];
indeks[i] = indeks[i - 1];
}
snavn[rad] = nodenavn;
navn[antall] = nodenavn;
indeks[rad] = antall;
antall++;
return true;
}
public void leggInnKant(String franode, String tilnode, int vekt)
{
if (franode.equals(tilnode)) throw
new IllegalArgumentException(franode + " er lik " + tilnode + "!");
int i = finn(franode);
if (i < 0) throw new NoSuchElementException(franode + " er ukjent!");
i = indeks[i];
int j = finn(tilnode);
if (j < 0) throw new NoSuchElementException(tilnode + " er ukjent!");
j = indeks[j];
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;
}
public String kanterFra(String node)
{
int i = finn(node);
if (i < 0) return null;
i = indeks[i];
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()
{
return antall;
}
public int dimensjon()
{
return graf.length;
}
public String[] nodenavn()
{
return Arrays.copyOf(snavn, antall);
}
private int finn(String nodenavn)
{
return Arrays.binarySearch(snavn, 0, antall, nodenavn);
}
public boolean nodeFinnes(String nodenavn)
{
return finn(nodenavn) >= 0;
}
}