CodeX
Published in

CodeX

Use cases for inner classes in Java

Photo by Ludovic Charlet on Unsplash

In a linked list, each node has an obvious and predictable relationship to other nodes in the list. The nodes of a linked list can be implemented as instances of a private class nested in the linked list class.

As we saw in my article about nested static classes, the nodes of a linked list don’t need to have any knowledge of the enclosing linked list class, so they can be declared as static.

Now let’s consider a more complicated data structure, like a partially calculated tree or graph, that does need to have access to the enclosing class. Each node has connections to other nodes, but the program does not try to identify all the node connections all at once.

Let’s say for example that you’re working on a family tree program. You want your program to be able to find connections between family trees, and merge them into a single tree if the connection is confirmed.

One way that could be accomplished would be by holding the separate family trees as their own separate structures but also keeping a map of each and every person that appears in any family tree.

Then an inner class for a person node would need to be able to inquire the map of all persons known by the instance of the enclosing class.

However, the family tree example is a little too complicated for the purpose of this article. So I’m going to choose something simpler: a Collatz tree, to help us make sense of a famous unsolved mathematical problem, the Collatz conjecture, or 3x + 1 problem.

The Collatz conjecture is very easy to describe, but very hard to prove or disprove. The conjecture concerns the Collatz function. Pick an integer n, any integer. If n is even, halve it; if n is odd, multiply by 3 and add 1. Repeat with the result.

For example, n = 20. Half that is 10, and half of 10 is 5. Since 5 is odd, we multiply it by 3 to get 15, and add 1 to get 16, which leads to a few consecutive halving steps. The sequence is then 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, with the “4, 2, 1” part repeating endlessly.

The Collatz conjecture says that if n is positive, iterating the Collatz function will always eventually lead to 1. This conjecture must either be true or it must be false, but no one has been able to prove it one way or the other.

If the conjecture is true, it would mean that all positive integers are connected to each other in a Collatz tree or graph (I’m not sure either of these terms is technically correct, but you understand what I mean).

I would like to be able to visualize this in some way. So I made a diagram in LucidChart.

Diagram of some iterations of the Collatz function. Diagram made in LucidChart.

LucidChart is very easy to use, but making a Collatz tree in this way is still a very time-consuming process. And what if we want to use a different function to connect the integers, like 5n + 1 instead of 3n + 1?

I would like a program that takes a function like that and generates the corresponding tree or graph. So I wrote a class, in Scala, actually. It can be done in Java, it’s just a little clunky compared to Scala.

Here’s the rough draft for the enclosing class, with a placeholder for the inner class:

So the IntegerGraph constructor receives what in Scala would simply be an Int to Int function.

The idea is that each IntegerNode instance will keep track of its precursors that have been discovered so far. When a number’s successor is queried, the node will make sure to connect to the successor’s node, whether the successor node already exists or has to be created anew.

In order to make that connection, an IntegerNode instance needs to know two things about the enclosing IntegerGraph instance: what’s the integer-to-integer function that was provided to the enclosing class constructor, and whether or not the successor node is already known to enclosing instance.

With these requirements in mind, nest the following class into IntegerGraph where indicated by the To Do comment near the end.

Since there is an obvious need to compare nodes, we need to provide an equals() override. And when we override equals() we should also override hashCode() so as to meet the expectations (or “contracts”) for how those two functions relate to each other.

The way this is supposed to work is that the caller will call scan() to discover part of the graph as specified by a particular range of integers, and there would be some bound on iterations (which generally won’t be necessary for the Collatz function).

For example, consider the classic Collatz function “scanned” for 1 to 10. The program discovers the cycle 1, 4, 2 like this: a node is made for 1, then f(1) = 4 leads the program to make a node for 4 connected from the node for 1, and since f(4) = 2, a node is made for 2 connected from the node for 4. And f(2) = 1, but the node for 1 already exists, so the program can move on to the next number to be scanned.

The next number is 2, but that already has a node, so the program moves on to 3, which leads to the creation of nodes in the sequence 3, 10, 5, 16, 8 and that last one connects to the existing node for 4.

Then, after scanning, a query like path(3, 1) will lead to a traversal of nodes that delivers the list 3, 10, 5, 16, 8, 4, 2, 1 wrapped in an Optional.

The main takeaway here is that once we’ve written the tests and have taken each test from failing to passing, we’ll have an inner class for nodes that checks with the enclosing class for the existence of nodes to connect to or from.

I think you can figure out how to adapt this to the family tree use case if that interests you.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Alonso Del Arte

Alonso Del Arte

is a composer and photographer from Detroit, Michigan. He has been working on a Java program to display certain mathematical diagrams.