// Dobbellenket liste med en peker til f?rste node

import java.util.Iterator;

public class SparegrisGenerisk<E extends Comparable<E>> implements Iterable<E> {
    private int antall = 0;
    private Seddel foerst = null;

    // Privat node-klasse som kun kan opprettes objekter av i skopet til sparegris
    private class Seddel implements Comparable<Seddel> {
        Seddel neste, forrige = null;
        private E verdi;

        public Seddel(E verdi) {
            this.verdi = verdi;
        }

        public E hentVerdi() {
            return verdi;
        }

        @Override
        public int compareTo(Seddel o) {
            return hentVerdi().compareTo(o.hentVerdi());    
        } 
    }

    public E finnSt?rst() {
        Seddel st?rst = foerst;
        Seddel peker = foerst;

        while (peker != null) {
            if (st?rst.compareTo(peker) < 0) {
                st?rst = peker;
            }
            peker = peker.neste;
        }
        return st?rst.hentVerdi();
    }

    private class SparegrisIterator implements Iterator<E> {
        Seddel peker = foerst;

        @Override
        public boolean hasNext() {
            return peker != null;
        }

        @Override
        public E next() {
            E verdi = peker.hentVerdi();
            peker = peker.neste;
            return verdi;
        }
    }

    // Metode som returnerer et objekt av SparegrisIterator klassen
    @Override
    public Iterator<E> iterator() {
        return new SparegrisIterator();
    }

    public void leggTilFoerst(E verdi) {
        Seddel ny = new Seddel(verdi);

        // Invariant: Dersom sparegrisen er tom
        if (antall == 0) {
            foerst = ny;
            antall++;
            return;
        }

        // Invariant: Hvis sparegrisen ikke er tom
        foerst.forrige = ny;
        ny.neste = foerst;
        foerst = ny;

        antall++;
    }

    public void leggTilSist(E verdi) {
        Seddel ny = new Seddel(verdi);

        // Invariant: Dersom sparegrisen er tom
        if (antall == 0) {
            foerst = ny;
            antall++;
            return;
        }

        // Invariant: Sparegrisen er ikke tom
        Seddel peker = foerst; // Peker er for ? navigere gjennom sparegrisen

        while (peker.neste != null) {
            peker = peker.neste;
        }

        // N? vet vi at peker peker p? siste seddel-objekt i sparegrisen

        peker.neste = ny;
        ny.forrige = peker;

        antall++;
    }

    public E fjernFoerst() {
        // Invariant: Sparegris er tom
        if (antall == 0) {
            System.out.println("Ingen sedler, skjerp deg");
            return null;
        }

        // Invariant: sparegrisen har ett element
        if (antall == 1) {
            E verdi = foerst.hentVerdi();
            foerst = null;
            antall--;
            return verdi;
        }

        // Invariant: Sparegrisen har mer enn 1 element

        E verdi = foerst.hentVerdi();
        foerst = foerst.neste;
        foerst.forrige = null;
        antall--;
        return verdi;
    }

    public E fjernSiste() {
        // Invariant: Sparegris er tom
        if (antall == 0) {
            System.out.println("Ingen sedler, skjerp deg");
            return null;
        }

        // Invariant: sparegrisen har ett element
        if (antall == 1) {
            E verdi = foerst.hentVerdi();
            foerst = null;
            antall--;
            return verdi;
        }

        // Invariant: Ellers

        Seddel peker = foerst;

        while (peker.neste != null) {
            peker = peker.neste;
        }

        E verdi = peker.hentVerdi();
        peker.forrige.neste = null;
        antall--;
        return verdi;
    }

    // HOMEWORK: Pr?v ? implementere metoder hentFoerst() og hentSist()

    // Jeg vil at tostring skal returnere summen i sparegrisen som en streng
    @Override
    public String toString() {
        Seddel peker = foerst;
        String sum = "";

        while (peker != null) {
            sum += peker.hentVerdi();
            peker = peker.neste;
        }
        return "Sum: " + sum;
    }
}