Changeset 2263 in josm for trunk


Ignore:
Timestamp:
2009-10-10T14:08:39+02:00 (13 years ago)
Author:
stoecker
Message:

applied #3671 - patch by Dave Hansen - performance fixes of data storage

Location:
trunk/src/org/openstreetmap/josm/data
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/data/coor/QuadTiling.java

    r2165 r2263  
    9898        return (int)(mask & (quad >> total_shift));
    9999    }
    100     static public int index(Node n, int level)
     100    static public int index(LatLon coor, int level)
    101101    {
    102         LatLon coor = n.getCoor();
    103102        // The nodes that don't return coordinates will all get
    104103        // stuck in a single tile.  Hopefully there are not too
     
    106105        if (coor == null)
    107106            return 0;
    108         long quad = coorToTile(n.getCoor());
     107        long quad = coorToTile(coor);
    109108        return index(level, quad);
    110109    }
  • trunk/src/org/openstreetmap/josm/data/osm/DataSet.java

    r2181 r2263  
    11// License: GPL. Copyright 2007 by Immanuel Scholz and others
    22package org.openstreetmap.josm.data.osm;
    3 
     3import org.openstreetmap.josm.tools.ReverseLookup;
    44import static org.openstreetmap.josm.tools.I18n.tr;
    55
     
    3939     * conversion of the whole DataSet by iterating over this data structure.
    4040     */
    41     public Collection<Node> nodes = new QuadBuckets();
     41    public QuadBuckets<Node> nodes = new QuadBuckets<Node>();
    4242
    4343    /**
     
    4646     * The way nodes are stored only in the way list.
    4747     */
    48     public Collection<Way> ways = new LinkedList<Way>();
     48    public QuadBuckets<Way> ways = new QuadBuckets<Way>();
    4949
    5050    /**
  • trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java

    r2197 r2263  
    11package org.openstreetmap.josm.data.osm;
     2import java.lang.reflect.Array;
    23import java.util.ArrayList;
    34import java.util.Collection;
     
    910import org.openstreetmap.josm.data.coor.EastNorth;
    1011import org.openstreetmap.josm.data.osm.Node;
     12import org.openstreetmap.josm.data.osm.Way;
     13import org.openstreetmap.josm.data.osm.OsmPrimitive;
    1114import org.openstreetmap.josm.tools.Pair;
    1215
     
    3538
    3639
    37 public class QuadBuckets implements Collection<Node>
     40public class QuadBuckets<T extends OsmPrimitive> implements Collection<T>
    3841{
    3942    public static boolean debug = false;
     
    8083    public static int TILES_PER_LEVEL_SHIFT = 2;
    8184    public static int TILES_PER_LEVEL = 1<<TILES_PER_LEVEL_SHIFT;
     85    // Maybe this should just be a Rectangle??
    8286    class BBox
    8387    {
    84         private double xmin;
    85         private double xmax;
    86         private double ymin;
    87         private double ymax;
     88        private double xmin = Double.POSITIVE_INFINITY;
     89        private double xmax = Double.NEGATIVE_INFINITY;
     90        private double ymin = Double.POSITIVE_INFINITY;
     91        private double ymax = Double.NEGATIVE_INFINITY;
    8892        void sanity()
    8993        {
     
    107111        public String toString()
    108112        {
    109             return "[ " + xmin + " -> " + xmax + ", " +
    110                          ymin + " -> " + ymax + " ]";
     113            return "[ x: " + xmin + " -> " + xmax +
     114                   ", y: " + ymin + " -> " + ymax + " ]";
    111115        }
    112116        double min(double a, double b)
     
    122126            return b;
    123127        }
     128        private void add(LatLon c)
     129        {
     130            xmin = min(xmin, c.lon());
     131            xmax = max(xmax, c.lon());
     132            ymin = min(ymin, c.lat());
     133            ymax = max(ymax, c.lat());
     134        }
    124135        public BBox(LatLon a, LatLon b)
    125136        {
    126             xmin = min(a.lon(), b.lon());
    127             xmax = max(a.lon(), b.lon());
    128             ymin = min(a.lat(), b.lat());
    129             ymax = max(a.lat(), b.lat());
     137            add(a);
     138            add(b);
    130139            sanity();
    131140        }
     
    137146            ymax = max(a_y, b_y);
    138147            sanity();
     148        }
     149        public BBox(Way w)
     150        {
     151            for (Node n : w.getNodes()) {
     152                LatLon coor = n.getCoor();
     153                if (coor == null)
     154                    continue;
     155                add(coor);
     156            }
     157            this.sanity();
    139158        }
    140159        public double height()
     
    180199            return this.inside(b) || b.inside(this);
    181200        }
     201        List<LatLon> points()
     202        {
     203            LatLon p1 = new LatLon(ymin, xmin);
     204            LatLon p2 = new LatLon(ymin, xmax);
     205            LatLon p3 = new LatLon(ymax, xmin);
     206            LatLon p4 = new LatLon(ymax, xmax);
     207            List<LatLon> ret = new ArrayList<LatLon>();
     208            ret.add(p1);
     209            ret.add(p2);
     210            ret.add(p3);
     211            ret.add(p4);
     212            return ret;
     213        }
    182214    }
    183215    class QBLevel
     
    187219        QBLevel parent;
    188220
    189         public List<Node> content;
     221        public List<T> content;
    190222        public QBLevel children[];
     223        public String toString()
     224        {
     225            return super.toString()+ "["+level+"]: " + bbox;
     226        }
    191227        public QBLevel(QBLevel parent)
    192228        {
    193229            init(parent);
    194230        }
    195         String quads(Node n)
    196         {
    197             return Long.toHexString(QuadTiling.quadTile(n.getCoor()));
     231        String quads(T o)
     232        {
     233            if (o instanceof Node) {
     234                LatLon coor = ((Node)o).getCoor();
     235                if (coor == null)
     236                    return "null node coordinates";
     237                return Long.toHexString(QuadTiling.quadTile(coor));
     238            }
     239            return "Way??";
     240        }
     241        boolean remove_content(T o)
     242        {
     243            boolean ret = this.content.remove(o);
     244            if (this.content.size() == 0)
     245                this.content = null;
     246            return ret;
     247        }
     248        // Get the correct index for the given primitive
     249        // at the given level.  If the primitive can not
     250        // fit into a single quad at this level, return -1
     251        int get_index(T o, int level)
     252        {
     253            if (debug)
     254                out("getting index for " + o + " at level: " + level);
     255            if (o instanceof Node) {
     256                Node n = (Node)o;
     257                LatLon coor = ((Node)o).getCoor();
     258                if (coor == null)
     259                    return -1;
     260                return QuadTiling.index(coor, level);
     261            }
     262            if (o instanceof Way) {
     263                Way w = (Way)o;
     264                int index = -1;
     265                //for (Node n : w.getNodes()) {
     266                for (LatLon c : way_bbox(w).points()) {
     267                //    LatLon c = n.getCoor();
     268                    if (debug)
     269                        out("getting index for point: " + c);
     270                    if (index == -1) {
     271                        index = QuadTiling.index(c, level);
     272                        if (debug)
     273                            out("set initial way index to: " + index);
     274                        continue;
     275                    }
     276                    int node_index = QuadTiling.index(c, level);
     277                    if (debug)
     278                        out("other node way index: " + node_index);
     279                    if (node_index != index) {
     280                        // This happens at level 0 sometimes when a way has no
     281                        // nodes present.
     282                        if (debug) {
     283                            out("way ("+w.getId()+") would have gone across two quads "
     284                                    + node_index + "/" + index + " at level: " + level + "    ");
     285                            out("node count: " + w.getNodes().size());
     286                            for (LatLon c2 : way_bbox(w).points())
     287                                out("points: " + c2);
     288                        }
     289                        return -1;
     290                    }
     291                }
     292                return index;
     293            }
     294            abort("bad primitive: " + o);
     295            return -1;
    198296        }
    199297        void split()
     
    206304                abort("overwrote children");
    207305            }
    208             children = new QBLevel[QuadTiling.TILES_PER_LEVEL];
     306            // This is ugly and hackish.  But, it seems to work,
     307            // and using an ArrayList here seems to cost us
     308            // a significant performance penalty -- 50% in my
     309            // testing.  Child access is one of the single
     310            // hottest code paths in this entire class.
     311            children = (QBLevel[])Array.newInstance(this.getClass(), QuadTiling.TILES_PER_LEVEL);
    209312            // deferring allocation of children until use
    210313            // seems a bit faster
    211314            //for (int i = 0; i < TILES_PER_LEVEL; i++)
    212315            //    children[i] = new QBLevel(this, i);
    213             List<Node> tmpcontent = content;
     316            List<T> tmpcontent = content;
    214317            content = null;
    215             for (Node n : tmpcontent) {
    216                 int new_index = QuadTiling.index(n, level);
     318            for (T o : tmpcontent) {
     319                int new_index = get_index(o, level);
     320                if (new_index == -1) {
     321                    this.add_content(o);
     322                    //out("adding content to branch: " + this);
     323                    continue;
     324                }
    217325                if (children[new_index] == null)
    218326                    children[new_index] = new QBLevel(this, new_index);
    219327                QBLevel child = children[new_index];
    220328                if (debug)
    221                     out("putting "+n+"(q:"+quads(n)+") into ["+new_index+"] " + child.bbox());
    222                 child.add(n);
    223             }
    224         }
    225         void add_leaf(Node n)
    226         {
    227             LatLon c = n.getCoor();
     329                    out("putting "+o+"(q:"+quads(o)+") into ["+new_index+"] " + child.bbox());
     330                child.add(o);
     331            }
     332        }
     333        boolean add_content(T o)
     334        {
     335            boolean ret = false;
     336            if (content == null)
     337                content = new LinkedList<T>();
     338            ret = content.add(o);
     339            if (debug && !this.isLeaf())
     340                pout("added "+o.getClass().getName()+" to non-leaf with size: " + content.size());
     341            return ret;
     342        }
     343        void add_to_leaf(T o)
     344        {
    228345            QBLevel ret = this;
    229             if (content == null) {
    230                 if (debug)
    231                     out("   new content array");
    232                 // I chose a LinkedList because we do not do
    233                 // any real random access to this.  We generally
    234                 // just run through the whole thing all at once
    235                 content = new LinkedList<Node>();
    236             }
    237             content.add(n);
     346            add_content(o);
    238347            if (content.size() > MAX_OBJECTS_PER_LEVEL) {
    239348                if (debug)
     
    255364                return;
    256365            }
    257             if (debug) {
    258                 out("   plain content put now have " + content.size());
    259                 if (content.contains(c))
    260                     out("   and I already have that one");
    261             }
    262         }
    263 
    264         List<Node> search(BBox bbox, LatLon point, double radius)
    265         {
    266             if (isLeaf())
    267                 return search_leaf(bbox, point, radius);
    268             return search_branch(bbox, point, radius);
    269         }
    270         private List<Node> search_leaf(BBox bbox, LatLon point, double radius)
    271         {
    272             if (debug)
    273                 out("searching contents in tile " + this.bbox() + " for " + bbox);
     366        }
     367        /*
     368         * This is a quick hack.  The problem is that we need the
     369         * way's bounding box a *bunch* of times when it gets
     370         * inserted.  It gets expensive if we have to recreate
     371         * them each time.
     372         *
     373         * An alternative would be to calculate it at .add() time
     374         * and passing it down the call chain.
     375         */
     376        HashMap<Way,BBox> way_bbox_cache = new HashMap<Way, BBox>();
     377        BBox way_bbox(Way w)
     378        {
     379            if (way_bbox_cache.size() > 100)
     380                way_bbox_cache.clear();
     381            BBox b = way_bbox_cache.get(w);
     382            if (b == null) {
     383                b = new BBox(w);
     384                way_bbox_cache.put(w, b);
     385            }
     386            return b;
     387            //return new BBox(w);
     388        }
     389
     390        boolean matches(T o, BBox search_bbox)
     391        {
     392            if (o instanceof Node) {
     393                LatLon coor = ((Node)o).getCoor();
     394                if (coor == null)
     395                    return false;
     396                return search_bbox.bounds(coor);
     397            }
     398            if (o instanceof Way) {
     399                BBox bbox = way_bbox((Way)o);
     400                return bbox.intersects(search_bbox);
     401            }
     402            abort("matches() bad primitive: " + o);
     403            return false;
     404        }
     405        private List<T> search_contents(BBox search_bbox)
     406        {
     407            String size = "null";
     408            if (content != null)
     409                size = ""+content.size();
     410            if (debug)
     411                out("searching contents (size: "+size+") for " + search_bbox);
    274412            /*
    275413             * It is possible that this was created in a split
     
    284422            // the iterator's calls to ArrayList.size() were showing up in
    285423            // some profiles, so I'm trying a LinkedList instead
    286             List<Node> ret = new LinkedList<Node>();
    287             for (Node n : content) {
    288                 // This supports two modes: one where the bbox is just
    289                 // an outline of the point/radius combo, and one where
    290                 // it is *just* the bbox.  If it is *just* the bbox,
    291                 // don't consider the points below
    292                 if (point == null) {
    293                     ret.add(n);
    294                     continue;
    295                 }
    296                 LatLon c = n.getCoor();
    297                 // is greatCircleDistance really necessary?
    298                 double d = c.greatCircleDistance(point);
    299                 if (debug)
    300                     out("[" + level + "] Checking coor: " + c + " dist: " + d + " vs. " + radius + " " + quads(n));
    301                 if (d > radius)
    302                     continue;
    303                 if (debug)
    304                     out("hit in quad: "+Long.toHexString(this.quad)+"\n");
    305                 //if (ret == null)
    306                 //    ret = new LinkedList<Node>();
    307                 ret.add(n);
     424            List<T> ret = new LinkedList<T>();
     425            for (T o : content) {
     426                if (matches(o, search_bbox))
     427                    ret.add(o);
    308428            }
    309429            if (debug)
     
    355475            return null;
    356476        }
    357         QBLevel nextLeaf()
     477        boolean hasContent()
     478        {
     479            if (content == null)
     480                return false;
     481            return true;
     482        }
     483        QBLevel nextContentNode()
    358484        {
    359485            QBLevel next = this;
     
    381507            // and find the first leaf
    382508            while (!next.isLeaf()) {
    383                 if (debug)
    384                     out("["+next.level+"] next node is a branch, moving down...");
     509                if (next.hasContent() && next != this)
     510                    break;
     511                if (debug)
     512                    out("["+next.level+"] next node ("+next+") is a branch (content: "+next.hasContent()+"), moving down...");
    385513                for (QBLevel child : next.children) {
    386514                    if (child == null)
     
    417545                ret += l.size();
    418546            }
     547            if (content != null)
     548                ret += content.size();
    419549            if (debug)
    420550                out("["+level+"] branch size: " + ret);
    421551            return ret;
    422552        }
    423         boolean contains(Node n)
     553        boolean contains(T n)
    424554        {
    425555            QBLevel res = find_exact(n);
     
    428558            return true;
    429559        }
    430         QBLevel find_exact(Node n)
     560        QBLevel find_exact(T n)
    431561        {
    432562            if (isLeaf())
     
    434564            return find_exact_branch(n);
    435565        }
    436         QBLevel find_exact_leaf(Node n)
     566        QBLevel find_exact_leaf(T n)
    437567        {
    438568            QBLevel ret = null;
     
    441571            return ret;
    442572        }
    443         QBLevel find_exact_branch(Node n)
     573        QBLevel find_exact_branch(T n)
    444574        {
    445575            QBLevel ret = null;
     
    453583            return ret;
    454584        }
    455         boolean add(Node n)
    456         {
     585        boolean add(T n)
     586        {
     587            if (consistency_testing) {
     588                if (!matches(n, this.bbox())) {
     589                    out("-----------------------------");
     590                    debug = true;
     591                    get_index(n, level);
     592                    abort("object " + n + " does not belong in node at level: " + level + " bbox: " + this.bbox());
     593                }
     594            }
    457595            if (isLeaf())
    458                 add_leaf(n);
     596                add_to_leaf(n);
    459597            else
    460                 add_branch(n);
     598                add_to_branch(n);
    461599            return true;
    462600        }
    463         QBLevel add_branch(Node n)
    464         {
    465             LatLon c = n.getCoor();
    466             int index = QuadTiling.index(n, level);
    467             if (debug)
     601        QBLevel add_to_branch(T n)
     602        {
     603            int index = get_index(n, level);
     604            if (index == -1) {
     605                if (debug)
     606                    out("unable to get index for " + n + "at level: " + level + ", adding content to branch: " + this);
     607                this.add_content(n);
     608                return this;
     609            }
     610            if (debug) {
    468611                out("[" + level + "]: " + n +
    469612                    " index " + index + " levelquad:" + this.quads() + " level bbox:" + this.bbox());
    470             if (debug)
    471613                out("   put in child["+index+"]");
     614            }
    472615            if (children[index] == null)
    473616                children[index] = new QBLevel(this, index);
    474617            children[index].add(n);
    475             /* this is broken at the moment because we need to handle the null n.getCoor()
    476             if (consistency_testing && !children[index].bbox().bounds(n.getCoor())) {
    477                 out("target child["+index+"] does not bound " + children[index].bbox() + " " + c);
    478                 for (int i = 0; i < children.length; i++) {
    479                     QBLevel ch = children[i];
    480                     if (ch == null)
    481                         continue;
    482                     out("child["+i+"] quad: " + ch.quads() + " bounds: " + ch.bbox.bounds(n.getCoor()));
    483                 }
    484                 out(" coor quad: " + quads(n));
    485                 abort("");
    486             }*/
    487 
    488             if (consistency_testing) {
    489                 for (int i = 0; i < children.length; i++) {
    490                     QBLevel ch = children[i];
    491                     if (ch == null)
    492                         continue;
    493                     if (ch.bbox().bounds(c) && i != index) {
    494                         out("multible bounding?? expected: " + index + " but saw at " + i + " " + ch.quads());
    495                         out("child["+i+"] bbox: " + ch.bbox());
    496                     }
    497                 }
    498             }
    499618            return this;
    500619        }
    501         private List<Node> search_branch(BBox bbox, LatLon point, double radius)
    502         {
    503             List<Node> ret = null;
     620        private List<T> search(BBox search_bbox)
     621        {
     622            List<T> ret = null;
    504623            if (debug)
    505624                System.out.print("[" + level + "] qb bbox: " + this.bbox() + " ");
    506             if (!this.bbox().intersects(bbox)) {
     625            if (!this.bbox().intersects(search_bbox)) {
    507626                if (debug) {
    508627                    out("miss " + Long.toHexString(this.quad));
     
    511630                return ret;
    512631            }
     632            if (this.hasContent())
     633                ret = this.search_contents(search_bbox);
     634            if (this.isLeaf()) {
     635                return ret;
     636            }
     637            //if (this.hasContent())
     638            //    abort("branch had stuff");
    513639            if (debug)
    514640                out("hit " + this.quads());
     
    516642            if (debug)
    517643                out("[" + level + "] not leaf, moving down");
    518             int child_nr = 0;
    519             for (QBLevel q : children) {
     644            for (int i = 0; i < children.length; i++) {
     645                QBLevel q = children[i];
     646                if (debug)
     647                    out("child["+i+"]: " + q);
    520648                if (q == null)
    521649                    continue;
    522                 child_nr++;
    523                 if (debug)
    524                     System.out.print(child_nr+": ");
    525                 List<Node> coors = q.search(bbox, point, radius);
     650                if (debug)
     651                    System.out.print(i+": ");
     652                List<T> coors = q.search(search_bbox);
    526653                if (coors == null)
    527654                    continue;
     
    530657                else
    531658                    ret.addAll(coors);
    532                 if (q.bbox().bounds(bbox)) {
     659                if (q.bbox().bounds(search_bbox)) {
    533660                    search_cache = q;
    534661                    // optimization: do not continue searching
     
    551678        {
    552679                this.parent = parent;
    553                 if (parent != null)
     680                if (parent == null)
     681                    this.level = 0;
     682                else
    554683                    this.level = parent.level + 1;
    555684                this.quad = 0;
     
    569698        {
    570699            this.init(parent);
    571             this.level = parent.level+1;
    572             this.parent = parent;
    573700            int shift = (QuadBuckets.NR_LEVELS - level) * 2;
    574701            long mult = 1;
     
    645772        root = new QBLevel(null);
    646773        search_cache = null;
     774        if (debug) {
     775            out("QuadBuckets() cleared: " + this);
     776            out("root: " + root + " level: " + root.level + " bbox: " + root.bbox());
     777        }
     778    }
     779    public boolean add(T n)
     780    {
    647781        if (debug)
    648             out("QuadBuckets() cleared: " + this);
    649     }
    650     public boolean add(Node n)
    651     {
    652         if (debug)
    653             out(this + " QuadBuckets() add: " + n + " size now: " + this.size());
     782            out("QuadBuckets() add: " + n + " size now: " + this.size());
    654783        int before_size = -1;
    655784        if (consistency_testing)
    656785            before_size = root.size();
    657         boolean ret = root.add(n);
     786        boolean ret;
     787        // A way with no nodes will have an infinitely large
     788        // bounding box.  Just stash it in the root node.
     789        if (!n.isUsable())
     790            ret = root.add_content(n);
     791        else
     792            ret = root.add(n);
    658793        if (consistency_testing) {
    659794            int end_size = root.size();
     
    663798                abort("size inconsistency before add: " + before_size + " after: " + end_size);
    664799        }
     800        if (debug)
     801            out("QuadBuckets() add: " + n + " size after: " + this.size());
    665802        return ret;
     803    }
     804    public void reindex()
     805    {
     806        QBLevel newroot = new QBLevel(null);
     807        Iterator<T> i = this.iterator();
     808        while (i.hasNext()) {
     809            T o = i.next();
     810            newroot.add(o);
     811        }
     812        root = newroot;
    666813    }
    667814    public void unsupported()
     
    670817        throw new UnsupportedOperationException();
    671818    }
    672     public boolean retainAll(Collection nodes)
    673     {
    674         for (Node n : this) {
    675             if (nodes.contains(n))
     819    public boolean retainAll(Collection objects)
     820    {
     821        for (T o : this) {
     822            if (objects.contains(o))
    676823                continue;
    677             if (!this.remove(n))
     824            if (!this.remove(o))
    678825                return false;
    679826        }
    680827        return true;
    681828    }
    682     public boolean removeAll(Collection nodes)
    683     {
    684         for (Object o : nodes) {
    685             if (!(o instanceof Node))
    686                 return false;
    687             Node n = (Node)o;
    688             if (!this.remove(n))
     829    boolean canStore(Object o)
     830    {
     831        if (o instanceof Way)
     832            return true;
     833        if (o instanceof Node)
     834            return true;
     835        return false;
     836    }
     837    public boolean removeAll(Collection objects)
     838    {
     839        for (Object o : objects) {
     840            if (!canStore(o))
     841                return false;
     842            if (!this.remove(o))
    689843                return false;
    690844        }
    691845        return true;
    692846    }
    693     public boolean addAll(Collection nodes)
    694     {
    695         for (Object o : nodes) {
    696             if (!(o instanceof Node))
    697                 return false;
    698             Node n = (Node)o;
    699             if (!this.add(n))
     847    public boolean addAll(Collection objects)
     848    {
     849        for (Object o : objects) {
     850            if (!canStore(o))
     851                return false;
     852            if (!this.add(convert(o)))
    700853                return false;
    701854        }
    702855        return true;
    703856    }
    704     public boolean containsAll(Collection nodes)
     857    public boolean containsAll(Collection objects)
    705858    {
    706859        boolean ret = true;
    707         for (Object o : nodes) {
    708             if (!(o instanceof Node))
    709                 return false;
    710             Node n = (Node)o;
    711             if (!this.contains(n))
     860        for (Object o : objects) {
     861            if (!canStore(o))
     862                return false;
     863            if (!this.contains(o))
    712864                return false;
    713865        }
     
    716868    private void check_type(Object o)
    717869    {
    718         if (o instanceof Node)
     870        if (canStore(o))
    719871            return;
    720872        unsupported();
    721873    }
     874    // If anyone has suggestions for how to fix
     875    // this properly, I'm listening :)
     876    private T convert(Object raw)
     877    {
     878        //@SuppressWarnings("unchecked")
     879        return (T)raw;
     880    }
    722881    public boolean remove(Object o)
    723882    {
    724883        check_type(o);
    725         return this.remove((Node)o);
    726     }
    727     public boolean remove(Node n)
     884        return this.remove(convert(o));
     885    }
     886    public boolean remove(T n)
    728887    {
    729888        QBLevel bucket = root.find_exact(n);
    730889        if (!bucket.isLeaf())
    731890            abort("found branch where leaf expected");
    732         return bucket.content.remove(n);
     891        boolean ret = bucket.remove_content(n);
     892        return ret;
    733893    }
    734894    public boolean contains(Object o)
    735895    {
    736         if (!(o instanceof Node))
     896        if (!canStore(o))
    737897            return false;
    738         QBLevel bucket = root.find_exact((Node)o);
     898        QBLevel bucket = root.find_exact(convert(o));
    739899        if (bucket == null)
    740900            return false;
    741901        return true;
    742902    }
    743     public ArrayList<Node> toArrayList()
    744     {
    745         ArrayList<Node> a = new ArrayList<Node>();
    746         for (Node n : this)
     903    public ArrayList<T> toArrayList()
     904    {
     905        ArrayList<T> a = new ArrayList<T>();
     906        for (T n : this)
    747907            a.add(n);
    748         out("returning array list with size: " + a.size());
     908        if (debug)
     909           out("returning array list with size: " + a.size());
    749910        return a;
    750911    }
     
    757918        return this.toArrayList().toArray(template);
    758919    }
    759     class QuadBucketIterator implements Iterator<Node>
    760     {
    761         QBLevel current_leaf;
    762         int index_in_leaf;
     920    class QuadBucketIterator implements Iterator<T>
     921    {
     922        QBLevel current_node;
     923        int content_index;
    763924        int iterated_over;
    764         QBLevel next_leaf(QBLevel q)
     925        QBLevel next_content_node(QBLevel q)
    765926        {
    766927            if (q == null)
    767928                return null;
    768929            QBLevel orig = q;
    769             QBLevel next = q.nextLeaf();
    770             if (consistency_testing && (orig == next))
     930            QBLevel next = q.nextContentNode();
     931            //if (consistency_testing && (orig == next))
     932            if (orig == next)
    771933                abort("got same leaf back leaf: " + q.isLeaf());
    772934            return next;
    773935        }
    774         public QuadBucketIterator(QuadBuckets qb)
    775         {
    776             if (debug)
    777                 out(this + " is a new iterator qb.root: " + qb.root + " size: " + qb.size());
    778             if (qb.root.isLeaf())
    779                 current_leaf = qb.root;
     936        public QuadBucketIterator(QuadBuckets<T> qb)
     937        {
     938            if (debug)
     939                out(this + " is a new iterator qb: " + qb + " size: " + qb.size());
     940            if (qb.root.isLeaf() || qb.root.hasContent())
     941                current_node = qb.root;
    780942            else
    781                 current_leaf = next_leaf(qb.root);
    782             if (debug)
    783                 out("\titerator first leaf: " + current_leaf);
     943                current_node = next_content_node(qb.root);
     944            if (debug)
     945                out("\titerator first leaf: " + current_node);
    784946            iterated_over = 0;
    785947        }
     
    793955            return true;
    794956        }
    795         Node peek()
    796         {
    797             if (current_leaf == null) {
     957        T peek()
     958        {
     959            if (current_node == null) {
    798960                if (debug)
    799961                    out("null current leaf, nowhere to go");
    800962                return null;
    801963            }
    802             while((current_leaf.content == null) ||
    803                   (index_in_leaf >= current_leaf.content.size())) {
     964            while((current_node.content == null) ||
     965                  (content_index >= current_node.content.size())) {
    804966                if (debug)
    805967                    out("moving to next leaf");
    806                 index_in_leaf = 0;
    807                 current_leaf = next_leaf(current_leaf);
    808                 if (current_leaf == null)
     968                content_index = 0;
     969                current_node = next_content_node(current_node);
     970                if (current_node == null)
    809971                    break;
    810972            }
    811             if (current_leaf == null || current_leaf.content == null) {
    812                 if (debug)
    813                     out("late nowhere to go " + current_leaf);
     973            if (current_node == null || current_node.content == null) {
     974                if (debug)
     975                    out("late nowhere to go " + current_node);
    814976                return null;
    815977            }
    816             return current_leaf.content.get(index_in_leaf);
    817         }
    818         public Node next()
    819         {
    820             Node ret = peek();
    821             index_in_leaf++;
    822             if (debug)
    823                 out("iteration["+iterated_over+"] " + index_in_leaf + " leaf: " + current_leaf);
     978            return current_node.content.get(content_index);
     979        }
     980        public T next()
     981        {
     982            T ret = peek();
     983            content_index++;
     984            if (debug)
     985                out("iteration["+iterated_over+"] " + content_index + " leaf: " + current_node);
    824986            iterated_over++;
    825987            if (ret == null) {
     
    835997            // 2. move the index back since we removed
    836998            //    an element
    837             index_in_leaf--;
    838             current_leaf.content.remove(index_in_leaf);
    839         }
    840     }
    841     public Iterator<Node> iterator()
     999            content_index--;
     1000            T object = peek();
     1001            current_node.content.remove(content_index);
     1002        }
     1003    }
     1004    public Iterator<T> iterator()
    8421005    {
    8431006        return new QuadBucketIterator(this);
     
    8501013            out(this + " QuadBuckets size: " + ret);
    8511014        return ret;
     1015    }
     1016    public int size_iter()
     1017    {
     1018        int count = 0;
     1019        Iterator<T> i = this.iterator();
     1020        while (i.hasNext()) {
     1021            i.next();
     1022            count++;
     1023        }
     1024        return count;
    8521025    }
    8531026    public boolean isEmpty()
     
    8681041        return bbox;
    8691042    }
    870     List<Node> search(LatLon point, double radius)
    871     {
    872         return this.search(search_to_bbox(point, radius), point, radius);
    873     }
    874     List<Node> search(BBox bbox)
    875     {
    876         return this.search(bbox, null, -1);
    877     }
    878     public List<Node> search(LatLon b1, LatLon b2)
     1043    List<T> search(Way w)
     1044    {
     1045        BBox way_bbox = new BBox(w);
     1046        return this.search(way_bbox);
     1047    }
     1048    public List<T> search(Node n, double radius)
     1049    {
     1050        return this.search(n.getCoor(), radius);
     1051    }
     1052    public List<T> search(LatLon point, double radius)
     1053    {
     1054        if (point == null)
     1055            return Collections.emptyList();
     1056        return this.search(search_to_bbox(point, radius));
     1057    }
     1058    public List<T> search(LatLon b1, LatLon b2)
    8791059    {
    8801060        BBox bbox = new BBox(b1.lon(), b1.lat(), b2.lon(), b2.lat());
     
    8821062        return this.search(bbox);
    8831063    }
    884     List<Node> search(BBox bbox, LatLon point, double radius)
     1064    List<T> search(BBox search_bbox)
    8851065    {
    8861066        if (debug) {
    887             out("qb root search at " + point + " around: " + radius);
     1067            out("qb root search at " + search_bbox);
    8881068            out("root bbox: " + root.bbox());
    8891069        }
    890         List<Node> ret = null;
     1070        List<T> ret;
    8911071        // Doing this cuts down search cost on a real-life data
    8921072        // set by about 25%
     
    8981078            // search spot can not cover the current
    8991079            // search
    900             while (!search_cache.bbox().bounds(bbox)) {
     1080            while (!search_cache.bbox().bounds(search_bbox)) {
     1081                out("bbox: " + search_bbox);
     1082                if (debug) {
     1083                    out("search_cache: " + search_cache + " level: " + search_cache.level);
     1084                    out("search_cache.bbox(): " + search_cache.bbox());
     1085                }
    9011086                search_cache = search_cache.parent;
     1087                if (debug)
     1088                    out("new search_cache: " + search_cache);
    9021089            }
    9031090        } else {
    9041091            search_cache = root;
    9051092        }
    906         return search_cache.search(bbox, point, radius);
     1093        ret = search_cache.search(search_bbox);
     1094        if (ret == null)
     1095            ret = new ArrayList<T>();
     1096        // A way that spans this bucket may be stored in one
     1097        // of the nodes which is a parent of the search cache
     1098        QBLevel tmp = search_cache.parent;
     1099        while (tmp != null) {
     1100            List<T> content_result = tmp.search_contents(search_bbox);
     1101            if (content_result != null)
     1102                ret.addAll(content_result);
     1103            tmp = tmp.parent;
     1104        }
     1105        if (ret == null || ret.size() == 0)
     1106            return Collections.emptyList();
     1107        if (debug)
     1108            out("search of QuadBuckets for " + search_bbox + " ret len: " + ret.size());
     1109        return ret;
    9071110    }
    9081111}
Note: See TracChangeset for help on using the changeset viewer.