how to sort my array of Custom Point class?

I am working on an algorithm that has to identify all pairs of 4 or more co-linear points and form the line segments between them without repetition.

I am using a Point class to represent a point(x,y). It looks like this:

public class Point

{
private final int x; // x-coordinate
private final int y; // y-coordinate
.
...
.....
......
}


I have an array of Point class entities from which I have to identify whether the array has duplicate points(same points repeated more than once). I know there are so many ways like nesting for loops of depth 2.

But I am interested in the sorting of that array in such a way that all the equal points should come first followed by unequal points in ascending order. Is it possible using the Comparator interface?

Comparator

1 Answer
1

As mentioned by JB Nizet, you can not use a sorting algorithm in order to group all identical items at the beginning of a sorted Data Structure and have a sorted ordering of the remaining unique items at the end of the Data Structure.

Sorting allows you to use a grading method (compareTo) in order to decide, given 2 items, which one appear before the other in the resulting sorted Data Structure. But this works only for a single group of sorted elements. The Comparable interface explains this in detail.

compareTo

Your problem handles 2 groups of elements and therefore requires special treatment.

As for a practical solution to your problem, consider the following possible solution:

import java.util.*;

import java.lang.*;
import java.util.stream.*;

public class MyClass {

private static class Point implements Comparable<Point>{
public int x;
public int y;
public Point (int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {

if (o == this) return true;
if (!(o instanceof Point)) {
return false;
}

Point point = (Point) o;

return point.x == this.x &&
point.y == this.y;
}
@Override
public int hashCode() {
int result = 17;
result = 31 * result + x;
result = 31 * result + y;
return result;
}
@Override
public int compareTo(Point other) {
int xCompare = Integer.compare(this.x,other.x);
if(xCompare == 0) {
return Integer.compare(this.y,other.y);
}
else {
return xCompare;
}
}
@Override
public String toString() {
return "(x = " + x + ", y = " + y + ")";
}

}
public static void main(String args) {
Point points = { new Point(1,1), new Point(2,2), new Point(0,1), new Point(2,1),
new Point(5,5), new Point(1,1), new Point (1,3), new Point(2,2)};
System.out.println("Points " + Arrays.toString(points));
List<Point> pntList = customSort(points);
System.out.println("Points " + pntList);
}


private static List<Point> customSort(Point pointArr) {
// start by sorting the array
Arrays.sort(pointArr);
// create an occurences map
Map<Point,Integer> occurences = new HashMap<>();
Arrays.stream(pointArr).forEach(point -> {
occurences.put(point, occurences.getOrDefault(point,0) + 1);
});
// get 2 point lists - the first for matching items
// (will have more then 1 occurence in the map), the second of unique value items
Map<Boolean, List<Point>> groups = Arrays.stream(pointArr).collect(
Collectors.partitioningBy(p -> occurences.get(p) == 1));
// first concat the list of all points with 2 or more occurences (duplicates), then concat all the unique occurences
List<Point> customSortedPoints = new ArrayList<>(groups.get(Boolean.FALSE));
customSortedPoints.addAll(groups.get(Boolean.TRUE));
return customSortedPoints;
}
}


And the output is:

Points [(x = 1, y = 1), (x = 2, y = 2), (x = 0, y = 1), (x = 2, y = 1), (x = 5, y = 5), (x = 1, y = 1), (x = 1, y = 3), (x = 2, y = 2)] ---> Unsorted
Points [(x = 1, y = 1), (x = 1, y = 1), (x = 2, y = 2), (x = 2, y = 2), (x = 0, y = 1), (x = 1, y = 3), (x = 2, y = 1), (x = 5, y = 5)] ---> Sorted


Update:

I have updated the sorting algorithm by introducing a uniqueness attribute to the Point class. This requires an O(n) processing iteration on the point array (in order to determine the number of occurrences of each point and set the uniqueness attribute). Once the point uniqueness is set, the compare method can sort the array in place with the desired ordering. Please note that this implementation uses additional Java APIs, but can be implemented without the Arrays and Map classes (and I will do so if requested):

private static class Point implements Comparable<Point>{
// ...
public boolean isUnique;
// ...
// ...
@Override
public int compareTo(Point other) {
if(this.isUnique == other.isUnique) {
int xCompare = Integer.compare(this.x,other.x);
if(xCompare == 0) {
return Integer.compare(this.y,other.y);
}
else {
return xCompare;
}
}
// a non-unique point will always be sorted before a unique point
else {
return this.isUnique ? 1 : -1;
}
}
// ...
}

public static void main(String args) {
Point points = { new Point(1,1), new Point(2,2), new Point(0,1), new Point(2,1),
new Point(5,5), new Point(1,1), new Point (1,3), new Point(2,2)};
System.out.println("Points " + Arrays.toString(points));
customSort(points);
System.out.println("Points " + Arrays.toString(points));
}


private static void customSort(Point pointArr) {
// create an occurences map
Map<Point,Integer> occurences = new HashMap<>();
Arrays.stream(pointArr).forEach(point -> {
occurences.put(point, occurences.getOrDefault(point,0) + 1);
});
// iterate on occurences map in order to update the uniqueness of each point
Arrays.stream(pointArr).forEach(point -> {
point.isUnique = (occurences.get(point) == 1);
});
// sort the array after updating the uniqueness
Arrays.sort(pointArr);

}


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.