=============== Summary ===============
Change Set: LinkedList copyFromTo Date: 10 January 2024 Author: Christoph Thiede
Adds efficient version of LinkedList>>#copyFrom:to: and tests edge cases.
=============== Diff ===============
LinkedList>>copyFrom:to: {copying} · ct 1/10/2024 17:55 + copyFrom: startIndex to: stopIndex + "Optimized for copying in O(n) instead of O(n^2)." + + | copy i | + startIndex <= 0 ifTrue: [^ self error: 'startIndex is out of bounds']. + stopIndex < 0 ifTrue: [^ self error: 'stopIndex is out of bounds']. + copy := self class new. + i := 0. + self linksDo: [:link | + (i := i + 1) >= startIndex ifTrue: + [i > stopIndex ifTrue: [^ copy]. + copy addLast: link value]]. + i + 1 < startIndex ifTrue: [^ self error: 'startIndex is out of bounds']. + i >= stopIndex ifTrue: [^ copy]. + ^ self error: 'stopIndex is out of bounds'
LinkedListTest>>testCopyFromToBounds {tests - copying part of sequenceable} · ct 1/10/2024 17:31 + testCopyFromToBounds + | collection | + collection := self collectionWithoutEqualElements . + + self + should: [collection copyFrom: 0 to: -1] + raise: Error. + self assert: (collection copyFrom: 1 to: 0) isEmpty. + self assert: (collection copyFrom: 2 to: 1) isEmpty. + self assert: (collection copyFrom: collection size to: collection size - 1) isEmpty. + self assert: (collection copyFrom: collection size + 1 to: collection size) isEmpty. + self + should: [collection copyFrom: collection size + 2 to: collection size + 1] + raise: Error. + + self + should: [collection copyFrom: 0 to: 0] + raise: Error. + self assert: (collection copyFrom: 1 to: 1) asArray = {collection first}. + self assert: (collection copyFrom: collection size to: collection size) asArray = {collection last}. + self + should: [collection copyFrom: collection size + 1 to: collection size + 1] + raise: Error. + + self assert: (collection copyFrom: 1 to: collection size) = collection. + self + should: [collection copyFrom: 0 to: collection size] + raise: Error. + self + should: [collection copyFrom: 1 to: collection size + 1] + raise: Error. + + self + should: [collection copyFrom: 1 to: -1] + raise: Error. + self assert: (collection copyFrom: 2 to: 0) isEmpty. + self assert: (collection copyFrom: collection size + 1 to: collection size - 1) isEmpty. + self + should: [collection copyFrom: collection size + 2 to: collection size] + raise: Error.
--- Sent from Squeak Inbox Talk ["LinkedList copyFromTo.1.cs"]
Note that this changes the return type of #copyFrom:to: from Array to LinkedList (or its respective subclass). But I think this makes even more sense?
Best, Christoph ________________________________ Von: Thiede, Christoph christoph.thiede@student.hpi.uni-potsdam.de Gesendet: Mittwoch, 10. Januar 2024 17:56 Uhr An: squeak-dev@lists.squeakfoundation.org squeak-dev@lists.squeakfoundation.org Betreff: [squeak-dev] Review Request: LinkedList copyFromTo.1.cs
=============== Summary ===============
Change Set: LinkedList copyFromTo Date: 10 January 2024 Author: Christoph Thiede
Adds efficient version of LinkedList>>#copyFrom:to: and tests edge cases.
=============== Diff ===============
LinkedList>>copyFrom:to: {copying} · ct 1/10/2024 17:55 + copyFrom: startIndex to: stopIndex + "Optimized for copying in O(n) instead of O(n^2)." + + | copy i | + startIndex <= 0 ifTrue: [^ self error: 'startIndex is out of bounds']. + stopIndex < 0 ifTrue: [^ self error: 'stopIndex is out of bounds']. + copy := self class new. + i := 0. + self linksDo: [:link | + (i := i + 1) >= startIndex ifTrue: + [i > stopIndex ifTrue: [^ copy]. + copy addLast: link value]]. + i + 1 < startIndex ifTrue: [^ self error: 'startIndex is out of bounds']. + i >= stopIndex ifTrue: [^ copy]. + ^ self error: 'stopIndex is out of bounds'
LinkedListTest>>testCopyFromToBounds {tests - copying part of sequenceable} · ct 1/10/2024 17:31 + testCopyFromToBounds + | collection | + collection := self collectionWithoutEqualElements . + + self + should: [collection copyFrom: 0 to: -1] + raise: Error. + self assert: (collection copyFrom: 1 to: 0) isEmpty. + self assert: (collection copyFrom: 2 to: 1) isEmpty. + self assert: (collection copyFrom: collection size to: collection size - 1) isEmpty. + self assert: (collection copyFrom: collection size + 1 to: collection size) isEmpty. + self + should: [collection copyFrom: collection size + 2 to: collection size + 1] + raise: Error. + + self + should: [collection copyFrom: 0 to: 0] + raise: Error. + self assert: (collection copyFrom: 1 to: 1) asArray = {collection first}. + self assert: (collection copyFrom: collection size to: collection size) asArray = {collection last}. + self + should: [collection copyFrom: collection size + 1 to: collection size + 1] + raise: Error. + + self assert: (collection copyFrom: 1 to: collection size) = collection. + self + should: [collection copyFrom: 0 to: collection size] + raise: Error. + self + should: [collection copyFrom: 1 to: collection size + 1] + raise: Error. + + self + should: [collection copyFrom: 1 to: -1] + raise: Error. + self assert: (collection copyFrom: 2 to: 0) isEmpty. + self assert: (collection copyFrom: collection size + 1 to: collection size - 1) isEmpty. + self + should: [collection copyFrom: collection size + 2 to: collection size] + raise: Error.
--- Sent from Squeak Inbox Talkhttps://github.com/hpi-swa-lab/squeak-inbox-talk ["LinkedList copyFromTo.1.cs"]
Hi Christoph --
Note that this changes the return type of #copyFrom:to: from Array to LinkedList (or its respective subclass). But I think this makes even more sense?
Yeah, I would consider this a bug in LinkedList that we should fix. :-) BUT why did somebody implement #species in LinkedList as Array?! We should honor this or change this. Hmm....
Note that Stack uses a LinkedList internally. We should be fine.
Well, if we change #species in LinkedList to itself, we MUST overwrite it in Mutex, Semaphore, Monitor to still fall-back to Array. Tricky ... I assume that, currently, nobody uses LinkedList but only Array (via OrderedCollection etc.) to store data? Hmm...
Not sure. :-)
Best, Marcel
Am 10.01.2024 18:08:06 schrieb Thiede, Christoph christoph.thiede@student.hpi.uni-potsdam.de:
Note that this changes the return type of #copyFrom:to: from Array to LinkedList (or its respective subclass). But I think this makes even more sense?
Best, Christoph ________________________________ Von: Thiede, Christoph christoph.thiede@student.hpi.uni-potsdam.de Gesendet: Mittwoch, 10. Januar 2024 17:56 Uhr An: squeak-dev@lists.squeakfoundation.org squeak-dev@lists.squeakfoundation.org Betreff: [squeak-dev] Review Request: LinkedList copyFromTo.1.cs
=============== Summary ===============
Change Set: LinkedList copyFromTo Date: 10 January 2024 Author: Christoph Thiede
Adds efficient version of LinkedList>>#copyFrom:to: and tests edge cases.
=============== Diff ===============
LinkedList>>copyFrom:to: {copying} · ct 1/10/2024 17:55 + copyFrom: startIndex to: stopIndex + "Optimized for copying in O(n) instead of O(n^2)." + + | copy i | + startIndex <= 0 ifTrue: [^ self error: 'startIndex is out of bounds']. + stopIndex < 0 ifTrue: [^ self error: 'stopIndex is out of bounds']. + copy := self class new. + i := 0. + self linksDo: [:link | + (i := i + 1) >= startIndex ifTrue: + [i > stopIndex ifTrue: [^ copy]. + copy addLast: link value]]. + i + 1 < startIndex ifTrue: [^ self error: 'startIndex is out of bounds']. + i >= stopIndex ifTrue: [^ copy]. + ^ self error: 'stopIndex is out of bounds'
LinkedListTest>>testCopyFromToBounds {tests - copying part of sequenceable} · ct 1/10/2024 17:31 + testCopyFromToBounds + | collection | + collection := self collectionWithoutEqualElements . + + self + should: [collection copyFrom: 0 to: -1] + raise: Error. + self assert: (collection copyFrom: 1 to: 0) isEmpty. + self assert: (collection copyFrom: 2 to: 1) isEmpty. + self assert: (collection copyFrom: collection size to: collection size - 1) isEmpty. + self assert: (collection copyFrom: collection size + 1 to: collection size) isEmpty. + self + should: [collection copyFrom: collection size + 2 to: collection size + 1] + raise: Error. + + self + should: [collection copyFrom: 0 to: 0] + raise: Error. + self assert: (collection copyFrom: 1 to: 1) asArray = {collection first}. + self assert: (collection copyFrom: collection size to: collection size) asArray = {collection last}. + self + should: [collection copyFrom: collection size + 1 to: collection size + 1] + raise: Error. + + self assert: (collection copyFrom: 1 to: collection size) = collection. + self + should: [collection copyFrom: 0 to: collection size] + raise: Error. + self + should: [collection copyFrom: 1 to: collection size + 1] + raise: Error. + + self + should: [collection copyFrom: 1 to: -1] + raise: Error. + self assert: (collection copyFrom: 2 to: 0) isEmpty. + self assert: (collection copyFrom: collection size + 1 to: collection size - 1) isEmpty. + self + should: [collection copyFrom: collection size + 2 to: collection size] + raise: Error.
--- Sent from Squeak Inbox Talkhttps://github.com/hpi-swa-lab/squeak-inbox-talk ["LinkedList copyFromTo.1.cs"]
squeak-dev@lists.squeakfoundation.org