/**
 * @author bzibae2s
 *
 */

import java.util.Comparator;

public class FeldUtil {

//Übung 8 Aufgabe 2 Binäre Suche
    public static <T> int sucheBinaerPos(Feld<T> f, Comparable<T> o) {
        int l = 0;
        int r = f.size();
        while(l < r) {
            int m = (l + r) / 2;
            if(o.compareTo(f.get(m)) <= 0 ) {
                r = m;
            }
            else {
                l = m + 1;
            }
        }
        return l;
    }

    public static <T> int sucheBinaer(Feld<T> f, Comparable<T> o) {
        int p = sucheBinaerPos(f, o);
        return p < f.size() &&  o.compareTo(f.get(p)) == 0 ? p : -1;
        }

//Übung 9 Aufgabe 2
    //Selection Sort Method
    public static <T> void sortSelect(Feld<? extends T> feld, java.util.Comparator<? super T> comp) {
        for (int i = 0; i < feld.size() - 1; i++) {
            feld.swap(i, minPos(feld, comp, i));
        }
    }
    //Hilfsmethode minPos liefert Position wo kleines Element
    //mittels for-Schleife wie in VL
    private static <T> int minPos(Feld<? extends T> feld, Comparator<? super T> comp, int i) {
        T p = feld.get(i);
        int res = i;
        for (++i; i < feld.size(); ++i) {
            if(comp.compare(p, feld.get(i)) > 0) {
                res = i;
                p = feld.get(res);
            }
        }
        return res;
    }

    //mittels Iterator (test)
    /* private static <T> int minPos2(Feld<T> feld, Comparator<T> comp, int i) {
        T p = feld.get(i);
        int res = i;
        java.util.Iterator<T> it = feld.iterator(++i);
        while(it.hasNext()) {
            if(comp.compare(p, it.next()) > 0) {
                p = feld.get(i);
                res = i;
            }
            i++;
        }
        return res;
    }
    */
    //b) Insert Sort
    public static <T> void sortInsert(Feld<? extends T> feld, java.util.Comparator<? super T> comp) {

        for (int i = 1; i < feld.size(); ++i) {
            for (int j = i; j > 0 && comp.compare(feld.get(j-1), feld.get(j)) > 0; --j) {
                feld.swap(j-1, j);
            }
        }
    }

    //c) Bubble Sort
    public static <T> void sortBubble(Feld<? extends T> feld, java.util.Comparator<? super T> comp) {
        int p = feld.size() - 1;
        while (p > 0) {
            int r = p;
            p = 0;
            for(int i = 0; i < r; ++i) {
                if(comp.compare(feld.get(i), feld.get(i+1)) > 0) {
                    feld.swap(i, i + 1);
                    p = i;
                }
            }
        }
    }

    //Aufgabe 3a)
    //Merge Sort
    public static <T> void sortMerge(Feld<? extends T> feld, java.util.Comparator<? super T> comp) {
        sortMerge(feld, comp, 0, feld.size());
    }

    private static <T> void sortMerge(Feld<T> feld, java.util.Comparator<? super T> comp, int l, int r) {
        if(r - l <= 1) {
            return;
        }
        int m = (l + r) / 2;

        sortMerge(feld, comp, l, m);
        sortMerge(feld, comp, m, r);

        Feld<T> ff = new FeldFix<>(r-l);
        Feld<T> fc = new FeldCount<>(ff);

        int i = 0;
        int jl = l;
        int jr = m;

        while(jl < m && jr < r) {
            if(comp.compare(feld.get(jl), feld.get(jr)) <= 0) {
                fc.set(i++, feld.get(jl++));
            }
            else {
                fc.set(i++, feld.get(jr++));
            }
        }
        while(jl < m) {
            fc.set(i++, feld.get(jl++));
        }
        while(jr < r) {
            fc.set(i++, feld.get(jr++));
        }
        for(int k = 0; k < fc.size(); ++k) {
            feld.set(l+k, fc.get(k));
        }

    }

//Übung 10 Aufgabe 2
    //Quick-Sort
    public static <T> void sortQuick(Feld<T> feld, java.util.Comparator<? super T> comp, PivotPicker<T> p) {
        sortQuick(feld, comp, p, 0, feld.size());
    }

    public static <T> void sortQuick(Feld<T> feld, java.util.Comparator<? super T> comp, PivotPicker<T> p, int l, int r) {
        if(l >= r) {
            return;
        }
        PivotPickerMedian<T> pP = new PivotPickerMedian<>(comp);
        int pivot = pP.pivot(feld, l, r);
        feld.swap(pivot, r); //tausche Pivot nach rechts
        int il = l;         //Linksaussen
        int ir = r;         //Rechtsaussen
        do {
            while(il <= ir && comp.compare(feld.get(il), feld.get(r)) < 0) {
                ++il; //nach innen laufen von links
            }
            while(il < ir && comp.compare(feld.get(ir), feld.get(r)) >= 0) {
                --ir; //nach innen laufen von rechts
            }
            if(il < ir) {   //Fehlstand?
                feld.swap(il++, ir); //tausche linken mit rechtem Wert
            }
        } while(il <= --ir);
        pivot = il;     //Pivot folgt auf linken Teil
        feld.swap(pivot, r); //Pivot an richtige Position tauschen

        sortQuick(feld, comp, pP, l, pivot-1);  //linken Teil rek. sortieren
        sortQuick(feld, comp, pP, pivot+1, r);  //rechten Teil rek. sortieren


    }


}