[squeak-dev] The Trunk: Collections-topa.726.mcz

Chris Muller ma.chris.m at gmail.com
Tue Dec 6 19:42:09 UTC 2016


Not sure if you were joking; but..  :)  Magma includes an
implementation of Split-Ordered Lists (which make heavy use of
LinkedLists) to serve as the foundation of MagmaCollection.

http://cs.ucf.edu/~dcm/Teaching/COT4810-Spring2011/Literature/SplitOrderedLists.pdf

Its the use-case for having collections whose size exceeds available
RAM.  OrderedCollection is designed to operate on a fully-allocated
Array, which would be too large for memory.

LinkedList is a fundamental a data structure, this is reason enough it
should be included in Smalltalk and Squeak, IMO.


On Tue, Dec 6, 2016 at 1:08 PM, Levente Uzonyi <leves at caesar.elte.hu> wrote:
> Is there any use of these lists? I mean besides process scheduling.
> I can't imagine a use-case where I would use a LinkedList instead of an
> OrderedCollection (or another data structure).
> I would also get rid of the current Stack implementation.
>
> Levente
>
>
> On Tue, 6 Dec 2016, Tobias Pape wrote:
>
>>
>> On 06.12.2016, at 19:11, Chris Muller <asqueaker at gmail.com> wrote:
>>
>>> More specifically, will existing instances work or is there some
>>> conversion needed?
>>
>>
>> As far as I can tell, no work needed.
>>
>>
>>>
>>> On Tue, Dec 6, 2016 at 12:10 PM, Chris Muller <asqueaker at gmail.com>
>>> wrote:
>>>>
>>>> Is this backward compatible?
>>>>
>>>> On Tue, Dec 6, 2016 at 7:31 AM,  <commits at source.squeak.org> wrote:
>>>>>
>>>>> Tobias Pape uploaded a new version of Collections to project The Trunk:
>>>>> http://source.squeak.org/trunk/Collections-topa.726.mcz
>>>>>
>>>>> ==================== Summary ====================
>>>>>
>>>>> Name: Collections-topa.726
>>>>> Author: topa
>>>>> Time: 6 December 2016, 2:31:08.021296 pm
>>>>> UUID: 8409fe6a-d5ea-4d4e-ac78-243182dd1fd7
>>>>> Ancestors: Collections-topa.725
>>>>>
>>>>> Adopt improved (ie, actually working) Linked List from our relatives.
>>>>>
>>>>> =============== Diff against Collections-topa.725 ===============
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: Link>>asLink (in category 'converting') -----
>>>>> + asLink
>>>>> +
>>>>> +       ^ self!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: Link>>nextLink (in category 'accessing') -----
>>>>>  nextLink
>>>>> -       "Answer the link to which the receiver points."
>>>>>
>>>>> +       ^ nextLink!
>>>>> -       ^nextLink!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: Link>>nextLink: (in category 'accessing') -----
>>>>>  nextLink: aLink
>>>>>        "Store the argument, aLink, as the link to which the receiver
>>>>> refers.
>>>>>        Answer aLink."
>>>>>
>>>>> +       ^ nextLink := aLink!
>>>>> -       ^nextLink := aLink!
>>>>>
>>>>> Item was changed:
>>>>>  SequenceableCollection subclass: #LinkedList
>>>>>        instanceVariableNames: 'firstLink lastLink'
>>>>>        classVariableNames: ''
>>>>>        poolDictionaries: ''
>>>>>        category: 'Collections-Sequenceable'!
>>>>>
>>>>> + !LinkedList commentStamp: 'topa 12/6/2016 14:17' 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.
>>>>> +
>>>>> + If you attempt to add any object into a LinkedList that is not a
>>>>> Link, it will automatically be wrapped by a ValueLink. A LinkedList
>>>>> therefore behaves very much like any collection, except that certain calls
>>>>> such as atIndex: are linear rather than constant time.!
>>>>> - !LinkedList commentStamp: '<historical>' 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.!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList class>>new: (in category 'instance
>>>>> creation') -----
>>>>> + new: anInt
>>>>> +       "LinkedList don't need capacity"
>>>>> +       ^self new!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList class>>new:streamContents: (in category
>>>>> 'stream creation') -----
>>>>> + new: size streamContents: aBlock
>>>>> +       ^ self withAll: (super new: size streamContents: aBlock)!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList class>>newFrom: (in category 'instance
>>>>> creation') -----
>>>>> + newFrom: aCollection
>>>>> +       "Answer an instance with same elements as aCollection."
>>>>> +       ^self new
>>>>> +               addAll: aCollection;
>>>>> +               yourself!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>add: (in category 'adding') -----
>>>>> + add: aLinkOrObject
>>>>> - add: aLink
>>>>>        "Add aLink to the end of the receiver's list. Answer aLink."
>>>>>
>>>>> +       ^self addLast: aLinkOrObject!
>>>>> -       ^self addLast: aLink!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>add:after: (in category 'adding') -----
>>>>> + add: link after: otherLinkOrObject
>>>>> - add: link after: otherLink
>>>>> -
>>>>>        "Add otherLink  after link in the list. Answer aLink."
>>>>>
>>>>> +       | otherLink |
>>>>> +       otherLink := self linkAt: (self indexOf: otherLinkOrObject).
>>>>> +       ^ self add: link afterLink: otherLink!
>>>>> -       | savedLink |
>>>>> -       lastLink == otherLink ifTrue: [^ self addLast: link].
>>>>> -       savedLink := otherLink nextLink.
>>>>> -       otherLink nextLink: link.
>>>>> -       link nextLink:  savedLink.
>>>>> -       ^link.!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>add:afterLink: (in category 'adding') -----
>>>>> + add: aLinkOrObject afterLink: otherLink
>>>>> +
>>>>> +       "Add otherLink  after link in the list. Answer aLink."
>>>>> +
>>>>> +       | savedLink aLink |
>>>>> +       lastLink == otherLink ifTrue: [^ self addLast: aLinkOrObject].
>>>>> +       savedLink := otherLink nextLink.
>>>>> +       aLink := aLinkOrObject asLink.
>>>>> +       otherLink nextLink: aLink.
>>>>> +       aLink nextLink:  savedLink.
>>>>> +       ^aLink.!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>add:before: (in category 'adding') -----
>>>>> + add: link before: otherLinkOrObject
>>>>> +       "Add otherLink  after link in the list. Answer aLink."
>>>>> - add: link before: otherLink
>>>>>
>>>>> +       | otherLink |
>>>>> +       otherLink := self linkAt: (self indexOf: otherLinkOrObject).
>>>>> +       ^ self add: link beforeLink: otherLink!
>>>>> -       | aLink |
>>>>> -       firstLink == otherLink ifTrue: [^ self addFirst: link].
>>>>> -       aLink := firstLink.
>>>>> -       [aLink == nil] whileFalse: [
>>>>> -               aLink nextLink == otherLink ifTrue: [
>>>>> -                       link nextLink: aLink nextLink.
>>>>> -                       aLink nextLink: link.
>>>>> -                       ^ link
>>>>> -               ].
>>>>> -                aLink := aLink nextLink.
>>>>> -       ].
>>>>> -       ^ self errorNotFound: otherLink!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>add:beforeLink: (in category 'adding')
>>>>> -----
>>>>> + add: aLinkOrObject beforeLink: otherLink
>>>>> +
>>>>> +       | currentLink|
>>>>> +
>>>>> +       firstLink == otherLink ifTrue: [^ self addFirst:
>>>>> aLinkOrObject].
>>>>> +
>>>>> +       currentLink := firstLink.
>>>>> +       [currentLink == nil] whileFalse: [
>>>>> +               currentLink nextLink == otherLink ifTrue: [
>>>>> +                       | aLink |
>>>>> +                       aLink := aLinkOrObject asLink.
>>>>> +                       aLink nextLink: currentLink nextLink.
>>>>> +                       currentLink nextLink: aLink.
>>>>> +                       ^ aLink
>>>>> +               ].
>>>>> +                currentLink := currentLink nextLink.
>>>>> +       ].
>>>>> +       ^ self errorNotFound: otherLink!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>addFirst: (in category 'adding') -----
>>>>> + addFirst: aLinkOrObject
>>>>> - addFirst: aLink
>>>>>        "Add aLink to the beginning of the receiver's list. Answer
>>>>> aLink."
>>>>> +       |aLink|
>>>>> +       aLink := aLinkOrObject asLink.
>>>>> -
>>>>>        self isEmpty ifTrue: [lastLink := aLink].
>>>>>        aLink nextLink: firstLink.
>>>>>        firstLink := aLink.
>>>>>        ^aLink!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>addLast: (in category 'adding') -----
>>>>> + addLast: aLinkOrObject
>>>>> - addLast: aLink
>>>>>        "Add aLink to the end of the receiver's list. Answer aLink."
>>>>> +       |aLink|
>>>>> +       aLink := aLinkOrObject asLink.
>>>>> -
>>>>>        self isEmpty
>>>>>                ifTrue: [firstLink := aLink]
>>>>>                ifFalse: [lastLink nextLink: aLink].
>>>>>        lastLink := aLink.
>>>>>        ^aLink!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>at: (in category 'accessing') -----
>>>>>  at: index
>>>>>
>>>>> +       ^(self linkAt: index) value!
>>>>> -       | i |
>>>>> -       i := 0.
>>>>> -       self do: [:link |
>>>>> -               (i := i + 1) = index ifTrue: [^ link]].
>>>>> -       ^ self errorSubscriptBounds: index!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>at:put: (in category 'accessing') -----
>>>>> + at: index put: anObject
>>>>> +
>>>>> +       ^self at: index putLink: (self linkOf: anObject ifAbsent:
>>>>> [anObject asLink])!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>at:putLink: (in category 'accessing') -----
>>>>> + at: index putLink: aLink
>>>>> +       | previousLink nextLink |
>>>>> +       "Please don't put a link which is already in the list, or you
>>>>> will create an infinite loop"
>>>>> +       (self validIndex: index) ifFalse: [^ self errorOutOfBounds].
>>>>> +
>>>>> +       index = 1 ifTrue: [
>>>>> +               aLink nextLink: self firstLink nextLink.
>>>>> +               firstLink := aLink.
>>>>> +               aLink nextLink ifNil: [lastLink := aLink].
>>>>> +               ^ aLink].
>>>>> +
>>>>> +       previousLink := self linkAt: index - 1.
>>>>> +       nextLink := previousLink nextLink nextLink.
>>>>> +
>>>>> +       nextLink
>>>>> +               ifNil: [aLink nextLink: self lastLink]
>>>>> +               ifNotNil: [:link |aLink nextLink: link].
>>>>> +
>>>>> +       previousLink nextLink: aLink.
>>>>> +
>>>>> +       nextLink ifNil: [
>>>>> +               lastLink := aLink.
>>>>> +               aLink nextLink: nil].
>>>>> +
>>>>> +       ^ aLink!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>collect: (in category 'enumerating') -----
>>>>> + collect: aBlock
>>>>> +       "Evaluate aBlock with each of the receiver's elements as the
>>>>> argument.
>>>>> +       Collect the resulting values into a collection like the
>>>>> receiver. Answer
>>>>> +       the new collection."
>>>>> +
>>>>> +       | aLink newCollection |
>>>>> +       newCollection := self class new.
>>>>> +       aLink := firstLink.
>>>>> +       [aLink == nil] whileFalse:
>>>>> +               [newCollection add: (aBlock value: aLink value).
>>>>> +                aLink := aLink nextLink].
>>>>> +       ^ newCollection!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>collect:thenSelect: (in category
>>>>> 'enumerating') -----
>>>>> + collect: collectBlock thenSelect: selectBlock
>>>>> +       "Optimized version of
>>>>> SequenceableCollection>>#collect:#thenSelect:"
>>>>> +
>>>>> +       | newCollection newElement |
>>>>> +       newCollection := self class new.
>>>>> +       self
>>>>> +               do: [ :each |
>>>>> +                       newElement := collectBlock value: each.
>>>>> +                       (selectBlock value: newElement)
>>>>> +                               ifTrue: [ newCollection add: newElement
>>>>> ] ].
>>>>> +       ^ newCollection!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>copyWith: (in category 'copying') -----
>>>>> + copyWith: newElement
>>>>> +       ^self copy add: newElement; yourself!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>copyWithout: (in category 'copying') -----
>>>>> + copyWithout: oldElement
>>>>> +       |newInst|
>>>>> +       newInst := self class new.
>>>>> +       self do: [:each | each = oldElement ifFalse: [newInst add:
>>>>> each]].
>>>>> +       ^newInst!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>do: (in category 'enumerating') -----
>>>>>  do: aBlock
>>>>>
>>>>>        | aLink |
>>>>>        aLink := firstLink.
>>>>>        [aLink == nil] whileFalse:
>>>>> +               [aBlock value: aLink value.
>>>>> -               [aBlock value: aLink.
>>>>>                 aLink := aLink nextLink]!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>first (in category 'accessing') -----
>>>>>  first
>>>>>        "Answer the first link. Create an error notification if the
>>>>> receiver is
>>>>>        empty."
>>>>>
>>>>> +       ^ self firstLink value!
>>>>> -       self emptyCheck.
>>>>> -       ^firstLink!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>firstLink (in category 'accessing') -----
>>>>> + firstLink
>>>>> +       "Answer the first link. Create an error notification if the
>>>>> receiver is
>>>>> +       empty."
>>>>> +
>>>>> +       self emptyCheck.
>>>>> +       ^firstLink!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>indexOf:startingAt:ifAbsent: (in category
>>>>> 'private') -----
>>>>> + indexOf: anElement startingAt: start ifAbsent: exceptionBlock
>>>>> +       "Answer the index of the first occurence of anElement after
>>>>> start
>>>>> +       within the receiver. If the receiver does not contain
>>>>> anElement,
>>>>> +       answer the      result of evaluating the argument,
>>>>> exceptionBlock."
>>>>> +
>>>>> +       |currentLink index|
>>>>> +       currentLink := self linkAt: start ifAbsent: [nil].
>>>>> +       index := start.
>>>>> +       [currentLink isNil ]
>>>>> +               whileFalse: [currentLink value = anElement value
>>>>> ifTrue: [^index].
>>>>> +                                       currentLink := currentLink
>>>>> nextLink.
>>>>> +                                       index := index +1].
>>>>> +       ^exceptionBlock value!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>isEmpty (in category 'testing') -----
>>>>>  isEmpty
>>>>>
>>>>> +       ^ firstLink isNil!
>>>>> -       ^firstLink == nil!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>last (in category 'accessing') -----
>>>>>  last
>>>>>        "Answer the last link. Create an error notification if the
>>>>> receiver is
>>>>>        empty."
>>>>>
>>>>> +
>>>>> +       ^self lastLink value!
>>>>> -       self emptyCheck.
>>>>> -       ^lastLink!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>lastLink (in category 'accessing') -----
>>>>> + lastLink
>>>>> +       "Answer the last link. Create an error notification if the
>>>>> receiver is
>>>>> +       empty."
>>>>> +
>>>>> +       self emptyCheck.
>>>>> +       ^lastLink!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>linkAt: (in category 'private') -----
>>>>> + linkAt: index
>>>>> +
>>>>> +       ^self linkAt: index ifAbsent: [ self errorSubscriptBounds:
>>>>> index]!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>linkAt:ifAbsent: (in category 'private')
>>>>> -----
>>>>> + linkAt: index ifAbsent: errorBlock
>>>>> +
>>>>> +       | i |
>>>>> +       i := 0.
>>>>> +       self linksDo: [:link | (i := i + 1) = index ifTrue: [^ link]].
>>>>> +       ^ errorBlock value!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>linkOf: (in category 'private') -----
>>>>> + linkOf: anObject
>>>>> +
>>>>> +       ^ self
>>>>> +               linkOf: anObject
>>>>> +               ifAbsent: [self error: 'No such element']!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>linkOf:ifAbsent: (in category 'private')
>>>>> -----
>>>>> + linkOf: anObject ifAbsent: errorBlock
>>>>> +
>>>>> +       self    linksDo: [:link | link value = anObject value ifTrue:
>>>>> [^ link]].
>>>>> +       ^ errorBlock value!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>linksDo: (in category 'enumerating') -----
>>>>> + linksDo: aBlock
>>>>> +
>>>>> +       | aLink |
>>>>> +       aLink := firstLink.
>>>>> +       [aLink == nil] whileFalse:
>>>>> +               [aBlock value: aLink.
>>>>> +                aLink := aLink nextLink]!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>postCopy (in category 'copying') -----
>>>>>  postCopy
>>>>>        | aLink |
>>>>>        super postCopy.
>>>>> +       firstLink ifNotNil: [
>>>>> -       firstLink isNil ifFalse: [
>>>>>                aLink := firstLink := firstLink copy.
>>>>>                [aLink nextLink isNil] whileFalse: [aLink nextLink:
>>>>> (aLink := aLink nextLink copy)].
>>>>>                lastLink := aLink].!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>remove:ifAbsent: (in category 'removing')
>>>>> -----
>>>>> + remove: aLinkOrObject ifAbsent: aBlock
>>>>> +       "Remove aLink from the receiver. If it is not there, answer the
>>>>> result of evaluating aBlock."
>>>>> +
>>>>> +       | link |
>>>>> +       link := self linkOf: aLinkOrObject ifAbsent: [^aBlock value].
>>>>> +       self removeLink: link ifAbsent: [^aBlock value].
>>>>> +       ^aLinkOrObject!
>>>>> - remove: aLink ifAbsent: aBlock
>>>>> -       "Remove aLink from the receiver. If it is not there, answer the
>>>>> result of
>>>>> -       evaluating aBlock."
>>>>> -
>>>>> -       | tempLink |
>>>>> -       aLink == firstLink
>>>>> -               ifTrue: [firstLink := aLink nextLink.
>>>>> -                               aLink == lastLink
>>>>> -                                       ifTrue: [lastLink := nil]]
>>>>> -               ifFalse: [tempLink := firstLink.
>>>>> -                               [tempLink == nil ifTrue: [^aBlock
>>>>> value].
>>>>> -                                tempLink nextLink == aLink]
>>>>> -                                       whileFalse: [tempLink :=
>>>>> tempLink nextLink].
>>>>> -                               tempLink nextLink: aLink nextLink.
>>>>> -                               aLink == lastLink
>>>>> -                                       ifTrue: [lastLink :=
>>>>> tempLink]].
>>>>> -       aLink nextLink: nil.
>>>>> -       ^aLink!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>removeAllSuchThat: (in category 'removing')
>>>>> -----
>>>>> + removeAllSuchThat: aBlock
>>>>> +       "Evaluate aBlock for each element and remove all that elements
>>>>> from
>>>>> +       the receiver for that aBlock evaluates to true.  For
>>>>> LinkedLists, it's safe to use do:."
>>>>> +
>>>>> +       self do: [:each | (aBlock value: each) ifTrue: [self remove:
>>>>> each]]!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>removeFirst (in category 'removing') -----
>>>>>  removeFirst
>>>>>        "Remove the first element and answer it. If the receiver is
>>>>> empty, create
>>>>>        an error notification."
>>>>>
>>>>>        | oldLink |
>>>>>        self emptyCheck.
>>>>>        oldLink := firstLink.
>>>>>        firstLink == lastLink
>>>>>                ifTrue: [firstLink := nil. lastLink := nil]
>>>>>                ifFalse: [firstLink := oldLink nextLink].
>>>>>        oldLink nextLink: nil.
>>>>> +       ^oldLink value!
>>>>> -       ^oldLink!
>>>>>
>>>>> Item was changed:
>>>>>  ----- Method: LinkedList>>removeLast (in category 'removing') -----
>>>>>  removeLast
>>>>>        "Remove the receiver's last element and answer it. If the
>>>>> receiver is
>>>>>        empty, create an error notification."
>>>>>
>>>>>        | oldLink aLink |
>>>>>        self emptyCheck.
>>>>>        oldLink := lastLink.
>>>>>        firstLink == lastLink
>>>>>                ifTrue: [firstLink := nil. lastLink := nil]
>>>>>                ifFalse: [aLink := firstLink.
>>>>>                                [aLink nextLink == oldLink] whileFalse:
>>>>>                                        [aLink := aLink nextLink].
>>>>>                                 aLink nextLink: nil.
>>>>>                                 lastLink := aLink].
>>>>>        oldLink nextLink: nil.
>>>>> +       ^oldLink value!
>>>>> -       ^oldLink!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>removeLink: (in category 'removing') -----
>>>>> + removeLink: aLink
>>>>> +       ^self removeLink: aLink ifAbsent: [self error: 'no such
>>>>> method!!']!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>removeLink:ifAbsent: (in category
>>>>> 'removing') -----
>>>>> + removeLink: aLink ifAbsent: aBlock
>>>>> +       "Remove aLink from the receiver. If it is not there, answer the
>>>>> result of
>>>>> +       evaluating aBlock."
>>>>> +
>>>>> +       | tempLink |
>>>>> +       aLink == firstLink
>>>>> +               ifTrue: [firstLink := aLink nextLink.
>>>>> +                               aLink == lastLink
>>>>> +                                       ifTrue: [lastLink := nil]]
>>>>> +               ifFalse: [tempLink := firstLink.
>>>>> +                               [tempLink == nil ifTrue: [^aBlock
>>>>> value].
>>>>> +                                tempLink nextLink == aLink]
>>>>> +                                       whileFalse: [tempLink :=
>>>>> tempLink nextLink].
>>>>> +                               tempLink nextLink: aLink nextLink.
>>>>> +                               aLink == lastLink
>>>>> +                                       ifTrue: [lastLink :=
>>>>> tempLink]].
>>>>> +       "Not nilling the link enables us to delete while iterating"
>>>>> +       "aLink nextLink: nil."
>>>>> +       ^aLink!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>select: (in category 'enumerating') -----
>>>>> + select: aBlock
>>>>> +       "Reimplemennt #select: for speedup on linked lists.
>>>>> +       The super implemention accesses the linkes by index, thus
>>>>> causing an O(n^2)"
>>>>> +
>>>>> +       | newCollection |
>>>>> +       newCollection := self class new.
>>>>> +       self do: [:each | (aBlock value: each) ifTrue: [newCollection
>>>>> add: each]].
>>>>> +       ^newCollection!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>select:thenCollect: (in category
>>>>> 'enumerating') -----
>>>>> + select: selectBlock thenCollect: collectBlock
>>>>> +       "Optimized version of
>>>>> SequenceableCollection>>#select:thenCollect:"
>>>>> +
>>>>> +       | newCollection |
>>>>> +       newCollection := self class new.
>>>>> +       self    do: [ :each | (selectBlock value: each) ifTrue:
>>>>> [newCollection add: (collectBlock value: each)]].
>>>>> +       ^ newCollection!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>swap:with: (in category 'accessing') -----
>>>>> + swap: ix1 with: ix2
>>>>> +       "Reimplemented, super would create an infinite loop"
>>>>> +       | minIx maxIx link1Prev link2Prev link1 link2 link1Next
>>>>> link2Next newLink2Next |
>>>>> +       ((self validIndex: ix1) and: [self validIndex: ix2])
>>>>> ifFalse: [^ self errorOutOfBounds].
>>>>> +
>>>>> +       "Get edge case out of the way"
>>>>> +       ix1 = ix2 ifTrue: [^ self ].
>>>>> +
>>>>> +       "Sort indexes to make boundary-checks easier"
>>>>> +       minIx := ix1 min: ix2.
>>>>> +       maxIx := ix2 max: ix1.
>>>>> +
>>>>> +       link1Prev := (minIx = 1) ifFalse: [self linkAt: minIx -1].
>>>>> +       link1 := link1Prev ifNotNil: [ link1Prev nextLink]
>>>>> +                               ifNil: [self linkAt: minIx].
>>>>> +       link1Next := link1 nextLink.
>>>>> +       link2Prev := self linkAt: maxIx -1.
>>>>> +       link2 := link2Prev nextLink.
>>>>> +       link2Next := link2 nextLink.
>>>>> +
>>>>> +       "Link at start being swapped"
>>>>> +       link1 = firstLink ifTrue: [firstLink := link2.] ifFalse:
>>>>> [link1Prev nextLink: link2].
>>>>> +       "Link at end being swapped"
>>>>> +       link2 = lastLink ifTrue: [lastLink := link1] ifFalse: [].
>>>>> +       "Links  being swapped adjacent"
>>>>> +       newLink2Next := (link1 nextLink = link2) ifTrue: [link1]
>>>>> ifFalse: [link2Prev nextLink: link1.
>>>>> +               link1Next].
>>>>> +       link1 nextLink: link2Next.
>>>>> +       link2 nextLink: newLink2Next.
>>>>> +       !
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: LinkedList>>validIndex: (in category 'private') -----
>>>>> + validIndex: index
>>>>> +
>>>>> +        ^ index > 0 and: [index <= self size]!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: Object>>asLink (in category '*collections') -----
>>>>> + asLink
>>>>> +
>>>>> +       ^ ValueLink value: self!
>>>>>
>>>>> Item was added:
>>>>> + Link subclass: #ValueLink
>>>>> +       instanceVariableNames: 'value'
>>>>> +       classVariableNames: ''
>>>>> +       poolDictionaries: ''
>>>>> +       category: 'Collections-Support'!
>>>>> +
>>>>> + !ValueLink commentStamp: 'HenrikSperreJohansen 10/18/2009 15:57'
>>>>> prior: 0!
>>>>> + A ValueLink is a Link containing a Value.
>>>>> + Adding an object to a LinkedList which is not a Link will create a
>>>>> ValueLink containing that object.
>>>>> +
>>>>> +
>>>>> + value - The object this link points to.!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: ValueLink class>>value: (in category 'instance
>>>>> creation') -----
>>>>> + value: aValue
>>>>> +
>>>>> +       ^self new value: aValue!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: ValueLink>>= (in category 'comparing') -----
>>>>> + = anotherObject
>>>>> +
>>>>> +       ^self species == anotherObject species
>>>>> +       and: [self value = anotherObject value
>>>>> +       and: [self nextLink == anotherObject nextLink]]!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: ValueLink>>hash (in category 'comparing') -----
>>>>> + hash
>>>>> +
>>>>> +       ^self value hash bitXor: self nextLink identityHash
>>>>> + !
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: ValueLink>>printOn: (in category 'printing') -----
>>>>> + printOn: aStream
>>>>> +
>>>>> +       super printOn: aStream.
>>>>> +       aStream nextPut: $(.
>>>>> +       value printOn: aStream.
>>>>> +       aStream nextPut: $)
>>>>> + !
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: ValueLink>>value (in category 'accessing') -----
>>>>> + value
>>>>> +
>>>>> +       ^ value!
>>>>>
>>>>> Item was added:
>>>>> + ----- Method: ValueLink>>value: (in category 'accessing') -----
>>>>> + value: anObject
>>>>> +
>>>>> +       value := anObject.!
>>>>>
>>>>>
>>>
>


More information about the Squeak-dev mailing list