package com.allendowney.thinkdast;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * Zapewnia implementację algorytmów sortowania.
 *
 */
public class ListSorter<T> {

   /**
    * Sortuje listę, korzystając z obiektu Comparator.
    * 
    * @param list
    * @param comparator
    * @return
    */
   public void insertionSort(List<T> list, Comparator<T> comparator) {
   
      for (int i=1; i < list.size(); i++) {
         T elt_i = list.get(i);
         int j = i;
         while (j > 0) {
            T elt_j = list.get(j-1);
            if (comparator.compare(elt_i, elt_j) >= 0) {
               break;
            }
            list.set(j, elt_j);
            j--;
         }
         list.set(j, elt_i);
      }
   }

   /**
    * Sortuje listę, korzystając z obiektu Comparator.
    * 
    * @param list
    * @param comparator
    * @return
    */
   public void mergeSortInPlace(List<T> list, Comparator<T> comparator) {
      List<T> sorted = mergeSort(list, comparator);
      list.clear();
      list.addAll(sorted);
   }

   /**
    * Sortuje listę, korzystając z obiektu Comparator.
    * 
    * Zwraca listę, która może być nowa.
    * 
    * @param list
    * @param comparator
    * @return
    */
   public List<T> mergeSort(List<T> list, Comparator<T> comparator) {
      int size = list.size();
      if (size <= 1) {
         return list;
      }
      // utwórz dwie listy, w każdej z nich umieszczając połowę elementów.
      List<T> first = mergeSort(new LinkedList<T>(list.subList(0, size/2)), comparator);
      List<T> second = mergeSort(new LinkedList<T>(list.subList(size/2, size)), comparator);
      
      return merge(first, second, comparator);
   }

   /**
    * Scala dwie posortowane listy w jedną posortowaną listę.
    * 
    * @param first
    * @param second
    * @param comparator
    * @return
    */
   private List<T> merge(List<T> first, List<T> second, Comparator<T> comparator) {
      // UWAGA: zastosowanie obiektu LinkedList ma znaczenie, ponieważ musimy 
      // usuwać elementy z początku kolekcji w czasie stałym
      List<T> result = new LinkedList<T>();
      int total = first.size() + second.size();
      for (int i=0; i<total; i++) {
         List<T> winner = pickWinner(first, second, comparator);
         result.add(winner.remove(0));
      }
      return result;
   }

   /**
    * Zwraca listę z najmniejszym elementem na pierwszym miejscu, zgodnie z zasadą stosowaną przez 'comparator'.
    * 
    * Jeśli któraś lista jest pusta, 'pickWinner' zwraca tę drugą.
    * 
    * @param first
    * @param second
    * @param comparator
    * @return
    */
   private List<T> pickWinner(List<T> first, List<T> second, Comparator<T> comparator) {
      if (first.size() == 0) {
         return second;
      }
      if (second.size() == 0) {
         return first;
      }
      int res = comparator.compare(first.get(0), second.get(0));
      if (res < 0) {
         return first;
      }
      if (res > 0) {
         return second;
      }
      return first;
   }

   /**
    * Sortuje listę, korzystając z obiektu Comparator.
    * 
    * @param list
    * @param comparator
    * @return
    */
   public void heapSort(List<T> list, Comparator<T> comparator) {
      PriorityQueue<T> heap = new PriorityQueue<T>(list.size(), comparator);
      heap.addAll(list);
      list.clear();
      while (!heap.isEmpty()) {
         list.add(heap.poll());
      }
   }

   
   /**
    * Zwraca 'k' największych elementów w kolekcji 'list' uporządkowanych rosnąco.
    * 
    * @param k
    * @param list
    * @param comparator
    * @return 
    * @return
    */
   public List<T> topK(int k, List<T> list, Comparator<T> comparator) {
      PriorityQueue<T> heap = new PriorityQueue<T>(list.size(), comparator);
      for (T element: list) {
         if (heap.size() < k) {
            heap.offer(element);
            continue;
         }
         int cmp = comparator.compare(element, heap.peek());
         if (cmp > 0) {
            heap.poll();
            heap.offer(element);
         }
      }
      List<T> res = new ArrayList<T>();
      while (!heap.isEmpty()) {
         res.add(heap.poll());
      }
      return res;
   }

   
   /**
    * @param args
    */
   public static void main(String[] args) {
      List<Integer> list = new ArrayList<Integer>(Arrays.asList(3, 5, 1, 4, 2));
      
      Comparator<Integer> comparator = new Comparator<Integer>() {
         @Override
         public int compare(Integer elt1, Integer elt2) {
            return elt1.compareTo(elt2);
         }
      };
      
      ListSorter<Integer> sorter = new ListSorter<Integer>();
      sorter.insertionSort(list, comparator);
      System.out.println(list);

      list = new ArrayList<Integer>(Arrays.asList(3, 5, 1, 4, 2));
      sorter.mergeSortInPlace(list, comparator);
      System.out.println(list);

      list = new ArrayList<Integer>(Arrays.asList(3, 5, 1, 4, 2));
      sorter.heapSort(list, comparator);
      System.out.println(list);
   
      list = new ArrayList<Integer>(Arrays.asList(6, 3, 5, 8, 1, 4, 2, 7));
      List<Integer> queue = sorter.topK(4, list, comparator);
      System.out.println(queue);
   }
}