Custom Comparators and Coordinate Compression

C++

C++

A C++ struct is the same as a class in C++, but all members are public by default.

Copy
#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int a, b, w;
};

/* alternatively,
class Edge {
    public:

Java

Copy
import java.util.*;

public class Sol {
	static class Edge {
		int a, b, w;
		public Edge(int _a, int _b, int _w) {
			a = _a;
			b = _b;
			w = _w;
		}

Python

Copy
class Edge:
	def __init__(self, a, b, w):
		self.a = a
		self.b = b
		self.w = w


v = []
M = 4
for i in range(M):
	a, b, w = map(int, input().split())
	v.append(Edge(a, b, w))
for e in v:
	print(e.a, e.b, e.w)

C++

What a comparator does is compare two objects as follows, based on our comparison criteria:

• If object $x$ is less than object $y$, return true
• If object $x$ is greater than or equal to object $y$, return false

Essentially, the comparator determines whether object $x$ belongs to the left of object $y$ in a sorted ordering.

In addition to returning the correct answer, comparators should also satisfy the following conditions:

• The function must be consistent with respect to reversing the order of the arguments: if $x \neq y$ and compare(x, y) is true, then compare(y, x) should be false and vice versa.
• The function must be transitive. If compare(x, y) is true and compare(y, z) is true, then compare(x, z) should also be true. If the first two compare functions both return false, the third must also return false.

Method 1 - Overloading the Less Than Operator

This is the easiest to implement. However, it only works for objects (not primitives) and it doesn't allow you to define multiple ways to compare the same type of class.

In the context of Wormhole Sort (note the use of const Edge&):

Copy
#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int a, b, w;
	bool operator<(const Edge &y) { return w < y.w; }
};

int main() {
	int M = 4;

We can also overload the operator outside of the class:

Copy
struct Edge {
	int a, b, w;
};
bool operator<(const Edge &x, const Edge &y) { return x.w < y.w; }

or within it using friend:

Copy
struct Edge {
	int a, b, w;
	friend bool operator<(const Edge &x, const Edge &y) { return x.w < y.w; }
};

Method 2 - Comparison Function

This works for both objects and primitives, and you can declare many different comparators for the same object.

Copy
#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int a, b, w;
};

bool cmp(const Edge &x, const Edge &y) { return x.w < y.w; }

int main() {

We can also use lambda expressions in C++11 or above:

Copy
sort(begin(v), end(v), [](const Edge &x, const Edge &y) { return x.w < y.w; });

Java

What a Comparator does is compare two objects as follows, based on our comparison criteria:

• If object $x$ is less than object $y$, return a negative integer.
• If object $x$ is greater than object $y$, return a positive integer.
• If object $x$ is equal to object $y$, return 0.

In addition to returning the correct number, comparators should also satisfy the following conditions:

• The function must be consistent with respect to reversing the order of the arguments: if compare(x, y) is positive, then compare(y, x) should be negative and vice versa.
• The function must be transitive. If compare(x, y) > 0 and compare(y, z) > 0, then compare(x, z) > 0. Same applies if the compare functions return negative numbers.
• Equality must be consistent. If compare(x, y) = 0, then compare(x, z) and compare(y, z) must both be positive, both negative, or both zero. Note that they don't have to be equal, they just need to have the same sign.

Java has default functions for comparing int, long, double types. The Integer.compare(), Long.compare(), and Double.compare() functions take two arguments $x$ and $y$ and compare them as described above.

There are two ways of implementing this in Java: Comparable, and Comparator. They essentially serve the same purpose, but Comparable is generally easier and shorter to code. Comparable is a function implemented within the class containing the custom object, while Comparator is its own class.

Method 1 - Comparable

We'll need to put implements Comparable<Edge> into the heading of the class. Furthermore, we'll need to implement the compareTo method. Essentially, compareTo(x) is the compare function that we described above, with the object itself as the first argument, or compare(self, x).

When using Comparable, we can just call Arrays.sort(arr) or Collections.sort(list) on the array or list as usual.

Copy
import java.util.*;

public class Sol {
	static class Edge implements Comparable<Edge> {
		int a, b, w;
		public Edge(int _a, int _b, int _w) {
			a = _a;
			b = _b;
			w = _w;
		}

Method 2 - Comparator

If instead we choose to use Comparator, we'll need to declare a second class that implements Comparator<Edge>:

Copy
import java.util.*;

public class Sol {
	static class Edge {
		int a, b, w;
		public Edge(int _a, int _b, int _w) {
			a = _a;
			b = _b;
			w = _w;
		}

When using Comparator, the syntax for using the built-in sorting function requires a second argument: Arrays.sort(arr, new Comp()), or Collections.sort(list, new Comp()).

Python

Defining Less Than Operator

Copy
class Edge:
	def __init__(self, a, b, w):
		self.a = a
		self.b = b
		self.w = w

	def __lt__(self, other):  # lt means less than
		return self.w < other.w

Key Function

This method maps an object to another comparable datatype with which to be sorted. This is the preferred method if you are only sorting something once. In this case we map edges to their weights.

Copy
class Edge:
	def __init__(self, a, b, w):
		self.a = a
		self.b = b
		self.w = w


v = []
M = 4
for i in range(M):
	a, b, w = map(int, input().split())
	v.append(Edge(a, b, w))
v.sort(key=lambda x: x.w)
for e in v:
	print(e.a, e.b, e.w)

Comparison Function

A comparison function in Python must satisfy the same properties as a comparator in Java. Note that old-style cmp functions are no longer supported, so the comparison function must be converted into a key function with cmp_to_key. Most of the time, it is better to use the key function, but in the rare case that the comparison function is not easily represented as a key function, we can use this.

Copy
from functools import cmp_to_key


class Edge:
	def __init__(self, a, b, w):
		self.a = a
		self.b = b
		self.w = w

C++

Copy
struct Edge {
	int a, b, w;
	bool operator<(const Edge &y) {
		if (w != y.w) return w < y.w;
		return a < y.a;
	}
};

Java

Copy
static class Edge implements Comparable<Edge> {
	int a, b, w;
	public Edge(int _a, int _b, int _w) {
		a = _a;
		b = _b;
		w = _w;
	}
	public int compareTo(Edge y) {
		if (w != y.w) return Integer.compare(w, y.w);
		return Integer.compare(a, y.a);
	}
}

Python

In Python, tuples have a natural order based on their elements in order. We can take advantage of this to write a comparator:

Copy
class Edge:
	def __init__(self, a, b, w):
		self.a = a
		self.b = b
		self.w = w

	def __lt__(self, other):  # lt means less than
		return (self.w, self.a) < (other.w, other.a)

This also gives an easy way to write a key function to sort in this way:

Copy
edges: list[Edge]
edges.sort(key=lambda edge: (edge.w, edge.a))

C++

Java

With Java, we can implement a comparator for arrays of arbitrary length (although this might be more confusing than creating a separate class).

Copy
import java.util.*;

public class Sol {
	static class Comp implements Comparator<int[]> {
		public int compare(int[] a, int[] b) {
			for (int i = 0; i < a.length; ++i)
				if (a[i] != b[i]) return Integer.compare(a[i], b[i]);
			return 0;
		}
	}

Python

C++

Copy
 Code Snippet: Solution code (Click to expand)

typedef pair<int, int> Point;
bool ycomp(Point p, Point q) { return p.second < q.second; }

 Code Snippet: Solution code (Click to expand)

	sort(P, P + N);
	for (int i = 0; i < N; i++) P[i].first = i + 1;
	sort(P, P + N, ycomp);
	for (int i = 0; i < N; i++) P[i].second = i + 1;

 	Code Snippet: Solution code (Click to expand)

Java

Copy
 Code Snippet: Solution code (Click to expand)

		int[] xs = new int[n];
		int[] ys = new int[n];

		Integer[] cows = new Integer[n];
		for (int j = 0; j < n; j++) {
			xs[j] = in.nextInt();
			ys[j] = in.nextInt();
			cows[j] = j;

The solution uses a lambda function as the custom comparator, which our guide didn't discuss, but it should be apparent which coordinate (x or y) that the comparator is sorting by.

C++

Copy
 Code Snippet: Solution code (Click to expand)

// finds the "compressed index" of a special index (a.k.a. its position in the
// sorted list)
int getCompressedIndex(int a) {
	return lower_bound(indices.begin(), indices.end(), a) - indices.begin();
}

 Code Snippet: Solution code (Click to expand)
	//========= COORDINATE COMPRESSION =======

Java

Copy
 Code Snippet: Solution code (Click to expand)
	// finds the "compressed index" of a special index (a.k.a. its position in
	// the sorted list)
	static int getCompressedIndex(int a) {
		return Collections.binarySearch(indices, a);
	}
 	Code Snippet: Solution code (Click to expand)
		//========= COORDINATE COMPRESSION =======
		TreeSet<Integer> temp = new TreeSet<Integer>(indices);
		// Since temp is a set, all duplicate elements are removed