leafset.java

pastry的java实现的2.0b版

        if (-ccw == ccwSet.size()) {
          if ((ccw = complement(ccw)) == tmp) {
            return set;
          }
          wrapped++;
        }
        ccw--;

      }
    }

    return set;
  }

  /**
   * Perform (x mod y). This is necessary because the java % operator is
   * actually remainder instead of mod. Useless.
   *
   * @param x DESCRIBE THE PARAMETER
   * @param y DESCRIBE THE PARAMETER
   * @return x mod y
   */
  private int mod(int x, int y) {
    if ((x < 0) ^ (y < 0)) {
      return y + (x % y);
    } else {
      return x % y;
    }
  }

  /**
   * range computes the range of keys for which node n is a i-root, 0<=i<=r a
   * node is the r-root for a key of the node becomes the numerically closest
   * node to the key when i-roots for the key fail, O<=i<r, where a key's 0-root
   * is the numerically closest node to the key.
   *
   * @param n the nodehandle
   * @param r
   * @return the range of keys, or null if n is not a member of the leafset, or
   *      if the range cannot be computed
   */
  public IdRange range(NodeHandle n, int r) {
    // first, we check the arguments
    if (r < 0) {
      throw new IllegalArgumentException("Range must be greater than or equal to zero. Attempted " + r);
    }
    if (!(member(n) || baseHandle.equals(n))) {
      throw new LSRangeCannotBeDeterminedException("Node " + n + " is not in this leafset.", r, Integer.MIN_VALUE, getUniqueCount(), n, this);
    }

    // get the position of the node and the number of nodes in the network
    int pos = getIndex(n);
    int num = getUniqueCount();
    NodeHandle cw;
    NodeHandle ccw;
    // these are the nodes in the Leafset that represent the extents of the range

    // if this leafset overlaps (or we are the only node in the network), then we have
    // global knowledge about the network and can determine any range.  Otherwise, we
    // need to determine whether or not we can determine the range
    if (overlaps() || (num == 1)) {

      // if the rank is more than the number of nodes in the network, then we return
      // the whole range.
      if (r + 1 >= num) {
        return new IdRange(n.getNodeId(), n.getNodeId());
      }

      // we determine the locations if it's pair nodes
      // note that what we are doing is the following:
      //   we want the nodes at indices {pos-r, pos+r}, but these indices
      //   might be beyond the range of the leafset.  since the range of the unique
      //   leafset is [-ccwSize .. num-ccwSize-1], we shift the range up to
      //   [0 .. num-1] by adding ccwSize.  then, we want to mod p+-r
      //   in order to bring it within this range.  this is done by modding
      //   num (as this will result in the range [0 .. num-1] as
      //   desired.  Last, we shift the range back down by substracting
      //   ccwSize.
      ccw = get(mod(pos - r - 1 + ccwSet.size(), num) - ccwSet.size());
      cw = get(mod(pos + r + 1 + ccwSet.size(), num) - ccwSet.size());
    } else {
      // now, we need to find the pair nodes for this node range
      ccw = get(pos - r - 1);
      cw = get(pos + r + 1);
    }

    // if either of it's pair nodes are null, then we cannot determine the range
    if ((ccw == null) || (cw == null)) {
      throw new LSRangeCannotBeDeterminedException("This leafset doesn't have enough information to provide the correct range.", r, pos, getUniqueCount(), n, this);
    }

    // otherwise, we then construct the ranges which comprise the main range, and finally
    // return the overlap
    IdRange cwRange = (new IdRange(n.getNodeId(), cw.getNodeId())).ccwHalf();
    IdRange ccwRange = (new IdRange(ccw.getNodeId(), n.getNodeId())).cwHalf();

    return ccwRange.merge(cwRange);
  }

  /**
   * range computes the ranges of keys for which node n is a r-root a node is
   * the r-root for a key of the node becomes the numerically closest node to
   * the key when i-roots for the key fail, O<=i<r, where a key's 0-root is the
   * numerically closest node to the key. there can be two contiguous ranges of
   * keys; the cw parameter selects which one is returned.
   *
   * @param n the nodehandle
   * @param r
   * @param cw if true returns the clockwise range, else the counterclockwise
   *      range
   * @return the range of keys, or null if n is not a member of the leafset, or
   *      if the range cannot be computed
   */
  public IdRange range(NodeHandle n, int r, boolean cw) {
    IdRange rr = range(n, r);
    if (r == 0) {
      return rr;
    }
    IdRange rprev = null;
    try {
      rprev = range(n, r - 1);
    } catch (LSRangeCannotBeDeterminedException rcbde) {
      // keeps previous functionality now that we are throwing rcbde rather than returning null
    }
    if (rr == null || rprev == null) {
      return rr;
    }

    //IdRange res = rr.diff(rprev, cw);
    IdRange res;

    if (!cw) {
      res = rr.diff(rprev);
    } else {
      res = rprev.diff(rr);
    }
    return res;
  }


  /**
   * Merge a remote leafset into this
   *
   * @param remotels the remote leafset
   * @param from the node from which we received the leafset
   * @param routeTable the routing table
   * @param testOnly if true, do not change the leafset
   * @param insertedHandles if not null, a Set that contains, upon return of
   *      this method, the nodeHandles that would be inserted into this LeafSet
   *      if testOnly is true
   * @return true if the local leafset changed
   */
  public boolean merge(LeafSet remotels, NodeHandle from, RoutingTable routeTable,
                       boolean testOnly, Set insertedHandles) {

    boolean changed;

    boolean result = false;
    int cwSize = remotels.cwSize();
    int ccwSize = remotels.ccwSize();

    // merge the received leaf set into our own
    // to minimize inserts/removes, we do this from nearest to farthest nodes

    // get indeces of localId in the leafset
    int cw = remotels.cwSet.getIndex(baseId);
    int ccw = remotels.ccwSet.getIndex(baseId);

    if (cw < 0) {
      // localId not in cw set

      if (ccw < 0) {
        // localId not in received leafset, that means local node is joining

        if (remotels.size() < 2) {
          cw = ccw = 0;
        } else {

          // find the num. closest to localId in the remotels
          int closest = remotels.mostSimilar(baseId);
          Id closestId = remotels.get(closest).getNodeId();

          if (closest == -remotels.ccwSize() || closest == remotels.cwSize()) {
            // doesn't hurt to merge it anyways
            //return;
          }

          if (closest == 0) {
            // from is closest
            if (baseId.clockwise(closestId)) {
              cw = closest;
              ccw = remotels.complement(closest - 1);
            } else {
              cw = remotels.complement(closest + 1);
              ccw = closest;
            }
          } else if (closest < 0) {
            // from is cw
            if (baseId.clockwise(closestId)) {
              cw = closest;
              ccw = remotels.complement(closest - 1);
            } else {
              cw = closest + 1;
              ccw = remotels.complement(closest);
            }
          } else {
            // from is ccw
            if (baseId.clockwise(closestId)) {
              cw = remotels.complement(closest);
              ccw = closest - 1;
            } else {
              ccw = closest;
              cw = remotels.complement(closest + 1);
            }
          }

        }
      } else {
        // localId in ccw set

        ccw = -ccw - 2;
        cw = ccw + 2;
      }
    } else {
      // localId in cw set

      if (ccw < 0) {
        cw = cw + 2;
        ccw = cw - 2;
      } else {
        // localId is in both halves
        int tmp = ccw;
        ccw = cw;
        cw = -tmp;
      }
    }

    for (int i = cw; i <= cwSize; i++) {
      NodeHandle nh;

      if (i == 0) {
        nh = from;
      } else {
        nh = remotels.get(i);
      }

      if (nh.isAlive() == false) {
        continue;
      }
      //if (member(nh.getNodeId())) continue;

      if (testOnly) {
        // see it is missing
        changed = cwSet.test(nh);
      } else {
        // merge into our cw leaf set half
        changed = cwSet.put(nh);

        // update RT as well
        routeTable.put(nh);
      }

      result |= changed;
      if (insertedHandles != null && changed) {
        insertedHandles.add(nh);
      }
    }

    for (int i = ccw; i >= -ccwSize; i--) {
      NodeHandle nh;

      if (i == 0) {
        nh = from;
      } else {
        nh = remotels.get(i);
      }

      if (nh.isAlive() == false) {
        continue;
      }
      //if (member(nh.getNodeId())) continue;

      if (testOnly) {
        // see if it is missing
        changed = ccwSet.test(nh);
      } else {
        // merge into our leaf set
        changed = ccwSet.put(nh);

        // update RT as well
        routeTable.put(nh);
      }

      result |= changed;
      if (insertedHandles != null && changed) {
        insertedHandles.add(nh);
      }
    }

    // if there is overlap, insert nearest nodes regardless of orientation
    if (overlaps()) {
      for (int i = -ccwSize; i <= cwSize; i++) {
        NodeHandle nh;

        if (i == 0) {
          nh = from;
        } else {
          nh = remotels.get(i);
        }

        if (nh.isAlive() == false) {
          continue;
        }

        if (testOnly) {
          // merge into our leaf set
          changed = test(nh);
        } else {
          // merge into our leaf set
          changed = put(nh);
        }

        result |= changed;
        if (insertedHandles != null && changed) {
          insertedHandles.add(nh);
        }
      }
    }

    return result;
  }

  /**
   * Add observer method.
   *
   * @param o the observer to add.
   * @deprecated use addNodeSetListener
   */
  public void addObserver(Observer o) {
    cwSet.addObserver(o);
    ccwSet.addObserver(o);
  }

  /**
   * Delete observer method.
   *
   * @param o the observer to delete.
   * @deprecated use deleteNodeSetListener
   */
  public void deleteObserver(Observer o) {
    cwSet.deleteObserver(o);
    ccwSet.deleteObserver(o);
  }

  /**
   * Add observer method.
   *
   * @param listener The feature to be added to the NodeSetListener attribute
   */
  public void addNodeSetListener(NodeSetListener listener) {
    cwSet.addNodeSetListener(listener);
    ccwSet.addNodeSetListener(listener);
  }

  /**
   * Delete observer method.
   *
   * @param listener DESCRIBE THE PARAMETER
   */
  public void deleteNodeSetListener(NodeSetListener listener) {
    cwSet.removeNodeSetListener(listener);
    ccwSet.removeNodeSetListener(listener);
  }

  /**
   * Returns a string representation of the leaf set
   *
   * @return DESCRIBE THE RETURN VALUE
   */
  public String toString() {
    String s = "leafset: ";
    for (int i = -ccwSet.size(); i < 0; i++) {
      s = s + get(i).getNodeId();
    }
    s = s + " [ " + baseId + " ] ";
    for (int i = 1; i <= cwSet.size(); i++) {
      s = s + get(i).getNodeId();
    }

    s += " complete:" + isComplete();
    s += " size:" + size();
    if (size() > 0) {
      s += " s1:" + ccwSet.member(cwSet.get(cwSet.size() - 1));
    }
    s += " s2:" + cwSet.member(ccwSet.get(ccwSet.size() - 1));

    return s;
  }

  /**
   * A unit test for JUnit
   *
   * @param set DESCRIBE THE PARAMETER
   * @param handle DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */
  protected boolean testOtherSet(SimilarSet set, NodeHandle handle) {
    //if (true) return false;
    SimilarSet otherSet = ccwSet;
    if (otherSet == set) {
      otherSet = cwSet;
    }

    return otherSet.test(handle);
  }

  /**
   * DESCRIBE THE METHOD
   *
   * @param handle DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   */
  public boolean directTest(NodeHandle handle) {
    return cwSet.test(handle) || ccwSet.test(handle);
  }

  /**
   * DESCRIBE THE METHOD
   *
   * @return DESCRIBE THE RETURN VALUE
   */
  public LeafSet copy() {
    return new LeafSet(this);
  }

  /**
   * So that small LeafSets (who have overlapping nodes) don't waste bandwidth,
   * leafset first defines the NodeHandles to be loaded into an array, then
   * specifies their locations. We do this because a NodeHandle takes up a lot
   * more space than the index in the leafset, and it may be in the leafset 1 or
   * 2 times. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   * + byte theSize +numUniqueHandls+ byte cwSize + byte ccwSize +
   * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
   * NodeHandle baseHandle + ... + + + +
   * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
   * NodeHandle 1st + ... + + + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   * ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
   * NodeHandle numUniqueHandls-th + ... + + + +
   * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + byte cw
   * 1st + cw 2nd + ... + ccw 1st + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   * + ccw 2nd + ... + ... + ccw Nth + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   * TODO 2.23.2006 the synchronization of LeafSet is nonexistent and it's
   * difficult to add because the listeneer interface should not be called while
   * holding a lock, but the lock should be acquired once while making the
   * change
   *
   * @param buf DESCRIBE THE PARAMETER
   * @exception IOException DESCRIBE THE EXCEPTION
   */
  public synchronized void serialize(OutputBuffer buf) throws IOException {
    HashSet superset = new HashSet();
    superset.addAll(cwSet.getCollection());
    superset.addAll(ccwSet.getCollection());
    ArrayList list = new ArrayList(superset);

    buf.writeByte((byte) theSize);
    buf.writeByte((byte) list.size());
    buf.writeByte((byte) cwSize());
    buf.writeByte((byte) ccwSize());

    baseHandle.serialize(buf);

    Iterator it = list.iterator();
    while (it.hasNext()) {
      NodeHandle nh = (NodeHandle) it.next();
      nh.serialize(buf);
    }

    for (int i = 0; i < cwSet.size(); i++) {
      buf.writeByte((byte) list.indexOf(cwSet.get(i)));
    }

    for (int i = 0; i < ccwSet.size(); i++) {
      buf.writeByte((byte) list.indexOf(ccwSet.get(i)));
    }
  }

  /**
   * So that small LeafSets (who have overlapping nodes) don't waste bandwidth,
   * leafset first defines the NodeHandles to be loaded into an array, then
   * specifies their locations. We do this because a NodeHandle takes up a lot
   * more space than the index in the leafset, and it may be in the leafset 1 or
   * 2 times. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   * + byte theSize +numUniqueHandls+ byte cwSize + byte ccwSize +
   * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
   * NodeHandle baseHandle + ... + + + +
   * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
   * NodeHandle 1st + ... + + + + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   * ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
   * NodeHandle numUniqueHandls-th + ... + + + +
   * +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + byte cw
   * 1st + cw 2nd + ... + ccw 1st + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   * + ccw 2nd + ... + ... + ccw Nth + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   *
   * @param buf DESCRIBE THE PARAMETER
   * @param nhf DESCRIBE THE PARAMETER
   * @return DESCRIBE THE RETURN VALUE
   * @exception IOException DESCRIBE THE EXCEPTION
   */
  public static LeafSet build(InputBuffer buf, NodeHandleFactory nhf) throws IOException {
    byte theSize = buf.readByte();
    byte numUniqueHandles = buf.readByte();
    byte cwSize = buf.readByte();
    byte ccwSize = buf.readByte();
    NodeHandle baseHandle = nhf.readNodeHandle(buf);
    NodeHandle[] nhTable = new NodeHandle[numUniqueHandles];
    for (int i = 0; i < numUniqueHandles; i++) {
      nhTable[i] = nhf.readNodeHandle(buf);
    }

    NodeHandle[] cwTable = new NodeHandle[cwSize];
    NodeHandle[] ccwTable = new NodeHandle[ccwSize];

    for (int i = 0; i < cwSize; i++) {
      cwTable[i] = nhTable[buf.readByte()];
    }

    for (int i = 0; i < ccwSize; i++) {
      ccwTable[i] = nhTable[buf.readByte()];
    }

    return new LeafSet(baseHandle, theSize, true, cwTable, ccwTable);
  }
}