Re: Immutable Datastructures with good Sharing
On Sun, 6 Nov 2011, Lew wrote:
Tom Anderson wrote:
Jan Burse wrote:
Somebody here, who could throw a spot light on how they do a Queue?
I can tell you how i do an O(1), well-sharing queue:
public final class ImmutableQueue<E> {
private static class Link<E> {
Side note: One might observe that this 'E' does not correspond to the
'E' of the outer class's generic parameter. One might also observe that
this does no harm whatsoever.
Yes, certainly worth noting, though. I did have this being a non-static
inner class at some point; i think that works, but given that instances of
it are shared between many different instances of the outer class, it
seems wrong.
Side note 2: TABs? Really?
I wrote it in Eclipse, which i have set up to use tabs, and
copy-and-pasted it. The tabs stayed tabs. I could have reformatted it with
spaces, but i just wanted to post it and get to bed.
Actually, i did it just to annoy you.
public int size() {
if (isEmpty()) return 0;
int size = 1;
Link<E> link = head;
while (link != tail) {
++size;
link = link.next;
}
Alternative form if you like for loops:
for (Link<E> link = head; link != tail; link = link.next) {
++size;
}
return size;
}
Yes, that's nice.
A serious implementation of this would probably just track the size in a
variable, rather than counting the links each time.
tom
--
There is no violence or enmity in the LEGO universe until you, the
builder, decide what to build with the pieces. -- Pyrogenic