rtree.java

shape file read and write

                     */
                    if (ret[0].getEntriesCount() < ret[1].getEntriesCount()) {
                        pointer = 0;
                    } else {
                        pointer = 1;
                    }
                }
            }

            ret[pointer].addEntry(toAssign);

            entries.remove(toAssign);
        }

        ret[0].save();
        ret[1].save();

        return ret;
    }

    /**
     * Returns the 2 new <code>Node</code>s
     * 
     * @param entries
     * 
     */
    private Entry[] quadraticPickSeeds(Entry[] entries) {
        Entry[] ret = new Entry[2];
        Envelope env = null;
        double actualD = 0d;
        double choosedD = Double.NEGATIVE_INFINITY;

        // Foreach pair of entries...
        for (int i = 0; i < (entries.length - 1); i++) {
            env = new Envelope(entries[i].getBounds());

            for (int j = i + 1; j < entries.length; j++) {
                env.expandToInclude(entries[j].getBounds());

                // find the inefficency of groupping together
                actualD = this.getAreaDifference(env, entries[i], entries[j]);

                // Choose the pair with the largest area
                if (actualD > choosedD) {
                    choosedD = actualD;
                    ret[0] = entries[i];
                    ret[1] = entries[j];
                }
            }
        }

        return ret;
    }

    private Entry[] linearPickSeeds(Entry[] entries) {
        // TODO Implement
        return null;
    }

    /**
     * DOCUMENT ME!
     * 
     * @param nodes
     * @param entries
     * 
     */
    private Entry quadraticPickNext(Node[] nodes, ArrayList entries) {
        Entry ret = null;
        double[] d = new double[] { 0d, 0d };

        double diff = 0d;
        double maxDiff = Double.NEGATIVE_INFINITY;
        Envelope e = null;

        for (int i = 0; i < entries.size(); i++) {
            e = ((Entry) entries.get(i)).getBounds();
            d[0] = this.getAreaIncrease(nodes[0].getBounds(), e);
            d[1] = this.getAreaIncrease(nodes[1].getBounds(), e);

            diff = Math.abs(d[0] - d[1]);

            if (diff > maxDiff) {
                maxDiff = diff;
                ret = (Entry) entries.get(i);
            }
        }

        return ret;
    }

    /**
     * DOCUMENT ME!
     * 
     * @param nodes
     * @param entries
     * 
     */
    private Entry linearPickNext(Node[] nodes, ArrayList entries) {
        // TODO implement
        return null;
    }

    /**
     * DOCUMENT ME!
     * 
     * @param node1
     * @param node2
     * 
     * @throws TreeException
     */
    private void adjustTree(Node node1, Node node2) throws TreeException {
        Node n = node1;
        Node nn = node2;

        Node p = null;
        Entry e = null;

        while (true) {
            if (n.equals(this.store.getRoot())) {
                if (nn != null) {
                    Node newRoot = this.store.getEmptyNode(false);

                    e = this.store.createEntryPointingNode(n);
                    newRoot.addEntry(e);

                    e = this.store.createEntryPointingNode(nn);
                    newRoot.addEntry(e);

                    newRoot.save();
                    this.store.setRoot(newRoot);

                    n.setParent(newRoot);
                    nn.setParent(newRoot);

                    n.save();
                    nn.save();
                } else {
                    // Force root save...
                    this.store.setRoot(n);
                }

                break;
            }

            p = n.getParent();
            e = p.getEntry(n);
            e.setBounds(new Envelope(n.getBounds()));

            if (nn != null) {
                Entry e2 = this.store.createEntryPointingNode(nn);

                p.addEntry(e2);

                if (p.getEntriesCount() > this.store.getMaxNodeEntries()) {
                    Node[] split = this.splitNode(p);
                    n = split[0];
                    nn = split[1];

                    // splitNodes saves the 2 nodes before returning
                } else {
                    // No more to check
                    p.save();

                    nn = null;
                    n = p;
                }
            } else {
                p.save();
                n = p;
            }
        }
    }

    /**
     * Deletes the entry with the specified <code>Envelope</code> as its
     * bounds.<br>
     * If more than one entry exists with the same bounds, then subsequent calls
     * to <code>delete</code> are needed to remove all this elements.
     * 
     * @param env
     *                The <code>Envelope</code>
     * 
     * @throws TreeException
     * @throws LockTimeoutException
     *                 DOCUMENT ME!
     */
    public void delete(Envelope env) throws TreeException, LockTimeoutException {
        this.checkOpen();

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

        try {
            Node node = this.findLeaf(this.store.getRoot(), env);

            if (node == null) {
                throw new TreeException(
                        "No node found with the supplied envelope: " + env);
            }

            Entry e = null;

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

                if (e.getBounds().equals(env)) {
                    this.doDelete(lock, node, e);

                    break;
                }
            }
        } finally {
            // Release the lock
            this.store.releaseLock(lock);
        }
    }

    /**
     * DOCUMENT ME!
     * 
     * @param lock
     * @param node
     * @param entry
     * 
     * @throws TreeException
     */
    private void doDelete(Lock lock, Node node, Entry entry)
            throws TreeException {
        node.removeEntry(entry);
        node.save();

        Collection toRemove = this.condenseTree(node);

        Node root = this.store.getRoot();

        if ((root.getEntriesCount() == 1) && !root.isLeaf()) {
            root = this.store.getNode(root.getEntry(0), root);
            this.store.setRoot(root);
        }

        Collection entries = new ArrayList();
        Iterator iter = toRemove.iterator();

        while (iter.hasNext()) {
            this.free((Node) iter.next(), entries);
        }

        // Reinsert orphaned entries
        Entry e = null;

        for (Iterator iterator = entries.iterator(); iterator.hasNext();) {
            e = (Entry) iterator.next();
            this.insert(lock, e);
        }
    }

    /**
     * Frees a non leaf Node
     * 
     * @param node
     *                The Node to free
     * @param entries
     *                A <code>Collection</code> used to store Node Entry
     * 
     * @throws TreeException
     *                 DOCUMENT ME!
     */
    private void free(final Node node, final Collection entries)
            throws TreeException {
        if (node.isLeaf()) {
            entries.addAll(node.getEntries());
        } else {
            for (int i = 0; i < node.getEntriesCount(); i++) {
                this.free(this.store.getNode(node.getEntry(i), node), entries);
            }
        }

        this.store.free(node);
    }

    /**
     * Closes this index and the associated <code>PageStore</code>
     * 
     * @throws TreeException
     */
    public void close() throws TreeException {
        this.store.close();
        this.store = null;
    }

    /**
     * Checks to see if the index is open
     * 
     * @throws TreeException
     *                 If the index is closed
     */
    private void checkOpen() throws TreeException {
        if (this.store == null) {
            throw new TreeException("The index is closed!");
        }
    }

    /**
     * Finds the first leaf node that contains the element with the supplied
     * envelope
     * 
     * @param node
     *                Starting node
     * @param envelope
     *                <code>Envelope</code> to search
     * 
     * @return The <code>Node</code> that contains the element
     * 
     * @throws TreeException
     */
    private Node findLeaf(Node node, Envelope envelope) throws TreeException {
        Node ret = null;
        Entry entry = null;

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

            if (node.isLeaf()) {
                if (entry.getBounds().equals(envelope)) {
                    ret = node;
                }
            } else {
                if (entry.getBounds().contains(envelope)) {
                    ret = this.findLeaf(this.store.getNode(entry, node),
                            envelope);
                }
            }

            if ((ret != null) && ret.isLeaf()) {
                break;
            }
        }

        return ret;
    }

    /**
     * DOCUMENT ME!
     * 
     * @param node
     * 
     * 
     * @throws TreeException
     */
    private Collection condenseTree(Node node) throws TreeException {
        ArrayList removed = new ArrayList();

        if (node.equals(this.store.getRoot())) {
            return removed;
        }

        Node parentNode = node.getParent();
        Entry parentEntry = parentNode.getEntry(node);

        if (node.getEntriesCount() < this.store.getMinNodeEntries()) {
            removed.add(node);
            parentNode.removeEntry(parentEntry);
        } else {
            parentEntry.setBounds(node.getBounds());
        }

        parentNode.save();

        if (this.store.getRoot().equals(parentNode)) {
            this.store.setRoot(parentNode);
        }

        removed.addAll(this.condenseTree(parentNode));

        return removed;
    }

    /**
     * Gets the area of an <code>Entry</code>
     * 
     * @param e
     *                The <code>Entry</code>
     * 
     * @return the area
     */
    private double getEntryArea(Entry e) {
        return this.getEnvelopeArea(e.getBounds());
    }

    private double getEnvelopeArea(Envelope env) {
        return env.getWidth() * env.getHeight();
    }

    private double getAreaIncrease(Envelope orig, Envelope add) {
        double ret = 0d;

        // The old values
        Envelope env = new Envelope(orig);
        double w = env.getWidth();
        double h = env.getHeight();

        // Expand the envelope
        env.expandToInclude(add);

        // Check area delta
        double nw = env.getWidth();
        double nh = env.getHeight();

        ret += ((nw - w) * nh); // new height
        ret += ((nh - h) * w); // old width

        return ret;
    }

    private double getAreaDifference(Envelope env, Entry e1, Entry e2) {
        return this.getEnvelopeArea(env) - this.getEntryArea(e1)
                - this.getEntryArea(e2);
    }

    /**
     * @see java.lang.Object#toString()
     */
    public String toString() {
        Node root = this.store.getRoot();

        String ret = null;

        try {
            ret = this.dump(root, 0);
        } catch (TreeException e) {
            e.printStackTrace();
        }

        return ret;
    }

    private String dump(Node node, int indent) throws TreeException {
        StringBuffer spc = new StringBuffer();

        for (int i = 0; i < indent; i++) {
            spc.append("  ");
        }

        StringBuffer ret = new StringBuffer();
        ret.append(spc);
        ret.append("Node: ").append(node.getBounds());
        ret.append(System.getProperty("line.separator"));

        spc.append("  ");

        for (int i = 0; i < node.getEntriesCount(); i++) {
            ret.append(spc).append(node.getEntry(i)).append(
                    System.getProperty("line.separator"));

            if (!node.isLeaf()) {
                ret
                        .append(this.dump(this.store.getNode(node.getEntry(i),
                                node), indent + 1));
            }
        }

        return ret.toString();
    }
}