package com.mmnaseri.cs.skiena.ch04.s8.impl;

import com.mmnaseri.cs.qa.annotation.Quality;
import com.mmnaseri.cs.qa.annotation.Stage;
import com.mmnaseri.cs.skiena.ch04.s8.Merger;

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

/**
 * @author Milad Naseri (milad.naseri@cdk.com)
 * @since 1.0 (11/17/16, 3:27 PM)
 */
@Quality(Stage.TESTED)
public class NaiveMerger<E> implements Merger<E> {

    private final Comparator<E> comparator;

    public NaiveMerger(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    @SafeVarargs
    @Override
    public final List<E> merge(List<E>... lists) {
        int done = 0;
        final List<E> result = new ArrayList<>();
        while (done < lists.length) {
            int which = -1;
            for (int i = 0; i < lists.length; i++) {
                final List<E> list = lists[i];
                if (!list.isEmpty() && (which == -1 || comparator.compare(lists[which].get(0), list.get(0)) > 0)) {
                    which = i;
                }
            }
            if (which >= 0) {
                result.add(lists[which].remove(0));
                if (lists[which].isEmpty()) {
                    done++;
                }
            }
        }
        return result;
    }

}

@@ -648,30 +648,8 @@
 ) %7B%0A
-        int done = 0;%0A
     
@@ -713,27 +713,12 @@
 le (
-done %3C lists.length
+true
 ) %7B%0A
@@ -1122,87 +1122,39 @@
     
-    if (lists%5Bwhich%5D.isEmpty()) %7B%0A                    done++;%0A                %7D
+%7D else %7B%0A                break;
 %0A   

simplify naive k-way merger algorithm