package amphis;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.TreeSet;
import java.util.Vector;

/* les M titres de Wikipedia les plus longs
 * utilisation :
 *   gzip -cd frwiki-... | java Wiki 5
 */

class Title implements Comparable<Title> {
  private String title;
  
  Title(String title) { this.title = title; }
  
  @Override
    public String toString() {
      return this.title;
    }

  @Override
  public int compareTo(Title that) {
    return this.title.length() - that.title.length(); 
  }
  
}

// 1. solution vraiment naïve : lire tout le fichier et le trier
class Wiki0 {

  public static void main(String[] args) throws IOException {
    double start = System.currentTimeMillis();
    int m = Integer.parseInt(args[0]);
    System.out.print("reading... ");
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    Vector<Title> v = new Vector<Title>();
    while (true) {
      String s = r.readLine();
      if (s == null) break;
      v.add(new Title(s));
    }
    int n = v.size();
    System.out.println(n + " titles");
    System.out.print("sorting... ");
    Collections.sort(v);
    System.out.println("done");
    for (int i = n-m; i < n; i++)
      System.out.println(v.get(i));
    System.err.println((System.currentTimeMillis() - start) / 1000 + "s");
  }
  
}

// 1. avec un tableau trié de taille M

class Wiki1 {
  
  public static void main(String[] args) throws IOException {
    double start = System.currentTimeMillis();
    int m = Integer.parseInt(args[0]);
    System.out.print("reading... ");
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    Title[] v = new Title[m];
    int n = 0, total = 0;
    while (true) {
      String s = r.readLine();
      if (s == null) break;
      total++;
      Title t = new Title(s);
      int i = n;
      while (i > 0 && v[i-1].compareTo(t) <= 0) {
        if (i < m) v[i] = v[i-1];
        i--;
      }
      if (i < m) v[i] = t;
      if (n < m) n++;
    }
    System.out.println(total + " titles");
    System.out.println("done");
    for (int i = n-1; i >= 0; i--)
      System.out.println(v[i]);
    System.err.println((System.currentTimeMillis() - start) / 1000 + "s");
  }

}

// 2. solution efficace avec une file de priorité

class Wiki2 {

  public static void main(String[] args) throws IOException {
    double start = System.currentTimeMillis();
    int m = Integer.parseInt(args[0]);
    System.out.print("reading... ");
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    PriorityQueue<Title> h = new PriorityQueue<Title>(m);
    int n = 0;
    while (true) {
      String s = r.readLine();
      if (s == null) break;
      n++;
      h.add(new Title(s));
      if (h.size() > m) h.remove();
    }
    System.out.println(n + " titles");
    while (h.size() > 0)
      System.out.println(h.remove());
    System.err.println((System.currentTimeMillis() - start) / 1000 + "s");
  }

}

// 3. solution avec un TreeSet (pour comparer)
// mais TreeSet n'admet pas de doublons => ne donne pas la bonne réponse

class Wiki3 {

 public static void main(String[] args) throws IOException {
   double start = System.currentTimeMillis();
   int m = Integer.parseInt(args[0]);
   System.out.print("reading... ");
   BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
   TreeSet<Title> h = new TreeSet<Title>();
   int n = 0;
   while (true) {
     String s = r.readLine();
     if (s == null) break;
     n++;
     h.add(new Title(s));
     if (h.size() > m) h.remove(h.first());
   }
   System.out.println(n + " titles");
   for (Title t: h)
     System.out.println(t.toString());
   System.err.println((System.currentTimeMillis() - start) / 1000 + "s");
 }

}