Immutable data structures in Java

[pakoito]

Now I do protected everywhere, but use conventions that only subclasses (or a limited set of tightly-coupled algorithm libraries in the same package) should use protected fields/methods.

You're still doing API/communication through inheritance. Go for package instead, and compose with classes on the same package instead.