Any nice way to make a chain of immutable objects loop around?

Question

This question is an extension of this question.

I have a class similar to the following.

 class HighlightableStructure {
      private final HighlightableStructure NEXT;  

      HighlightableStructure(HighlightableStructure next) {
           NEXT = next;
      }    
 }

where a HighlightableStructure points to the next structure to highlight.

Sometimes, these HighlightableStructures loop around and refer to a previous HighlightableStructure, but not the first in the chain. Something like h_1 -> h_2 ->h_3 -> ... -> h_n -> h_2, where h_i is an instance of HighlightableStructure.

Is there anyway I could construct something like this without reflection or losing immutability?

What problems are you facing? I'm not sure how immutability is a problem here as you aren't trying to mutate a previously created object. — RaminS, Jul 21 '19 at 22:46
It's sort of a chicken and egg thing I think, where you pass h_n+1 to h_n at construction time, so there's no opportunity to get access to h_n-1, say, because it's not been created yet. — Alex Hart, Jul 21 '19 at 22:50
@Gendarme The problem is that there is no previously created object. In order to create h_2, I need h_3. In order to create h_3, I need h_4, and so on until I get to h_n which needs h_2. I could create h_2 and set its reference to `null` and then use reflection at the end, or I could just avoid immutability entirely, but i would hope to avoid these options. — Lindstorm, Jul 21 '19 at 22:50
If you start out with a linked list, then just have the last node point to the root. That means that, for all practical purposes, there is no specific root, and you can insert a node in at any location. For indexed arrays you could just use a modulus of the array size. In one sense, you are talking about a circular buffer, which is a well known data structure. — WJS, Jul 22 '19 at 03:35

score 3 · Answer 1 · answered Sep 18 '19 at 15:10

The answer of the linked question is easily expandable to an arbitrary number of objects, if you have a way to specify the needed nodes at construction time, e.g.

final class CircularLinkedList<T> {
    final CircularLinkedList<T> next;
    final T value;

    public CircularLinkedList(T firstValue, List<T> other) {
        value = firstValue;
        next = other.isEmpty()? this: new CircularLinkedList<>(this, 0, other);

    }
    private CircularLinkedList(CircularLinkedList<T> head, int pos, List<T> values) {
        value = values.get(pos);
        next = ++pos == values.size()? head: new CircularLinkedList<>(head, pos, values);
    }

    @Override
    public String toString() {
        StringJoiner sj = new StringJoiner(", ").add(value.toString());
        for(CircularLinkedList<T> node = next; node != this; node = node.next)
            sj.add(node.value.toString());
        return sj.toString();
    }
}

Which you can use like

CircularLinkedList<String> cll
    = new CircularLinkedList<>("first", Arrays.asList("second", "third", "fourth"));
System.out.println(cll);

// demonstrate the wrap-around:
for(int i = 0; i < 10; i++, cll = cll.next) {
    System.out.print(cll.value+" .. ");
}
System.out.println(cll.value);

Alex Hart · Accepted Answer · 2019-07-21T23:52:24.790

1

One possible solution:

class HSequenceBuilder {
    private long id = 0;
    private final Map<Integer, H> map = new HashMap<Integer, H>();

    static H create(int next) {
        H h = new H(id, next, Collections.unmodifiableMap(map));
        map.put(id, h);
        id++;
        return h;
    }

    static H create() {
        create(id + 1);
    }

}

class H {
    private final id;
    private final Map<Integer, H> map;
    private final int next;

    H(int id, int next, Map<Integer, H> map) {
        this.id = id;
        this.next = next;
        this.map = map;
    }

    int getId() { return id; }
}
HSequenceBuilder builer = new HSequenceBuilder();
H h1 = builder.create(); // 1.
H h2 = builder.create(); // 2.
H h3 = builder.create(h2.getId()); // 3.

edited Jul 21 '19 at 23:52

answered Jul 21 '19 at 22:58

Alex Hart

1,663
12
15

I like this solution a lot. Is there a reason why you have `map` in the `H` class non-static? If I am understanding it correctly, `map` will contain all nodes with the node ID being the key. The only reason I see is that you might have multiple graphs each with the same set of IDs. – Lindstorm Jul 22 '19 at 00:19
1

Yeah, if you want to create multiple sequences, you'd prefer a non-static map. You could also change up id generation to be static as well (or to use a random UUID) and at that point you could get away with a static map. However, in this case I believe you'd want to use a WeakMap so you don't start leaking memory... I guess because otherwise it gets more complicated hah. – Alex Hart Jul 22 '19 at 00:20
2

Wasn’t the question how to create a circular linked immutable list? Where is that list in your answer? – Holger Sep 18 '19 at 14:53
@Holger The question wasn’t about circular linked lists specifically. It was more about how to create something which is similar to a standard circular linked list which is immutable but is not perfectly circular: i.e. where tail does not necessarily point to head – Lindstorm Sep 18 '19 at 18:09
1

@Lindstorm how similar is a solution when asking about an immutable circular linked list and the solution is 1) not circular, 2) not a linked list, and 3) not immutable? The solution is just a wrapper around a `Map` *which is modified after the `H` instance creation* and, by the way, is just an inefficient `List` when you use ascending integer values as keys. When you are fine with a mutable non-circular list, just use `ArrayList` in the first place. But then, the whole question becomes pointless. – Holger Sep 19 '19 at 08:15

score 0 · Answer 3 · answered Jul 21 '19 at 23:56

0

You’ve got a linked list, which requires its nodes to be mutable. You can have mutable object but still get very similar benefits to immutability if you publish safe copies of your nodes.

Hide you nodes inside a containing object and when your API must return a node, return a copy of it instead, or even a copy of the entire structure as required.

answered Jul 21 '19 at 23:56

Bohemian

412,405
93
575
722

I do not see how linked lists would help. If you are saying have the nodes in a linked list implementation be the nodes in my question , how could I have a node at the end of the list refer to something in the middle of the list? If you are saying have the linked list contain my nodes (ie `LinkedList`), would you then have the reference in `HighlightableStructure` class be the index in the list? If so, wouldn't another data structure be better because you would not have to iterate though the linked list? – Lindstorm Jul 22 '19 at 00:24
I don’t mean you should have a linked list *of* `HighlightableStructure`, I mean your class `HighlightableStructure` fits the definition of a linked list node and the structure that your `HighlightableStructure` instances create (by referring to another node) fits the definition of a linked list. The data structure your objects create *is* a linked list. There’s no getting around it. – Bohemian Jul 22 '19 at 20:35

Any nice way to make a chain of immutable objects loop around?

3 Answers3

Linked

Related