| /** |
| * 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 |
| * Floyd's cycle-finding algorithm |
| * http://en.wikipedia.org/wiki/Cycle_detection |
| * http://fr.wikipedia.org/wiki/Algorithme_du_li%C3%A8vre_et_de_la_tortue |
| * |
| */ |
| public abstract class AbstractFloydCycleDetection<T> extends AbstractCycleDetection<T> { |
| |
| public AbstractFloydCycleDetection() { |
| this(null); |
| } |
| |
| public AbstractFloydCycleDetection(T element_p) { |
| super(element_p); |
| } |
| |
| @Override |
| public void setElement(T element_p) { |
| super.setElement(element_p); |
| _tortoise = move(element_p); |
| _hare = move(move(element_p)); |
| } |
| |
| @Override |
| public T getFirstRepetition() { |
| // is there something to process |
| if (_solvedFirstRepetition) { |
| return _firstRepetition; |
| } |
| // Search |
| while (_hare != null) { |
| if (_hare.equals(_tortoise)) { |
| // The hare has caught up with the tortoise |
| _firstRepetition = _hare; |
| break; |
| } |
| if (move(_hare) == null) { |
| // The hare reached the end |
| break; |
| } |
| // The hare moves twice as quickly as the tortoise |
| _tortoise = move(_tortoise); |
| _hare = move(move(_hare)); |
| } |
| // The hare reached the end |
| _solvedFirstRepetition = 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 |
| // The hare and tortoise move at the same speeds |
| _mu = 0; |
| _tortoise = _hare = _element; |
| 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 mu if necessary |
| if (_solvedMu == false) { |
| getMu(); |
| } |
| // Find the length of the shortest cycle starting from _firstRepetitionPosition |
| // The hare moves while the tortoise stays still |
| _lambda = 1; |
| _hare = move(_tortoise); |
| while (_hare != null) { |
| if (_hare.equals(_tortoise)) { |
| break; |
| } |
| _hare = move(_hare); |
| _lambda += 1; |
| } |
| // Done |
| _solvedLambda = true; |
| return _lambda; |
| } |
| |
| } |