/*
 * @author Ranides Atterwim {@literal <ranides@gmail.com>}
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */
package net.ranides.assira.collection.rmq;

import java.util.List;

/**
 * Interface for structures implementing RMQ (range minimum query).
 *
 * Every structure capable of solving RMQ is capable to present content as a list by definition,
 * so thats why we extend standard List.
 *
 * It is possible to store any values, not only numbers, as long, as we provide comparison function.
 *
 * Please note, that IT IS NOT searching inside sorted list of values, in such case solution would be trival:
 * first element from range would be minimal element. It is all about searching inside UNSORTED list of values.
 *
 * RMQ against unsorted list requires O(N) operations (just by searching through whole range).
 * We try to minimize this time to O(1) or O(logN).
 *
 * @param <T> type of value
 */
public interface RMQList<T> extends List<T> {

    /**
     * Find minimum value in specified range.
     *
     * @param begin begin
     * @param end end
     * @return non-null value
     */
    T find(int begin, int end);

    /**
     * Find minimum value in whole list.
     *
     * @return non-null value
     */
    T find();
    
}
