import java.util.Iterator;

// Dobbellenket liste, med en peker til f?rste objekt

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

    private class Seddel implements Comparable<Seddel> {
        Seddel neste, forrige = null;
        private E verdi;

        public Seddel(E v) {
            verdi = v;
        }

        public E hentVerdi() {
            return verdi;
        }

        @SuppressWarnings("unchecked")
        @Override
        public int compareTo(Seddel o) {
            if (verdi instanceof Comparable) {
                Comparable c1 = (Comparable) verdi;
                Comparable c2 = (Comparable) o.verdi;
                return c1.compareTo(c2);
            }
            return 0;
        }
    }

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

        @Override
        public E next() {
            E data = it.hentVerdi();
            it = it.neste;
            return data;
        }

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

    @Override
    public Iterator<E> iterator() {
        return new SparegrisIterator();
    }

    public E finnSt?rst() {
        Seddel st?rst = foerst;
        Seddel peker = foerst;
        
        while (peker != null) {
            if (peker.compareTo(st?rst) > 0) {
                st?rst = peker;
            }
            peker = peker.neste;
        }

        return st?rst.hentVerdi();
    }

    public int hentAntall() {
        return antall;
    }

    // Legger til f?rst i lenkelista
    public void leggTilFoerst(E verdi) {
        Seddel ny = new Seddel(verdi);

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

        // Invariant: Lenkelista er ikke tom

        foerst.forrige = ny;
        ny.neste = foerst;
        foerst = ny;

        antall++;
    }

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

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

        // Invariant: Lenkelista er ikke tom
        Seddel peker = foerst;

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

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

        antall++;
    }

    public E fjernFoerst() {
        // IV: Lenkelista er tom

        if (antall == 0) {
            System.out.println("Ingen sedler");
            return null;
        }


        // IV: Lenkelista har ett element
        if (antall == 1) {
            Seddel midlertidig = foerst;
            foerst = null;
            antall--;
            return midlertidig.hentVerdi();
        }

        // IV: Ellers

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

    public E fjernSist() {

        // IV: Lenkelista er tom
        if (antall == 0) {
            System.out.println("Ingen sedler");
            return null;
        }


        // IV: Lenkelista har ett element
        if (antall == 1) {
            Seddel midlertidig = foerst;
            foerst = null;
            antall--;
            return midlertidig.hentVerdi();
        }
        
        Seddel peker = foerst;

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

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

    public E hentFoerst() {
        if (foerst != null) {
            return foerst.hentVerdi();
        }

        return null;
    }

    public E hentSist() {
        if (foerst == null) {
            return null;
        }

        if (antall == 1) {
            return foerst.hentVerdi();
        }

        Seddel peker = foerst;

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

        return peker.hentVerdi();
    }

    @Override
    public String toString() {
        Seddel peker = foerst;
        String sum = "";

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

        return "Sum: " + sum;
    }
}