Dentista

A minha dentista conhece os meus podres todos.

Posted in Uncategorized | 5 Comments

Java: Immutable Stack

Here is the challenge: write an immutable stack in Java.

You might be thinking that a stack is by its very nature something that changes. A stack is an abstract data type with the interface:

IStack<T> push(T value);

IStack<T> pop();

T peek();

boolean isEmpty();

You push stuff onto it, you pop stuff off of it, it changes. How can it be immutable?

Every time you need to make a data structure immutable, you use basically the same trick: an operation which “changes” the data structure does so by constructing a new data structure. The original data structure stays the same.

How can that possibly be efficient? Surely we’ll be allocating memory all over the place! Well, actually, in this case, no. An immutable stack is every bit as efficient as a mutable stack. Even better: in some cases, it can be considerably more efficient, as we’ll see.

Let’s start by defining an interface for our immutable structure. While we’re at it, we’ll fix a problem with the stack ADT above, namely that you cannot interrogate the stack without changing it. And we’ll make the stack enumerable just for the heck of it:

interface IStack<T> extends Iterable<T> {
IStack<T> push(T value);

IStack<T> pop();

T peek();

boolean isEmpty();
}

 

Pushing and popping give you back an entirely new stack, and Peek lets you look at the top of the stack without popping it.

Now let’s think about constructing one of these things here. Clearly if we have an existing stack we can construct a new one by pushing or popping it. But we have to start somewhere. Since every empty stack is the same, it seems sensible to have a singleton empty stack.

class Stack<T> implements IStack<T> {
private T head;
private IStack<T> tail;
public Stack(final T head, final IStack<T> tail) {
this.head = head;
this.tail = tail;
}
public static <U> IStack<U> empty(final Class<U> type) { return new EmptyStack<U>(); }

public boolean isEmpty() { return false; }

public T peek() { return this.head; }

public IStack<T> pop() { return this.tail; }

public IStack<T> push(T value) { return new Stack<T>(value, this); }

public Iterator<T> iterator() { return new StackIterator<T>(this); }
private static class StackIterator<U> implements Iterator<U> {
private IStack<U> stack;
public StackIterator(final IStack<U> stack) { this.stack = stack; }

public boolean hasNext() { return !this.stack.isEmpty(); }

public U next() {
U result = this.stack.peek();
this.stack = this.stack.pop();
return result;
}

public void remove() { }
}
private static class EmptyStack<U> implements IStack<U> {

public boolean isEmpty() { return true; }

public U peek() { throw new RuntimeException(“empty stack”); }

public IStack<U> pop() { throw new RuntimeException(“empty stack”); }

public IStack<U> push(U value) { return new Stack<U>(value, this); }

public Iterator<U> iterator() { return new StackIterator<U>(this); }
}
}

 

And now we can easily create stacks and push stuff onto them. Notice how the fact that we have immutability means that stacks with the same tail can share state, saving on memory:

IStack<Integer> s1 = Stack.empty(Integer.class);
IStack<Integer> s2 = s1.push(10);
IStack<Integer> s3 = s2.push(20);
IStack<Integer> s4 = s2.push(30); // shares its tail with s3.
Posted in Uncategorized | 3 Comments

Cinema Ad

Posted in Uncategorized | Leave a comment

José Inácio

José Inácio agricultor de vocação assumava à ombreira da porta e especou a olhar para a mulher. Foi apenas quando Maria da Ascensão espantada com o marido o inquiriu "o qué q’ouve" que José Inácio foi iluminado pelo espírito das piadas secas e respondeu motejando "é uma hortaliça".

Posted in Uncategorized | Leave a comment

Celibato Eterno

Ele ia jurar que enquanto usava os braços como escudo para se proteger das agressões da companheira por se ter esquecido do aniversário tinha ouvido as palavras "celibato eterno".

Posted in Uncategorized | 1 Comment

Mi caricatura

Caricatura feita por Nélson Santos no Techdays 2008 em Lisboa.
Posted in Uncategorized | Leave a comment

Era uma bela ideia

Nuno (nome fictício) desligava as luzes do carro à noite quando se aproximava de uma cruzamento para conseguir ver melhor se outro carro se aproximava. Naquela sexta-feira à noite outro condutor tinha tido a mesma excelente ideia.

Posted in Uncategorized | Leave a comment