rtree.java

shape file read and write

/*
 *    GeoTools - OpenSource mapping toolkit
 *    http://geotools.org
 *    (C) 2003-2006, GeoTools Project Managment Committee (PMC)
 *    (C) 2002, Centre for Computational Geography
 *
 *    This library is free software; you can redistribute it and/or
 *    modify it under the terms of the GNU Lesser General Public
 *    License as published by the Free Software Foundation;
 *    version 2.1 of the License.
 *
 *    This library is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *    Lesser General Public License for more details.
 */
package org.geotools.index.rtree;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;

import org.geotools.filter.visitor.ExtractBoundsFilterVisitor;
import org.geotools.geometry.jts.ReferencedEnvelope;
import org.geotools.index.Data;
import org.geotools.index.DataDefinition;
import org.geotools.index.Lock;
import org.geotools.index.LockTimeoutException;
import org.geotools.index.TreeException;
import org.geotools.index.UnsupportedFilterException;
import org.opengis.filter.Filter;

import com.vividsolutions.jts.geom.Envelope;

/**
 * Relational index.
 * 
 * @author Tommaso Nolli
 * @source $URL:
 *         http://svn.geotools.org/geotools/trunk/gt/modules/plugin/shapefile/src/main/java/org/geotools/index/rtree/RTree.java $
 */
public class RTree {
    private Logger logger = org.geotools.util.logging.Logging
            .getLogger("org.geotools.index.rtree");
    private PageStore store;

    public RTree(PageStore store) throws TreeException {
        this.store = store;
    }

    /**
     * Gets this index bounding box
     * 
     * @return An Envelope
     * 
     * @throws TreeException
     *                 DOCUMENT ME!
     */
    public Envelope getBounds() throws TreeException {
        this.checkOpen();

        Node root = this.store.getRoot();

        return (root == null) ? null : root.getBounds();
    }

    /**
     * Returns the maxiumal boudns for the provided filter.
     * <p>
     * This method will try and produce a filter for the provided bounds, see
     * ExtractBoundsFilterVisitor.BOUNDS_VISITOR for details of generation.
     * 
     * @param filter
     * @throws TreeException
     * @throws UnsupportedFilterException
     *                 For Filter.EXCLUDES
     */
    public Envelope getBounds(Filter filter) throws TreeException,
            UnsupportedFilterException {
        this.checkOpen();

        Envelope env;
        env = (Envelope) filter.accept(
                ExtractBoundsFilterVisitor.BOUNDS_VISITOR,
                new ReferencedEnvelope());

        if (env == null || env.isNull()) {
            throw new UnsupportedFilterException(
                    "Filter does not contains any Geometry");
        }

        Node root = this.store.getRoot();

        return env.contains(root.getBounds()) ? root.getBounds() : this
                .getBoundsInternal(env, root);
    }

    /*
     * public Envelope getBounds(Envelope env) {
     *  }
     */

    /**
     * DOCUMENT ME!
     * 
     * @param query
     * @param node
     * 
     * @return DOCUMENT ME!
     * 
     * @throws TreeException
     */
    private Envelope getBoundsInternal(final Envelope query, final Node node)
            throws TreeException {
        Envelope result = null;
        Entry entry = null;

        for (int i = 0; i < node.getEntriesCount(); i++) {
            entry = node.getEntry(i);

            if (entry.getBounds().intersects(query)) {
                if (node.isLeaf()) {
                    if (result == null) {
                        result = new Envelope(entry.getBounds());
                    } else {
                        result.expandToInclude(entry.getBounds());
                    }
                } else {
                    this.getBoundsInternal(query, this.store.getNode(entry,
                            node));
                }
            }
        }

        return result;
    }

    public DataDefinition getDataDefinition() {
        return this.store.getDataDefinition();
    }

    /**
     * Performs a search on this <code>RTree</code>
     * 
     * @param query
     *                the query <code>Envelope</code>
     * 
     * @return a <code>Collection</code> of <code>Data</code>
     * 
     * @throws TreeException
     *                 DOCUMENT ME!
     * @throws LockTimeoutException
     *                 DOCUMENT ME!
     */
    public List search(Envelope query) throws TreeException,
            LockTimeoutException {
        // Aquire a read lock
        Lock lock = this.store.getReadLock();
        List ret = null;

        try {
            ret = this.search(query, lock);
        } finally {
            // Release the lock
            this.store.releaseLock(lock);
        }

        return ret;
    }

    /**
     * Performs a search on this <code>RTree</code>
     * 
     * @param filter
     *                a <code>Filter</code>
     * 
     * @return a <code>Collection</code> of <code>Data</code>
     * 
     * @throws TreeException
     * @throws UnsupportedFilterException
     *                 DOCUMENT ME!
     * @throws LockTimeoutException
     *                 DOCUMENT ME!
     */
    public List search(Filter filter) throws TreeException,
            UnsupportedFilterException, LockTimeoutException {
        // Aquire a read lock
        Lock lock = this.store.getReadLock();
        List ret = null;

        try {
            Envelope env = (Envelope) filter.accept(
                    ExtractBoundsFilterVisitor.BOUNDS_VISITOR,
                    new ReferencedEnvelope());

            if (env == null || env.isNull()) {
                throw new UnsupportedFilterException("Not a valid filter");
            }
            ret = this.search(env, lock);
        } finally {
            // Release the lock
            this.store.releaseLock(lock);
        }

        return ret;
    }

    /**
     * Performs a search on the index
     * 
     * @param query
     *                The query <code>Envelope</code>
     * @param lock
     *                A <code>Lock</code> on the index
     * 
     * @return A <code>Collection</code> of <code>Data</code>
     * 
     * @throws TreeException
     * @throws LockTimeoutException
     */
    private List search(Envelope query, Lock lock) throws TreeException,
            LockTimeoutException {
        long start = System.currentTimeMillis();
        this.checkOpen();

        ArrayList matches = new ArrayList();

        Node root = this.store.getRoot();
        this.searchNode(query, root, matches);

        if (logger.isLoggable(Level.FINEST)) {
            logger.log(Level.FINEST, matches.size()
                    + " Data objects retrieved in "
                    + (System.currentTimeMillis() - start) + "ms.");
        }

        return matches;
    }

    /**
     * DOCUMENT ME!
     * 
     * @param query
     * @param node
     * @param matches
     * 
     * @throws TreeException
     */
    private void searchNode(final Envelope query, final Node node,
            final ArrayList matches) throws TreeException {
        Entry entry = null;

        for (int i = 0; i < node.getEntriesCount(); i++) {
            entry = node.getEntry(i);

            if (entry.getBounds().intersects(query)) {
                if (node.isLeaf()) {
                    matches.add(entry.getData());
                } else {
                    searchNode(query, this.store.getNode(entry, node), matches);
                }
            }
        }
    }

    /**
     * DOCUMENT ME!
     * 
     * @param bounds
     * @param data
     * 
     * @throws TreeException
     * @throws LockTimeoutException
     */
    public void insert(Envelope bounds, Data data) throws TreeException,
            LockTimeoutException {
        if (!data.isValid()) {
            throw new TreeException("Invalid data supplied!");
        }

        // Aquire a write lock
        Lock lock = this.store.getWriteLock();

        try {
            this.insert(lock, new Entry(bounds, data));
        } finally {
            // Release the lock
            this.store.releaseLock(lock);
        }
    }

    /**
     * DOCUMENT ME!
     * 
     * @param lock
     * @param entry
     * 
     * @throws TreeException
     */
    private void insert(Lock lock, Entry entry) throws TreeException {
        this.checkOpen();

        // Get the right leaf
        Node leaf = this.chooseLeaf(this.store.getRoot(), entry);

        leaf.addEntry(entry);

        if (leaf.getEntriesCount() <= this.store.getMaxNodeEntries()) {
            // If leaf has room add to it
            leaf.save();
            this.adjustTree(leaf, null);
        } else {
            // Overflow...
            Node[] split = this.splitNode(leaf);
            this.adjustTree(split[0], split[1]);
        }
    }

    /**
     * DOCUMENT ME!
     * 
     * @param node
     * @param newEntry
     * 
     * 
     * @throws TreeException
     *                 DOCUMENT ME!
     */
    private Node chooseLeaf(Node node, Entry newEntry) throws TreeException {
        if (node.isLeaf()) {
            return node;
        }

        Collection entries = node.getEntries();

        // Find the best Entry
        Entry best = null;
        Envelope env = null;
        double lastArea = Double.POSITIVE_INFINITY;
        double currentArea = 0d;
        double w = 0;
        double h = 0;
        double nw = 0;
        double nh = 0;

        Entry element = null;

        for (Iterator iter = entries.iterator(); iter.hasNext();) {
            element = (Entry) iter.next();

            currentArea = this.getAreaIncrease(element.getBounds(), newEntry
                    .getBounds());

            if (currentArea < lastArea) {
                lastArea = currentArea;
                best = element;
            } else if ((currentArea == lastArea)
                    && (this.getEntryArea(best) > this.getEntryArea(element))) {
                best = element;
            }
        }

        // Now best is the best Entry
        return this.chooseLeaf(this.store.getNode(best, node), newEntry);
    }

    /**
     * DOCUMENT ME!
     * 
     * @param node
     * 
     * 
     * @throws TreeException
     */
    private Node[] splitNode(Node node) throws TreeException {
        Collection entriesTmp = node.getEntries();

        Entry[] e = (Entry[]) entriesTmp.toArray(new Entry[entriesTmp.size()]);
        Entry[] firsts = null;

        if (this.store.getSplitAlgorithm() == PageStore.SPLIT_QUADRATIC) {
            firsts = this.quadraticPickSeeds(e);
        } else {
            firsts = this.linearPickSeeds(e);
        }

        ArrayList entries = new ArrayList(e.length - 2);

        for (int i = 0; i < e.length; i++) {
            if (!e[i].equals(firsts[0]) && !e[i].equals(firsts[1])) {
                entries.add(e[i]);
            }
        }

        // Clear the node in order to reuse it
        node.clear();

        Node newNode = this.store.getEmptyNode(node.isLeaf());

        Node[] ret = new Node[] { node, newNode };
        ret[0].addEntry(firsts[0]);
        ret[1].addEntry(firsts[1]);

        Entry toAssign = null;
        double d1 = 0d;
        double d2 = 0d;
        int pointer = -1;

        while (true) {
            if (entries.size() == 0) {
                break;
            } else {
                /*
                 * If the remaining elements are not enough for reaching the
                 * minNodeElements of a group or are just right to reach it, add
                 * all entries to the group
                 */
                if ((ret[0].getEntriesCount() + entries.size()) <= this.store
                        .getMinNodeEntries()) {
                    for (int i = 0; i < entries.size(); i++) {
                        ret[0].addEntry((Entry) entries.get(i));
                    }

                    break;
                }

                if ((ret[1].getEntriesCount() + entries.size()) <= this.store
                        .getMinNodeEntries()) {
                    for (int i = 0; i < entries.size(); i++) {
                        ret[1].addEntry((Entry) entries.get(i));
                    }

                    break;
                }
            }

            toAssign = null;

            if (this.store.getSplitAlgorithm() == PageStore.SPLIT_QUADRATIC) {
                toAssign = this.quadraticPickNext(ret, entries);
            } else {
                toAssign = this.linearPickNext(ret, entries);
            }

            d1 = this.getAreaIncrease(ret[0].getBounds(), toAssign.getBounds());
            d2 = this.getAreaIncrease(ret[1].getBounds(), toAssign.getBounds());

            if (d1 < d2) {
                pointer = 0;
            } else if (d1 > d2) {
                pointer = 1;
            } else {
                // If areas increase are the same, smallest wins
                d1 = this.getEnvelopeArea(ret[0].getBounds());
                d2 = this.getEnvelopeArea(ret[1].getBounds());

                if (d1 < d2) {
                    pointer = 0;
                } else if (d1 > d2) {
                    pointer = 1;
                } else {
                    /*
                     * If areas are the same the one with less entries wins