package com.wrox.algorithms.bsearch;

import com.wrox.algorithms.lists.List;
import com.wrox.algorithms.sorting.Comparator;

public class RecursiveBinaryListSearcher implements ListSearcher {
    /** Komparator wyznaczający porządek elementów listy */
    private final Comparator _comparator;

    /**
     * Konstruktor.
     * Parametr: komparator wyznaczający porządek elementów listy
     */
    public RecursiveBinaryListSearcher(Comparator comparator) {
        assert comparator != null : "nie określono komparatora";
        _comparator = comparator;
    }


    private int searchRecursively(List list, Object key, 
                                  int lowerIndex, int upperIndex) {
        assert list != null : "nie określono listy";

        if (lowerIndex > upperIndex) {
            return -(lowerIndex + 1);
        }

        int index = lowerIndex + (upperIndex - lowerIndex) / 2;

        int cmp = _comparator.compare(key, list.get(index));

        if (cmp < 0) {
            index = searchRecursively (list, key, lowerIndex, index - 1);
        } else if (cmp > 0) {
            index = searchRecursively (list, key, index + 1, upperIndex);
        }

        return index;
    }

    public int search(List list, Object value) {
        assert list != null : "nie określono listy";

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


}