585 beginAndSizeOfCycle

   586     "true if the list contains a cycle.

   587      Floyd's cycle-finding algorithm"

   588 

   589     |t h i loopStartIndex loopSize|

   590 

   591     t := self cdr. t isNil ifTrue:[^ nil].

   592     h := t cdr. h isNil ifTrue:[^ nil].

   593 

   594     [t ~~ h] whileTrue:[

   595         t := t cdr.

   596         h := h cdr. h isNil ifTrue:[^ nil].

   597         h := h cdr. h isNil ifTrue:[^ nil].

   598     ].

   599 

   600     "/ both h and t are now inside the cycle,

   601     "/ equidistant from the start of the cycle

   602     t := self.

   603     i := 1.

   604     [t ~~ h] whileTrue:[

   605         t := t cdr.

   606         h := h cdr.

   607         i := i + 1.

   608     ].

   609     loopStartIndex := i.

   610 

   611     loopSize := 1.

   612     h := t cdr.

   613     [t ~~ h] whileTrue:[

   614         h := h cdr.

   615         i := i + 1.

   616         loopSize := loopSize + 1.

   617     ].

   618     

   619     ^ { loopStartIndex. loopSize }

   620 

   621     "

   622      |n1 n2 n3 n4 n5|

   623 

   624      n1 := Cons new car:1.

   625      n2 := Cons new car:2.

   626      n3 := Cons new car:3.

   627      n4 := Cons new car:4.

   628      n5 := Cons new car:5.

   629      n1 cdr: n2.

   630      n2 cdr: n3.

   631      n3 cdr: n4.

   632      n4 cdr: n5.

   633      n1 beginAndSizeOfCycle.      

   634      n5 cdr: n3.    

   635      n1 beginAndSizeOfCycle.             

   636     "

   637 

   638     "Created: / 27-07-2012 / 00:00:36 / cg"

   639 !

   640 

   643 !

   644 

   645 isCyclic

   646     "true if the list contains a cycle"

   647 

   648     ^ self beginAndSizeOfCycle notNil

   649 

   650     "

   651      |n1 n2 n3 n4 n5|

   652 

   653      n1 := Cons new car:1.

   654      n2 := Cons new car:2.

   655      n3 := Cons new car:3.

   656      n4 := Cons new car:4.

   657      n5 := Cons new car:5.

   658      n1 cdr: n2.

   659      n2 cdr: n3.

   660      n3 cdr: n4.

   661      n4 cdr: n5.

   662      n1 isCyclic.

   663      n5 cdr: n3.    

   664      n1 isCyclic.   

   665     "

   666 

   667     "Created: / 26-07-2012 / 23:32:52 / cg"