LinkedList>>#containsCycle
Locked
LinkedList>>#containsCycle
 
|
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 <[hidden email]> 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 > > |
|
|
In reply to this post by Sven Van Caekenberghe-2
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/ |
|
|
In reply to this post by Sven Van Caekenberghe-2
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/ |
|
|
In reply to this post by stepharo
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 <[hidden email]> 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 <[hidden email]> 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/ |
«
Return to Pharo Smalltalk Developers
|
1 view|%1 views
| Free forum by Nabble | Edit this page |