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
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 <sven@stfx.eu> 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
Hi Sven I'm collecting alternative Collection implementations in the project Container I do not remember if I have linkedList but we can add it there. You may wonder why I'm doing that? - I want to be able to have strong collections that are independent from the kernel - Ideally the kernel of Pharo should be mininmal so it means that I would like to have as few as possible as collections inside the bootstrapped kernel and that other collections are nicely packaged in Container. Now I can understand that others do not like what I'm doing but I will just continue. I have Grid, LinkedList, DoubleLinkedList, I have on my disc two implementation of Trees I should harvest BTrees and SkipList. If people want to help they are welcome, else I will just do it alone. Stef
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/
Hi Stef, Would it make sense to put the collection extensions from Moose in the Container project? Cheers, Doru
On Nov 26, 2016, at 12:11 PM, stepharo <stepharo@free.fr> wrote:
Hi Sven
I'm collecting alternative Collection implementations in the project Container I do not remember if I have linkedList but we can add it there.
You may wonder why I'm doing that? - I want to be able to have strong collections that are independent from the kernel - Ideally the kernel of Pharo should be mininmal so it means that I would like to have as few as possible as collections inside the bootstrapped kernel and that other collections are nicely packaged in Container.
Now I can understand that others do not like what I'm doing but I will just continue. I have Grid, LinkedList, DoubleLinkedList, I have on my disc two implementation of Trees I should harvest BTrees and SkipList.
If people want to help they are welcome, else I will just do it alone.
Stef
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/
-- www.tudorgirba.com www.feenk.com "Not knowing how to do something is not an argument for how it cannot be done."
Hi doru
Hi Stef,
Would it make sense to put the collection extensions from Moose in the Container project?
If you think it make sense. Yes. For example Ropes could be managed there. Have a look I have tiny packages. The idea is to make sure that - people can use one abstraction and not be forced to load a complete library - document them with tests and others - gather most of collections in one place to make sure that we do not lose energy reimplementing them. I'm packaging the collection from the image that have no users in the image for now. Then I will continue to package a Tree package (I tried to contact his author but may be he passed away) SkipList Quadtrees. Stef
Cheers, Doru
On Nov 26, 2016, at 12:11 PM, stepharo <stepharo@free.fr> wrote:
Hi Sven
I'm collecting alternative Collection implementations in the project Container I do not remember if I have linkedList but we can add it there.
You may wonder why I'm doing that? - I want to be able to have strong collections that are independent from the kernel - Ideally the kernel of Pharo should be mininmal so it means that I would like to have as few as possible as collections inside the bootstrapped kernel and that other collections are nicely packaged in Container.
Now I can understand that others do not like what I'm doing but I will just continue. I have Grid, LinkedList, DoubleLinkedList, I have on my disc two implementation of Trees I should harvest BTrees and SkipList.
If people want to help they are welcome, else I will just do it alone.
Stef
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/
-- www.tudorgirba.com www.feenk.com
"Not knowing how to do something is not an argument for how it cannot be done."
-- Using Opera's mail client: http://www.opera.com/mail/
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/
participants (4)
-
Max Leske -
stepharo -
Sven Van Caekenberghe -
Tudor Girba