package com.ogerardin.xpman.util;

import lombok.experimental.UtilityClass;

import java.util.Comparator;
import java.util.List;

@UtilityClass
public class Sort {

    public <X> void insertionSort(List<X> list, Comparator<X> comparator) {
        for (int i = 1; i < list.size(); i++) {
            X current = list.get(i);
            int j = i - 1;
            while (j >= 0 && (comparator.compare(list.get(j), current) > 0)) {
                list.set(j + 1, list.get(j));
                j--;
            }
            list.set(j + 1, current);
        }
    }

    public <X> void selectionSort(List<X> arr, Comparator<X> comparator) {
        for (int i = 0; i < arr.size() - 1; i++) {
            int minElementIndex = i;
            for (int j = i + 1; j < arr.size(); j++) {
                if (comparator.compare(arr.get(minElementIndex), arr.get(j)) > 0) {
                    minElementIndex = j;
                }
            }
            if (minElementIndex != i) {
                X temp = arr.get(i);
                arr.set(i, arr.get(minElementIndex));
                arr.set(minElementIndex, temp);
            }
        }
    }

    public <X> void cycleSort(List<X> arr, Comparator<X> comparator) {
        cycleSort(arr, comparator, arr.size());
    }

    public <X> void cycleSort(List<X> arr, Comparator<X> comparator, int n)
    {
        // count number of memory writes
        int writes = 0;

        // traverse array elements and put it to on
        // the right place
        for (int cycle_start = 0; cycle_start <= n - 2; cycle_start++) {
            // initialize item as starting point
            X item = arr.get(cycle_start);

            // Find position where we put the item. We basically
            // count all smaller elements on right side of item.
            int pos = cycle_start;
            for (int i = cycle_start + 1; i < n; i++)
                if (comparator.compare(arr.get(i), item) <0)
                    pos++;

            // If item is already in correct position
            if (pos == cycle_start)
                continue;

            // ignore all duplicate elements
            while (comparator.compare(item, arr.get(pos)) == 0) {
                pos += 1;
            }

            // put the item to it's right position
            if (pos != cycle_start) {
                X temp = item;
                item = arr.get(pos);
                arr.set(pos,temp);
                writes++;
            }

            // Rotate rest of the cycle
            while (pos != cycle_start) {
                pos = cycle_start;

                // Find position where we put the element
                for (int i = cycle_start + 1; i < n; i++)
                    if (comparator.compare(arr.get(i), item) <0) {
                        pos += 1;
                    }

                // ignore all duplicate elements
                while (comparator.compare(item, arr.get(pos)) == 0) {
                    pos += 1;
                }

                // put the item to it's right position
                if (comparator.compare(item, arr.get(pos)) != 0) {
                    X temp = item;
                    item = arr.get(pos);
                    arr.set(pos, temp);
                    writes++;
                }
            }
        }
    }

}