package com.wrox.algorithms.sorting;

import com.wrox.algorithms.lists.List;
import com.wrox.algorithms.lists.LinkedList;
import com.wrox.algorithms.iteration.Iterator;

public class InsertionSortListSorter implements ListSorter {
    private final Comparator _comparator;

   /**
     * Konstruktor
     * parametr: komparator określający uporządkowanie elementów
     */

    public InsertionSortListSorter(Comparator comparator) {
        assert comparator != null : "nie określono komparatora";
        _comparator = comparator;
    }



   public List sort(List list) {
        assert list != null : "nie określono listy";

        final List result = new LinkedList();

        sort(list, result);

        return result;
    }

    void sort(List list, final List result) {
        assert list != null : "nie określono listy źródłowej";
        assert result != null : "nie określono listy docelowej";

        Iterator it = list.iterator();

        for (it.first(); !it.isDone(); it.next()) {
            int slot = result.size();
            while (slot > 0) {
                if (_comparator.compare(it.current(), result.get(slot - 1)) >= 0) {
                    break;
                }
                --slot;
            }
            result.insert(slot, it.current());
        }
    }



}
