Very nice. In such a case I would like to know, which elements are causing the cycle or, alternatively, their positions. Maybe #cyclicElements?
Cheers, Max > On 24 Nov 2016, at 15:16, Sven Van Caekenberghe <[email protected]> wrote: > > 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 > >
