Skip to main content
Bounty Ended with 50 reputation awarded by mjolka
Add SRP reference, some typos
Source Link
rolfl
  • 97.5k
  • 17
  • 218
  • 418

The other observation I have is that the SortedMapSortedMap should probably have a custom comparator that sorts in reverse-height order. This is another small item, but it is more intuitive to me to have a call to heights.firstKey() rather than heights.lastKey()

The HeightTrackerHeightTracker may even be better off as a completely custom class without the SortedMapSortedMap at all. I would have to rewrite it myself to see.

Apart from these issues, the algorithm stikesstrikes me as being sound. It's not quite the same as some papers I read on the subject, but the performance time-complexity of \$O(n \log{n})\$ is in line with expectations.

I do have an issue with the multi-responsibility method though, building the skyiline and appending to the StringBuilder at the same time. For more flexibility and cleaner code, you should produce list of events from the getSkyline and only then convert those events to the String output... Single Responsibility Principle

The other observation I have is that the SortedMap should probably have a custom comparator that sorts in reverse-height order. This is another small item, but it is more intuitive to me to have a call to heights.firstKey() rather than heights.lastKey()

The HeightTracker may even be better off as a completely custom class without the SortedMap at all. I would have to rewrite it myself to see.

Apart from these issues, the algorithm stikes me as being sound. It's not quite the same as some papers I read on the subject, but the performance time-complexity of \$O(n \log{n})\$ is in line with expectations.

The other observation I have is that the SortedMap should probably have a custom comparator that sorts in reverse-height order. This is another small item, but it is more intuitive to me to have a call to heights.firstKey() rather than heights.lastKey()

The HeightTracker may even be better off as a completely custom class without the SortedMap at all. I would have to rewrite it myself to see.

Apart from these issues, the algorithm strikes me as being sound. It's not quite the same as some papers I read on the subject, but the performance time-complexity of \$O(n \log{n})\$ is in line with expectations.

I do have an issue with the multi-responsibility method though, building the skyiline and appending to the StringBuilder at the same time. For more flexibility and cleaner code, you should produce list of events from the getSkyline and only then convert those events to the String output... Single Responsibility Principle

Source Link
rolfl
  • 97.5k
  • 17
  • 218
  • 418

##Reading Points

you have the method and class:

  private static List<Point> readPoints(String line) {
    List<Point> points = new ArrayList<>();
    Scanner scanner = new Scanner(line);
    while (scanner.hasNext()) {
      int left = scanner.next();
      int height = scanner.next();
      int right = scanner.next();
      points.add(new Point(left, height, true));
      points.add(new Point(right, height, false));
    }
  }

This is to process data of the form:

(1,2,6);(9,23,22);(22,6,24);(8,14,19);(23,12,30)

The common way in Java to process input like this is to use a Matcher:

  private static final Pattern POINT_PATTERN = Pattern.compile("\\((\\d+),(\\d+),(\\d+)\\);?");

  private static List<Point> readPoints(String line) {
    List<Point> points = new ArrayList<>();
    Matcher matcher = POINT_PATTERN.matcher(line);
    while (matcher.find()) {
        int left   = Integer.parseInt(matcher.group(1));
        int height = Integer.parseInt(matcher.group(2));
        int right  = Integer.parseInt(matcher.group(3));
        points.add(new Point(left, height, true));
        points.add(new Point(right, height, false));
    }
    return points;
  }

Note that the matcher looks for three comma-separated number-groups inside explicit parenthesis, with an optional trailing semi-colon. The parenthesis around the \\d+ in the pattern makes those available as groups. The (expanded) pattern is:

\(    (\d+)   ,   (\d+)   ,   (\d+)   \)    ;?

      ^^^^^       ^^^^^       ^^^^^         ^^
      | Group 1
                  | Group 2
                              | Group 3
                                            | Optional ;

That would significantly simplify the code.


##Point

Your Point class implements Comparable. This is nice, but whenever you have a natural order implied with a class, you should also override equals() and hashCode() (the contract is that any two objects which have compareTo() return 0, should also be equals().

The 'y' variable is also a bit of a poor name, I would prefer the name 'height'. While we are naming things, I would call the 'Point' class 'Event' too.

I used some bit-shifting to pre-calculate the hashCode.

I ended up with:

private static class Event implements Comparable<Event> {

    private final boolean isStart;
    private final int x;
    private final int height;
    private final int hash;

    public Event(int x, int height, boolean isStart) {
        this.x = x;
        this.height = height;
        this.isStart = isStart;
        this.hash = ((isStart ? 1 : -1) * x) ^ (height << 16 | height >>> 16);
    }
    
    @Override
    public int hashCode() {
        return hash;
    }
    
    @Override
    public boolean equals(Object obj) {
        return obj == this || ((obj instanceof Event) && hashCode() == obj.hashCode() && compareTo((Event)obj) == 0);
    }

    @Override
    public int compareTo(Event other) {
        int result = Integer.compare(this.x, other.x);
        if (result != 0) {
            return result;
        }
        if (this.isStart == other.isStart) {
            return this.isStart ? Integer.compare(other.height, this.height) : Integer.compare(this.height, other.height);
        }
        return this.isStart ? -1 : 1;
    }
    
}

##Algorithm

It took me a while to understand the algorithm.

In general, i dislike the use of a Map<Integer,Integer> because it is ugly that you have to check for the null value before you can increment the count (the value is a Counter of sorts).

This part is something I believe should have been rewritten as a separate class. A HeightTracker class perhaps. The class could have a mutable inner class called Counter that can be incremented/decremented in place. When it decrements to 0, it auto-removes from the Map. The removal of the autoboxing may lead to performance improvements, but those will be small.

The other observation I have is that the SortedMap should probably have a custom comparator that sorts in reverse-height order. This is another small item, but it is more intuitive to me to have a call to heights.firstKey() rather than heights.lastKey()

The HeightTracker may even be better off as a completely custom class without the SortedMap at all. I would have to rewrite it myself to see.

Apart from these issues, the algorithm stikes me as being sound. It's not quite the same as some papers I read on the subject, but the performance time-complexity of \$O(n \log{n})\$ is in line with expectations.