////////////////// class HeapPrioritetsKø //////////////////////////////

package hjelpeklasser;

import java.util.*;

public class HeapPrioritetsKø<T> implements PrioritetsKø<T>
{
  private T[] heap;                          // heaptabellen
  private int antall;                        // antall verdier i køen
  private Comparator<? super T> comp;        // for sammenligninger

  @SuppressWarnings("unchecked")
  public HeapPrioritetsKø(int kapasitet, Comparator<? super T> c)
  {
    if (kapasitet < 0) throw new IllegalArgumentException("Negativ kapasitet!");

    heap = (T[])new Object[kapasitet + 1];   // indeks 0 brukes ikke
    antall = 0;
    comp = c;
  }

  public HeapPrioritetsKø(Comparator<? super T> c)
  {
    this(8,c);  // bruker 8 som startkapasitet
  }

  public static <T extends Comparable<? super T>>
  HeapPrioritetsKø<T> naturligOrden(int kapasitet)
  {
    // bruker en komparator for datatypens naturlige orden
    return new HeapPrioritetsKø<>(kapasitet, Comparator.naturalOrder());
  }

  public static
  <T extends Comparable<? super T>> HeapPrioritetsKø<T> naturligOrden()
  {
    return naturligOrden(8);
  }

  @Override
  public T kikk()
  {
    if (tom()) throw new NoSuchElementException("Køen er tom!");
    return heap[1];
  }

  @Override
  public void nullstill()
  {
    for (int i = 0; i <= antall; i++) heap[i] = null;
    antall = 0;
  }

  @Override
  public void leggInn(T verdi)
  {
    Objects.requireNonNull(verdi, "verdi er null!");

    // øker antaller først og "dobler" tabellen hvis den er full
    if (++antall == heap.length) heap = Arrays.copyOf(heap, 2*antall);

    int k = antall;                    // første ledige plass i tabellen
    heap[0] = verdi;                   // stoppverdi for while-løkken

    while (comp.compare(verdi, heap[k/2]) < 0)
    {
      heap[k] = heap[k/2];             // trekker verdien i heap[k/2] nedover
      k /= 2;                          // k går opp til forelderen
    }
    heap[0] = null;                    // fjerner referansen
    heap[k] = verdi;                   // verdi skal ligge i posisjon k
  }

  @Override
  public T taUt()
  {
    throw new UnsupportedOperationException("Ikke laget ennå!");
  }

  @Override
  public boolean taUt(T verdi)
  {
    throw new UnsupportedOperationException("Ikke laget ennå!");
  }

  @Override
  public int antall()
  {
    return antall;
  }

  @Override
  public boolean tom()
  {
    return antall == 0;
  }

  @Override
  public String toString()
  {
    StringBuilder s = new StringBuilder();
    s.append('[');

    if (antall > 0) s.append(heap[1]);

    for (int i = 2; i <= antall; i++)
    {
      s.append(',');
      s.append(' ');
      s.append(heap[i]);
    }

    s.append(']');

    return s.toString();
  }

}  // HeapPrioritetsKø