////////////////// class MGraf //////////////////////////////

package hjelpeklasser;

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

public final class MGraf
{
  private boolean[][] graf;                    // grafmatrisen
  private int antall;                          // antall noder
  private String[] navn;                       // nodenavn - usortert
  private String[] snavn;                      // nodenavn - sortert
  private int[] indeks;                        // indekser
  private int[] forrige;                       // for senere bruk

  public MGraf(int dimensjon)                  // konstruktør
  {
    graf = new boolean[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
  }

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

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

  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);     // soretert navnetabell
    indeks = Arrays.copyOf(indeks, nydimensjon);   // indekstabell

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

    for (int i = 0; i < antall; i++)
    {
      System.arraycopy(gammelgraf[i], 0, graf[i], 0, antall);
    }
  }

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