package com.wrox.algorithms.sorting;

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

public class MergesortListSorter implements ListSorter {
    /** Komparator wyznaczający porządek sortowanych wartości */
    private final Comparator _comparator;

    /**
     * Konstruktor 
     * Parametr: komparator wyznaczający porządek sortowanych wartości
     */
    public MergesortListSorter(Comparator comparator) {
        assert comparator != null : "nie określono komparatora";
        _comparator = comparator;
    }


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

        return mergesort(list, 0, list.size() - 1);
    }


    private List mergesort(List list, int startIndex, int endIndex) {
        if (startIndex == endIndex) {           // lista jednoelementowa
            List result = new ArrayList();
            result.add(list.get(startIndex));
            return result;
        }

        // indeks graniczny lewej połówki
        int splitIndex = startIndex + (endIndex - startIndex) / 2;

        // sortowanie lewej połówki
        List left = mergesort(list, startIndex, splitIndex);
        
        // sortowanie prawej połówki
        List right = mergesort(list, splitIndex + 1, endIndex);

        // łączenie posortowanych połówek
        return merge(left, right);
    }


    private List merge(List left, List right) {
        List result = new ArrayList();

        Iterator l = left.iterator();
        Iterator r = right.iterator();

        l.first();
        r.first();

        while (!(l.isDone() && r.isDone())) {
            if (l.isDone()) {
                result.add(r.current());
                r.next();
            } else if (r.isDone()) {
                result.add(l.current());
                l.next();
            } else if (_comparator.compare(l.current(), r.current()) <= 0) {
                result.add(l.current());
                l.next();
            } else {
                result.add(r.current());
                r.next();
            }
        }

        return result;
    }




}
