/** | |
* Copyright (c) 2009-2010 Thales Corporate Services S.A.S. | |
* This program and the accompanying materials | |
* are made available under the terms of the Eclipse Public License v2.0 | |
* which accompanies this distribution, and is available at | |
* https://www.eclipse.org/legal/epl-v2.0 | |
* | |
* SPDX-License-Identifier: EPL-2.0 | |
* | |
* Contributors: | |
* Thales Corporate Services S.A.S - initial API and implementation | |
*/ | |
package org.eclipse.egf.common.cycle; | |
/** | |
* @author Xavier Maysonnave | |
* | |
* Tortoise and hare | |
* Brent's cycle-finding algorithm | |
* http://en.wikipedia.org/wiki/Cycle_detection | |
* | |
*/ | |
public abstract class AbstractBrentCycleDetection<T> extends AbstractCycleDetection<T> { | |
private double _power; | |
public AbstractBrentCycleDetection() { | |
this(null); | |
} | |
public AbstractBrentCycleDetection(T element_p) { | |
super(element_p); | |
} | |
@Override | |
public void setElement(T element_p) { | |
super.setElement(element_p); | |
_power = 1; | |
_tortoise = element_p; | |
_hare = move(element_p); | |
} | |
@Override | |
public T getFirstRepetition() { | |
// is there something to process | |
if (_solvedFirstRepetition) { | |
return _firstRepetition; | |
} | |
// Search successive powers of two | |
while (_hare != null) { | |
if (_hare.equals(_tortoise)) { | |
// The hare has caught up with the tortoise | |
_firstRepetition = _hare; | |
break; | |
} | |
if (_power == _lambda) { | |
// Time to start a new power of two | |
_tortoise = _hare; | |
_power *= 2; | |
_lambda = 0; | |
} | |
// Move | |
_hare = move(_hare); | |
_lambda += 1; | |
} | |
// The hare reached the end | |
_solvedFirstRepetition = true; | |
_solvedLambda = true; | |
return _firstRepetition; | |
} | |
@Override | |
public int getMu() { | |
// is there something to process | |
if (_solvedMu) { | |
return _mu; | |
} | |
// Solve Cycle if necessary | |
if (_solvedFirstRepetition == false) { | |
getFirstRepetition(); | |
} | |
// Find the position of the first repetition of length lambda | |
_mu = 0; | |
_tortoise = _hare = _element; | |
for (int i = 0; i < _lambda; i++) { | |
_hare = move(_hare); | |
} | |
while (_hare != null) { | |
if (_hare.equals(_tortoise)) { | |
break; | |
} | |
_tortoise = move(_tortoise); | |
_hare = move(_hare); | |
_mu += 1; | |
} | |
// Done | |
_solvedMu = true; | |
return _mu; | |
} | |
@Override | |
public int getLambda() { | |
// is there something to process | |
if (_solvedLambda) { | |
return _lambda; | |
} | |
// Solve Cycle and lambda if necessary | |
if (_solvedFirstRepetition == false) { | |
getFirstRepetition(); | |
} | |
return _lambda; | |
} | |
} |