import java.util.concurrent.CountDownLatch;

public class Main {
    public static void main(String[] args) {
        Monitor monitor = new Monitor();
        String[] ordene = lesInnStringArray("mangeord.txt");
        CountDownLatch barriere = new CountDownLatch(39);
        for (int i = 0; i < 39; i++) {
            new Sorter().start();
        }
        barriere.await();
        LenkeListe<String> sortertLenkeliste = monitor.hentSortertListe();
        //hent sortert lenkeliste
    }
    public class LenkeListe<T extends Comparable<T>>{
        private ListeHode lHode; // listehodet
        private ListeHale lHale; // listehalen
        private int antall; // antall objekter i lista
        LenkeListe() {
            antall = 0;
            lHode = new ListeHode(null);
            lHale = new ListeHale(null, lHode);
            lHode.neste = lHale;
    
        }
    
        private interface Elem {
            int compareTo (Elem k) ;
            void settInnOrdnet (Elem k);
        }
    
        private abstract class AbstrNode {
            T obj ;
            AbstrNode neste;
            AbstrNode(T t) {
                obj = t;
                neste = null;
            }
            abstract int compareTo (AbstrNode k);
            abstract void settInnOrdnet (AbstrNode k);
        }
    
        private class ListeHode extends AbstrNode { 
            ListeHode(T t){
                super(t);
            }
            int compareTo(AbstrNode node) {
                return -9;
            }
            void settInnOrdnet (AbstrNode ny) {
                if (neste.compareTo(ny) >= 0) {
                    ny.neste = neste;
                    neste = ny;
                    if (ny.neste == lHale) {
                        lHale.forrige = ny;
                    }
                    antall++;
                }
                else {
                    neste.settInnOrdnet(ny);
                }
            }
        }
    
        private class ListeHale extends AbstrNode { 
            AbstrNode forrige;
            ListeHale(T t, AbstrNode lhode){
                super(t);
                forrige = lhode;
            }
            int compareTo(AbstrNode node) {
                return 9;
            }
            void settInnOrdnet (AbstrNode k) {
                System.out.println("LISTEHALE");
            }
        }
    
        private class Node extends AbstrNode {
            
            Node (T t) { // t peker til objekt av type Comparable<T>
                super(t);
            }
            int compareTo (AbstrNode k) {
                return obj.compareTo (k.obj);
            }
            void settInnOrdnet (AbstrNode ny) {
                if (neste.compareTo(ny) < 0) {
                    neste.settInnOrdnet(ny);
                }
                else {
                    ny.neste = neste;
                    neste = ny;
                    if (ny.neste == lHale) {
                        lHale.forrige = ny;
                    }
                    antall++;
                }
            }
    
            
        }
    
        public int antall () {
            return antall;
        }
    
        // denne metoden skal ikke endres
        public void settInnOrdnet (T nyComparable){
            Node nyNode = new Node ( nyComparable ) ;
            lHode.settInnOrdnet(nyNode);
        }
    
        public void settInnBak (T nyComparable) {
            Node nyNode = new Node (nyComparable);
            lHale.forrige.neste = nyNode;
            lHale.forrige = nyNode;
            nyNode.neste = lHale;
            antall++;
        }
    
        public T taUtForan() throws Exception { 
            if (antall > 0) {
                AbstrNode ut = lHode.neste;
                lHode.neste = ut.neste;
                antall--;
                return ut.obj;
            }
            else {
                throw new Exception ("Kall p? taUtForan i tom Liste");
            }
            
            
        }
    
        public boolean tom () { 
            return antall == 0;
        }
    }
    
    
    private class Sorter extends Thread {
        Monitor monitor;
        int traadNummer;
        String[] ord;
        CountDownLatch barriere;
        int startIndeks;
        int antall;

        Sorter(int traadNummer, Monitor monitor, String[] ord, CountDownLatch barriere, int startIndeks, int antall) {
            this.monitor = monitor;
            this.traadNummer = traadNummer;
            this.ord = ord;
            this.barriere = barriere;
            this.startIndeks = startIndeks;
            this.antall = antall;
        }
        void run() {
            LenkeListe<String> sortert = new LenkeListe<>();
            for (int i = startIndeks; i < startIndeks + antall; i++) {
                sortert.settInnOrdnet(ordene[i]); //insertion
            } 
            //fletting
            LenkeListe<String> liste1 = sortert;
            LenkeListe<String> liste2 = monitor.leggInnEllerTaUt(sortert);
            while (liste2 != null) {
                sortert = flett(liste1, liste2);
                liste1 = sortert;
                liste2 = monitor.leggInnEllerTaUt(sortert);
            }
            barriere.countDown();
        }
        public LenkeListe<String> flett(LenkeListe<String> a, LenkeListe<String> b) throws Exception{
            // fletter de ordnede listene a og b sammen til ei ny ordnet liste c
            LenkeListe<String> c = new LenkeListe<String>( );
            String fraA = a.taUtForan( );
            String fraB = b.taUtForan( );
            while (fraA != null && fraB != null) {
                if (fraA.compareTo(fraB) <= 0) {
                    c.settInnBak(fraA);
                    fraA = a.taUtForan();
                }
                else {
                    c.settInnBak (fraB);
                    fraB = b.taUtForan ( );
                }
            }
            while (fraA != null) {
                c.settInnBak(fraA);
                fraA = a.taUtForan();
            }
            while (fraB != null) {
                c.settInnBak(fraB);
                fraB= b.taUtForan();
            }
            return c;
        }
    

    }
    private class Monitor() {
        LenkeListe<String> liste = null;
        synchronized LenkeListe<String> leggInnEllerTaUt (Lenkeliste<String> innListe) {
            Lenkeliste<String> utListe = null;
            if (liste == null) {
                liste = innListe;
            }
            else {
                utListe = liste;
                liste = null;
            }
            return utListe;
        }
        LenkeListe<String> hentSortertListe() {
            return liste;
        }
    }
}