ingo@1115: /*
ingo@1115:  * Copyright (c) 2010 by Intevation GmbH
ingo@1115:  *
ingo@1115:  * This program is free software under the LGPL (>=v2.1)
ingo@1115:  * Read the file LGPL.txt coming with the software for details
ingo@1115:  * or visit http://www.gnu.org/licenses/ if it does not exist.
ingo@1115:  */
ingo@1115: 
sascha@450: package de.intevation.gnv.jfreechart;
sascha@450: 
sascha@450: import java.util.LinkedList;
sascha@450: 
sascha@450: /**
sascha@780:  * @author <a href="mailto:sascha.teichmann@intevation.de">Sascha L. Teichmann</a>
sascha@450:  */
sascha@450: public class LevelOrderIndices
sascha@450: {
sascha@450:     public interface Visitor {
ingo@815: 
sascha@450:         Object visit(int index);
sascha@450:     }
sascha@450: 
ingo@815: 
sascha@450:     protected int from;
ingo@815: 
sascha@450:     protected int to;
sascha@450: 
ingo@815: 
sascha@450:     public LevelOrderIndices() {
sascha@450:     }
sascha@450: 
ingo@815: 
sascha@450:     public LevelOrderIndices(int to) {
sascha@450:         this(0, to);
sascha@450:     }
sascha@450: 
ingo@815: 
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@815: 
sascha@450:     public Object visit(Visitor visitor) {
sascha@450:         LinkedList<int[]> queue = new LinkedList<int[]>();
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 :