Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
From: Lew <lewbloch@gmail.com>
Newsgroups: comp.lang.java.programmer
Subject: Re: Immutable Datastructures with good Sharing
Date: Sun, 6 Nov 2011 17:26:10 -0800 (PST)
Organization: http://groups.google.com
Lines: 158
Message-ID: <24833877.1073.1320629170928.JavaMail.geo-discussion-forums@prep8>
References: <j9292v$f69$1@news.albasani.net> <jamdnUwVbvmRMSjTnZ2dnUVZ_uKdnZ2d@posted.palinacquisition> <j94ajg$ost$1@news.albasani.net> <IuednQhC8Y-dLSjTnZ2dnUVZ_gmdnZ2d@posted.palinacquisition> <j94bip$r6v$1@news.albasani.net> <j94bqu$r6v$2@news.albasani.net> <qotwrbdbspe.fsf@ruuvi.it.helsinki.fi> <j95jkv$p42$1@news.albasani.net> <UCvtq.20364$Cr1.10065@newsfe03.iad> <j961n4$uts$1@news.albasani.net> <slrnjbd6fu.fvg.avl@gamma.logic.tuwien.ac.at> <CADC63E1.8F1D%bravegag@hotmail.com> <j96aql$n73$1@news.albasani.net> <alpine.DEB.2.00.1111070037450.4201@urchin.earth.li>
Reply-To: comp.lang.java.programmer@googlegroups.com
NNTP-Posting-Host: 173.164.137.214
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
X-Trace: posting.google.com 1320629278 29549 127.0.0.1 (7 Nov 2011 01:27:58 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Mon, 7 Nov 2011 01:27:58 +0000 (UTC)
In-Reply-To: <alpine.DEB.2.00.1111070037450.4201@urchin.earth.li>
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=173.164.137.214; posting-account=CP-lKQoAAAAGtB5diOuGlDQk0jIwmH0T
User-Agent: G2/1.0
X-Google-Web-Client: true
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:9718

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.

Side note 2:  TABs?  Really?

>  		public final E element;
>  		public final Link<E> next;
> 
>  		public Link(E element, Link<E> next) {
>  			this.element = element;
>  			this.next = next;
>  		}
> 
>  	}
> 
>  	private final Link<E> head;
>  	private final Link<E> tail;
>  	private final Link<Link<E>> tuft;
> 
>  	private ImmutableQueue(Link<E> head, Link<E> tail, Link<Link<E>> tuft) {
>  		assert (tuft == null) || (tuft.element.next == tail);
>  		this.head = head;
>  		this.tail = tail;
>  		this.tuft = tuft;
>  	}
> 
>  	private ImmutableQueue(Link<E> element) {
>  		this(element, element, null);
>  	}
> 
>  	public ImmutableQueue() {
>  		this(null);
>  	}
> 
>  	public boolean isEmpty() {
>  		return head == null;
>  	}
> 
>  	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;
>  	}
> 
>  	public ImmutableQueue<E> enqueue(E element) {
>  		Link<E> enqueued = new Link<E>(element, head);
>  		if (isEmpty()) return new ImmutableQueue<E>(enqueued);
>  		else return new ImmutableQueue<E>(enqueued, tail, null);
>  	}
> 
>  	public ImmutableQueue<E> dequeue(E[] holder) {
>  		ImmutableQueue<E> queue;
> 
>  		if (head == null) {
>  			throw new NoSuchElementException();
>  		}
>  		else if (head == tail) {
>  			queue = new ImmutableQueue<E>();
>  		}
>  		else {
>  			Link<Link<E>> tuft = this.tuft;
>  			if (tuft == null) {
>  				tuft = backcomb();
>  				assert tuft.element.next == tail;
>  			}
>  			queue = new ImmutableQueue<E>(head, tuft.element, tuft.next);
>  		}
> 
>  		holder[0] = tail.element;
>  		return queue;
>  	}
> 
>  	private Link<Link<E>> backcomb() {
>  		Link<Link<E>> tuft = null;
>  		Link<E> link = head;
>  		while (link != tail) {
>  			tuft = new Link<Link<E>>(link, tuft);
>  			link = link.next;
>  		}
>  		return tuft;
>  	}
> 
> }
> 
> I'm sure it's obvious what's going on here.
> 
> But if not: the core of it is a normal immutable linked list, growing at 
> the enqueue end. Dequeue is handled by tracking a tail pointer, and 
> pretending that links past the tail don't exist (rather than treating a 
> null next pointer as defining the end as usual). There is then an 
> antiparallel linked list (rooted in 'tuft' - extending the 'tail' metaphor 
> a bit), starting just before the tail and running back to the head; this 
> list essentially turns the list into a doubly-linked list, and so allows 
> efficient dequeues.
> 
> Keeping that list accurate at all times would be expensive, so instead, it 
> is constructed when needed, ie when we need to dequeue and we don't have 
> it. Note that when it is constructed, it reaches all the way back to the 
> head, but as more elements are enqueued, the head moves away from its 
> tail, leaving it only partially covering the queue. That's fine: we only 
> use it to find the link before the tail, so we don't need it to go far. 
> When we've dequeued enough elements to have worn it down completely, we 
> rebuild it.
> 
> Enqueueing is obviously O(1). Dequeueing is O(1) if you don't need to 
> rebuild the backwards list. If you do need to rebuild the backwards list, 
> it's O(n); you will then not need to rebuild for another n dequeues, which 
> makes it amortatively O(1).
> 
> In terms of sharing, all the forward links are shared. Backwards links 
> will be shared too, but if two separate lineages of queues both have to 
> rebuild the backwards list, the links will not be shared, even though 
> they are identical. Consider:
> 
> ImmutableQueue noah; // has one backward link remaining
> ImmutableQueue shem = noah.dequeue(holder);
> ImmutableQueue ham = noah.dequeue(holder);
> // shem and ham are identical
> ImmutableQueue elam = shem.dequeue(holder);
> ImmutableQueue cush = ham.dequeue(holder);
> // elam and cush are identical, but have separate backward lists
> 
> In terms of packratting, backwards lists become garbage, but the links in 
> forward lists never do. You could always walk from any head right back yea 
> even unto the first tail. I think that's hard to avoid in an immutable 
> structure.
> 
> Also, i think i've just grokked what that C# dude's half-backwards list is 
> all about. It's like this, but throwing away the forwards list when you 
> make the backwards list, which saves memory and lets forward list links 
> become garbage. Clever stuff.

It's a sweet piece of work.  Thanks for sharing it.

-- 
Lew