[Pharo-project] Why is Stack extending from LinkedList?
Hi list, is there a specific reason Stack is extending from LinkedList, instead of using a LinkedList internally? To me, it seems that the protocol that LinkedList, SequenceableCollection, ... provides is not the protocol you expect from a Stack? Any thoughts on this? Kind regards, Bart -- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
I wonder why there is the need for a stack class at all? OrderedCollection is the class designed to do Stacks and Queues efficiently and portably, see #addFirst:, #addLast:, #first, #last, #removeFirst, #removeLast. Lukas 2010/8/26 Bart Gauquie <bart.gauquie@gmail.com>:
Hi list,
is there a specific reason Stack is extending from LinkedList, instead of using a LinkedList internally? To me, it seems that the protocol that LinkedList, SequenceableCollection, ... provides is not the protocol you expect from a Stack?
Any thoughts on this?
Kind regards,
Bart
-- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli www.lukas-renggli.ch
Good thinking, remove Stack then? On Thu, Aug 26, 2010 at 1:33 PM, Lukas Renggli <renggli@gmail.com> wrote:
I wonder why there is the need for a stack class at all?
OrderedCollection is the class designed to do Stacks and Queues efficiently and portably, see #addFirst:, #addLast:, #first, #last, #removeFirst, #removeLast.
Lukas
2010/8/26 Bart Gauquie <bart.gauquie@gmail.com>:
Hi list,
is there a specific reason Stack is extending from LinkedList, instead of using a LinkedList internally? To me, it seems that the protocol that LinkedList, SequenceableCollection, ... provides is not the protocol you expect from a Stack?
Any thoughts on this?
Kind regards,
Bart
-- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
On Thu, 26 Aug 2010, Lukas Renggli wrote:
I wonder why there is the need for a stack class at all?
OrderedCollection is the class designed to do Stacks and Queues efficiently and portably, see #addFirst:, #addLast:, #first, #last, #removeFirst, #removeLast.
If so, then there are some problems: o := OrderedCollection new: 1000. 1 to: 1000 do: [ :each | o add: each ]. [ 100000 timesRepeat: [ o addFirst: o removeLast ] ] timeToRun. "===> 11660" Levente
Lukas
2010/8/26 Bart Gauquie <bart.gauquie@gmail.com>:
Hi list,
is there a specific reason Stack is extending from LinkedList, instead of using a LinkedList internally? To me, it seems that the protocol that LinkedList, SequenceableCollection, ... provides is not the protocol you expect from a Stack?
Any thoughts on this?
Kind regards,
Bart
-- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
In my machine: o := OrderedCollection new: 1000. 1 to: 1000 do: [ :each | o add: each ]. [ 100000 timesRepeat: [ o addFirst: o removeLast ] ] timeToRun. ==> 12842 o := LinkedList new: 1000. 1 to: 1000 do: [ :each | o add: each ]. [ 100000 timesRepeat: [ o addFirst: o removeLast ] ] timeToRun. ==> 5603 On Fri, Aug 27, 2010 at 1:35 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Thu, 26 Aug 2010, Lukas Renggli wrote:
I wonder why there is the need for a stack class at all?
OrderedCollection is the class designed to do Stacks and Queues efficiently and portably, see #addFirst:, #addLast:, #first, #last, #removeFirst, #removeLast.
If so, then there are some problems:
o := OrderedCollection new: 1000. 1 to: 1000 do: [ :each | o add: each ]. [ 100000 timesRepeat: [ o addFirst: o removeLast ] ] timeToRun. "===> 11660"
Levente
Lukas
2010/8/26 Bart Gauquie <bart.gauquie@gmail.com>:
Hi list,
is there a specific reason Stack is extending from LinkedList, instead of using a LinkedList internally? To me, it seems that the protocol that LinkedList, SequenceableCollection, ... provides is not the protocol you expect from a Stack?
Any thoughts on this?
Kind regards,
Bart
-- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On Fri, 27 Aug 2010, Guillermo Polito wrote:
In my machine:
o := OrderedCollection new: 1000. 1 to: 1000 do: [ :each | o add: each ]. [ 100000 timesRepeat: [ o addFirst: o removeLast ] ] timeToRun. ==> 12842
o := LinkedList new: 1000. 1 to: 1000 do: [ :each | o add: each ]. [ 100000 timesRepeat: [ o addFirst: o removeLast ] ] timeToRun. ==> 5603
LinkedList should be used this way if you want to use it as a Queue: o := LinkedList new: 1000. 1 to: 1000 do: [ :each | o add: each ]. [ 100000 timesRepeat: [ o addLast: o removeFirst ] ] timeToRun. "===> 119" Levente
On Fri, Aug 27, 2010 at 1:35 PM, Levente Uzonyi <leves@elte.hu> wrote:
On Thu, 26 Aug 2010, Lukas Renggli wrote:
I wonder why there is the need for a stack class at all?
OrderedCollection is the class designed to do Stacks and Queues efficiently and portably, see #addFirst:, #addLast:, #first, #last, #removeFirst, #removeLast.
If so, then there are some problems:
o := OrderedCollection new: 1000. 1 to: 1000 do: [ :each | o add: each ]. [ 100000 timesRepeat: [ o addFirst: o removeLast ] ] timeToRun. "===> 11660"
Levente
Lukas
2010/8/26 Bart Gauquie <bart.gauquie@gmail.com>:
Hi list,
is there a specific reason Stack is extending from LinkedList, instead of using a LinkedList internally? To me, it seems that the protocol that LinkedList, SequenceableCollection, ... provides is not the protocol you expect from a Stack?
Any thoughts on this?
Kind regards,
Bart
-- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
2010/8/27 Levente Uzonyi <leves@elte.hu>:
On Thu, 26 Aug 2010, Lukas Renggli wrote:
I wonder why there is the need for a stack class at all?
OrderedCollection is the class designed to do Stacks and Queues efficiently and portably, see #addFirst:, #addLast:, #first, #last, #removeFirst, #removeLast.
If so, then there are some problems:
o := OrderedCollection new: 1000. 1 to: 1000 do: [ :each | o add: each ]. [ 100000 timesRepeat: [ o addFirst: o removeLast ] ] timeToRun. "===> 11660"
Levente
OrderedCollection could be implemented differently, like for example having a circular array and maintaining a firstIndex and size instead of lastIndex. The main drawback would be that fast copy/replace would have to be split in two parts. Nicolas
Lukas
2010/8/26 Bart Gauquie <bart.gauquie@gmail.com>:
Hi list,
is there a specific reason Stack is extending from LinkedList, instead of using a LinkedList internally? To me, it seems that the protocol that LinkedList, SequenceableCollection, ... provides is not the protocol you expect from a Stack?
Any thoughts on this?
Kind regards,
Bart
-- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On Fri, 27 Aug 2010, Nicolas Cellier wrote:
2010/8/27 Levente Uzonyi <leves@elte.hu>:
On Thu, 26 Aug 2010, Lukas Renggli wrote:
I wonder why there is the need for a stack class at all?
OrderedCollection is the class designed to do Stacks and Queues efficiently and portably, see #addFirst:, #addLast:, #first, #last, #removeFirst, #removeLast.
If so, then there are some problems:
o := OrderedCollection new: 1000. 1 to: 1000 do: [ :each | o add: each ]. [ 100000 timesRepeat: [ o addFirst: o removeLast ] ] timeToRun. "===> 11660"
Levente
OrderedCollection could be implemented differently, like for example having a circular array and maintaining a firstIndex and size instead of lastIndex.
This issue is already fixed in Squeak 4.1. I tried the OrderedCollection with a circular array just like you suggested, but it was a bit slower than Squeak's OrderedCollection. Also note that this is an edge case. Levente
The main drawback would be that fast copy/replace would have to be split in two parts.
Nicolas
Lukas
2010/8/26 Bart Gauquie <bart.gauquie@gmail.com>:
Hi list,
is there a specific reason Stack is extending from LinkedList, instead of using a LinkedList internally? To me, it seems that the protocol that LinkedList, SequenceableCollection, ... provides is not the protocol you expect from a Stack?
Any thoughts on this?
Kind regards,
Bart
-- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On Thu, 26 Aug 2010, Bart Gauquie wrote:
Hi list,
is there a specific reason Stack is extending from LinkedList, instead of using a LinkedList internally? To me, it seems that the protocol that LinkedList, SequenceableCollection, ... provides is not the protocol you expect from a Stack?
Any thoughts on this?
Originally it used encapsulation, but for some reason it was changed to use inheritance, probably for a "cleaner" system. IMHO the changes should be reverted. Levente
Kind regards,
Bart
-- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
On Aug 27, 2010, at 6:32 PM, Levente Uzonyi wrote:
On Thu, 26 Aug 2010, Bart Gauquie wrote:
Hi list,
is there a specific reason Stack is extending from LinkedList, instead of using a LinkedList internally? To me, it seems that the protocol that LinkedList, SequenceableCollection, ... provides is not the protocol you expect from a Stack?
Any thoughts on this?
Originally it used encapsulation,
when where?
but for some reason it was changed to use inheritance, probably for a "cleaner" system. IMHO the changes should be reverted.
I was not aware that Stack was a subclass of linkedList, it looks again subclassing versus subtyping. And subtyping is better. Stef
Levente
Kind regards,
Bart
-- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On Fri, 27 Aug 2010, Stéphane Ducasse wrote:
On Aug 27, 2010, at 6:32 PM, Levente Uzonyi wrote:
On Thu, 26 Aug 2010, Bart Gauquie wrote:
Hi list,
is there a specific reason Stack is extending from LinkedList, instead of using a LinkedList internally? To me, it seems that the protocol that LinkedList, SequenceableCollection, ... provides is not the protocol you expect from a Stack?
Any thoughts on this?
Originally it used encapsulation,
when where?
In Pharo 1.0 (and Squeak of course). Levente
but for some reason it was changed to use inheritance, probably for a "cleaner" system. IMHO the changes should be reverted.
I was not aware that Stack was a subclass of linkedList, it looks again subclassing versus subtyping. And subtyping is better.
Stef
Levente
Kind regards,
Bart
-- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
In Pharo 1.0 (and Squeak of course).
I'm amazed. Our quality process seems weak :) I will check and revert it. Thanks for spotting that. Stef
but for some reason it was changed to use inheritance, probably for a "cleaner" system. IMHO the changes should be reverted.
I was not aware that Stack was a subclass of linkedList, it looks again subclassing versus subtyping. And subtyping is better.
Stef
Levente
Kind regards,
Bart
-- imagination is more important than knowledge - Albert Einstein Logic will get you from A to B. Imagination will take you everywhere - Albert Einstein Learn from yesterday, live for today, hope for tomorrow. The important thing is not to stop questioning. - Albert Einstein The true sign of intelligence is not knowledge but imagination. - Albert Einstein However beautiful the strategy, you should occasionally look at the results. - Sir Winston Churchill It's not enough that we do our best; sometimes we have to do what's required. - Sir Winston Churchill
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
participants (6)
-
Bart Gauquie -
Guillermo Polito -
Levente Uzonyi -
Lukas Renggli -
Nicolas Cellier -
Stéphane Ducasse