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: {
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<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 :