Linked list structure?

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?

On Mon, Jul 28, 2008 at 2:27 PM, Marcin Tustin <[hidden email]> 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?

I believe it's called an OrderedCollection, and it's in every Smalltalk image you'll find(*).

I recommend reading through Chapter 9 of Squeak by Example (under "Documentation" on http://www.squeak.org/). It give a good explanation of Squeak collections and how to use them.

Gulik.

(*) Perhaps except for Craig Latta's 1337-byte image.

--
http://people.squeakfoundation.org/person/mikevdg
http://gulik.pbwiki.com/

_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

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
[hidden email]
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 mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners