3
\$\begingroup\$

Challenge

Write a program which reads a file and outputs a specified number of lines, sorted on length in descending order.

Specifications

  1. The first argument is a path to a file.
  2. The file contains multiple lines.
  3. The first line indicates the number of lines to output.
  4. The following lines are of differing lengths and presented randomly.
  5. Print the specified number of lines in descending order of length.

Constraints

  1. The number in the first line is a valid positive integer.
  2. The input file is correctly formatted.

Input Sample

2
Hello World
Code Reviews
Quick Fox
A
San Francisco

Output Sample

San Francisco
Code Reviews

Source

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.NavigableMap;
import java.util.Scanner;
import java.util.TreeMap;

public class Solution {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner input = new Scanner(new File(args[0]));
        int numberOfLinesToPrint = Integer.parseInt(input.nextLine());

        NavigableMap<Integer, String> lineMap = new TreeMap<>();
        while (input.hasNextLine()) {
            addLine(lineMap, input.nextLine());
        }
        printLongestLines(lineMap, numberOfLinesToPrint);
    }

    private static void printLongestLines(NavigableMap<Integer, String> lineMap, int numberOfLinesToPrint) {
        for (int i = 0; i < numberOfLinesToPrint; i++) {
            System.out.println(lineMap.pollLastEntry().getValue());
        }
    }

    private static void addLine(NavigableMap<Integer, String> lineMap, String line) {
        lineMap.put(line.length(), line);
    }
}

I thought about implementing a data structure based on the size of the input that would sort itself right after adding an input -- if the input was a valid addition, but then I remembered TreeMap and thought why reinvent the wheel? This works, but I'm curious if I've misjudged and the alternative would've been more efficient.

\$\endgroup\$
  • 1
    \$\begingroup\$ I would expect a solution to be memory-efficient. There is no need to ever keep more than n lines in the map. Therefore the map in your solution should be cleaned up from time to time. \$\endgroup\$ – Roland Illig Jun 12 '16 at 23:05
4
\$\begingroup\$

Remember to close resources

You are opening a file with

Scanner input = new Scanner(new File(args[0]));

but you are never closing the Scanner. This can lead to resource leaks and hard to track down bugs. This is typically solved by using a try-with-resources construct:

try (Scanner input = new Scanner(new File(args[0]))) {
    // ...
}

With this change, the Scanner will be opened at the beginning of the block, and always closed, automatically, at the end. This ensures that, whatever happens in the try block (exception or not), the resource will be properly closed.

Use of methods

Your code makes use of 2 methods:

  • printLongestLines, which is responsible for printing the top-most lines read.
  • addLine, which adds a line into a map.

The first method, printLongestLines, is great: its name is descriptive and does the job it is intended to do.

However, the second is awkward: it takes as parameter a map that it will modify. Generally, modifying input parameters inside a method is a bad practice. It means that the code isn't correctly decoupled. In this case, it is because this method is actually part of a bigger responsibility: storing the lines of the file inside a map. Conceptually, you want to break down the program into meaningful methods that perform a task; the task here is reading the file.

As such, consider the following method readLines instead:

private static NavigableMap<Integer, String> readLines(Scanner input) {
    NavigableMap<Integer, String> lineMap = new TreeMap<>();
    while (input.hasNextLine()) {
        String line = input.nextLine();
        lineMap.put(line.length(), line);
    }
    return lineMap;
}

The advantage is that reading from the Scanner and populating the line map is done inside a well defined method, that the main part of the code just invokes.

Iterators

The method printLongestLines is currently using pollLastEntry() to retrieve, and remove, the last entry of the map. This is a side-effect operation: this method is modifying the input map, by removing elements from it.

It would be preferable to use an Iterator to iterate over the map. Consider the following:

private static void printLongestLines(NavigableMap<Integer, String> lineMap, int numberOfLinesToPrint) {
    Iterator<String> iterator = lineMap.descendingMap().values().iterator();
    int i = 0;
    while (i < numberOfLinesToPrint && iterator.hasNext()) {
        System.out.println(iterator.next());
        i++;
    }
}

This gets the reversed map (with descendingMap) and iterates over the values only, since we're not interested in the key. It also highlights a potential bug in your current implementation: if you were to print a number of lines greater than the size of the map, it would fail. This is handled here by checking whether the iterator has a next element.

You don't need a map

You will notice that, in the map that was built, we're only interested in the values, i.e. the lines themselves. This shows that, in fact, we do not need a map. We can directly use a SortedSet where the String are sorted by their length.

private static SortedSet<String> readLines(Scanner input) {
    SortedSet<String> set = new TreeSet<>(Comparator.comparing(String::length, Comparator.reverseOrder()));
    while (input.hasNextLine()) {
        set.add(input.nextLine());
    }
    return set;
}

This creates a set that is sorted in reverse order using a comparator comparing their length. This is using Java 8 specific code (comparing and the method reference String::length) but the same can be done with anonymous classes.

With this change, you can have a very simple printLongestLines method:

private static void printLongestLines(SortedSet<String> set, int numberOfLinesToPrint) {
    set.stream().limit(numberOfLinesToPrint).forEach(System.out::println);
}

This is using the Stream API, but you could keep the same code as before for Java <= 7, using explicitely an iterator.


As oopexpert points out in a comment, you can also directly use a List<String> to store the lines of the file. Depending on the use-case, this also would have the advantage that duplicate lines are kept. The change to do in readLines would simply be to explicitely sort the list once the lines are read, with:

List<String> lines = new ArrayList<>();
// loop over input to add each line
lines.sort(Comparator.comparing(String::length).reversed());
\$\endgroup\$
  • \$\begingroup\$ I do not recommend to use a SortedSet or a SortedMap in general. These classes are violating the liskov substitution principle (LSP). For SortedSet this is also mentioned in the documentation: "The behavior of a sorted set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface". This is not a problem as long as you never have these classes hidden behind the abstractions they violate (Map or Set). \$\endgroup\$ – oopexpert Jun 12 '16 at 22:07
  • 1
    \$\begingroup\$ Furthermore I do not recommend to use a SortedSet or a SortedMap for sorting. To keep the order "List" is the proper Collection to go with. For the rest I am totally with you. \$\endgroup\$ – oopexpert Jun 12 '16 at 22:12
  • \$\begingroup\$ @oopexpert Yes, reconsidering this, using a List might be the way to go, thanks for that comment. I edited with this information. \$\endgroup\$ – Tunaki Jun 12 '16 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.