zone.java

High performance DB query

/*
 * @(#)$Id: Zone.java,v 1.8 2004/07/02 23:59:20 huebsch Exp $
 *
 * Copyright (c) 2001-2004 Regents of the University of California.
 * All rights reserved.
 *
 * This file is distributed under the terms in the attached BERKELEY-LICENSE
 * file. If you do not find these files, copies can be found by writing to:
 * Computer Science Division, Database Group, Universite of California,
 * 617 Soda Hall #1776, Berkeley, CA 94720-1776. Attention: Berkeley License
 *
 * Copyright (c) 2003-2004 Intel Corporation. All rights reserved.
 *
 * This file is distributed under the terms in the attached INTEL-LICENSE file.
 * If you do not find these files, copies can be found by writing to:
 * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300,
 * Berkeley, CA, 94704.  Attention:  Intel License Inquiry.
 */


package overlay.location.can;

import services.network.Payload;
import util.network.serialization.GenericByteBuffer;
import util.network.serialization.SerializationManager;
import util.network.serialization.SerializeArray;

/** The class encapsulates a CAN zone.  The zone object contains real-number intervals denoting the span of an area along each dimension.  The number of dimensions is resourceLocation.can.Can.DIM. */
public class Zone implements Payload {

    public static long serialVersionUID =
        SerializationManager.getSerialUID("overlay.location.can.Zone");
    private double[][] intervals;
    private double[] center;
    private double[] scratchCoordinates;
    public static final Zone FULL = new Zone(true);
    public static final Zone PHANTOM = new Zone(false);

    /**
     * DeSerialize the object from the provided GenericByteBuffer.
     *
     * @param inputBuffer
     */
    public Zone(GenericByteBuffer inputBuffer) {
        double[][] newIntervals = new double[Can.DIM][];

        for (int i = 0; i < Can.DIM; i++) {
            newIntervals[i] = SerializeArray.deSerializeDouble(inputBuffer);
        }

        init(newIntervals);
    }

    /**
     * Serialize the object into the provided GenericByteBuffer.
     *
     * @param outputBuffer
     * @return
     */
    public long serialize(GenericByteBuffer outputBuffer) {
        for (int i = 0; i < Can.DIM; i++) {
            SerializeArray.serializeDouble(outputBuffer, intervals[i]);
        }

        return serialVersionUID;
    }

    /** The full-hash-space zone */
    private Zone(boolean full) {
        intervals = new double[Can.DIM][2];
        center = new double[Can.DIM];
        scratchCoordinates = new double[Can.DIM];

        for (int i = 0; i < Can.DIM; i++) {
            intervals[i][0] = 0.0;

            if (full == true) {
                intervals[i][1] = 1.0;
            } else {
                intervals[i][1] = 0.0;
            }
        }

        findCenter();
    }

    /**
     * Create a new zone given an array of intervals.
     *
     * @param newIntervals
     */
    public Zone(double[][] newIntervals) {
        init(newIntervals);
    }

    /**
     * Create a copy of a Zone.
     *
     * @param oldZone
     */
    public Zone(Zone oldZone) {
        init(oldZone.intervals);
    }

    private void init(double[][] newIntervals) {
        intervals = new double[Can.DIM][2];
        center = new double[Can.DIM];
        scratchCoordinates = new double[Can.DIM];

        for (int i = 0; i < Can.DIM; i++) {
            intervals[i][0] = newIntervals[i][0];
            intervals[i][1] = newIntervals[i][1];
        }

        findCenter();

        if ( !validZone()) {
            throw new RuntimeException("Bad zone");
        }
    }

    /**
     * Span of zone
     * @return
     */
    public double getArea() {
        double area = 1;

        // find the percentage of the space for each dimension
        for (int i = 0; i < Can.DIM; i++) {
            area *= (intervals[i][1] - intervals[i][0]);
        }

        return area;
    }

    /** Compute the center of this zone */
    private void findCenter() {
        for (int i = 0; i < Can.DIM; i++) {
            center[i] = (intervals[i][0] + intervals[i][1]) / 2.0;
        }
    }

    /**
     * Method getIntervals
     * @return
     */
    public double[][] getIntervals() {
        return intervals;
    }

    /**
     * Method getCenter
     * @return
     */
    public double[] getCenter() {
        return center;
    }

    /**
     * Returns TRUE is both zones have same center. Acts as a unique identifier for each zone
     *
     * @param zone
     * @return
     */
    public boolean equalCenter(Zone zone) {
        double[] yourCenter = zone.getCenter();

        if (yourCenter.length != center.length) {
            return false;
        }

        for (int k = 0; k < center.length; k++) {
            if (yourCenter[k] != center[k]) {
                return false;
            }
        }

        return true;
    }

    /**
     * Containment check.  If all coordinates are within the corresponding intervals, return true and false otherwise.
     *
     * @param coordinates
     * @return
     */
    public boolean contains(double[] coordinates) {
        for (int i = 0; i < Can.DIM; i++) {
            if ((coordinates[i] < intervals[i][0])
                    || (coordinates[i] >= intervals[i][1])) {
                return false;
            }
        }

        return true;
    }

    /**
     * Calculate the distance from the center of this zone to the given point
     *
     * @param coordinates
     * @return
     */
    public double distance(double[] coordinates) {
        double distance = 0;
        double projection;

        for (int i = 0; i < Can.DIM; i++) {
            projection = (coordinates[i] - center[i]);
            projection *= projection;
            distance += projection;
        }

        return Math.sqrt(distance);
    }

    /**
     * Does the given zone overlap this one along the given axis?
     *
     * @param zone
     * @param dimension
     * @return
     */
    public boolean overlaps(Zone zone, int dimension) {
        double a = intervals[dimension][0];
        double b = intervals[dimension][1];
        double c = zone.intervals[dimension][0];
        double d = zone.intervals[dimension][1];

        return (((a >= c) && (a < d)) || ((b > c) && (b <= d))
                || ((c >= a) && (c < b)) || ((d > a) && (d <= b)));
    }

    /**
     * Does the given zone overlap this one, must overlap on all dimensions
     *
     * @param zone
     * @return
     */
    public boolean overlaps(Zone zone) {
        for (int i = 0; i < Can.DIM; i++) {
            if (this.overlaps(zone, i) == false) {
                return false;
            }
        }

        return true;
    }

    /**
     * Check if the given zone abut me in the given direction and dimension
     *
     * @param zone
     * @param dimension
     * @param low
     * @return
     */
    public boolean abuts(Zone zone, int dimension, boolean low) {
        return ((low && (intervals[dimension][0]
                         % 1.0 == zone.intervals[dimension][1]
                                  % 1.0)) || ( !low && (intervals[dimension][1]
                                                        % 1.0 == zone.intervals[dimension][0]
                                                            % 1.0)));
    }

    /**
     * In which dimension does the given zone neighbor me? The result
     * is the dimension number or -1 if the zone doesn't neighbor me.
     *
     * @param zone
     * @return
     */
    public int neighbors(Zone zone) {
        int overlaps = 0;
        int abuts = 0;
        int abutsDim = -1;

        for (int dimension = 0; dimension < Can.DIM; dimension++) {
            if (overlaps(zone, dimension)) {
                overlaps++;
            } else {
                if (abuts(zone, dimension, true)
                        || abuts(zone, dimension, false)) {
                    abutsDim = dimension;

                    abuts++;
                } else {
                    return -1;
                }
            }
        }

        if ((abuts != 1) || (overlaps != Can.DIM - 1)) {
            return -1;
        } else {
            return abutsDim;
        }
    }

    /**
     * returns true if can merge with zone
     *
     * @param zone
     * @return
     */
    public boolean canMerge(Zone zone) {
        double[][] currentIntervals = this.getIntervals();
        double[][] arrivalIntervals = zone.getIntervals();
        double[][] newIntervals = new double[Can.DIM][2];
        int neighborDimension = neighbors(zone);

        for (int k = 0; k < Can.DIM; k++) {
            for (int j = 0; j < 2; j++) {
                if (k == neighborDimension) {
                    newIntervals[k][0] = Math.min(currentIntervals[k][0],
                                                  arrivalIntervals[k][0]);
                    newIntervals[k][1] = Math.max(currentIntervals[k][1],
                                                  arrivalIntervals[k][1]);
                } else {
                    newIntervals[k][0] = currentIntervals[k][0];
                    newIntervals[k][1] = currentIntervals[k][1];
                }
            }
        }

        Zone newZone = new Zone(newIntervals);

        return (newZone.getArea() == (getArea() + zone.getArea()));
    }

    /**
     * Find the closest-point distance of this zone to the given point
     *
     * @param coordinates
     * @return
     */
    public double closestPointDistance(double[] coordinates) {

        // Fill up the temporary coordinates with my closest point and then measure the distance between the two
        for (int i = 0; i < Can.DIM; i++) {

            // if this value is under my low value
            if (coordinates[i] < intervals[i][0]) {

                // Then compare its distance from my low value to its distance shifted by one tile to my high value
                if ((intervals[i][0] - coordinates[i])
                        < (coordinates[i] + 1.0 - intervals[i][1])) {

                    // If it's closer to the low point, use the low point
                    scratchCoordinates[i] = intervals[i][0];
                } else {
                    scratchCoordinates[i] = intervals[i][1];
                }
            } else if (coordinates[i] < intervals[i][1]) {

                // Otherwise, if the point is under my high value (i.e., within my interval, just use the point itself
                scratchCoordinates[i] = coordinates[i];
            } else {

                // Otherwise, (i.e., the point is over my high value), compare its distance from my high value to its distance shifted left to my low value and use my interval value that's closest
                if ((coordinates[i] - intervals[i][1])
                        < (intervals[i][0] - (coordinates[i] - 1.0))) {
                    scratchCoordinates[i] = intervals[i][1];
                } else {
                    scratchCoordinates[i] = intervals[i][0];
                }
            }
        }

        // Now that we have in scratch my closest point, measure the distance from the coordinates.  Measure the closest torus distance, i.e., the distance where all points are at most .5 from each other in every dimension
        double distance = 0;
        double projection;

        for (int i = 0; i < Can.DIM; i++) {
            projection = Math.abs(coordinates[i] - scratchCoordinates[i]);

            if (projection > .5) {
                projection = 1.0 - projection;
            }

            projection *= projection;
            distance += projection;
        }

        return Math.sqrt(distance);
    }

    /**
     * Return the number of intervals that contain the projection of this point
     *
     * @param coordinates
     * @return
     */
    public int dimensionContainment(double[] coordinates) {
        int counter = 0;

        for (int i = 0; i < Can.DIM; i++) {
            if ((coordinates[i] >= intervals[i][0])
                    && (coordinates[i] < intervals[i][1])) {
                counter++;
            }
        }

        return counter;
    }

    /**
     * Method validZone
     * @return
     */
    public boolean validZone() {

        // Check if intervals have correct number of dimensions
        if (intervals.length != Can.DIM) {
            return false;
        }

        for (int i = 0; i < Can.DIM; i++) {

            // Check to make sure interval is the proper size, 2, low and high
            if (intervals[i].length != 2) {
                return false;
            }

            // Check if low end is in bounds
            if ((intervals[i][0] < 0) || (intervals[i][0] > 1)) {
                return false;
            }

            // Check if high end is out of bounds
            if ((intervals[i][1] < 0) || (intervals[i][1] > 1)) {
                return false;
            }

            // Check if high is actually higher than low
            if (intervals[i][0] >= intervals[i][1]) {
                return false;
            }
        }

        return true;
    }

    /**
     * Method getSize
     * @return
     */
    public int getSize() {
        return (Payload.DOUBLE_SIZE * 2 * Can.DIM);
    }

    /**
     * Method toString
     * @return
     */
    public String toString() {
        String outStr = new String("<ZONE: (");

        for (int i = 0; i < Can.DIM; i++) {
            outStr += intervals[i][0] + " ";
        }

        outStr += ") to (";

        for (int i = 0; i < Can.DIM; i++) {
            outStr += intervals[i][1] + " ";
        }

        return outStr + ")>";
    }
}