Java records are available since JDK 16. They represent a simplified and restricted variant of a Java class and form their public API on the arguments passed to their constructor. A use case that comes immediately to mind is that of a simple data container - and Java records fit very well into that kind of situation as they come with auto-generated equals and hashCode methods that close over all arguments that the record comprises. Youre not allowed to mutate the state of a Java record. This is not a shortcoming though, but a well thought-out feature: Immutable data is easy to share, since you don't need to create defensive copies before you can pass things safely around. Java records also come with an auto-generated toString method. Last but not least: You're allowed to add your own methods to the definition of a Java record.
Java records are suitable for a variety of things. You can represent compound keys (e.g. a key for identifiying a cached item), data transfer objects or parameter value objects.
I won't bore you with simple code examples for each of these traits. Instead, we'll code a simple library for solving optimization problems and learn a thing about Java records along the way.
Defining the abstractions for optimization problems
Let's talk a bit about we're trying to do. The quality of a solution to a given optimization problem is determined by its cost. We want to either maximize or minimize that cost by running it through an optimization algorithm of our choice. Every solution defines a neighbourhood of prototypes. The solution is the basis for such a prototype, but the prototype carries information on how to change that solution in order to get to a new solution that exhibits different characteristics with possibly a better cost (again, depending on whether we want to maximize or minimize the cost). Hence, a prototype closes over the 2-tuple (solution, change information). Representing a prototype is a perfect use case for a record.
public record Prototype<T, D>(T solution, D modification) {
}
IntelliJ IDEA provides a context menu action that converts a given record to its equivalent Java class (hit ALT+ENTER on the record name and choose Convert record to class). For the sake of comparison, here is the result of the conversion.
public final class Prototype<T, D> {
private final T solution;
private final D modification;
public Prototype(T solution, D modification) {
this.solution = solution;
this.modification = modification;
}
public T solution() {
return solution;
}
public D modification() {
return modification;
}
@Override
public boolean equals(Object obj) {
if (obj == this) return true;
if (obj == null || obj.getClass() != this.getClass()) return false;
var that = (Prototype) obj;
return Objects.equals(this.solution, that.solution) &&
Objects.equals(this.modification, that.modification);
}
@Override
public int hashCode() {
return Objects.hash(solution, modification);
}
@Override
public String toString() {
return "Prototype[" +
"solution=" + solution + ", " +
"modification=" + modification + ']';
}
}
It is obvious that records provide a great way to minimize the amount of code you have to write if all you need is a simply data holder.
With the Prototype<T, D> record in place, we're now able to represent a neighbourhood of such prototypes. What we'll want to do here is to compute neighbours lazily as the optimization algorithm moves through the neighbourhood. We'll make use of the Java Streams API for that.
public interface Neighbourhood<T, D> {
Stream<Prototype<T, D>> neighbours();
}
A solution must be able to compute its costs and reach new states (new solutions) by applying changes. A neighbourhood can only be constructed for a given solution. We'll express that dependency by extending from the Neighbourhood<T, D> interface.
public interface Solution<T, D> extends Neighbourhood<T, D> {
double costs();
Solution<T, D> apply(D modification);
}
Implementing optimization algorithms
With these few classes in place, we're already able to implement optimization algorithms that work through a given problem in a generic way. What's common to all these algorithms is that they need to run off some initial state. That initial state is a valid solution, but most likely an unfavourable one due to high costs. After the algorithm is done working on the problem, it should return a solution of the same type, but - hopefully, this is a heuristic after all - with better costs. The public API of an algorithm can thus be expressed with the following interface.
public interface Algorithm<T, D> {
Solution<T, D> solve(Solution<T, D> initialState);
}
A local search is a very simple technique to work on a given optimization problem. It is easy to implement, but has the caveat that it is likely to run into a local optimum. But for the sake of this article, it'll do just fine. The idea is to walk through the neighbourhood of a given solution, construct prototypes as we move along and compute their costs. The prototype that with the lowest costs compared to all others and the solution that it is based off becomes the new solution. This process is repeated until there are no new prototypes that offer better costs than the previous solution.
public class LocalSearch<T, D> implements Algorithm<T, D> {
@Override
public Solution<T, D> solve(Solution<T, D> initialState) {
var solution = initialState;
var foundBetter = true;
var costs = solution.costs();
while (foundBetter) {
final var s = solution;
final var c = costs;
final Optional<Solution<T, D>> nextSolution = solution
.neighbours()
.map(prototype -> s.apply(prototype.modification()))
.map(candidate -> new Tuple<>(candidate, candidate.costs()))
.dropWhile(t -> t.r() >= c)
.map(Tuple::l)
.findFirst();
if (nextSolution.isPresent()) {
solution = nextSolution.get();
costs = nextSolution.get().costs();
} else {
foundBetter = false;
}
}
return solution;
}
}
Solving the Travelling Salesperson Problem
For those of you that are unfamiliar with the Travelling Salesperson Problem (TSP), please have a look at the excellent article on Wikipedia about it. I'll cite a brief section of its introduction here.
The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"
It should be clear that we can model this problem using a set of vertices that are connected using edges in such a way that the resulting graph forms a tour, meaning that each vertex has a single inbound and a single outbound edge and every vertex is connected. The orientation of the edges doesn't matter though.
A Vertex is simply a data holder over a pair of coordinates, but it needs to be identifiable as well. This is not a particular common case for Java records, as the identity of a record comprises all of its attributes. But nonetheless, we're able to override the equals and hashCode contract of that particular record and still get all the other benefits that Java records have to offer.
public record Vertex(int id, int x, int y) {
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Vertex vertex = (Vertex) o;
return Objects.equals(id, vertex.id);
}
@Override
public int hashCode() {
return Objects.hash(id);
}
}
An Edge connects two of such Vertex. It needs to be able to compute the distance between those two vertices and answer the question whether two given edges are disjoint. This is important for constructing the neighbourhood of solution, but we'll get to that in a minute. As I've mentioned, an edge has no orientation in our case, so we're essentially working on an undirected graph. This affects our equals and hashCode contract as well, since Edge(head, tail) would lead be treated not the same as Edge(tail, head) otherwise.
Please note that we're allowed to extend a Java record by adding methods to its definition. Hence, we can simply write out the methods for computing the distance the edge covers as well as the disjointness check.
/* imports for Math.abs, Math.pow, Math.sqrt omitted for brevity */
public record Edge(Vertex head, Vertex tail) {
public double distance() {
return sqrt(abs(pow(head.x() - tail.x(), 2)) + abs(pow(head.y() - tail.y(), 2)));
}
public boolean isDisjoint(Edge o) {
return head.id() != o.head.id() &&
head.id() != o.tail.id() &&
tail.id() != o.head.id() &&
tail.id() != o.tail.id();
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Edge edge = (Edge) o;
return (Objects.equals(head, edge.head) && Objects.equals(tail, edge.tail)) ||
(Objects.equals(head, edge.tail) && Objects.equals(tail, edge.head));
}
@Override
public int hashCode() {
return Objects.hash(head, tail) + Objects.hash(tail, head);
}
}
We progress through the neighbourhood of a given solution to the TSP using a method called 2-OPT. The idea behind 2-OPT is that we take each disjoint pair of edges and swap them. This yields a new solution with slightly altered connections and possibly better costs. Computing the costs of a given TSP is quite easy: We'll simply iterate over all edges and sum up their individual distances. Thus, a lower cost represents a better solution. Applying a 2-OPT modification is simply done by swaping heads and tails of the original edges and swapping the resulting edges for the old ones.
A Java record is allowed to implement an interface. In our case, we'll implement Solution<TSP, TwoOpt> for the TSP record.
public record TSP(List<Edge> edges) implements Solution<TSP, TwoOpt> {
@Override
public double costs() {
return edges.stream().map(Edge::distance).reduce(0.0, Double::sum);
}
@Override
public Stream<Prototype<TSP, TwoOpt>> neighbours() {
List<Tuple<Edge, Edge>> combinations = new ArrayList<>();
for (Edge l : edges) {
for (Edge r : edges) {
if (l.isDisjoint(r)) {
combinations.add(new Tuple<>(l, r));
}
}
}
return combinations
.stream()
.map(t -> new TwoOpt(t.l(), t.r()))
.distinct()
.map(t -> new Prototype<>(this, t));
}
@Override
public Solution<TSP, TwoOpt> apply(TwoOpt modification) {
Edge l = modification.l();
Edge r = modification.r();
Edge ll = new Edge(l.head(), r.head());
Edge rr = new Edge(l.tail(), r.tail());
return new TSP(Stream.concat(Stream.of(ll, rr), edges.stream()
.filter(e -> !e.equals(l))
.filter(e -> !e.equals(r)))
.collect(Collectors.toList());
}
}
What's missing now is a short piece of code that demonstrates that all of this works as expected. For that purpose, we'll randomize a couple of vertices, construct a tour for these vertices and use this as an initial solution to our algorithm. Running the original solution through the local search algorithm we just implemented should return a new solution that is better in terms of its costs.
public class Demonstrator {
public static void main(String[] args) {
var initialState = randomSolution();
var solution = localSearch.solve(initialState);
System.out.println("Original costs: " + initialState.costs());
System.out.println("Costs : " + solution.costs());
}
private static TSP randomSolution() {
List<Vertex> vertices = new ArrayList<>();
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < 50; i++) {
vertices.add(randomVertex(i));
}
for (int i = 0; i < 50; i++) {
edges.add(new Edge(vertices.get(i), vertices.get((i + 1) % 50)));
}
return new TSP(edges);
}
private static Vertex randomVertex(int id) {
int x = (int) (Math.random() * 100);
int y = (int) (Math.random() * 100);
return new Vertex(id, x, y);
}
}
Running this piece of code should print out something along the lines of
Original costs: 3074.382132611025
Costs : 398.6492705992807
to the console. It seems that we're done!
Summary
Java records are great way to reduce boilerplate code. They are a good match for typical data holders, but can be extended by implementing custom methods or overriding parts of their traits as we've seen in this article. The latter is mostly for the sake of demonstration though and should not be overdone. If you feel the need to modify the traits of a Java record, your best bet is probably to use a Java class instead.
