neighborhood.java

High performance DB query

        // This is only used to pick one out of many neighbors with 0 distance.  A neighbor has 0 distance from a point without containing it, when that point lies at the top end of at least one of the neighbor's intervals.  Among many such neighbors, we pick the one that has the most intervals that actually contain the destination point.
        double maximumDimensionOverlap = 0;
        InetSocketAddress nextHop = null;
        Iterator iterator = iterator();

        // while there are more neighbors
        while (iterator.hasNext()) {
            InetSocketAddress neighbor = (InetSocketAddress) iterator.next();
            NodeRecord neighborNode = (NodeRecord) nodes.get(neighbor);

            // if the point is enclosed in the neighbor
            if (neighborNode.zone.contains(coordinates)) {
                return neighbor;
            }

            // otherwise, find the distance from the closest point of the neighbor to the point
            double distance =
                neighborNode.zone.closestPointDistance(coordinates);

            // If distance is not 0, just compare distances
            if (distance != 0) {

                // Is this the minimum?
                if (distance < minimumDistance) {
                    minimumDistance = distance;
                    nextHop = neighbor;
                }
            } else {

                // Otherwise, count the dimension overlap of the point in the neighbor.  Neighbors with more intervals containing the destination should be picked first.
                int dimensionOverlap =
                    neighborNode.zone.dimensionContainment(coordinates);

                // If the minimum is higher than 0, or is 0 but has a lower dimension overlap, then the new guy wins
                if ((minimumDistance > 0)
                        || ((minimumDistance == 0)
                            && (maximumDimensionOverlap < dimensionOverlap))) {
                    minimumDistance = distance;
                    nextHop = neighbor;
                    maximumDimensionOverlap = dimensionOverlap;
                }
            }
        }

        return nextHop;
    }

    /** Refresh the zone and current time of a node */
    private void refresh(InetSocketAddress node, Zone zone, int version,
                         double currentTime) {

        // Find the neighbor
        NodeRecord record = (NodeRecord) nodes.get(node);

        if ((zone == null) || (version < 0) || (currentTime < 0)) {
            throw new RuntimeException("Invalid node refresh");
        }

        record.lastHeard = currentTime;
        record.zone = zone;
        record.version = version;
    }

    /** Refresh the current time of a node */
    private void refresh(InetSocketAddress node, double currentTime) {

        // Find the neighbor
        NodeRecord record = (NodeRecord) nodes.get(node);

        if (currentTime < 0) {
            throw new RuntimeException("Invalid node refresh");
        }

        record.lastHeard = currentTime;
    }

    /**
     * Update a neighbor by the given address and zone.  If the node is known to me and his version number is no greater than the one updated, ignore the update.  If the new zone neighbors mine, insert if unknown or refresh if known.  Otherwise ignore the update.
     *
     * @param localZone
     * @param node
     * @param zone
     * @param version
     * @param currentTime
     */
    public void update(Zone localZone, InetSocketAddress node, Zone zone,
                       int version, double currentTime) {

        // Retrieve existing record if it exists
        NodeRecord record = (NodeRecord) nodes.get(node);

        if (record != null) {

            // Check if the version is a newer than exisiting
            if (record.version < version) {

                // Check if new zone is a neighbor
                if (localZone.neighbors(zone) != -1) {
                    refresh(node, zone, version, currentTime);
                } else {
                    remove(node);
                }
            } else {

                // Old zone information, but update last contact time
                refresh(node, currentTime);
            }
        } else {

            // New neighbor
            int dimension = localZone.neighbors(zone);

            if (dimension != -1) {
                insert(localZone, node, zone, dimension, version, currentTime);
            }
        }
    }

    /**
     * Remove a neighbor from the neighborhood.
     *
     * @param node
     */
    public void remove(InetSocketAddress node) {
        NodeRecord record = (NodeRecord) nodes.remove(node);

        if (record != null) {
            streets[record.dimension][0].remove(node);
            streets[record.dimension][1].remove(node);
        }
    }

    /**
     * Method checkInsert
     *
     * @param localZone
     * @param zone
     * @return
     */
    public int checkInsert(Zone localZone, Zone zone) {
        for (int k = 0; k < Can.DIM; k++) {
            if (localZone.abuts(zone, k, false)) {
                return k;
            }

            if (localZone.abuts(zone, k, true)) {
                return k;
            }
        }

        return -1;
    }

    /**
     * Insert a new neighbor given its new zone, its street and the current time.
     *
     * @param localZone
     * @param node
     * @param zone
     * @param dimension
     * @param version
     * @param currentTime
     */
    public void insert(Zone localZone, InetSocketAddress node, Zone zone,
                       int dimension, int version, double currentTime) {

        // Create the node record
        NodeRecord record = new NodeRecord(zone, currentTime, dimension,
                                           version);

        nodes.put(node, record);

        // Which of the directions on this dimension should I add this into?  Only where it abuts.
        if (localZone.abuts(zone, dimension, true)) {

            // Low side
            streets[dimension][0].insert(node);
        }

        if (localZone.abuts(zone, dimension, false)) {

            // High side
            streets[dimension][1].insert(node);
        }
    }

    /**
     * Cleanup the neighborhood, by eliminating all neighbors whose updates are overdue
     *
     * @param currentTime
     * @param expirationBuffer
     */
    public void cleanup(double currentTime, double expirationBuffer) {

        // The earliest acceptable lastHeard time
        double earliestTime = currentTime - expirationBuffer;

        // Empty out the toRemove list
        toRemove.clear();

        Iterator iterator = iterator();

        while (iterator.hasNext()) {
            InetSocketAddress node = (InetSocketAddress) iterator.next();
            NodeRecord record = (NodeRecord) nodes.get(node);

            if (record.lastHeard < earliestTime) {
                toRemove.add(node);
            }
        }

        // Now go through and perform the removals
        while ( !toRemove.isEmpty()) {
            InetSocketAddress node = (InetSocketAddress) toRemove.get(0);

            remove(node);
            toRemove.remove(0);
        }
    }

    /**
     * Return a ArrayList of Zones that are my neighbours
     * @return
     */
    public ArrayList getAllNeighbours() {
        ArrayList toRet = new ArrayList();
        Iterator iterator = iterator();

        while (iterator.hasNext()) {
            InetSocketAddress neighbor = (InetSocketAddress) iterator.next();
            NodeRecord record = (NodeRecord) nodes.get(neighbor);

            toRet.add(record.zone);
        }

        return toRet;
    }

    /**
     * Method getZone
     *
     * @param socketAddress
     * @return
     */
    public Zone getZone(InetSocketAddress socketAddress) {
        NodeRecord record = (NodeRecord) nodes.get(socketAddress);

        if (record != null) {
            return record.zone;
        }

        return null;
    }

    /**
     * Return an unordered iterator on all neighbor addresses.
     * @return
     */
    public Iterator iterator() {
        return nodes.keySet().iterator();
    }
}