Re: Immutable Datastructures with good Sharing

Jan Burse wrote:


I can tell you how i do an O(1), well-sharing queue:

public final class ImmutableQueue<E> {

  private static class Link<E> {

  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;
  }

  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.