/**
* An inplace implementation of the deterministic linear time selection 
* by Blum, Floyd, Pratt, Rivest, and Tarjan (1973)
* 
* @author Gerth Stølting Brodal
*/

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class DeterministicSelection<Element extends Comparable>
{
    static Boolean LOG = true;  // print log of recursive calls
    
    /**
    * Return an element with specific rank in List A (rank = 0, 1, 2,...),
    */   
    public Element select(List<Element> A, int rank)
    {
        return select(A, rank, 0);
    }
    
    /**
    * Return an element with specific rank in List A.
    * indent = visual indentation for tracking progression printed to System.out.
    */
    private Element select(List<Element> A, int rank, int indent)
    {   
        if (LOG) log(indent, "select rank " + rank, A);
        
        Element result;
        if (A.size() <= 5) {
            if (LOG) log(indent + 1, "InsertionSort", A);
            insertionSort(A);
            if (LOG) log(indent + 1, "             ", A);
            result = A.get(rank);
        } else {   
            int groups = (A.size() + 4) / 5;
            for (int i = 0; i < groups; i++) {
                int group_begin = 5 * i;
                int group_end = Math.min(A.size(), group_begin + 5);
                if (LOG) log(indent + 1, "InsertionSort", A.subList(group_begin, group_end));
                insertionSort(A.subList(group_begin, group_end));
                if (LOG) log(indent + 1, "             ", A.subList(group_begin, group_end));
                swap(A, i, (group_begin + group_end) / 2);
            }
            if (LOG) log(indent + 1, "moved medians-of-5 to front", A);
            
            Element pivot = select(A.subList(0, groups), groups / 2, indent + 1);
            
            if (LOG) log(indent + 1, "pivot = " + pivot);
    
            //    -------------------------------------------------------------------------
            //  A |       |     < pivot  |    = pivot   |   unknown   |    > pivot |      |
            //    -------------------------------------------------------------------------
            //             ^              ^              ^             ^            ^ 
            //             begin          less           equal         larger       end
    
            int less = 0;
            int equal = 0;
            int larger = A.size();
            while (equal < larger) {
                int cmp = A.get(equal).compareTo(pivot);
                if (cmp == 0)
                    equal++;
                else if (cmp  < 0)
                    swap(A, less++, equal++);
                else
                    swap(A, equal, --larger);

            }
            
            if (LOG) log(indent + 1, "after partition", A);
            
            if (rank < less)
                result = select(A.subList(0, less), rank, indent + 1);
            else if (rank < equal)
                result = A.get(less);
            else
                result = select(A.subList(larger, A.size()), rank - larger, indent + 1);
        }
        
        if (LOG) log(indent + 1, "selected = " + result, A);
        
        return result; 
    }
    
    /**
     * Insertion-Sort list A
     */
    private void insertionSort(List<Element> A)
    {
        for (int i = 1; i < A.size(); i++)
           for (int j = i; j > 0 && A.get(j - 1).compareTo(A.get(j)) > 0; j--)
               swap(A, j - 1, j);
    }
    
    /**
     * Swap elements A[i] and A[j] in List A
     */
    private void swap(List<Element> A, int i, int j) 
    {
        Element tmp = A.get(i);
        A.set(i, A.get(j));
        A.set(j, tmp);
    }
    
    /**
     * Show message with given indentation
     */
    static public void log(int indent, String message) {
        for (int i = 0; i < indent; i++) 
            System.out.print(">  ");
        System.out.println(message);
    }  
     
    /**
     *  Show indented message followed by List A
     */
    private void log(int indent, String message, List<Element> A) {
        List<String> parts = new ArrayList<String>();
        
        for (Element e : A)
            parts.add(e.toString());
        log(indent, message + ", A = " + String.join(" ", parts));
    }
   
    /**
     * Test selection on random integers
     */
    static public void test()
    {
        log(0, "DeterministicSelection test...");
        
        Random random_generator = new Random();
        int n = 33, rank = random_generator.nextInt(n);
        ArrayList<Integer> A = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) A.add(i);
     
        Collections.shuffle(A);
        Integer result = new DeterministicSelection<Integer>().select(A, rank);
        System.out.println("Select(A, " + rank + ") = " + result);
    }
}