sascha@450: package de.intevation.gnv.jfreechart; sascha@450: sascha@450: import java.util.LinkedList; sascha@450: sascha@450: /** sascha@780: * @author Sascha L. Teichmann sascha@450: */ sascha@450: public class LevelOrderIndices sascha@450: { ingo@795: /** ingo@795: * ingo@795: */ sascha@450: public interface Visitor { ingo@795: /** ingo@795: * ingo@795: * @param index ingo@795: * @return ingo@795: */ sascha@450: Object visit(int index); sascha@450: } sascha@450: ingo@795: /** ingo@795: * ingo@795: */ sascha@450: protected int from; ingo@795: /** ingo@795: * ingo@795: */ sascha@450: protected int to; sascha@450: ingo@795: /** ingo@795: * ingo@795: */ sascha@450: public LevelOrderIndices() { sascha@450: } sascha@450: ingo@795: /** ingo@795: * ingo@795: * @param to ingo@795: */ sascha@450: public LevelOrderIndices(int to) { sascha@450: this(0, to); sascha@450: } sascha@450: ingo@795: /** ingo@795: * ingo@795: * @param from ingo@795: * @param to ingo@795: */ sascha@450: public LevelOrderIndices(int from, int to) { sascha@450: this.from = Math.min(from, to); sascha@450: this.to = Math.max(from, to); sascha@450: } sascha@450: ingo@795: /** ingo@795: * ingo@795: * @param visitor ingo@795: * @return ingo@795: */ sascha@450: public Object visit(Visitor visitor) { sascha@450: LinkedList queue = new LinkedList(); sascha@450: sascha@450: queue.add(new int [] { from, to }); sascha@450: sascha@450: while (!queue.isEmpty()) { sascha@450: int [] pair = queue.remove(); sascha@450: sascha@450: int mid = (pair[0] + pair[1]) >> 1; sascha@450: sascha@450: Object result = visitor.visit(mid); sascha@450: sascha@450: if (result != null) { sascha@450: return result; sascha@450: } sascha@450: sascha@450: if (mid-1 >= pair[0]) { sascha@450: queue.add(new int [] { pair[0], mid-1 }); sascha@450: } sascha@450: sascha@450: if (mid+1 <= pair[1]) { sascha@450: pair[0] = mid+1; sascha@450: queue.add(pair); sascha@450: } sascha@450: } sascha@450: sascha@450: return null; sascha@450: } sascha@450: } sascha@450: // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf-8 :