java.util.BitSet#nextClearBit ( )源码实例Demo

/**
 * @param commState Node communication state.
 * @param initialNodes Topology snapshot when communication error resolve started.
 * @param top Current topology.
 * @return {@code True} if node has connection to all alive nodes.
 */
private boolean checkFullyConnected(BitSet commState, List<ClusterNode> initialNodes, ZkClusterNodes top) {
    int startIdx = 0;

    for (;;) {
        int idx = commState.nextClearBit(startIdx);

        if (idx >= initialNodes.size())
            return true;

        ClusterNode node = initialNodes.get(idx);

        if (top.nodesById.containsKey(node.id()))
            return false;

        startIdx = idx + 1;
    }
}
 

@Override
int nextClearBit(BitSet bitSet, int startIdx) {
  int bitNumber = bitSet.nextClearBit(startIdx);
  while (!isEven(bitNumber)) {
    bitNumber = bitSet.nextClearBit(bitNumber + 1);
  }
  return bitNumber;
}
 

/**
 * Checks that all the required props are supplied, and if not throws a useful exception
 *
 * @param requiredPropsCount expected number of props
 * @param required the bit set that identifies which props have been supplied
 * @param requiredPropsNames the names of all props used for a useful error message
 */
protected static void checkArgs(
    int requiredPropsCount, BitSet required, String[] requiredPropsNames) {
  if (required != null && required.nextClearBit(0) < requiredPropsCount) {
    List<String> missingProps = new ArrayList<>();
    for (int i = 0; i < requiredPropsCount; i++) {
      if (!required.get(i)) {
        missingProps.add(requiredPropsNames[i]);
      }
    }
    throw new IllegalStateException(
        "The following props are not marked as optional and were not supplied: "
            + Arrays.toString(missingProps.toArray()));
  }
}
 

/**
 * Remove the occurrence of a given value in a copied slice of array
 * defined by the array part from [begin, begin+length).
 * @param values the input array
 * @param begin start index of the array to include
 * @param length number of elements to include from begin
 * @param removedValue the value to be removed from the sliced array
 * @return the copy of the sliced array after removing the removedValue
 */
private static double[] removeAndSlice(final double[] values,
                                       final int begin, final int length,
                                       final double removedValue) {
    MathArrays.verifyValues(values, begin, length);
    final double[] temp;
    //BitSet(length) to indicate where the removedValue is located
    final BitSet bits = new BitSet(length);
    for (int i = begin; i < begin+length; i++) {
        if (Precision.equalsIncludingNaN(removedValue, values[i])) {
            bits.set(i - begin);
        }
    }
    //Check if empty then create a new copy
    if (bits.isEmpty()) {
        temp = copyOf(values, begin, length); // Nothing removed, just copy
    } else if(bits.cardinality() == length){
        temp = new double[0];                 // All removed, just empty
    }else {                                   // Some removable, so new
        temp = new double[length - bits.cardinality()];
        int start = begin;  //start index from source array (i.e values)
        int dest = 0;       //dest index in destination array(i.e temp)
        int nextOne = -1;   //nextOne is the index of bit set of next one
        int bitSetPtr = 0;  //bitSetPtr is start index pointer of bitset
        while ((nextOne = bits.nextSetBit(bitSetPtr)) != -1) {
            final int lengthToCopy = nextOne - bitSetPtr;
            System.arraycopy(values, start, temp, dest, lengthToCopy);
            dest += lengthToCopy;
            start = begin + (bitSetPtr = bits.nextClearBit(nextOne));
        }
        //Copy any residue past start index till begin+length
        if (start < begin + length) {
            System.arraycopy(values,start,temp,dest,begin + length - start);
        }
    }
    return temp;
}
 

public static int indexOfClearBit(@Nonnull final BitSet bits, final int nth,
        final int lastIndex) {
    int j = bits.nextClearBit(0);
    for (int c = 0; j <= lastIndex; j = bits.nextClearBit(j + 1), c++) {
        if (c == nth) {
            break;
        }
    }
    return j;
}
 

private void recalculateFreeOrdinals(BitSet populatedOrdinals) {
    freeOrdinalTracker.reset();

    int length = populatedOrdinals.length();
    int ordinal = populatedOrdinals.nextClearBit(0);

    while (ordinal < length) {
        freeOrdinalTracker.returnOrdinalToPool(ordinal);
        ordinal = populatedOrdinals.nextClearBit(ordinal + 1);
    }

    freeOrdinalTracker.setNextEmptyOrdinal(length);
}
 

private int getNextVolumeDeviceId(String vmUuid) {
    SimpleQuery<VolumeVO> q = dbf.createQuery(VolumeVO.class);
    q.select(VolumeVO_.deviceId);
    q.add(VolumeVO_.vmInstanceUuid, Op.EQ, vmUuid);
    q.add(VolumeVO_.deviceId, Op.NOT_NULL);
    q.orderBy(VolumeVO_.deviceId, Od.ASC);
    List<Integer> devIds = q.listValue();

    BitSet full = new BitSet(devIds.size() + 1);
    devIds.forEach(full::set);
    return full.nextClearBit(0);
}
 

@Override
int nextClearBit(BitSet bitSet, int startIdx) {
  int bitNumber = bitSet.nextClearBit(startIdx);
  while (isEven(bitNumber)) {
    bitNumber = bitSet.nextClearBit(bitNumber + 1);
  }
  return bitNumber;
}
 

@Override
int nextClearBit(BitSet bitSet, int startIdx) {
  int bitNumber = bitSet.nextClearBit(startIdx);
  while (!isEven(bitNumber)) {
    bitNumber = bitSet.nextClearBit(bitNumber + 1);
  }
  return bitNumber;
}
 

public long getApproximateHoleCostInBytes(BitSet populatedOrdinals, int shardNumber, int numShards) {
    HollowObjectTypeDataElements currentData = currentDataVolatile;
    long holeBits = 0;
    
    int holeOrdinal = populatedOrdinals.nextClearBit(0);
    while(holeOrdinal <= currentData.maxOrdinal) {
        if((holeOrdinal & (numShards - 1)) == shardNumber)
            holeBits += currentData.bitsPerRecord;
        
        holeOrdinal = populatedOrdinals.nextClearBit(holeOrdinal + 1);
    }
    
    return holeBits / 8;
}
 

@Override
int nextClearBit(BitSet bitSet, int startIdx) {
  int bitNumber = bitSet.nextClearBit(startIdx);
  while (isEven(bitNumber)) {
    bitNumber = bitSet.nextClearBit(bitNumber + 1);
  }
  return bitNumber;
}
 

public long getApproximateHoleCostInBytes(BitSet populatedOrdinals, int shardNumber, int numShards) {
    HollowSetTypeDataElements currentData = currentDataVolatile;
    long holeBits = 0;
    
    int holeOrdinal = populatedOrdinals.nextClearBit(0);
    while(holeOrdinal <= currentData.maxOrdinal) {
        if((holeOrdinal & (numShards - 1)) == shardNumber)
            holeBits += currentData.bitsPerFixedLengthSetPortion;
        
        holeOrdinal = populatedOrdinals.nextClearBit(holeOrdinal + 1);
    }
    
    return holeBits / 8;
}
 

private void generateSparseData() throws HiveException {
    float label = rnd1.nextFloat();
    float sign = (label <= prob_one) ? 1.f : 0.f;
    labels[position] = classification ? sign : label;
    String[] features = featuresArray[position];
    assert (features != null);
    final BitSet used = new BitSet(n_dimensions);
    int searchClearBitsFrom = 0;
    for (int i = 0, retry = 0; i < n_features; i++) {
        int f = rnd2.nextInt(n_dimensions);
        if (used.get(f)) {
            if (retry < 3) {
                --i;
                ++retry;
                continue;
            }
            searchClearBitsFrom = used.nextClearBit(searchClearBitsFrom);
            f = searchClearBitsFrom;
        }
        used.set(f);
        float w = (float) rnd2.nextGaussian() + (sign * eps);
        String y = f + ":" + w;
        features[i] = y;
        retry = 0;
    }
    if (sort) {
        Arrays.sort(features, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                int i1 = Integer.parseInt(o1.split(":")[0]);
                int i2 = Integer.parseInt(o2.split(":")[0]);
                return Primitives.compare(i1, i2);
            }
        });
    }
}
 

public long getApproximateHoleCostInBytes(BitSet populatedOrdinals, int shardNumber, int numShards) {
    HollowListTypeDataElements currentData = currentDataVolatile;
    long holeBits = 0;
    
    int holeOrdinal = populatedOrdinals.nextClearBit(0);
    while(holeOrdinal <= currentData.maxOrdinal) {
        if((holeOrdinal & (numShards - 1)) == shardNumber)
            holeBits += currentData.bitsPerListPointer;
        
        holeOrdinal = populatedOrdinals.nextClearBit(holeOrdinal + 1);
    }
    
    return holeBits / 8;
}
 

private static void verifyLCS(@Nonnull int[] sequence1, @Nonnull int[] sequence2, int start1, int count1, int start2, int count2, @Nonnull BitSet changes1, @Nonnull BitSet changes2) {
  int index1 = changes1.nextClearBit(start1);
  int index2 = changes2.nextClearBit(start2);

  while (index1 < start1 + count1 || index2 < start2 + count2) {
    assertTrue(index1 < start1 + count1);
    assertTrue(index2 < start2 + count2);

    assertEquals(sequence1[index1], sequence2[index2]);

    index1 = changes1.nextClearBit(index1 + 1);
    index2 = changes2.nextClearBit(index2 + 1);
  }
  assertTrue(index1 >= start1 + count1 && index2 >= start2 + count2);
}
 

@NonNull
public String formatName(
        @NonNull final String name,
        @NonNull final String textToFind,
        final boolean caseSensitive) {
    if (null == textToFind || "".equals(textToFind)) {
        return name;
    }
    BitSet bitSet = new BitSet(name.length());
    List<String> parts = splitByCamelCaseAndWildcards(textToFind);

    String convertedTypeName = caseSensitive ? name : name.toLowerCase();
    //mark the chars to be highlighted
    int startIndex = 0;
    for (String camelCasePart : parts) {

        int indexOf = convertedTypeName.indexOf(caseSensitive ? camelCasePart : camelCasePart.toLowerCase(), startIndex);
        if (indexOf != -1) {

            //mark the chars 
            bitSet.set(indexOf, indexOf + camelCasePart.length(), true);
        } else {
            break;
        }
        startIndex = indexOf + camelCasePart.length();
    }

    //highlight the marked chars via  tags
    StringBuilder formattedTypeName = new StringBuilder();
    int i = 0;
    while (i < name.length()) {

        boolean isMarked = bitSet.get(i);

        if (isMarked) {
            int numberOfContinuousHighlights = bitSet.nextClearBit(i) - i;
            String part = name.substring(i, i + numberOfContinuousHighlights);
            formattedTypeName.append(String.format(formatPattern, part));
            i += numberOfContinuousHighlights;
        } else {
            formattedTypeName.append(name.charAt(i));
            i++;
        }
    }
    return formattedTypeName.toString();
}
 

@Override
int nextClearBit(BitSet bitSet, int startIdx) {
  return bitSet.nextClearBit(startIdx);
}
 

public void test_nextClearBitI() {
    BitSet bs = new BitSet(500);
    // ensure all the bits from 0 to bs.size() - 1 are set to true
    bs.set(0, bs.size() - 1);
    bs.set(bs.size() - 1);
    bs.clear(5);
    bs.clear(32);
    bs.clear(63);
    bs.clear(64);
    bs.clear(71, 110);
    bs.clear(127, 130);
    bs.clear(193);
    bs.clear(450);
    try {
        bs.nextClearBit(-1);
        fail();
    } catch (IndexOutOfBoundsException expected) {
    }
    assertEquals(5, bs.nextClearBit(0));
    assertEquals(5, bs.nextClearBit(5));
    assertEquals(32, bs.nextClearBit(6));
    assertEquals(32, bs.nextClearBit(32));
    assertEquals(63, bs.nextClearBit(33));

    // boundary tests
    assertEquals(63, bs.nextClearBit(63));
    assertEquals(64, bs.nextClearBit(64));

    // at bitset element 1
    assertEquals(71, bs.nextClearBit(65));
    assertEquals(71, bs.nextClearBit(71));
    assertEquals(72, bs.nextClearBit(72));
    assertEquals(127, bs.nextClearBit(110));

    // boundary tests
    assertEquals(127, bs.nextClearBit(127));
    assertEquals(128, bs.nextClearBit(128));

    // at bitset element 2
    assertEquals(193, bs.nextClearBit(130));
    assertEquals(193, bs.nextClearBit(191));

    assertEquals(193, bs.nextClearBit(192));
    assertEquals(193, bs.nextClearBit(193));
    assertEquals(450, bs.nextClearBit(194));
    assertEquals(450, bs.nextClearBit(255));
    assertEquals(450, bs.nextClearBit(256));
    assertEquals(450, bs.nextClearBit(450));

    // bitset has 1 still the end of bs.size() -1, but calling nextClearBit
    // with any index value after the last true bit should return bs.size()
    assertEquals(512, bs.nextClearBit(451));
    assertEquals(512, bs.nextClearBit(511));
    assertEquals(512, bs.nextClearBit(512));

    // if the index is larger than bs.size(), nextClearBit should return index
    assertEquals(513, bs.nextClearBit(513));
    assertEquals(800, bs.nextClearBit(800));

    bs.clear();
    assertEquals(0, bs.nextClearBit(0));
    assertEquals(3, bs.nextClearBit(3));
    assertEquals(64, bs.nextClearBit(64));
    assertEquals(128, bs.nextClearBit(128));
}
 

/**
 * Removes all instructions from every unreachable block.
 */
private void pruneDeadInstructions() {
    HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>();

    BitSet reachable = ssaMeth.computeReachability();
    ArrayList<SsaBasicBlock> blocks = ssaMeth.getBlocks();
    int blockIndex = 0;

    while ((blockIndex = reachable.nextClearBit(blockIndex)) < blocks.size()) {
        SsaBasicBlock block = blocks.get(blockIndex);
        blockIndex++;

        // Prune instructions from unreachable blocks
        for (int i = 0; i < block.getInsns().size(); i++) {
            SsaInsn insn = block.getInsns().get(i);
            RegisterSpecList sources = insn.getSources();
            int sourcesSize = sources.size();

            // Delete this instruction completely if it has sources
            if (sourcesSize != 0) {
                deletedInsns.add(insn);
            }

            // Delete this instruction from all usage lists.
            for (int j = 0; j < sourcesSize; j++) {
                RegisterSpec source = sources.get(j);
                useList[source.getReg()].remove(insn);
            }

            // Remove this instruction result from the sources of any phis
            RegisterSpec result = insn.getResult();
            if (result == null) continue;
            for (SsaInsn use : useList[result.getReg()]) {
                if (use instanceof PhiInsn) {
                    PhiInsn phiUse = (PhiInsn) use;
                    phiUse.removePhiRegister(result);
                }
            }
        }
    }

    ssaMeth.deleteInsns(deletedInsns);
}
 

@Override
int nextClearBit(BitSet bitSet, int startIdx) {
  return bitSet.nextClearBit(startIdx);
}