I added to the CT package
Hi,
There exists a very elegant algorithm to detect cycles in linked lists.
https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare
I know that our LinkedList was written with the assumption that there
are no cycles. However, it seems to me that it would be nice to have a
test to check for cycles. This could be useful while printing or
inspecting a LinkedList (and prevent things from blowing up when there
is a cycle).
Here is the implementation:
LinkedList>>#containsCycle
| slow fast |
slow := fast := firstLink.
[ slow notNil and: [ fast notNil and: [ fast nextLink notNil ] ] ]
whileTrue: [
slow := slow nextLink.
fast := fast nextLink nextLink.
slow == fast
ifTrue: [ ^ true ] ].
^ false
And one of the tests:
LinkedListTests>>#testCycles
1 to: 42 do: [ :each |
list := LinkedList withAll: (1 to: each).
"Warning: the following statement creates a cylce,
inspecting/viewing list will probably fail"
list lastLink nextLink: list firstLink.
self assert: list containsCycle ]
Opinions ?
Sven
--
Using Opera's mail client: http://www.opera.com/mail/
