// Spatial Index Library
//
// Copyright (C) 2002  Navel Ltd.
//
// 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; either
// version 2.1 of the License, or (at your option) any later version.
//
// 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.
//
// You should have received a copy of the GNU Lesser General Public
// License aint with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
// Contact information:
//  Mailing address:
//    Marios Hadjieleftheriou
//    University of California, Riverside
//    Department of Computer Science
//    Surge Building, Room 310
//    Riverside, CA 92521
//
//  Email:
//    marioh@cs.ucr.edu
package org.geotools.caching.spatialindex.rtree;

import org.geotools.caching.spatialindex.spatialindex.*;
import org.geotools.caching.spatialindex.storagemanager.*;

import java.io.*;

import java.util.*;


public class RTree implements ISpatialIndex {
    RWLock m_rwLock;
    IStorageManager m_pStorageManager;
    int m_rootID;
    int m_headerID;
    int m_treeVariant;
    double m_fillFactor;
    int m_indexCapacity;
    int m_leafCapacity;
    int m_nearMinimumOverlapFactor;

    // The R*-Tree 'p' constant, for calculating nearly minimum overlap cost.
    // [Beckmann, Kriegel, Schneider, Seeger 'The R*-tree: An efficient and Robust Access Method
    // for Points and Rectangles, Section 4.1]
    double m_splitDistributionFactor;

    // The R*-Tree 'm' constant, for calculating spliting distributions.
    // [Beckmann, Kriegel, Schneider, Seeger 'The R*-tree: An efficient and Robust Access Method
    // for Points and Rectangles, Section 4.2]
    double m_reinsertFactor;

    // The R*-Tree 'p' constant, for removing entries at reinserts.
    // [Beckmann, Kriegel, Schneider, Seeger 'The R*-tree: An efficient and Robust Access Method
    //  for Points and Rectangles, Section 4.3]
    int m_dimension;
    Region m_infiniteRegion;
    Statistics m_stats;
    ArrayList m_writeNodeCommands = new ArrayList();
    ArrayList m_readNodeCommands = new ArrayList();
    ArrayList m_deleteNodeCommands = new ArrayList();

    public RTree(PropertySet ps, IStorageManager sm) {
        m_rwLock = new RWLock();
        m_pStorageManager = sm;
        m_rootID = IStorageManager.NewPage;
        m_headerID = IStorageManager.NewPage;
        m_treeVariant = SpatialIndex.RtreeVariantRstar;
        m_fillFactor = 0.7f;
        m_indexCapacity = 100;
        m_leafCapacity = 100;
        m_nearMinimumOverlapFactor = 32;
        m_splitDistributionFactor = 0.4f;
        m_reinsertFactor = 0.3f;
        m_dimension = 2;

        m_infiniteRegion = new Region();
        m_stats = new Statistics();

        Object var = ps.getProperty("IndexIdentifier");

        if (var != null) {
            if (!(var instanceof Integer)) {
                throw new IllegalArgumentException(
                    "Property IndexIdentifier must an Integer");
            }

            m_headerID = ((Integer) var).intValue();

            try {
                initOld(ps);
            } catch (IOException e) {
                System.err.println(e);
                throw new IllegalStateException(
                    "initOld failed with IOException");
            }
        } else {
            try {
                initNew(ps);
            } catch (IOException e) {
                System.err.println(e);
                throw new IllegalStateException(
                    "initNew failed with IOException");
            }

            Integer i = new Integer(m_headerID);
            ps.setProperty("IndexIdentifier", i);
        }
    }

    // added by CR
    //
    public void deleteLeaf(Leaf l) {
        Stack pathBuffer = new Stack();

        for (int i = 0; i < l.getChildrenCount(); i++) {
            //l.deleteEntry(i) ;
            //this.deleteData(l.getChildShape(i), l.getChildIdentifier(i)) ;
            l.deleteData(l.getChildIdentifier(i), pathBuffer);
            m_stats.m_data--;
        }
    }

    public void deleteLeaf(Index node, int leafIndex) {
        node.deleteEntry(leafIndex);
    }

    public List readLeaf(Leaf leaf) {
        List ret = new ArrayList();

        for (int i = 0; i < leaf.getChildrenCount(); i++) {
            ret.add(new String(leaf.m_pData[i]));
        }

        return ret;
    }

    //
    // ISpatialIndex interface
    //
    public void insertData(final byte[] data, final IShape shape, int id) {
        if (shape.getDimension() != m_dimension) {
            throw new IllegalArgumentException(
                "insertData: Shape has the wrong number of dimensions.");
        }

        m_rwLock.write_lock();

        try {
            Region mbr = shape.getMBR();

            byte[] buffer = null;

            if ((data != null) && (data.length > 0)) {
                buffer = new byte[data.length];
                System.arraycopy(data, 0, buffer, 0, data.length);
            }

            insertData_impl(buffer, mbr, id);

            // the buffer is stored in the tree. Do not delete here.
        } finally {
            m_rwLock.write_unlock();
        }
    }

    public boolean deleteData(final IShape shape, int id) {
        if (shape.getDimension() != m_dimension) {
            throw new IllegalArgumentException(
                "deleteData: Shape has the wrong number of dimensions.");
        }

        m_rwLock.write_lock();

        try {
            Region mbr = shape.getMBR();

            return deleteData_impl(mbr, id);
        } finally {
            m_rwLock.write_unlock();
        }
    }

    public void containmentQuery(final IShape query, final IVisitor v) {
        if (query.getDimension() != m_dimension) {
            throw new IllegalArgumentException(
                "containmentQuery: Shape has the wrong number of dimensions.");
        }

        rangeQuery(SpatialIndex.ContainmentQuery, query, v);
    }

    public void intersectionQuery(final IShape query, final IVisitor v) {
        if (query.getDimension() != m_dimension) {
            throw new IllegalArgumentException(
                "intersectionQuery: Shape has the wrong number of dimensions.");
        }

        rangeQuery(SpatialIndex.IntersectionQuery, query, v);
    }

    public void pointLocationQuery(final IShape query, final IVisitor v) {
        if (query.getDimension() != m_dimension) {
            throw new IllegalArgumentException(
                "pointLocationQuery: Shape has the wrong number of dimensions.");
        }

        Region r = null;

        if (query instanceof Point) {
            r = new Region((Point) query, (Point) query);
        } else if (query instanceof Region) {
            r = (Region) query;
        } else {
            throw new IllegalArgumentException(
                "pointLocationQuery: IShape can be Point or Region only.");
        }

        rangeQuery(SpatialIndex.IntersectionQuery, r, v);
    }

    public void nearestNeighborQuery(int k, final IShape query,
        final IVisitor v, final INearestNeighborComparator nnc) {
        if (query.getDimension() != m_dimension) {
            throw new IllegalArgumentException(
                "nearestNeighborQuery: Shape has the wrong number of dimensions.");
        }

        m_rwLock.read_lock();

        try {
            // I need a priority queue here. It turns out that TreeSet sorts unique keys only and since I am
            // sorting according to distances, it is not assured that all distances will be unique. TreeMap
            // also sorts unique keys. Thus, I am simulating a priority queue using an ArrayList and binarySearch.
            ArrayList queue = new ArrayList();

            Node n = readNode(m_rootID);
            queue.add(new NNEntry(n, 0.0));

            int count = 0;
            double knearest = 0.0;

            while (queue.size() != 0) {
                NNEntry first = (NNEntry) queue.remove(0);

                if (first.m_pEntry instanceof Node) {
                    n = (Node) first.m_pEntry;
                    v.visitNode((INode) n);

                    for (int cChild = 0; cChild < n.m_children; cChild++) {
                        IEntry e;

                        if (n.m_level == 0) {
                            e = new Data(n.m_pData[cChild], n.m_pMBR[cChild],
                                    n.m_pIdentifier[cChild]);
                        } else {
                            e = (IEntry) readNode(n.m_pIdentifier[cChild]);
                        }

                        NNEntry e2 = new NNEntry(e,
                                nnc.getMinimumDistance(query, e));

                        // Why don't I use a TreeSet here? See comment above...
                        int loc = Collections.binarySearch(queue, e2,
                                new NNEntryComparator());

                        if (loc >= 0) {
                            queue.add(loc, e2);
                        } else {
                            queue.add((-loc - 1), e2);
                        }
                    }
                } else {
                    // report all nearest neighbors with equal furthest distances.
                    // (neighbors can be more than k, if many happen to have the same
                    //  furthest distance).
                    if ((count >= k) && (first.m_minDist > knearest)) {
                        break;
                    }

                    v.visitData((IData) first.m_pEntry);
                    m_stats.m_queryResults++;
                    count++;
                    knearest = first.m_minDist;
                }
            }
        } finally {
            m_rwLock.read_unlock();
        }
    }

    public void nearestNeighborQuery(int k, final IShape query, final IVisitor v) {
        if (query.getDimension() != m_dimension) {
            throw new IllegalArgumentException(
                "nearestNeighborQuery: Shape has the wrong number of dimensions.");
        }

        NNComparator nnc = new NNComparator();
        nearestNeighborQuery(k, query, v, nnc);
    }

    public void queryStrategy(final IQueryStrategy qs) {
        m_rwLock.read_lock();

        int[] next = new int[] { m_rootID };

        try {
            while (true) {
                Node n = readNode(next[0]);
                boolean[] hasNext = new boolean[] { false };
                qs.getNextEntry(n, next, hasNext);

                if (hasNext[0] == false) {
                    break;
                }
            }
        } finally {
            m_rwLock.read_unlock();
        }
    }

    public PropertySet getIndexProperties() {
        PropertySet pRet = new PropertySet();

        // dimension
        pRet.setProperty("Dimension", new Integer(m_dimension));

        // index capacity
        pRet.setProperty("IndexCapacity", new Integer(m_indexCapacity));

        // leaf capacity
        pRet.setProperty("LeafCapacity", new Integer(m_leafCapacity));

        // R-tree variant
        pRet.setProperty("TreeVariant", new Integer(m_treeVariant));

        // fill factor
        pRet.setProperty("FillFactor", new Double(m_fillFactor));

        // near minimum overlap factor
        pRet.setProperty("NearMinimumOverlapFactor",
            new Integer(m_nearMinimumOverlapFactor));

        // split distribution factor
        pRet.setProperty("SplitDistributionFactor",
            new Double(m_splitDistributionFactor));

        // reinsert factor
        pRet.setProperty("ReinsertFactor", new Double(m_reinsertFactor));

        return pRet;
    }

    public void addWriteNodeCommand(INodeCommand nc) {
        m_writeNodeCommands.add(nc);
    }

    public void addReadNodeCommand(INodeCommand nc) {
        m_readNodeCommands.add(nc);
    }

    public void addDeleteNodeCommand(INodeCommand nc) {
        m_deleteNodeCommands.add(nc);
    }

    public boolean isIndexValid() {
        boolean ret = true;
        Stack st = new Stack();
        Node root = readNode(m_rootID);

        if (root.m_level != (m_stats.m_treeHeight - 1)) {
            System.err.println("Invalid tree height");

            return false;
        }

        HashMap nodesInLevel = new HashMap();
        nodesInLevel.put(new Integer(root.m_level), new Integer(1));

        ValidateEntry e = new ValidateEntry(root.m_nodeMBR, root);
        st.push(e);

        while (!st.empty()) {
            e = (ValidateEntry) st.pop();

            Region tmpRegion = (Region) m_infiniteRegion.clone();

            for (int cDim = 0; cDim < m_dimension; cDim++) {
                tmpRegion.m_pLow[cDim] = Double.POSITIVE_INFINITY;
                tmpRegion.m_pHigh[cDim] = Double.NEGATIVE_INFINITY;

                for (int cChild = 0; cChild < e.m_pNode.m_children; cChild++) {
                    tmpRegion.m_pLow[cDim] = Math.min(tmpRegion.m_pLow[cDim],
                            e.m_pNode.m_pMBR[cChild].m_pLow[cDim]);
                    tmpRegion.m_pHigh[cDim] = Math.max(tmpRegion.m_pHigh[cDim],
                            e.m_pNode.m_pMBR[cChild].m_pHigh[cDim]);
                }
            }

            if (!(tmpRegion.equals(e.m_pNode.m_nodeMBR))) {
                System.err.println("Invalid parent information");
                ret = false;
            } else if (!(tmpRegion.equals(e.m_parentMBR))) {
                System.err.println("Error in parent");
                ret = false;
            }

            if (e.m_pNode.m_level != 0) {
                for (int cChild = 0; cChild < e.m_pNode.m_children; cChild++) {
                    ValidateEntry tmpEntry = new ValidateEntry(e.m_pNode.m_pMBR[cChild],
                            readNode(e.m_pNode.m_pIdentifier[cChild]));

                    if (!nodesInLevel.containsKey(
                                new Integer(tmpEntry.m_pNode.m_level))) {
                        nodesInLevel.put(new Integer(tmpEntry.m_pNode.m_level),
                            new Integer(1));
                    } else {
                        int i = ((Integer) nodesInLevel.get(new Integer(
                                    tmpEntry.m_pNode.m_level))).intValue();
                        nodesInLevel.put(new Integer(tmpEntry.m_pNode.m_level),
                            new Integer(i + 1));
                    }

                    st.push(tmpEntry);
                }
            }
        }

        int nodes = 0;

        for (int cLevel = 0; cLevel < m_stats.m_treeHeight; cLevel++) {
            int i1 = ((Integer) nodesInLevel.get(new Integer(cLevel))).intValue();
            int i2 = ((Integer) m_stats.m_nodesInLevel.get(cLevel)).intValue();

            if (i1 != i2) {
                System.err.println("Invalid nodesInLevel information");
                ret = false;
            }

            nodes += i2;
        }

        if (nodes != m_stats.m_nodes) {
            System.err.println("Invalid number of nodes information");
            ret = false;
        }

        return ret;
    }

    public IStatistics getStatistics() {
        return (IStatistics) m_stats.clone();
    }

    public void flush() throws IllegalStateException {
        try {
            storeHeader();
            m_pStorageManager.flush();
        } catch (IOException e) {
            System.err.println(e);
            throw new IllegalStateException("flush failed with IOException");
        }
    }

    //
    // Internals
    //
    private void initNew(PropertySet ps) throws IOException {
        Object var;

        // tree variant.
        var = ps.getProperty("TreeVariant");

        if (var != null) {
            if (var instanceof Integer) {
                int i = ((Integer) var).intValue();

                if ((i != SpatialIndex.RtreeVariantLinear) &&
                        (i != SpatialIndex.RtreeVariantQuadratic) &&
                        (i != SpatialIndex.RtreeVariantRstar)) {
                    throw new IllegalArgumentException(
                        "Property TreeVariant not a valid variant");
                }

                m_treeVariant = i;
            } else {
                throw new IllegalArgumentException(
                    "Property TreeVariant must be an Integer");
            }
        }

        // fill factor.
        var = ps.getProperty("FillFactor");

        if (var != null) {
            if (var instanceof Double) {
                double f = ((Double) var).doubleValue();

                if ((f <= 0.0f) || (f >= 1.0f)) {
                    throw new IllegalArgumentException(
                        "Property FillFactor must be in (0.0, 1.0)");
                }

                m_fillFactor = f;
            } else {
                throw new IllegalArgumentException(
                    "Property FillFactor must be a Double");
            }
        }

        // index capacity.
        var = ps.getProperty("IndexCapacity");

        if (var != null) {
            if (var instanceof Integer) {
                int i = ((Integer) var).intValue();

                if (i < 3) {
                    throw new IllegalArgumentException(
                        "Property IndexCapacity must be >= 3");
                }

                m_indexCapacity = i;
            } else {
                throw new IllegalArgumentException(
                    "Property IndexCapacity must be an Integer");
            }
        }

        // leaf capacity.
        var = ps.getProperty("LeafCapacity");

        if (var != null) {
            if (var instanceof Integer) {
                int i = ((Integer) var).intValue();

                if (i < 3) {
                    throw new IllegalArgumentException(
                        "Property LeafCapacity must be >= 3");
                }

                m_leafCapacity = i;
            } else {
                throw new IllegalArgumentException(
                    "Property LeafCapacity must be an Integer");
            }
        }

        // near minimum overlap factor.
        var = ps.getProperty("NearMinimumOverlapFactor");

        if (var != null) {
            if (var instanceof Integer) {
                int i = ((Integer) var).intValue();

                if ((i < 1) || (i > m_indexCapacity) || (i > m_leafCapacity)) {
                    throw new IllegalArgumentException(
                        "Property NearMinimumOverlapFactor must be less than both index and leaf capacities");
                }

                m_nearMinimumOverlapFactor = i;
            } else {
                throw new IllegalArgumentException(
                    "Property NearMinimumOverlapFactor must be an Integer");
            }
        }

        // split distribution factor.
        var = ps.getProperty("SplitDistributionFactor");

        if (var != null) {
            if (var instanceof Double) {
                double f = ((Double) var).doubleValue();

                if ((f <= 0.0f) || (f >= 1.0f)) {
                    throw new IllegalArgumentException(
                        "Property SplitDistributionFactor must be in (0.0, 1.0)");
                }

                m_splitDistributionFactor = f;
            } else {
                throw new IllegalArgumentException(
                    "Property SplitDistriburionFactor must be a Double");
            }
        }

        // reinsert factor.
        var = ps.getProperty("ReinsertFactor");

        if (var != null) {
            if (var instanceof Double) {
                double f = ((Double) var).doubleValue();

                if ((f <= 0.0f) || (f >= 1.0f)) {
                    throw new IllegalArgumentException(
                        "Property ReinsertFactor must be in (0.0, 1.0)");
                }

                m_reinsertFactor = f;
            } else {
                throw new IllegalArgumentException(
                    "Property ReinsertFactor must be a Double");
            }
        }

        // dimension
        var = ps.getProperty("Dimension");

        if (var != null) {
            if (var instanceof Integer) {
                int i = ((Integer) var).intValue();

                if (i <= 1) {
                    throw new IllegalArgumentException(
                        "Property Dimension must be >= 1");
                }

                m_dimension = i;
            } else {
                throw new IllegalArgumentException(
                    "Property Dimension must be an Integer");
            }
        }

        m_infiniteRegion.m_pLow = new double[m_dimension];
        m_infiniteRegion.m_pHigh = new double[m_dimension];

        for (int cDim = 0; cDim < m_dimension; cDim++) {
            m_infiniteRegion.m_pLow[cDim] = Double.POSITIVE_INFINITY;
            m_infiniteRegion.m_pHigh[cDim] = Double.NEGATIVE_INFINITY;
        }

        m_stats.m_treeHeight = 1;
        m_stats.m_nodesInLevel.add(new Integer(0));

        Leaf root = new Leaf(this, -1);
        m_rootID = writeNode(root);

        storeHeader();
    }

    private void initOld(PropertySet ps) throws IOException {
        loadHeader();

        // only some of the properties may be changed.
        // the rest are just ignored.
        Object var;

        // tree variant.
        var = ps.getProperty("TreeVariant");

        if (var != null) {
            if (var instanceof Integer) {
                int i = ((Integer) var).intValue();

                if ((i != SpatialIndex.RtreeVariantLinear) &&
                        (i != SpatialIndex.RtreeVariantQuadratic) &&
                        (i != SpatialIndex.RtreeVariantRstar)) {
                    throw new IllegalArgumentException(
                        "Property TreeVariant not a valid variant");
                }

                m_treeVariant = i;
            } else {
                throw new IllegalArgumentException(
                    "Property TreeVariant must be an Integer");
            }
        }

        // near minimum overlap factor.
        var = ps.getProperty("NearMinimumOverlapFactor");

        if (var != null) {
            if (var instanceof Integer) {
                int i = ((Integer) var).intValue();

                if ((i < 1) || (i > m_indexCapacity) || (i > m_leafCapacity)) {
                    throw new IllegalArgumentException(
                        "Property NearMinimumOverlapFactor must be less than both index and leaf capacities");
                }

                m_nearMinimumOverlapFactor = i;
            } else {
                throw new IllegalArgumentException(
                    "Property NearMinimumOverlapFactor must be an Integer");
            }
        }

        // split distribution factor.
        var = ps.getProperty("SplitDistributionFactor");

        if (var != null) {
            if (var instanceof Double) {
                double f = ((Double) var).doubleValue();

                if ((f <= 0.0f) || (f >= 1.0f)) {
                    throw new IllegalArgumentException(
                        "Property SplitDistributionFactor must be in (0.0, 1.0)");
                }

                m_splitDistributionFactor = f;
            } else {
                throw new IllegalArgumentException(
                    "Property SplitDistriburionFactor must be a Double");
            }
        }

        // reinsert factor.
        var = ps.getProperty("ReinsertFactor");

        if (var != null) {
            if (var instanceof Double) {
                double f = ((Double) var).doubleValue();

                if ((f <= 0.0f) || (f >= 1.0f)) {
                    throw new IllegalArgumentException(
                        "Property ReinsertFactor must be in (0.0, 1.0)");
                }

                m_reinsertFactor = f;
            } else {
                throw new IllegalArgumentException(
                    "Property ReinsertFactor must be a Double");
            }
        }

        m_infiniteRegion.m_pLow = new double[m_dimension];
        m_infiniteRegion.m_pHigh = new double[m_dimension];

        for (int cDim = 0; cDim < m_dimension; cDim++) {
            m_infiniteRegion.m_pLow[cDim] = Double.POSITIVE_INFINITY;
            m_infiniteRegion.m_pHigh[cDim] = Double.NEGATIVE_INFINITY;
        }
    }

    private void storeHeader() throws IOException {
        ByteArrayOutputStream bs = new ByteArrayOutputStream();
        DataOutputStream ds = new DataOutputStream(bs);

        ds.writeInt(m_rootID);
        ds.writeInt(m_treeVariant);
        ds.writeDouble(m_fillFactor);
        ds.writeInt(m_indexCapacity);
        ds.writeInt(m_leafCapacity);
        ds.writeInt(m_nearMinimumOverlapFactor);
        ds.writeDouble(m_splitDistributionFactor);
        ds.writeDouble(m_reinsertFactor);
        ds.writeInt(m_dimension);
        ds.writeLong(m_stats.m_nodes);
        ds.writeLong(m_stats.m_data);
        ds.writeInt(m_stats.m_treeHeight);

        for (int cLevel = 0; cLevel < m_stats.m_treeHeight; cLevel++) {
            ds.writeInt(((Integer) m_stats.m_nodesInLevel.get(cLevel)).intValue());
        }

        ds.flush();
        m_headerID = m_pStorageManager.storeByteArray(m_headerID,
                bs.toByteArray());
    }

    private void loadHeader() throws IOException {
        byte[] data = m_pStorageManager.loadByteArray(m_headerID);
        DataInputStream ds = new DataInputStream(new ByteArrayInputStream(data));

        m_rootID = ds.readInt();
        m_treeVariant = ds.readInt();
        m_fillFactor = ds.readDouble();
        m_indexCapacity = ds.readInt();
        m_leafCapacity = ds.readInt();
        m_nearMinimumOverlapFactor = ds.readInt();
        m_splitDistributionFactor = ds.readDouble();
        m_reinsertFactor = ds.readDouble();
        m_dimension = ds.readInt();
        m_stats.m_nodes = ds.readLong();
        m_stats.m_data = ds.readLong();
        m_stats.m_treeHeight = ds.readInt();

        for (int cLevel = 0; cLevel < m_stats.m_treeHeight; cLevel++) {
            m_stats.m_nodesInLevel.add(new Integer(ds.readInt()));
        }
    }

    protected void insertData_impl(byte[] pData, Region mbr, int id) {
        assert mbr.getDimension() == m_dimension;

        boolean[] overflowTable;

        Stack pathBuffer = new Stack();

        Node root = readNode(m_rootID);

        overflowTable = new boolean[root.m_level];

        for (int cLevel = 0; cLevel < root.m_level; cLevel++)
            overflowTable[cLevel] = false;

        Node l = root.chooseSubtree(mbr, 0, pathBuffer);
        l.insertData(pData, mbr, id, pathBuffer, overflowTable);

        m_stats.m_data++;
    }

    protected void insertData_impl(byte[] pData, Region mbr, int id, int level,
        boolean[] overflowTable) {
        assert mbr.getDimension() == m_dimension;

        Stack pathBuffer = new Stack();

        Node root = readNode(m_rootID);
        Node n = root.chooseSubtree(mbr, level, pathBuffer);
        n.insertData(pData, mbr, id, pathBuffer, overflowTable);
    }

    protected boolean deleteData_impl(final Region mbr, int id) {
        assert mbr.getDimension() == m_dimension;

        boolean bRet = false;

        Stack pathBuffer = new Stack();

        Node root = readNode(m_rootID);
        Leaf l = root.findLeaf(mbr, id, pathBuffer);

        if (l != null) {
            l.deleteData(id, pathBuffer);
            m_stats.m_data--;
            bRet = true;
        }

        return bRet;
    }

    protected int writeNode(Node n) throws IllegalStateException {
        byte[] buffer = null;

        try {
            buffer = n.store();
        } catch (IOException e) {
            System.err.println(e);
            throw new IllegalStateException("writeNode failed with IOException");
        }

        int page;

        if (n.m_identifier < 0) {
            page = IStorageManager.NewPage;
        } else {
            page = n.m_identifier;
        }

        try {
            page = m_pStorageManager.storeByteArray(page, buffer);
        } catch (InvalidPageException e) {
            System.err.println(e);
            throw new IllegalStateException(
                "writeNode failed with InvalidPageException");
        }

        if (n.m_identifier < 0) {
            n.m_identifier = page;
            m_stats.m_nodes++;

            int i = ((Integer) m_stats.m_nodesInLevel.get(n.m_level)).intValue();
            m_stats.m_nodesInLevel.set(n.m_level, new Integer(i + 1));
        }

        m_stats.m_writes++;

        for (int cIndex = 0; cIndex < m_writeNodeCommands.size(); cIndex++) {
            ((INodeCommand) m_writeNodeCommands.get(cIndex)).execute(n);
        }

        return page;
    }

    protected Node readNode(int id) {
        byte[] buffer;
        DataInputStream ds = null;
        int nodeType = -1;
        Node n = null;

        try {
            buffer = m_pStorageManager.loadByteArray(id);
            ds = new DataInputStream(new ByteArrayInputStream(buffer));
            nodeType = ds.readInt();

            if (nodeType == SpatialIndex.PersistentIndex) {
                n = new Index(this, -1, 0);
            } else if (nodeType == SpatialIndex.PersistentLeaf) {
                n = new Leaf(this, -1);
            } else {
                throw new IllegalStateException(
                    "readNode failed reading the correct node type information");
            }

            n.m_pTree = this;
            n.m_identifier = id;
            n.load(buffer);

            m_stats.m_reads++;
        } catch (InvalidPageException e) {
            System.err.println(e);
            throw new IllegalStateException(
                "readNode failed with InvalidPageException");
        } catch (IOException e) {
            System.err.println(e);
            throw new IllegalStateException("readNode failed with IOException");
        }

        for (int cIndex = 0; cIndex < m_readNodeCommands.size(); cIndex++) {
            ((INodeCommand) m_readNodeCommands.get(cIndex)).execute(n);
        }

        return n;
    }

    protected void deleteNode(Node n) {
        try {
            m_pStorageManager.deleteByteArray(n.m_identifier);
        } catch (InvalidPageException e) {
            System.err.println(e);
            throw new IllegalStateException(
                "deleteNode failed with InvalidPageException");
        }

        m_stats.m_nodes--;

        int i = ((Integer) m_stats.m_nodesInLevel.get(n.m_level)).intValue();
        m_stats.m_nodesInLevel.set(n.m_level, new Integer(i - 1));

        for (int cIndex = 0; cIndex < m_deleteNodeCommands.size(); cIndex++) {
            ((INodeCommand) m_deleteNodeCommands.get(cIndex)).execute(n);
        }
    }

    private void rangeQuery(int type, final IShape query, final IVisitor v) {
        m_rwLock.read_lock();

        try {
            Stack st = new Stack();
            Node root = readNode(m_rootID);

            if ((root.m_children > 0) && query.intersects(root.m_nodeMBR)) {
                st.push(root);
            }

            while (!st.empty()) {
                Node n = (Node) st.pop();

                if (n.m_level == 0) {
                    v.visitNode((INode) n);

                    for (int cChild = 0; cChild < n.m_children; cChild++) {
                        boolean b;

                        if (type == SpatialIndex.ContainmentQuery) {
                            b = query.contains(n.m_pMBR[cChild]);
                        } else {
                            b = query.intersects(n.m_pMBR[cChild]);
                        }

                        if (b) {
                            Data data = new Data(n.m_pData[cChild],
                                    n.m_pMBR[cChild], n.m_pIdentifier[cChild]);
                            v.visitData(data);
                            m_stats.m_queryResults++;
                        }
                    }
                } else {
                    v.visitNode((INode) n);

                    for (int cChild = 0; cChild < n.m_children; cChild++) {
                        if (query.intersects(n.m_pMBR[cChild])) {
                            st.push(readNode(n.m_pIdentifier[cChild]));
                        }
                    }
                }
            }
        } finally {
            m_rwLock.read_unlock();
        }
    }

    public String toString() {
        String s = "Dimension: " + m_dimension + "\n" + "Fill factor: " +
            m_fillFactor + "\n" + "Index capacity: " + m_indexCapacity + "\n" +
            "Leaf capacity: " + m_leafCapacity + "\n";

        if (m_treeVariant == SpatialIndex.RtreeVariantRstar) {
            s += ("Near minimum overlap factor: " + m_nearMinimumOverlapFactor +
            "\n" + "Reinsert factor: " + m_reinsertFactor + "\n" +
            "Split distribution factor: " + m_splitDistributionFactor + "\n");
        }

        s += ("Utilization: " +
        ((100 * m_stats.getNumberOfData()) / (m_stats.getNumberOfNodesInLevel(0) * m_leafCapacity)) +
        "%" + "\n" + m_stats);

        return s;
    }

    class NNEntry {
        IEntry m_pEntry;
        double m_minDist;

        NNEntry(IEntry e, double f) {
            m_pEntry = e;
            m_minDist = f;
        }
    }

    class NNEntryComparator implements Comparator {
        public int compare(Object o1, Object o2) {
            NNEntry n1 = (NNEntry) o1;
            NNEntry n2 = (NNEntry) o2;

            if (n1.m_minDist < n2.m_minDist) {
                return -1;
            }

            if (n1.m_minDist > n2.m_minDist) {
                return 1;
            }

            return 0;
        }
    }

    class NNComparator implements INearestNeighborComparator {
        public double getMinimumDistance(IShape query, IEntry e) {
            IShape s = e.getShape();

            return query.getMinimumDistance(s);
        }
    }

    class ValidateEntry {
        Region m_parentMBR;
        Node m_pNode;

        ValidateEntry(Region r, Node pNode) {
            m_parentMBR = r;
            m_pNode = pNode;
        }
    }

    class Data implements IData {
        int m_id;
        Region m_shape;
        byte[] m_pData;

        Data(byte[] pData, Region mbr, int id) {
            m_id = id;
            m_shape = mbr;
            m_pData = pData;
        }

        public int getIdentifier() {
            return m_id;
        }

        public IShape getShape() {
            return new Region(m_shape);
        }

        public byte[] getData() {
            byte[] data = new byte[m_pData.length];
            System.arraycopy(m_pData, 0, data, 0, m_pData.length);

            return data;
        }
    }
}
