PStack is not a stack

[blackdrag]

From ddoc...@samplesurgeon.com on 2010-03-29T14:26:41Z

Stacks should support the operations: push, pop, peek.

Original issue: http://code.google.com/p/pcollections/issues/detail?id=7

[blackdrag]

From hrld...@gmail.com on 2010-03-29T11:38:18Z

I think you're right that the spec of PStack should make the stack-like constraints clearer.

PConsStack, however, is definitely a stack in terms of its structure: plus(e) is an O(1) push, minus(0) is an O(1)
pop, and get(0) is an O(1) peek.

I don't want to have methods actually named push(e) and pop() because those are traditionally mutators, and
plus(e) is already completely analogous to push(e), but do you think an index-less minus() method would be a
useful analogue to pop()? And perhaps similarly an index-less get() for peek()?

Basically the current design is that PSequence specifies any ordered PCollection, PVector is a PSequence with
good random-access, and PStack is a PSequence with good front-access. But yeah at the very least I agree
this should be more specified in the Javadoc.

Thoughts?

[blackdrag]

From ddoc...@samplesurgeon.com on 2010-03-29T14:53:57Z

push, pop and peek are traditionally mutators, yes. Even though you're making an
immutable structure, these operations still make sense logically, you just need to
get them to return new collections instead of mutating existing ones.

For an immutable stack, this is the interface I would expect... just these methods,
nothing else:

interface Stack {
Stack push(T o);
Stack pop();
T peek();
boolean isEmpty();
}

In general, I think you're trying to generalise your base immutable structure too
much and bash it into several forms. Instead, you really need to separate your
interface from implementation. You have some great base classes that perform well -
instead of subclassing from them, use them as the backing structures for your data
collections.

Your implementations are good, now you need to step back and consider what makes
sense as an interface. Basically, take the traditional operations you'd expect to see
on a mutable structure, and return modified values instead of mutating.

Have a look at this guy's implementation of an immutable stack... I think it's a nice
simple implementation that would perform well. http://imjorge.spaces.live.com/blog/cns!85B5DB672654118C!1021.entry

[blackdrag]

From ddoc...@samplesurgeon.com on 2010-03-29T14:55:52Z

Sorry, that should be:

interface Stack {
Stack push(T o);
Stack pop();
T peek();
boolean isEmpty();
}

[blackdrag]

From hrld...@gmail.com on 2010-04-01T22:12:48Z

I'm up for some sort of refactoring (in about a week I should have some time), but I'm not going to use
traditional mutator names for the producers because that doesn't fit with the rest of the library (e.g. I
intentionally use the preposition plus() instead of the verb add(), partly to be interoperable with java.util.* but
also for the semantic distinction).

You may have a point about bashing some sort of structure into too many forms, e.g. perhaps PStack being a
PSequence is excessive? Though a stack is fundamentally ordered, which was the intent of that relationship.
Could you be more specific?

I think you might be mistaken about implementation matters though. For one thing the only subclassing in
the library is extending java.util.Abstract* which is pretty harmless. Or were you referring to the interface
hierarchy, not the class hierarchy? Also, as far as implementation, ConsPStack is self-contained, i.e. it is one
of the few classes not based on a balanced tree map; it is just a simple cons.

Oh and also as far as implementation goes, note that ConsPStack's implementation is exactly like in the link
you cited above. See line 63 of http://code.google.com/p/pcollections/source/browse/trunk/PCollections/src/pcollections/ConsPStack.java for the relevant state.

So at the very least you should not be worried about the implementation; it really is a stack.

Thanks for your input, hope I don't sound too defensive! :P

[blackdrag]

From hrld...@gmail.com on 2010-04-01T22:27:55Z

[Looking through the code I did notice that I did a pretty lazy implementation of ConsPStack.minus(int) -- it
could easily be more efficient (though minus(0) is still O(1), just with a bigger constant than necessary...). Just
added an issue to fix it. But other than that the implementation should perform the same as the one you linked
to. ;) ]

[blackdrag]

From hrld...@gmail.com on 2010-05-09T18:51:53Z

Status: WontFix