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/
