leafset.java

pastry的java实现的2.0b版

/*************************************************************************

"FreePastry" Peer-to-Peer Application Development Substrate 

Copyright 2002, Rice University. All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

- Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.

- Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.

- Neither  the name  of Rice  University (RICE) nor  the names  of its
contributors may be  used to endorse or promote  products derived from
this software without specific prior written permission.

This software is provided by RICE and the contributors on an "as is"
basis, without any representations or warranties of any kind, express
or implied including, but not limited to, representations or
warranties of non-infringement, merchantability or fitness for a
particular purpose. In no event shall RICE or contributors be liable
for any direct, indirect, incidental, special, exemplary, or
consequential damages (including, but not limited to, procurement of
substitute goods or services; loss of use, data, or profits; or
business interruption) however caused and on any theory of liability,
whether in contract, strict liability, or tort (including negligence
or otherwise) arising in any way out of the use of this software, even
if advised of the possibility of such damage.

********************************************************************************/

package rice.pastry.leafset;

import rice.p2p.commonapi.rawserialization.*;
import rice.pastry.*;
import rice.pastry.routing.*;

import java.util.*;
import java.io.*;

/**
 * A class for representing and manipulating the leaf set. The leafset is not
 * strictly a set: when the ring is small, a node may appear in both the cw and
 * the ccw half of the "set".
 *
 * @version $Id: LeafSet.java 3274 2006-05-15 16:17:47Z jeffh $
 * @author Andrew Ladd
 * @author Peter Druschel
 */
public class LeafSet extends Observable implements Serializable {

  private Id baseId;
  private NodeHandle baseHandle;
  private SimilarSet cwSet;
  private SimilarSet ccwSet;

  transient boolean observe = true;
  private int theSize;
  private final static long serialVersionUID = 3960030608598552977L;

  /**
   * Constructor for LeafSet.
   *
   * @param that DESCRIBE THE PARAMETER
   */
  private LeafSet(LeafSet that) {
    this(that, true);
  }

  /**
   * Constructor for LeafSet.
   *
   * @param that DESCRIBE THE PARAMETER
   * @param observe DESCRIBE THE PARAMETER
   */
  private LeafSet(LeafSet that, boolean observe) {
    this.observe = observe;
    this.baseId = that.baseId;
    this.baseHandle = that.baseHandle;
    this.ccwSet = that.ccwSet.copy(this);
    this.cwSet = that.cwSet.copy(this);
    this.theSize = that.theSize;
  }

  /**
   * Constructor.
   *
   * @param size the size of the leaf set.
   * @param localNode DESCRIBE THE PARAMETER
   */
  public LeafSet(NodeHandle localNode, int size) {
    this(localNode, size, true);
  }

  /**
   * Constructor for LeafSet.
   *
   * @param localNode DESCRIBE THE PARAMETER
   * @param size DESCRIBE THE PARAMETER
   * @param observe DESCRIBE THE PARAMETER
   */
  public LeafSet(NodeHandle localNode, int size, boolean observe) {
    this.observe = observe;

    baseHandle = localNode;
    baseId = localNode.getNodeId();
    theSize = size;

    cwSet = new SimilarSet(this, localNode, size / 2, true);
    ccwSet = new SimilarSet(this, localNode, size / 2, false);
  }

  /**
   * Constructor for LeafSet.
   *
   * @param localNode DESCRIBE THE PARAMETER
   * @param size DESCRIBE THE PARAMETER
   * @param observe DESCRIBE THE PARAMETER
   * @param cwTable DESCRIBE THE PARAMETER
   * @param ccwTable DESCRIBE THE PARAMETER
   */
  public LeafSet(NodeHandle localNode, int size, boolean observe, NodeHandle[] cwTable, NodeHandle[] ccwTable) {
    this.observe = observe;

    baseHandle = localNode;
    baseId = localNode.getNodeId();
    theSize = size;

    cwSet = new SimilarSet(this, localNode, size / 2, true, cwTable);
    ccwSet = new SimilarSet(this, localNode, size / 2, false, ccwTable);
  }

  /**
   * Gets the Complete attribute of the LeafSet object
   *
   * @return The Complete value
   */
  public boolean isComplete() {
    if (size() == maxSize()) {
      return true;
    }
    if (overlaps()) {
      return true;
    }
    return false;
  }

  /**
   * Gets the Index attribute of the LeafSet object
   *
   * @param nh DESCRIBE THE PARAMETER
   * @return The Index value
   * @exception NoSuchElementException DESCRIBE THE EXCEPTION
   */
  public int getIndex(NodeHandle nh) throws NoSuchElementException {
    int index;

    if (baseId.equals(nh.getId())) {
      return 0;
    }

    index = cwSet.getIndex(nh);
    if (index >= 0) {
      return index + 1;
    }
    index = ccwSet.getIndex(nh);
    if (index >= 0) {
      return -index - 1;
    }

    throw new NoSuchElementException();
  }


  /**
   * Finds the NodeHandle at a given index.
   *
   * @param index an index.
   * @return the handle associated with that index.
   */
  public NodeHandle get(int index) {
    if (index == 0) {
      return baseHandle;
    }
    if (index >= 0) {
      return cwSet.get(index - 1);
    } else {
      return ccwSet.get(-index - 1);
    }
  }

  /**
   * Returns the number of unique nodes in the leafset
   *
   * @return the number of unique nodes in the leafset
   */
  public int getUniqueCount() {
    HashSet superset = new HashSet();
    superset.addAll(cwSet.getCollection());
    superset.addAll(ccwSet.getCollection());
    return superset.size() + 1;
    // the local node
//
//    Vector v = new Vector();
//
//    for (int i=-ccwSize(); i<=cwSize(); i++) {
//      if (! v.contains(get(i).getNodeId())) {
//        v.add(get(i).getNodeId());
//      }
//    }
//
//    return v.size();
  }

  /**
   * Gets the ProperlyRemoved attribute of the LeafSet object
   *
   * @param handle DESCRIBE THE PARAMETER
   * @return The ProperlyRemoved value
   */
  protected boolean isProperlyRemoved(NodeHandle handle) {
    return !member(handle);
  }

  /**
   * Puts a NodeHandle into the set.
   *
   * @param handle the handle to put.
   * @return true if successful, false otherwise.
   */
  public boolean put(NodeHandle handle) {
    Id nid = handle.getNodeId();
    if (nid.equals(baseId)) {
      return false;
    }
    if (member(handle)) {
      return false;
    }

    boolean res = cwSet.put(handle) | ccwSet.put(handle);
    return res;
  }

  /**
   * Test if a put of the given NodeHandle would succeed.
   *
   * @param handle the handle to test.
   * @return true if a put would succeed, false otherwise.
   */
  public boolean test(NodeHandle handle) {
    Id nid = handle.getNodeId();
    if (nid.equals(baseId)) {
      return false;
    }
    if (member(handle)) {
      return false;
    }

    return cwSet.test(handle) | ccwSet.test(handle);
  }

  /**
   * Test if the leafset overlaps
   *
   * @return true if the most distant cw member appears in the ccw set or vice
   *      versa, false otherwise
   */
  public boolean overlaps() {
    if (size() > 0 && (ccwSet.member(cwSet.get(cwSet.size() - 1)) ||
      cwSet.member(ccwSet.get(ccwSet.size() - 1)))) {
      return true;
    } else {
      return false;
    }
  }


  /**
   * Verifies if the set contains this particular handle.
   *
   * @param nid a NodeHandle.
   * @return true if that NodeHandle is in the set, false otherwise.
   */
  public boolean member(NodeHandle nid) {
    return cwSet.member(nid) || ccwSet.member(nid);
  }

  /**
   * Verifies if the set contains this particular id.
   *
   * @param nid a node id.
   * @return true if that node id is in the set, false otherwise.
   */
  public boolean member(Id nid) {
    return cwSet.member(nid) || ccwSet.member(nid);
  }


  /**
   * Removes a node id and its handle from the set.
   *
   * @param nh DESCRIBE THE PARAMETER
   * @return the node handle removed or null if nothing.
   */
  public NodeHandle remove(NodeHandle nh) {
    NodeHandle res1 = cwSet.remove(nh);
    NodeHandle res2 = ccwSet.remove(nh);
    if (res1 != null) {
      return res1;
    } else {
      return res2;
    }
  }

  /**
   * Gets the maximal size of the leaf set.
   *
   * @return the size.
   */
  public int maxSize() {
    return theSize;
  }

  /**
   * Gets the current size of the leaf set. Note that if the leafset overlaps,
   * there will be duplicates. If you want the unique nodes, use
   * getUniqueCount().
   *
   * @return the size.
   */
  public int size() {
    return cwSize() + ccwSize();
    // old code

    // 8.16.5 decided not to do this because it will break too much code
//    HashSet superset = new HashSet();
//    superset.addAll(cwSet.getCollection());
//    superset.addAll(ccwSet.getCollection());
//    return superset.size();
  }

  /**
   * Gets the current clockwise size.
   *
   * @return the size.
   */
  public int cwSize() {
    return cwSet.size();
  }

  /**
   * Gets the current counterclockwise size.
   *
   * @return the size.
   */
  public int ccwSize() {
    return ccwSet.size();
  }

  /**
   * complement - given an index of a node in the leafset, produces the index of
   * the same Id in the opposite half of the leafset
   *
   * @param inx DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */
  private int complement(int inx) {
    int res;

    if (inx == 0) {
      return 0;
    }
    if (inx < 0) {
      if (inx < -ccwSize()) {
        return inx;
      }
      res = cwSet.getIndex(ccwSet.get(-inx - 1)) + 1;
    } else {
      if (inx > cwSize()) {
        return inx;
      }
      res = -ccwSet.getIndex(cwSet.get(inx - 1)) - 1;
    }

    if (res == 0) {
      res = inx;
    }
    return res;
  }

  /**
   * Numerically closests node to a given a node in the leaf set.
   *
   * @param nid a node id.
   * @return the index of the numerically closest node (0 if baseId is the
   *      closest).
   */
  public int mostSimilar(Id nid) {
    Id.Distance cwMinDist;
    Id.Distance ccwMinDist;
    int cwMS;
    int ccwMS;
    int res;

    if (baseId.clockwise(nid)) {
      cwMS = cwSet.mostSimilar(nid);
      //ccwMS = ccwSet.size()-1;
      if (cwMS < cwSet.size() - 1) {
        return cwMS + 1;
      }
      ccwMS = ccwSet.mostSimilar(nid);
    } else {
      ccwMS = ccwSet.mostSimilar(nid);
      //cwMS = cwSet.size()-1;
      if (ccwMS < ccwSet.size() - 1) {
        return -ccwMS - 1;
      }
      cwMS = cwSet.mostSimilar(nid);
    }

    cwMinDist = cwSet.get(cwMS).getNodeId().distance(nid);
    ccwMinDist = ccwSet.get(ccwMS).getNodeId().distance(nid);

    int cmp = cwMinDist.compareTo(ccwMinDist);
    if (cmp < 0 || (cmp == 0 && nid.clockwise(cwSet.get(cwMS).getNodeId()))) {
      return cwMS + 1;
    } else {
      return -ccwMS - 1;
    }

    /*
     *  if (cwMinDist.compareTo(ccwMinDist) <= 0)
     *  return cwMS + 1;
     *  else
     *  return -ccwMS - 1;
     */
  }

  /**
   * compute an ordered set of nodes that are neighbors of this local node, in
   * order of numerical closeness to the local node
   *
   * @param max the maximal size of the set requested
   * @return the ordered set of nodehandles
   */
  public NodeSet neighborSet(int max) {
    NodeSet set;
    int cwSize = cwSize();
    int ccwSize = ccwSize();
    NodeHandle cwExtreme = get(cwSize);
    NodeHandle ccwExtreme = get(-ccwSize);
    set = replicaSet(baseId, max);
    if (!set.member(cwExtreme) && !set.member(ccwExtreme)) {
      // the value of max did not cause us to reach either end of the leafset
      // in the method replicaSet
      return set;
    } else {
      if (!set.member(cwExtreme)) {
        // All the nodes in the ccwSet are already members
        for (int i = 1; i <= cwSize; i++) {
          set.put(get(i));
        }
      }
      if (!set.member(ccwExtreme)) {
        // All the nodes in the cwSet are already members
        for (int i = 1; i <= ccwSize; i++) {
          set.put(get(-i));
        }
      }
      return set;
    }
  }

  /**
   * compute an ordered set of nodes, in order of numerical closeness to a given
   * key
   *
   * @param key the key
   * @param max the maximal size of the set requested
   * @return the ordered set of nodehandles
   */
  public NodeSet replicaSet(Id key, int max) {
    NodeSet set = new NodeSet();
    if (max < 1) {
      return set;
    }

    if (!overlaps() && size() > 0 &&
      !key.isBetween(get(-ccwSet.size()).getNodeId(), get(cwSet.size()).getNodeId()) &&
      !key.equals(get(cwSet.size()).getNodeId())) {
      // can't determine root of key, return empty set
      return set;
    }

    // compute the nearest node
    int nearest = mostSimilar(key);

    // add the key's root
    set.put(get(nearest));

    int cw = nearest;
    int ccw = nearest;
    int wrapped = 0;

    while (set.size() < max && wrapped < 3) {
      int tmp;

      // determine next nearest node
      NodeHandle cwNode = get(cw);
      NodeHandle ccwNode = get(ccw);
      Id.Distance cwDist = cwNode.getNodeId().distance(key);
      Id.Distance ccwDist = ccwNode.getNodeId().distance(key);

      if (cwDist.compareTo(ccwDist) <= 0) {
        // cwNode is closer to key
        set.put(cwNode);

        tmp = cw;
        if (cw == cwSet.size()) {
          if ((cw = complement(cw)) == tmp) {
            return set;
          }
          wrapped++;
        }
        cw++;

      } else {
        // ccwNode is closer to key
        set.put(ccwNode);

        tmp = ccw;