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

public class Autovermietung {

    private List<Auto> autos;

    public Autovermietung() {
        this.autos = new ArrayList<Auto>();
    }

    public List<Auto> getAutos() {
        return this.autos;
    }

    public void setAutos(List<Auto> autos) {
        this.autos = autos;
    }

    public void addAuto(Auto auto) {
        autos.add(auto);
    }

    public List<Auto> filtern(String typ, int maxKm) {
        List<Auto> result = new ArrayList<>();
        for (Auto a : autos) {
            if (a.getTyp().equals(typ) && a.getKilometer() < maxKm) {
                result.add(a);
            }
        }
        return result;
    }

    public static List<Auto> mergesort(List<Auto> autos) {
        if (autos.size() > 1) {
            List<Auto>[] teillisten = split(autos);
            List<Auto> a1 = mergesort(teillisten[0]);
            List<Auto> a2 = mergesort(teillisten[1]);
            return merge(a1, a2);
        }
        return autos;
    }

    public static List<Auto>[] split(List<Auto> autos) {
        List<Auto>[] result = new ArrayList[2];
        result[0] = new ArrayList<Auto>(autos.subList(0, (autos.size() + 1) / 2));
        result[1] = new ArrayList<Auto>(autos.subList(result[0].size(), autos.size()));
        return result;
    }

    public static List<Auto> merge(List<Auto> a1, List<Auto> a2) {
        List<Auto> result = new ArrayList<>();
        while ((a1.size() + a2.size()) > 0) {
            if (a1.size() != 0 && (a2.size() == 0 || a1.get(0).getKilometer() < a2.get(0).getKilometer())) {
                result.add(a1.remove(0));
            } else if (a1.size() == 0 || a1.get(0).getKilometer() >= a2.get(0).getKilometer()) {
                result.add(a2.remove(0));
            }
        }
        return result;
    }
}