neighborhood.java

High performance DB query

/*
 * @(#)$Id: Neighborhood.java,v 1.6 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 java.net.InetSocketAddress;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import services.network.Payload;
import util.network.serialization.SerializationManager;

/** The class encapsulates a CAN neighborhood.  The neighborhood object contains the entire set of neighbors of a single zone.  Neighbors are divided according to the dimension on which they abut the zone, and then on whether they come before or after the zone (wrapping around the edges of the space as necessary), into Streets. */
public class Neighborhood {

    /** My directory of nodes, indexed by node transport address.  For each node we maintain its currently known zone, the last time it was heard from and the dimension along which it abuts the neighborhood. */
    private HashMap nodes;

    /** My array of streets.  First index selects the dimension.  Second index selects before/after. */
    private Street[][] streets;

    /** My list of nodes to remove during cleanup */
    private ArrayList toRemove;

    /**
     * Get storage requirements
     * @return
     */
    public int getSize() {
        int streetSize = 0;

        for (int i = 0; i < Can.DIM; i++) {
            streetSize += SerializationManager.getPayloadSize(streets[i][0]);
            streetSize += SerializationManager.getPayloadSize(streets[i][1]);
        }

        if (nodes.isEmpty()) {
            return (toRemove.size() * Payload.INET_SOCKET_SIZE) + streetSize;
        } else {
            return (nodes.size() * ((NodeRecord) nodes.values().iterator().next()).getSize())
                   + (toRemove.size() * Payload.INET_SOCKET_SIZE) + streetSize;
        }
    }

    /**
     * Get number of neighbors
     * @return
     */
    public int getNumNeighbors() {
        int num = 0;

        for (int i = 0; i < Can.DIM; i++) {
            num += streets[i][0].getLength();
            num += streets[i][1].getLength();
        }

        return num;
    }

    /** Create a new neighborhood where I am the only resident in every direction, given who I am. */
    public Neighborhood() {
        nodes = new HashMap();
        streets = new Street[Can.DIM][2];

        for (int i = 0; i < Can.DIM; i++) {
            streets[i][0] = new Street();
            streets[i][1] = new Street();
        }

        toRemove = new ArrayList();
    }

    /**
     * Create a new neighborhood out of the given one, carved to match a given subzone.  It is assumed that the given subzone matches the neighborhood.  If that isn't the case, the results are undefined. The complementary zone and its future owner are also given.  The last heard times of my neighborhood are used here.
     *
     * @param old
     * @param oldZone
     * @param subZone
     * @param complementaryOwner
     * @param complementarySubZone
     * @param splitDimension
     * @param low
     */
    public Neighborhood(Neighborhood old, Zone oldZone, Zone subZone,
                        InetSocketAddress complementaryOwner,
                        Zone complementarySubZone, int splitDimension,
                        boolean low) {
        nodes = new HashMap();
        streets = new Street[Can.DIM][2];
        toRemove = new ArrayList();

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

                // Neighbors along the split Dimension are divided based on whether or not they abut the new zone.  Depending on the low input, the low or high street is included and the other street only contains the previous owner of the subzone.  In the special case where I span the entire dimension (i.e., from 0 to 1 and, therefore, I abut myself), the corresponding streets are empty, so I enter the zoneMate in both streets.
                if (oldZone.abuts(oldZone, i, true)) {    // doesn't matter

                    // which side
                    streets[i][0] = new Street(complementaryOwner);
                    streets[i][1] = new Street(complementaryOwner);
                } else if (low) {
                    streets[i][0] = new Street(old.streets[i][0]);

                    populateDirectory(old.nodes, streets[i][0]);

                    streets[i][1] = new Street(complementaryOwner);
                } else {
                    streets[i][1] = new Street(old.streets[i][1]);

                    populateDirectory(old.nodes, streets[i][1]);

                    streets[i][0] = new Street(complementaryOwner);
                }

                // Add the owner of the complementary zone into the directory.  Its last heard time will be updated when I instate the neighborhood and so will its version number.
                NodeRecord record = new NodeRecord(complementarySubZone, 0.0,
                                                   i, 0);

                nodes.put(complementaryOwner, record);
            } else {

                // Neighbors along other dimensions are divided based on whether or not they overlap the new zone along the split dimension.
                for (int j = 0; j < 2; j++) {
                    ArrayList overlappers = new ArrayList();
                    Iterator iterator = old.streets[i][j].iterator();

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

                        if (subZone.overlaps(record.zone, splitDimension)) {
                            overlappers.add(node);
                        }
                    }

                    streets[i][j] = new Street(overlappers);

                    populateDirectory(old.nodes, streets[i][j]);
                }
            }
        }
    }

    /**
     * Create a new neighborhood given its on-the-wire representation and the current time.
     *
     * @param neighbors
     * @param time
     */
    public Neighborhood(Neighbor[][][] neighbors, double time) {
        nodes = new HashMap();
        streets = new Street[Can.DIM][2];
        toRemove = new ArrayList();

        for (int dim = 0; dim < Can.DIM; dim++) {
            for (int dir = 0; dir < 2; dir++) {
                ArrayList streetNodes = new ArrayList();

                for (int i = 0; i < neighbors[dim][dir].length; i++) {
                    NodeRecord record =
                        new NodeRecord(neighbors[dim][dir][i].getZone(), time,
                                       dim,
                                       neighbors[dim][dir][i].getVersion());

                    nodes.put(neighbors[dim][dir][i].getAddress(), record);
                    streetNodes.add(neighbors[dim][dir][i].getAddress());
                }

                streets[dim][dir] = new Street(streetNodes);
            }
        }
    }

    /**
     * Fills up an array of neighbors with copies of my streets.
     *
     * @param neighbors
     */
    public void fillup(Neighbor[][][] neighbors) {
        Iterator iterator;

        for (int dim = 0; dim < Can.DIM; dim++) {
            for (int dir = 0; dir < 2; dir++) {
                neighbors[dim][dir] =
                    new Neighbor[streets[dim][dir].getLength()];
                iterator = streets[dim][dir].iterator();

                for (int i = 0; i < neighbors[dim][dir].length; i++) {
                    InetSocketAddress node =
                        (InetSocketAddress) iterator.next();
                    NodeRecord record = (NodeRecord) nodes.get(node);

                    neighbors[dim][dir][i] = new Neighbor(node, record.zone,
                                                          record.version);
                }
            }
        }
    }

    /** Populate the local node directory with the node records of the nodes in the given street, from the given map directory */
    private void populateDirectory(HashMap map, Street street) {
        Iterator iterator = street.iterator();

        while (iterator.hasNext()) {
            InetSocketAddress node = (InetSocketAddress) iterator.next();
            NodeRecord record = (NodeRecord) map.get(node);
            NodeRecord newRecord = new NodeRecord(record);

            nodes.put(node, newRecord);
        }
    }

    /**
     * pick a random neighbour to gracefully merge with
     *
     * @param myZone
     * @return
     */
    public InetSocketAddress getMergeableNeighbor(Zone myZone) {
        InetSocketAddress toRet = null;
        Iterator iterator = iterator();

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

            if (myZone.canMerge(record.zone)) {
                return neighbor;
            }
        }

        return toRet;
    }

    /**
     * Get the next hop neighbor for the given coordinates
     *
     * @param coordinates
     * @return
     */
    public InetSocketAddress nextHop(double[] coordinates) {

        // Silly implementation: go through each neighbor.  If the neighbor contains the point, forward to that neighbor.  Measure the distance from the neighbor's center to the point.  Forward to the neighbor with the shortest distance.
        double minimumDistance = Can.DIM;