eclipse-collections
eclipse-collections copied to clipboard
eclipse
IntStack should implement ReversibleIntIterable
[obviously applies to other primitives as well]
IntStack is, in its current implementation, backed by IntArrayList. While IntArrayList supports reverse iteration, IntStack does not.
I'm willing to implement this if this sounds like a sensible change to you. From what I can tell, it should simply be a matter of delegating everything to IntArrayList.
this sounds reasonable. That said, however, generally Stack is used to pop and push, so may be it might be an overkill. However, the code change would have a relatively less footprint so I wouldn't mind having it. Please go ahead and raise a PR! Thank you very much for your support to Eclipse Collections @yawkat !
Doesn't this break FILO? Our stacks are meant to honor their contracts, not expose their guts.
Said differently, why would one use a stack data structure, then choose to iterate from the bottom? Why not just use a list?
Well, the point of ReverseIterable is to give access to an iterable in reverse. I don't see how that's any worse than peek(size()).reverse() or iterating manually.
By the same token, why would you iterate a stack from the top? My particular use case was "replaying" a stack from its oldest value.
I see. That's as reasonable use case. No objection to this implementation.
How exactly should compatibility for this work? If I change primitiveStack to implement reversiblePrimitiveIterable, should any new methods reversiblePrimitiveIterable introduces be default in primitiveStack or is it enough if I simply implement them in all concrete implementations?
You can keep the implementation in the concrete classes and have a default method which throws to ensure compatibility for minor release. For a major version we don’t provide a default which throws. I am still in a dilemma if next release should be major or minor version. What do you think we should do?
StackIterable implements OrderedIterable. If we do this for primitive collections, we should do it for regular collections.
I don't think we should do this at all. StackIterable only allows iteration from the top, which is the whole point of a stack IMO. Making StackIterable into a ReversibleIterable would prevent a certain implementation of stack that I think ought to exist.
For some reason, the only ImmutableStackIterable we have today is ImmutableArrayStack. I think the most elementary and performant implementation of an immutable stack is a singly-linked list. A NonEmptyImmutableStack would have an element of type T and a next of type ImmutableStack<T>. NonEmptyImmutableStack.pop() would just return next. This implementation would have O(1) time performance for pop() instead of O(n) for ImmutableArrayStack.pop(). And this implementation cannot implement ReversibleIterable.
To clarify my earlier comment: I'm ok with implementing reversible on IntArrayStack (the concrete class), but not the interface.
I agree, it makes sense to have it on the concrete implementation.
I don't think we should do this at all. StackIterable only allows iteration from the top, which is the whole point of a stack IMO. Making StackIterable into a ReversibleIterable would prevent a certain implementation of stack that I think ought to exist.
As I have mentioned above, you can already do this with peek(size()).reversed() (though this is a copy - which is what ImmutableList does for .reversed() also). Additionally, it's not unusual for implementations in EC to only partially implement an interface.
Sure, you could also use toList(). Those are O(n) operations, and I think the signatures make it clear that they take O(n). I'd want to avoid supporting getLast(), asReversed() or anything else that look like they might take O(1) but actually take O(n). This conversation is making me realize that ReversibleIterable isn't the best name. The idea was that the implementations are double-ended, like Deque.
Did we have an agreement here how this should proceed @yawkat @motlin @mohrezaei or should we close the issue?
