--- a/Cons.st Fri Jul 20 20:38:41 2012 +0200
+++ b/Cons.st Fri Jul 27 00:04:19 2012 +0200
@@ -582,10 +582,91 @@
!Cons methodsFor:'queries'!
+beginAndSizeOfCycle
+ "true if the list contains a cycle.
+ Floyd's cycle-finding algorithm"
+
+ |t h i loopStartIndex loopSize|
+
+ t := self cdr. t isNil ifTrue:[^ nil].
+ h := t cdr. h isNil ifTrue:[^ nil].
+
+ [t ~~ h] whileTrue:[
+ t := t cdr.
+ h := h cdr. h isNil ifTrue:[^ nil].
+ h := h cdr. h isNil ifTrue:[^ nil].
+ ].
+
+ "/ both h and t are now inside the cycle,
+ "/ equidistant from the start of the cycle
+ t := self.
+ i := 1.
+ [t ~~ h] whileTrue:[
+ t := t cdr.
+ h := h cdr.
+ i := i + 1.
+ ].
+ loopStartIndex := i.
+
+ loopSize := 1.
+ h := t cdr.
+ [t ~~ h] whileTrue:[
+ h := h cdr.
+ i := i + 1.
+ loopSize := loopSize + 1.
+ ].
+
+ ^ { loopStartIndex. loopSize }
+
+ "
+ |n1 n2 n3 n4 n5|
+
+ n1 := Cons new car:1.
+ n2 := Cons new car:2.
+ n3 := Cons new car:3.
+ n4 := Cons new car:4.
+ n5 := Cons new car:5.
+ n1 cdr: n2.
+ n2 cdr: n3.
+ n3 cdr: n4.
+ n4 cdr: n5.
+ n1 beginAndSizeOfCycle.
+ n5 cdr: n3.
+ n1 beginAndSizeOfCycle.
+ "
+
+ "Created: / 27-07-2012 / 00:00:36 / cg"
+!
+
isCons
^ true
!
+isCyclic
+ "true if the list contains a cycle"
+
+ ^ self beginAndSizeOfCycle notNil
+
+ "
+ |n1 n2 n3 n4 n5|
+
+ n1 := Cons new car:1.
+ n2 := Cons new car:2.
+ n3 := Cons new car:3.
+ n4 := Cons new car:4.
+ n5 := Cons new car:5.
+ n1 cdr: n2.
+ n2 cdr: n3.
+ n3 cdr: n4.
+ n4 cdr: n5.
+ n1 isCyclic.
+ n5 cdr: n3.
+ n1 isCyclic.
+ "
+
+ "Created: / 26-07-2012 / 23:32:52 / cg"
+!
+
size
"for smalltalkers: the lists length"
@@ -615,9 +696,9 @@
!Cons class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic2/Cons.st,v 1.20 2011-09-27 09:42:46 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic2/Cons.st,v 1.21 2012-07-26 22:04:19 cg Exp $'
!
version_CVS
- ^ '$Header: /cvs/stx/stx/libbasic2/Cons.st,v 1.20 2011-09-27 09:42:46 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic2/Cons.st,v 1.21 2012-07-26 22:04:19 cg Exp $'
! !