Question

How to solve the problem with priority queue

fill the doIt(BufferedReader r, PrintWriter w) function

Read the input one line at a time and output the current line if and only if you have already read at least 1000 lines greater than the current line and at least 1000 lines less than the current line. (Again, greater than and less than are with respect to the ordering defined by String.compareTo().)

package comp2402a1;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Part7 {

   /**
   * Your code goes here - see Part0 for an example
   * @param r the reader to read from
   * @param w the writer to write to
   * @throws IOException
   */
   public static void doIt(BufferedReader r, PrintWriter w) throws IOException {
       // Your code goes here -
   }

   /**
   * The driver. Open a BufferedReader and a PrintWriter, either from System.in
   * and System.out or from filenames specified on the command line, then call doIt.
   * @param args
   */
   public static void main(String[] args) {
       try {
           BufferedReader r;
           PrintWriter w;
           if (args.length == 0) {
               r = new BufferedReader(new InputStreamReader(System.in));
               w = new PrintWriter(System.out);
           } else if (args.length == 1) {
               r = new BufferedReader(new FileReader(args[0]));
               w = new PrintWriter(System.out);
           } else {
               r = new BufferedReader(new FileReader(args[0]));
               w = new PrintWriter(new FileWriter(args[1]));
           }
           long start = System.nanoTime();
           doIt(r, w);
           w.flush();
           long stop = System.nanoTime();
           System.out.println("Execution time: " + 10e-9 * (stop-start));
       } catch (IOException e) {
           System.err.println(e);
           System.exit(-1);
       }
   }
}

Answer 1

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Collections;
import java.util.PriorityQueue;

public class Part7 {

    /**
     * Your code goes here - see Part0 for an example
     * @param r the reader to read from
     * @param w the writer to write to
     * @throws IOException
     */
    public static void doIt(BufferedReader r, PrintWriter w) throws IOException {
        String line;
        PriorityQueue<String> smallest = new PriorityQueue<String>(Collections.reverseOrder());
        PriorityQueue<String> largest = new PriorityQueue<String>();
        while ((line = r.readLine()) != null) {
            if (smallest.size() < 1000) {
                smallest.add(line);
                largest.add(line);
            }
            else {
                boolean write = false;
                if (line.compareTo(smallest.peek()) > 0) {
                    write = true;
                }
                if (line.compareTo(largest.peek()) < 0) {
                    write = false;
                }
                if (line.compareTo(smallest.peek()) < 0) {
                    smallest.poll();
                    smallest.add(line);
                }
                if (line.compareTo(largest.peek()) > 0) {
                    largest.poll();
                    largest.add(line);
                }
                if (write)
                    w.write(line);
            }
        }
    }

    /**
     * The driver. Open a BufferedReader and a PrintWriter, either from System.in
     * and System.out or from filenames specified on the command line, then call doIt.
     * @param args
     */
    public static void main(String[] args) {
        try {
            BufferedReader r;
            PrintWriter w;
            if (args.length == 0) {
                r = new BufferedReader(new InputStreamReader(System.in));
                w = new PrintWriter(System.out);
            } else if (args.length == 1) {
                r = new BufferedReader(new FileReader(args[0]));
                w = new PrintWriter(System.out);
            } else {
                r = new BufferedReader(new FileReader(args[0]));
                w = new PrintWriter(new FileWriter(args[1]));
            }
            long start = System.nanoTime();
            doIt(r, w);
            w.flush();
            long stop = System.nanoTime();
            System.out.println("Execution time: " + 10e-9 * (stop-start));
        } catch (IOException e) {
            System.err.println(e);
            System.exit(-1);
        }
    }
}