--- a/LinkedList.st Thu Jun 30 09:31:43 2016 +0100
+++ b/LinkedList.st Thu Jun 30 21:11:02 2016 +0100
@@ -1,5 +1,3 @@
-"{ Encoding: utf8 }"
-
"
COPYRIGHT (c) 1989 by Claus Gittinger
All Rights Reserved
@@ -92,7 +90,18 @@
examples
"
- [exBegin]
+ [exBegin]
+ |l|
+
+ l := LinkedList new.
+ l addLast:'one'.
+ l addLast:'two'.
+ l addLast:'three'.
+ l addLast:'four'.
+ l inspect
+ [exEnd]
+
+ [exBegin]
|l|
l := LinkedList new.
@@ -101,10 +110,9 @@
l addLast:(ValueLink new value:'three').
l addLast:(ValueLink new value:'four').
l inspect
- [exEnd]
+ [exEnd]
-
- [exBegin]
+ [exBegin]
|l|
l := LinkedList new.
@@ -113,10 +121,10 @@
l addLast:(ValueLink new value:'three').
l addLast:(ValueLink new value:'four').
(l at:3) value inspect. 'slow operation for large lists'.
- [exEnd]
+ [exEnd]
- [exBegin]
+ [exBegin]
|l link|
l := LinkedList new.
@@ -127,7 +135,7 @@
link := l removeFirst.
l addLast:link.
l inspect.
- [exEnd]
+ [exEnd]
"
! !
@@ -142,29 +150,27 @@
!LinkedList methodsFor:'accessing'!
at:index
- "return the n'th element - use of this method should be avoided,
+ "return the n'th value - use of this method should be avoided,
since it is slow to walk through the list - think about using
another collection if you need indexed access.
Notice:
that many methods in SeqColl are based on at:-access,
- so other inherited methods may be very slow (showing square runtime).
+ so other inherited methods may be very slow (showing O^2 runtime).
It is a very bad idea to access LinkedList elements by index.
many algorithms degenerate to poor performance if you do.
This method is provided for protocol completeness,
but please consider using another type of collection if you use it"
- self obsoleteFeatureWarning:'this will soon change to return the link''s value instead of the link itself'.
-
^ self at:index ifAbsent:[ self subscriptBoundsError:index]
!
at:index ifAbsent:exceptionBlock
- "return the n'th element - use of this method should be avoided,
+ "return the n'th value - use of this method should be avoided,
since it is slow to walk through the list - think about using
another collection if you need indexed access.
Notice:
that many methods in SeqColl are based on at:-access,
- so other inherited methods may be very slow (showing square runtime).
+ so other inherited methods may be very slow (showing O^2 runtime).
It is a very bad idea to access LinkedList elements by index.
many algorithms degenerate to poor performance if you do.
This method is provided for protocol completeness,
@@ -173,8 +179,6 @@
|theLink
runIndex "{Class: SmallInteger}"|
- self obsoleteFeatureWarning:'this will soon change to return the link''s value instead of the link itself'.
-
theLink := firstLink.
runIndex := 1.
[runIndex == index] whileFalse:[
@@ -182,24 +186,20 @@
theLink := theLink nextLink.
runIndex := runIndex + 1.
].
- ^ theLink
+ ^ theLink value
!
first
- "return the first node in the list"
+ "return the first value in the list"
- self obsoleteFeatureWarning:'this will soon change to return the link''s value instead of the link itself'.
-
- ^ self firstLink "value"
+ ^ self firstLink value
!
firstIfEmpty:exceptionalValue
- "return the first node in the list or exceptionlValue, if empty"
-
- self obsoleteFeatureWarning:'this will soon change to return the link''s value instead of the link itself'.
+ "return the first value in the list or exceptionlValue, if empty"
firstLink isNil ifTrue:[^ exceptionalValue value].
- ^ firstLink "value"
+ ^ firstLink value
!
firstLink
@@ -217,9 +217,7 @@
!
last
- "return last node in the list"
-
- self obsoleteFeatureWarning:'this will soon change to return the link''s value instead of the link itself'.
+ "return last value in the list"
lastLink isNil ifTrue:[^ self emptyCollectionError].
^ lastLink value
@@ -232,28 +230,13 @@
^ lastLink
!
-linkAt:index
- "return the n'th element - use of this method should be avoided,
+linkAt:index ifAbsent:exceptionBlock
+ "return the n'th link - use of this method should be avoided,
since it is slow to walk through the list - think about using
another collection if you need indexed access.
Notice:
that many methods in SeqColl are based on at:-access,
- so other inherited methods may be very slow (showing square runtime).
- It is a very bad idea to access LinkedList elements by index.
- many algorithms degenerate to poor performance if you do.
- This method is provided for protocol completeness,
- but please consider using another type of collection if you use it"
-
- ^ self linkAt:index ifAbsent:[ self subscriptBoundsError:index]
-!
-
-linkAt:index ifAbsent:exceptionBlock
- "return the n'th element - use of this method should be avoided,
- since it is slow to walk through the list - think about using
- another collection if you need indexed access.
- Notice:
- that many methods in SeqColl are based on at:-access,
- so other inherited methods may be very slow (showing square runtime).
+ so other inherited methods may be very slow (showing O^2 runtime).
It is a very bad idea to access LinkedList elements by index.
many algorithms degenerate to poor performance if you do.
This method is provided for protocol completeness,
@@ -292,18 +275,21 @@
^ newLink
!
-add:aLinkOrAnyOtherObject after:aLink
- "adds linkToAdd after another link, aLink. If aLink is nil,
- linkToAdd is inserted at the beginning. Returns linkToAdd."
+add:aLinkOrAnyOtherObject after:aLinkOrValue
+ "adds aLinkOrAnyOtherObject after another aLinkOrValue.
+ If aLinkOrValue is nil, linkToAdd is inserted at the beginning.
+ If aLinkOrValue is not in the list, linkToAdd is added at the end.
+ Returns aLinkOrAnyOtherObject."
- |this linkToAdd|
+ |this linkToAdd linkOrValue|
- aLink isNil ifTrue:[^ self addFirst:aLinkOrAnyOtherObject ].
+ aLinkOrValue isNil ifTrue:[^ self addFirst:aLinkOrAnyOtherObject ].
linkToAdd := aLinkOrAnyOtherObject asLink.
-
+ linkOrValue := aLinkOrValue value.
+
this := firstLink.
- [this notNil and:[this ~~ aLink]] whileTrue:[
+ [this notNil and:[this ~~ linkOrValue]] whileTrue:[
this := this nextLink
].
this isNil ifTrue:[^ self add:linkToAdd ].
@@ -329,14 +315,35 @@
^ linkToAdd
!
-remove:aLink ifAbsent:exceptionBlock
- "remove the argument, aLink from the sequence and return it;
- if absent, evaluate the exceptionBlock.
- Actually this is really a #removeIdentical (but for compatibility...)"
+remove:aLinkOrValue ifAbsent:exceptionBlock
+ "remove the argument, aLinkOrValue from the sequence and return it;
+ if absent, evaluate the exceptionBlock."
+
+ |prevNode nextNode thisNode linkOrValue|
- ^ self removeIdentical:aLink ifAbsent:exceptionBlock
+ linkOrValue := aLinkOrValue value.
+ thisNode := firstLink.
+ [thisNode notNil] whileTrue:[
+ nextNode := thisNode nextLink.
+ (thisNode value = linkOrValue) ifTrue:[
+ prevNode isNil ifTrue:[
+ firstLink := nextNode
+ ] ifFalse:[
+ prevNode nextLink:nextNode
+ ].
+ nextNode isNil ifTrue:[
+ lastLink := prevNode
+ ].
+ numberOfNodes := numberOfNodes - 1.
+ thisNode nextLink:nil.
+ ^ thisNode value
+ ].
+ prevNode := thisNode.
+ thisNode := nextNode
+ ].
+ ^ exceptionBlock value
- "Modified: / 30-11-2010 / 13:38:45 / cg"
+ "Created: / 30-11-2010 / 13:38:25 / cg"
!
removeAll
@@ -367,16 +374,17 @@
^ link
!
-removeIdentical:aLink ifAbsent:exceptionBlock
- "remove the argument, aLink from the sequence and return it;
+removeIdentical:aLinkOrValue ifAbsent:exceptionBlock
+ "remove the argument, aLinkOrValue from the sequence and return it;
if absent, evaluate the exceptionBlock."
- |prevNode nextNode thisNode|
+ |prevNode nextNode thisNode linkOrValue|
+ linkOrValue := aLinkOrValue value.
thisNode := firstLink.
[thisNode notNil] whileTrue:[
nextNode := thisNode nextLink.
- (thisNode == aLink) ifTrue:[
+ (thisNode value == linkOrValue) ifTrue:[
prevNode isNil ifTrue:[
firstLink := nextNode
] ifFalse:[
@@ -387,7 +395,7 @@
].
numberOfNodes := numberOfNodes - 1.
thisNode nextLink:nil.
- ^ aLink
+ ^ thisNode value
].
prevNode := thisNode.
thisNode := nextNode
@@ -479,10 +487,10 @@
!LinkedList methodsFor:'searching-equality'!
-indexOf:aLink startingAt:start
- "search the collection for aLink, starting the search at index start;
- if found, return the index otherwise return 0. Here, index is defined
- as the link-nodes position in the list.
+indexOf:aLinkOrValue startingAt:start
+ "search the collection for aLinkOrValue, starting the search at index start;
+ if found, return the index otherwise return 0.
+ Here, index is defined as the link-node's position in the list.
The comparison is done using = (i.e. equality test - not identity test).
Warning:
it is a very bad idea to access LinkedList elements by index.
@@ -491,8 +499,10 @@
but please consider using another type of collection if you use it.
"
- |theNode idx "{ Class: SmallInteger }"|
+ |theNode idx "{ Class: SmallInteger }"
+ linkOrValue|
+ linkOrValue := aLinkOrValue value.
theNode := firstLink.
idx := 1.
[idx < start] whileTrue:[
@@ -501,7 +511,7 @@
idx := idx + 1.
].
[theNode notNil] whileTrue:[
- (aLink = theNode) ifTrue:[^ idx].
+ (linkOrValue = theNode value) ifTrue:[^ idx].
theNode := theNode nextLink.
idx := idx + 1.
]. "reached the end"
@@ -527,20 +537,22 @@
!LinkedList methodsFor:'searching-identity'!
-identityIndexOf:aLink startingAt:start
- "search the collection for aLink, starting the search at index start;
- if found, return the index otherwise return 0. Here, index is defined
- as the link-nodes position in the list.
- The comparison is done using ==
- (i.e. identity test - not equality test).
- Notice:
- It is a very bad idea to access LinkedList elements by index.
+identityIndexOf:aLinkOrValue startingAt:start
+ "search the collection for aLinkOrValue, starting the search at index start;
+ if found, return the index otherwise return 0.
+ Here, index is defined as the link-node's position in the list.
+ The comparison is done using == (i.e. identity test - not equality test).
+ Warning:
+ it is a very bad idea to access LinkedList elements by index.
many algorithms degenerate to poor performance if you do.
This method is provided for protocol completeness,
- but please consider using another type of collection if you use it"
+ but please consider using another type of collection if you use it.
+ "
- |theNode idx "{ Class: SmallInteger }"|
+ |theNode idx "{ Class: SmallInteger }"
+ linkOrValue|
+ linkOrValue := aLinkOrValue value.
theNode := firstLink.
idx := 1.
[idx < start] whileTrue:[
@@ -549,7 +561,7 @@
idx := idx + 1.
].
[theNode notNil] whileTrue:[
- (aLink == theNode) ifTrue:[^ idx].
+ (linkOrValue == theNode value) ifTrue:[^ idx].
theNode := theNode nextLink.
idx := idx + 1.
]. "reached the end"
@@ -569,7 +581,7 @@
l add:(ValueLink new value:'one').
l add:(ValueLink new value:'two').
l add:(v := ValueLink new value:'hello').
- l identityIndexOf:v
+ l indexOf:v
"
! !
@@ -596,10 +608,10 @@
!LinkedList class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic/LinkedList.st,v 1.51 2015-03-02 15:14:00 cg Exp $'
+ ^ '$Header$'
!
version_CVS
- ^ '$Header: /cvs/stx/stx/libbasic/LinkedList.st,v 1.51 2015-03-02 15:14:00 cg Exp $'
+ ^ '$Header$'
! !