I am aware of LinkedList. It does not meet the criterion of accepting items whatever their protocol.
On Mon, Jul 28, 2008 at 7:12 AM, David T. Lewis lewis@mail.msen.com wrote:
On Sun, Jul 27, 2008 at 10:27:08PM -0400, Marcin Tustin wrote:
Is there - either as standard, or freely downloadable - a datastructure
that
is ordered, has constant-time appends of items, requires no particular protocol of the items stored, and can be iterated over (without
allocating a
new structure) starting with the first item added, proceeding to the next item added? I.e. has the characteristics of a linked list structure in
most
other datastructure libraries?
Have a look at class LinkedList. This is one of the "kernel" classes in Squeak and is used by ProcessorScheduler to manage processes (the "threads" within a Squeak image, instances of class Process). A Squeak Process is implemented as a subclass of Link, and it is kept as an entry in the linked list. Try evaluating "Processor explore" to look at the singleton instance of ProcessorScheduler that manages these linked lists.
Dave
Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
Marcin Tustin a écrit :
I am aware of LinkedList. It does not meet the criterion of accepting items whatever their protocol.
You are right, current implementation of LinkedList is very specialized and restricted. Creating Links transparently would be a plus. Hey, we can use a Dictionary without being aware of Association!
I am not aware of such implementation, but wouldn't be surprised it already exists. Rather than a long research, it is easier to DIY.
I provide an untested quick first implementation as an example. This implementation uses already existing StackLink transparently. This could of course be completed with addLink: removeLink: etc...
Reading code enabled me finding http://bugs.squeak.org/view.php?id=7136
So a prerequisite is: Installer mantis ensureFix: 7136.
Last, as all code I publicly released in Squeak until now, consider this code as MIT. Change it, republish it, sell it or throw it away at will.
Cheers
Nicolas
'From Squeak3.10beta of 22 July 2007 [latest update: #7159] on 28 July 2008 at 10:48:46 pm'! LinkedList subclass: #TransparentLinkedList instanceVariableNames: '' classVariableNames: '' poolDictionaries: '' category: 'Collections-Sequenceable'! !TransparentLinkedList commentStamp: 'nice 7/28/2008 21:47' prior: 0! I represent a collection of links, which are containers for other objects. Using the message sequence addFirst:/removeLast causes the receiver to behave as a stack; using addLast:/removeFirst causes the receiver to behave as a queue.
Unlike super, users won't see the Link objects, like users of Dictionary do not need to know about Association. That's why i am called TransparentLinkedList.!
!TransparentLinkedList methodsFor: 'adding' stamp: 'nice 7/28/2008 22:47'! add: anObject after: otherObject "Add anObject after otherObject in the list. Answer anObject. If otherObject is not in the list, then raise an error."
| otherLink | otherLink := self findLinkFor: otherObject ifAbsent: [^self error: 'otherObject is not in this list']. super add: (StackLink with: anObject) after: otherLink. ^anObject! !
!TransparentLinkedList methodsFor: 'adding' stamp: 'nice 7/28/2008 22:47'! add: anObject before: otherObject "Add anObject after otherObject in the list. Answer anObject. If otherObject is not in the list, then raise an error."
| otherLink | otherLink := self findLinkFor: otherObject ifAbsent: [^self error: 'otherObject is not in this list']. super add: (StackLink with: anObject) before: otherLink. ^anObject! !
!TransparentLinkedList methodsFor: 'adding' stamp: 'nice 7/28/2008 21:54'! addFirst: anObject "Add anObject to the beginning of the receiver's list. Answer anObject."
super addFirst: (StackLink with: anObject). ^anObject! !
!TransparentLinkedList methodsFor: 'adding' stamp: 'nice 7/28/2008 21:53'! addLast: anObject "Add anObject to the end of the receiver's list. Answer anObject."
super addLast: (StackLink with: anObject). ^anObject! !
!TransparentLinkedList methodsFor: 'removing' stamp: 'nice 7/28/2008 22:11'! remove: anObject ifAbsent: aBlock "Remove anObject from the receiver. If it is not there, answer the result of evaluating aBlock."
| aLink | aLink := self findLinkFor: anObject ifAbsent: [^aBlock value]. super remove: aLink ifAbsent: aBlock. ^anObject ! !
!TransparentLinkedList methodsFor: 'removing' stamp: 'nice 7/28/2008 21:55'! removeFirst "Remove the first element and answer it. If the receiver is empty, create an error notification."
^super removeFirst element! !
!TransparentLinkedList methodsFor: 'removing' stamp: 'nice 7/28/2008 21:55'! removeLast "Remove the first element and answer it. If the receiver is empty, create an error notification."
^super removeLast element! !
!TransparentLinkedList methodsFor: 'enumerating' stamp: 'nice 7/28/2008 22:12'! do: aBlock
self linkDo: [:aLink | aBlock value: aLink element]! !
!TransparentLinkedList methodsFor: 'enumerating' stamp: 'nice 7/28/2008 22:10'! findLinkFor: anObject ifAbsent: aBlock self linkDo: [:aLink | aLink element = anObject ifTrue: [^aLink]]. ^aBlock value! !
!TransparentLinkedList methodsFor: 'enumerating' stamp: 'nice 7/28/2008 22:15'! linkDo: aBlock "this could be ^super do: but I dislike sending super with a different message selector"
| aLink | aLink := firstLink. [aLink == nil] whileFalse: [aBlock value: aLink. aLink := aLink nextLink]! !
!TransparentLinkedList methodsFor: 'enumerating' stamp: 'nice 7/28/2008 21:57'! reverseDo: aBlock
super reverseDo: [:aLink | aBlock value: aLink element]! !
!TransparentLinkedList methodsFor: 'enumerating' stamp: 'nice 7/28/2008 21:58'! species
^ self class! !
!TransparentLinkedList methodsFor: 'accessing' stamp: 'nice 7/28/2008 21:58'! first ^super first element! !
!TransparentLinkedList methodsFor: 'accessing' stamp: 'nice 7/28/2008 21:58'! last ^super last element! !
beginners@lists.squeakfoundation.org