java.util.SortedMap#firstKey ( )源码实例Demo

/**
 * Find the longest match.
 * 
 * @param path find object with longest match where path.startsWith( key)
 * @return the value whose key is the longest that matches path, or null if none
 */
public Match match(String path) {
  SortedMap<String, Match> tail = treeMap.tailMap(path);
  if (tail.isEmpty())
    return null;
  String after = tail.firstKey();
  if (path.startsWith(after)) // common case
    return treeMap.get(after);

  // have to check more, until no common starting chars
  for (String key : tail.keySet()) {
    if (path.startsWith(key))
      return treeMap.get(key);
    // terminate when there's no match at all.
    if (StringUtil2.match(path, key) == 0)
      break;
  }

  return null;
}
 

/**
 * 根据参数值选择指定的服务提供者
 *
 * @author sxp
 * @since 2018/10/20
 */
public Map<String, ServiceProvider> select(String arg) {
  long hash = md5Hash(arg);

  // 数据映射在两台虚拟机器所在环之间，按顺时针方向寻找机器
  if (!circle.containsKey(hash)) {
    SortedMap<Long, Map.Entry<String, ServiceProvider>> tailMap = circle.tailMap(hash);
    hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
  }

  Map.Entry<String, ServiceProvider> providerEntry = circle.get(hash);

  Map<String, ServiceProvider> result = new ConcurrentHashMap<String, ServiceProvider>();
  result.put(providerEntry.getKey(), providerEntry.getValue());

  return result;
}
 

@Test
public void testAtStartOfOne() {
    // 12 AM - 1 AM
    long start_time_ms = new DateTime(2000, 1, 1, 0, 0, 0, 0, DTZ).getMillis();
    long start_time_s = TimeUnit.MILLISECONDS.toSeconds(start_time_ms);
    long end_time_ms = start_time_ms + TimeUnit.HOURS.toMillis(1);
    long end_time_s = TimeUnit.MILLISECONDS.toSeconds(end_time_ms);
    AgendaItem item = new AgendaItem();
    item.setEpochStartTime(start_time_s);
    item.setEpochEndTime(end_time_s);

    final List<AgendaItem> items_in = Collections.singletonList(item);
    final SortedMap<DateRange, List<AgendaItem>> map =
        AgendaItems.happeningNow(items_in, start_time_ms);

    assertEquals(1, map.size());
    final DateRange dr = map.firstKey();
    assertNotNull(dr);
    assertEquals(start_time_ms, dr.start);
    assertEquals(end_time_ms, dr.end);
    final List<AgendaItem> items_out = map.get(dr);
    assertEquals(1, items_out.size());
    assertSame(item, items_out.get(0));
}
 

@Test
public void testOneInRange() {
    // 12 AM - 1 AM
    long start_time_ms = new DateTime(2000, 1, 1, 0, 0, 0, 0, DTZ).getMillis();
    long start_time_s = TimeUnit.MILLISECONDS.toSeconds(start_time_ms);
    long end_time_ms = start_time_ms + TimeUnit.HOURS.toMillis(1);
    long end_time_s = TimeUnit.MILLISECONDS.toSeconds(end_time_ms);
    AgendaItem item = new AgendaItem();
    item.setEpochStartTime(start_time_s);
    item.setEpochEndTime(end_time_s);

    long look_ahead = TimeUnit.DAYS.toMillis(1);
    long now = start_time_ms - look_ahead + 1;  // Just inside of range
    final List<AgendaItem> items_in = Collections.singletonList(item);
    final SortedMap<DateRange, List<AgendaItem>> map =
        AgendaItems.upNext(items_in, now, TimeUnit.DAYS.toMillis(1), 0);

    assertEquals(1, map.size());
    final DateRange dr = map.firstKey();
    assertNotNull(dr);
    assertEquals(start_time_ms, dr.start);
    assertEquals(end_time_ms, dr.end);
    final List<AgendaItem> items_out = map.get(dr);
    assertEquals(1, items_out.size());
    assertSame(item, items_out.get(0));
}
 

protected List<String> getNodesForKey(final long hash, final int listSize) {
    long target = hash;
    // Local reference so the nodes aren't changed in the middle of calculation.
    final KetamaData localData = data;
    if (!data.getNodeMap().containsKey(target)) {
        // Java 1.6 adds a ceilingKey method, but I'm still stuck in 1.5
        // in a lot of places, so I'm doing this myself.
        final SortedMap<Long, String> tailMap = data.getNodeMap().tailMap(target);
        target = tailMap.isEmpty() ? data.getNodeMap().firstKey() : tailMap.firstKey();
    }
    final int maxSize = data.getNodeSet().size() > listSize ? listSize : data.getNodeSet().size();
    final List<String> results = new ArrayList<String>(maxSize);
    results.add(data.getNodeMap().get(target));

    // We're done if we're only looking for the first one.
    if (listSize == 1) { return results; }

    // Find the rest of the list (uniquely) in order.
    final Set<String> accounted = new TreeSet<String>();
    accounted.add(data.getNodeMap().get(target));

    Long pointerKey = data.getNodeMap().higherKey(target);
    while ((pointerKey == null || pointerKey.longValue() != target) && accounted.size() < maxSize) {
        if (pointerKey == null) { pointerKey = data.getNodeMap().firstKey(); }
        final String node = data.getNodeMap().get(pointerKey);
        // Only add nodes that haven't already been accounted for.
        if (node != null && !accounted.contains(node)) {
            results.add(node);
            accounted.add(node);
        }
        pointerKey = data.getNodeMap().higherKey(pointerKey);
    }

    return results;
}
 

@Test
public void testOneGroupOfTwoInRange() {
    // 12 AM - 1 AM
    long start_time0_ms = new DateTime(2000, 1, 1, 0, 0, 0, 0, DTZ).getMillis();
    long start_time0_s = TimeUnit.MILLISECONDS.toSeconds(start_time0_ms);
    long end_time0_ms = start_time0_ms + TimeUnit.HOURS.toMillis(1);
    long end_time0_s = TimeUnit.MILLISECONDS.toSeconds(end_time0_ms);
    AgendaItem item0 = new AgendaItem();
    item0.setEpochStartTime(start_time0_s);
    item0.setEpochEndTime(end_time0_s);

    // 12 AM - 1 AM
    AgendaItem item1 = new AgendaItem();
    item1.setEpochStartTime(start_time0_s);
    item1.setEpochEndTime(end_time0_s);

    long look_ahead = TimeUnit.DAYS.toMillis(1);
    long now = start_time0_ms - look_ahead + 1;  // Just inside of range
    final List<AgendaItem> items_in = Arrays.asList(item0, item1);
    final SortedMap<DateRange, List<AgendaItem>> map =
        AgendaItems.upNext(items_in, now, TimeUnit.DAYS.toMillis(1), 0);

    assertEquals(1, map.size());
    final DateRange dr = map.firstKey();
    assertNotNull(dr);
    assertEquals(start_time0_ms, dr.start);
    assertEquals(end_time0_ms, dr.end);
    final List<AgendaItem> items_out = map.get(dr);
    assertEquals(2, items_out.size());
    assertSame(item0, items_out.get(0));
    assertSame(item1, items_out.get(1));
}
 

/**
 * 取得真实机器节点
 * 
 * @param key
 * @return
 */
public T get(String key) {// 关键算法
  if (circle.isEmpty()) {
    return null;
  }
  // 计算hash值
  Long hash = hashFunction.hash(key);
  // 如果不包含这个hash值
  if (!circle.containsKey(hash)) {
    SortedMap<Long, T> tailMap = circle.tailMap(hash);// 沿环的顺时针找到一个虚拟节点
    hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
  }
  return circle.get(hash);// 返回该虚拟节点对应的真实机器节点的信息
}
 

MemcachedNode getNodeForKey(long hash) {
    final MemcachedNode rv;
    if (!ketamaNodes.get().containsKey(hash)) {
        // Java 1.6 adds a ceilingKey method, but I'm still stuck in 1.5
        // in a lot of places, so I'm doing this myself.
        SortedMap<Long, MemcachedNode> tailMap = getKetamaNodes().tailMap(hash);
        if (tailMap.isEmpty()) {
            hash = getKetamaNodes().firstKey();
        } else {
            hash = tailMap.firstKey();
        }
    }
    rv = getKetamaNodes().get(hash);
    return rv;
}
 

/**
 * with a specified key, route the nearest Node instance in the current hash ring
 *
 * @param objectKey the object key to find a nearest Node
 */
public T routeNode(String objectKey) {
    if (ring.isEmpty()) {
        return null;
    }
    Long hashVal = hashFunction.hash(objectKey);
    SortedMap<Long, VirtualNode<T>> tailMap = ring.tailMap(hashVal);
    Long nodeHashVal = !tailMap.isEmpty() ? tailMap.firstKey() : ring.firstKey();
    return ring.get(nodeHashVal).getPhysicalNode();
}
 

/**
     * with a specified key, route the nearest Node instance in the current hash ring 使用指定的键，路由当前哈希环中最近的节点实例
     *
     * @param objectKey the object key to find a nearest Node
     */
//
    public T routeNode(String objectKey) {
        if (ring.isEmpty()) {
            return null;
        }
        Long hashVal = hashFunction.hash(objectKey);
        SortedMap<Long, VirtualNode<T>> tailMap = ring.tailMap(hashVal);
        Long nodeHashVal = !tailMap.isEmpty() ? tailMap.firstKey() : ring.firstKey();
        return ring.get(nodeHashVal).getPhysicalNode();
    }
 

private BigInteger getAccountFirstPickingNonce(AionAddress sender) {
    SortedMap<BigInteger, ByteArrayWrapper> accountInfo = accountView.get(sender);
    if (accountInfo == null) {
        throw new IllegalStateException("Can't find the account info relate with sender: " + sender);
    }

    return accountInfo.firstKey();
}
 

private synchronized Pair<Long, SocketAddress> get(long hash) {
    if (circle.isEmpty()) {
        return null;
    }

    if (!circle.containsKey(hash)) {
        SortedMap<Long, SocketAddress> tailMap = circle.tailMap(hash);
        hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
    }
    return Pair.of(hash, circle.get(hash));
}
 

/**
 * with a specified key, route the nearest Node instance in the current hash ring
 *
 * @param objectKey the object key to find a nearest Node
 */
public T routeNode(String objectKey) {
    if (ring.isEmpty()) {
        return null;
    }
    Long hashVal = hashFunction.hash(objectKey);
    SortedMap<Long, VirtualNode<T>> tailMap = ring.tailMap(hashVal);
    Long nodeHashVal = !tailMap.isEmpty() ? tailMap.firstKey() : ring.firstKey();
    return ring.get(nodeHashVal).getPhysicalNode();
}
 

private void updateMetadata(long uncompressedSegmentSize,
    long compressedSegmentSize) {
  SortedMap<Long, Long> offsetPairs = metadata.getOffsetPairs();
  long lastUncompressedOffset = offsetPairs.firstKey();
  long lastCompressedOffset = offsetPairs.get(lastUncompressedOffset);
  long uncompressedOffset = lastUncompressedOffset + uncompressedSegmentSize;
  long compressedOffset = lastCompressedOffset + compressedSegmentSize;
  offsetPairs.clear();
  offsetPairs.put(uncompressedOffset, compressedOffset);
}
 

/**
 * Purges and renames old log files in preparation for rollover. The oldest file will have the smallest index, the
 * newest the highest.
 *
 * @param lowIndex low index. Log file associated with low index will be deleted if needed.
 * @param highIndex high index.
 * @param manager The RollingFileManager
 * @return true if purge was successful and rollover should be attempted.
 */
private int purgeAscending(final int lowIndex, final int highIndex, final RollingFileManager manager) {
    final SortedMap<Integer, Path> eligibleFiles = getEligibleFiles(manager);
    final int maxFiles = highIndex - lowIndex + 1;

    boolean renameFiles = !eligibleFiles.isEmpty() && eligibleFiles.lastKey() >= maxIndex;
    while (eligibleFiles.size() >= maxFiles) {
        try {
            LOGGER.debug("Eligible files: {}", eligibleFiles);
            final Integer key = eligibleFiles.firstKey();
            LOGGER.debug("Deleting {}", eligibleFiles.get(key).toFile().getAbsolutePath());
            Files.delete(eligibleFiles.get(key));
            eligibleFiles.remove(key);
            renameFiles = true;
        } catch (final IOException ioe) {
            LOGGER.error("Unable to delete {}, {}", eligibleFiles.firstKey(), ioe.getMessage(), ioe);
            break;
        }
    }
    final StringBuilder buf = new StringBuilder();
    if (renameFiles) {
        for (final Map.Entry<Integer, Path> entry : eligibleFiles.entrySet()) {
            buf.setLength(0);
            // LOG4J2-531: directory scan & rollover must use same format
            manager.getPatternProcessor().formatFileName(strSubstitutor, buf, entry.getKey() - 1);
            final String currentName = entry.getValue().toFile().getName();
            String renameTo = buf.toString();
            final int suffixLength = suffixLength(renameTo);
            if (suffixLength > 0 && suffixLength(currentName) == 0) {
               renameTo = renameTo.substring(0, renameTo.length() - suffixLength);
            }
            final Action action = new FileRenameAction(entry.getValue().toFile(), new File(renameTo), true);
            try {
                LOGGER.debug("DefaultRolloverStrategy.purgeAscending executing {}", action);
                if (!action.execute()) {
                    return -1;
                }
            } catch (final Exception ex) {
                LOGGER.warn("Exception during purge in RollingFileAppender", ex);
                return -1;
            }
        }
    }

    return eligibleFiles.size() > 0 ?
            (eligibleFiles.lastKey() < highIndex ? eligibleFiles.lastKey() + 1 : highIndex) : lowIndex;
}
 

/**
 * Removes a resource for the specified interval
 * 
 * @param reservationInterval the interval for which the resource is to be
 *          removed
 * @param capacity the resource to be removed
 * @return true if removal is successful, false otherwise
 */
public boolean removeInterval(ReservationInterval reservationInterval,
    ReservationRequest capacity) {
  Resource totCap =
      Resources.multiply(capacity.getCapability(),
          (float) capacity.getNumContainers());
  if (totCap.equals(ZERO_RESOURCE)) {
    return true;
  }
  writeLock.lock();
  try {
    long startKey = reservationInterval.getStartTime();
    long endKey = reservationInterval.getEndTime();
    // update the start key
    NavigableMap<Long, Resource> ticks =
        cumulativeCapacity.headMap(endKey, false);
    // Decrease all the capacities of overlapping intervals
    SortedMap<Long, Resource> overlapSet = ticks.tailMap(startKey);
    if (overlapSet != null && !overlapSet.isEmpty()) {
      Resource updatedCapacity = Resource.newInstance(0, 0);
      long currentKey = -1;
      for (Iterator<Entry<Long, Resource>> overlapEntries =
          overlapSet.entrySet().iterator(); overlapEntries.hasNext();) {
        Entry<Long, Resource> entry = overlapEntries.next();
        currentKey = entry.getKey();
        updatedCapacity = Resources.subtract(entry.getValue(), totCap);
        // update each entry between start and end key
        cumulativeCapacity.put(currentKey, updatedCapacity);
      }
      // Remove the first overlap entry if it is same as previous after
      // updation
      Long firstKey = overlapSet.firstKey();
      if (isSameAsPrevious(firstKey, overlapSet.get(firstKey))) {
        cumulativeCapacity.remove(firstKey);
      }
      // Remove the next entry if it is same as end entry after updation
      if ((currentKey != -1) && (isSameAsNext(currentKey, updatedCapacity))) {
        cumulativeCapacity.remove(cumulativeCapacity.higherKey(currentKey));
      }
    }
    return true;
  } finally {
    writeLock.unlock();
  }
}
 

private static String asString(SortedMap<Long, ?> map) {
  return map.isEmpty()? "[]": "[" + map.firstKey() + ".." + map.lastKey() + "]";
}
 

@Override
StaccatoResult process (Glyph glyph,
                        Measure measure,
                        Point dotCenter)
{
    Scale scale = measure.getScale();
    final int maxDx = scale.toPixels(
            constants.maxStaccatoDotDx);
    final int maxDy = scale.toPixels(
            constants.maxStaccatoDotDy);
    SortedMap<Double, Chord> distances = new TreeMap<>();

    ChordLoop:
    for (TreeNode node : measure.getChords()) {
        Chord chord = (Chord) node;

        for (TreeNode n : chord.getNotes()) {
            Note note = (Note) n;

            if (!note.isRest()) {
                // Check distance wrt both top & bottom of note
                for (Point noteRef : Arrays.asList(
                        note.getCenterTop(),
                        note.getCenterBottom())) {
                    Point toDot = new Point(
                            dotCenter.x - noteRef.x,
                            dotCenter.y - noteRef.y);

                    logger.debug("Staccato {} {}", toDot, note);

                    if (((glyph.getShape() == getTargetShape())
                         && glyph.isManualShape())
                        || ((Math.abs(toDot.x) <= maxDx)
                            && (Math.abs(toDot.y) <= maxDy))) {
                        distances.put(toDot.distanceSq(0, 0), chord);
                    } else if (toDot.x < (-2 * maxDx)) {
                        break ChordLoop; // Speed up
                    }
                }
            }
        }
    }

    if (!distances.isEmpty()) {
        Double firstKey = distances.firstKey();

        return new StaccatoResult(distances.get(firstKey), firstKey);
    } else {
        return null;
    }
}
 

/**
 * Returns the node which should contain the supplied key per consistent
 * hashing algorithm
 *
 * @param keyBytes key to search on
 *
 * @return Node which should contain the key, null if no Nodes are present
 * Callers should verify that the node returned is alive before
 * using it to retrieve the value.
 */
public T get(byte[] keyBytes) {
    Long hash = hashAlgo.call(keyBytes);
    if (!ring.containsKey(hash)) {
        SortedMap<Long, T> tailMap = ring.tailMap(hash);
        hash = tailMap.isEmpty() ? ring.firstKey() : tailMap.firstKey();
    }
    return ring.get(hash);
}
 

/**
 * Returns the smallest key in the symbol table greater than or equal to <tt>key</tt>.
 * @return the smallest key in the symbol table greater than or equal to <tt>key</tt>
 * @param key the key
 * @throws NoSuchElementException if the symbol table is empty
 * @throws NullPointerException if <tt>key</tt> is <tt>null</tt>
 */
public Key ceil(Key key) {
    if (key == null) throw new NullPointerException("called ceil() with null key");
    SortedMap<Key, Value> tail = st.tailMap(key);
    if (tail.isEmpty()) throw new NoSuchElementException();
    return tail.firstKey();
}