# HG changeset patch
# User Claus Gittinger <cg@exept.de>
# Date 1343340259 -7200
# Node ID aaebdee8dba9a84b85d373ded83d50472bfb1bc3
# Parent  051b5bef3be7cca43ae6fc8f0cafa827665a4e26
added:
        #beginAndSizeOfCycle
        #beginOfCycle
        #isCyclic

diff -r 051b5bef3be7 -r aaebdee8dba9 Cons.st
--- 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 $'
 ! !