下面列出了java.util.BitSet#nextSetBit ( ) 实例代码,或者点击链接到github查看源代码,也可以在右侧发表评论。
public de.metanome.algorithms.cfdfinder.structures.FDTreeElement addFunctionalDependency(BitSet lhs, int rhs) {
de.metanome.algorithms.cfdfinder.structures.FDTreeElement currentNode = this;
currentNode.addRhsAttribute(rhs);
int lhsLength = 0;
for (int i = lhs.nextSetBit(0); i >= 0; i = lhs.nextSetBit(i + 1)) {
lhsLength++;
if (currentNode.getChildren() == null) {
currentNode.setChildren(new de.metanome.algorithms.cfdfinder.structures.FDTreeElement[this.numAttributes]);
currentNode.getChildren()[i] = new de.metanome.algorithms.cfdfinder.structures.FDTreeElement(this.numAttributes);
}
else if (currentNode.getChildren()[i] == null) {
currentNode.getChildren()[i] = new de.metanome.algorithms.cfdfinder.structures.FDTreeElement(this.numAttributes);
}
currentNode = currentNode.getChildren()[i];
currentNode.addRhsAttribute(rhs);
}
currentNode.markFd(rhs);
this.depth = Math.max(this.depth, lhsLength);
return currentNode;
}
@Test(dataProvider = "cases")
public void testBitsetStream(String name, IntStream data) {
BitSet bs = new BitSet();
long setBits = data.distinct()
.peek(i -> bs.set(i))
.count();
assertEquals(bs.cardinality(), setBits);
assertEquals(bs.cardinality(), bs.stream().reduce(0, (s, i) -> s+1));
PrimitiveIterator.OfInt it = bs.stream().iterator();
for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
assertTrue(it.hasNext());
assertEquals(it.nextInt(), i);
}
assertFalse(it.hasNext());
}
/**
* Helper method for {@link #precomputedInternal} that doesn't test if the negation is cheaper.
*/
@GwtIncompatible // java.util.BitSet
private static CharMatcher precomputedPositive(int totalCharacters, BitSet table, String description) {
switch (totalCharacters) {
case 0:
return none();
case 1:
return is((char) table.nextSetBit(0));
case 2:
char c1 = (char) table.nextSetBit(0);
char c2 = (char) table.nextSetBit(c1 + 1);
return isEither(c1, c2);
default:
return isSmall(totalCharacters, table.length())
? SmallCharMatcher.from(table, description)
: new BitSetMatcher(table, description);
}
}
public void printDependencies(BitSet activePath) {
for (int attr = 1; attr <= maxAttributeNumber; attr++) {
if (isfd[attr - 1]) {
String out = "{";
for (int i = activePath.nextSetBit(0); i >= 0; i = activePath.nextSetBit(i + 1)) {
out += i + ",";
}
if (out.length() > 1) {
out = out.substring(0, out.length() - 1);
}
out += "} -> " + attr;
System.out.println(out);
}
}
for (int attr = 1; attr <= maxAttributeNumber; attr++) {
if (children[attr - 1] != null) {
activePath.set(attr);
children[attr - 1].printDependencies(activePath);
activePath.clear(attr);
}
}
}
protected ClusterIdentifier buildClusterIdentifier(int recordId, int[][] invertedPlis, BitSet lhs, int lhsSize) {
int[] cluster = new int[lhsSize];
int index = 0;
for (int lhsAttr = lhs.nextSetBit(0); lhsAttr >= 0; lhsAttr = lhs.nextSetBit(lhsAttr + 1)) {
int clusterId = invertedPlis[lhsAttr][recordId];
if (clusterId < 0)
return null;
cluster[index] = clusterId;
index++;
}
return new ClusterIdentifier(cluster);
}
private void build() {
if (!buildIndexOnUpdate) return;
// tell memory recycler to use current tst's long arrays next time when long array is requested.
// note reuse only happens once swap is called and bits are reset
TST current = prefixIndexVolatile;
if (current != null) current.recycleMemory(memoryRecycle);
long estimatedNumberOfNodes = estimateNumNodes(totalWords, averageWordLen);
TST tst = new TST(estimatedNumberOfNodes, estimatedMaxStringDuplicates, maxOrdinalOfType,
memoryRecycle);
BitSet ordinals = readStateEngine.getTypeState(type).getPopulatedOrdinals();
int ordinal = ordinals.nextSetBit(0);
while (ordinal != -1) {
for (String key : getKeys(ordinal)) {
tst.insert(key, ordinal);
}
ordinal = ordinals.nextSetBit(ordinal + 1);
}
prefixIndexVolatile = tst;
// safe to return previous long arrays on next request for long array.
memoryRecycle.swap();
buildIndexOnUpdate = false;
}
/**
* Returns an iterable over the bits in a bitmap that are set to '1'.
*
* <p>This allows you to iterate over a bit set using a 'foreach' construct.
* For instance:
*
* <blockquote><code>
* BitSet bitSet;<br>
* for (int i : Util.toIter(bitSet)) {<br>
* print(i);<br>
* }</code></blockquote>
*
* @param bitSet Bit set
* @return Iterable
*/
public static Iterable<Integer> toIter(final BitSet bitSet) {
return () -> new Iterator<Integer>() {
int i = bitSet.nextSetBit(0);
public boolean hasNext() {
return i >= 0;
}
public Integer next() {
int prev = i;
i = bitSet.nextSetBit(i + 1);
return prev;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
protected boolean containsFdOrGeneralization(BitSet lhs, int rhs, int currentLhsAttr) {
if (this.isFd(rhs))
return true;
// Is the dependency already read and we have not yet found a generalization?
if (currentLhsAttr < 0)
return false;
int nextLhsAttr = lhs.nextSetBit(currentLhsAttr + 1);
if ((this.children != null) && (this.children[currentLhsAttr] != null) && (this.children[currentLhsAttr].hasRhsAttribute(rhs)))
if (this.children[currentLhsAttr].containsFdOrGeneralization(lhs, rhs, nextLhsAttr))
return true;
return this.containsFdOrGeneralization(lhs, rhs, nextLhsAttr);
}
private void setPostRegisterTypeAndPropagateChanges(@Nonnull AnalyzedInstruction analyzedInstruction,
int registerNumber, @Nonnull RegisterType registerType) {
BitSet changedInstructions = new BitSet(analyzedInstructions.size());
if (!analyzedInstruction.setPostRegisterType(registerNumber, registerType)) {
return;
}
propagateRegisterToSuccessors(analyzedInstruction, registerNumber, changedInstructions);
//Using a for loop inside the while loop optimizes for the common case of the successors of an instruction
//occurring after the instruction. Any successors that occur prior to the instruction will be picked up on
//the next iteration of the while loop.
//This could also be done recursively, but in large methods it would likely cause very deep recursion,
//which requires the user to specify a larger stack size. This isn't really a problem, but it is slightly
//annoying.
while (!changedInstructions.isEmpty()) {
for (int instructionIndex=changedInstructions.nextSetBit(0);
instructionIndex>=0;
instructionIndex=changedInstructions.nextSetBit(instructionIndex+1)) {
changedInstructions.clear(instructionIndex);
propagateRegisterToSuccessors(analyzedInstructions.valueAt(instructionIndex), registerNumber,
changedInstructions);
}
}
if (registerType.category == RegisterType.LONG_LO) {
checkWidePair(registerNumber, analyzedInstruction);
setPostRegisterTypeAndPropagateChanges(analyzedInstruction, registerNumber+1, RegisterType.LONG_HI_TYPE);
} else if (registerType.category == RegisterType.DOUBLE_LO) {
checkWidePair(registerNumber, analyzedInstruction);
setPostRegisterTypeAndPropagateChanges(analyzedInstruction, registerNumber+1, RegisterType.DOUBLE_HI_TYPE);
}
}
/**
* Updates the phi insns in successor blocks with operands based
* on the current mapping of the rop register the phis represent.
*/
private void updateSuccessorPhis() {
PhiInsn.Visitor visitor = new PhiInsn.Visitor() {
public void visitPhiInsn (PhiInsn insn) {
int ropReg;
ropReg = insn.getRopResultReg();
if (isBelowThresholdRegister(ropReg)) {
return;
}
/*
* Never add a version 0 register as a phi
* operand. Version 0 registers represent the
* initial register state, and thus are never
* significant. Furthermore, the register liveness
* algorithm doesn't properly count them as "live
* in" at the beginning of the method.
*/
RegisterSpec stackTop = currentMapping[ropReg];
if (!isVersionZeroRegister(stackTop.getReg())) {
insn.addPhiOperand(stackTop, block);
}
}
};
BitSet successors = block.getSuccessors();
for (int i = successors.nextSetBit(0); i >= 0;
i = successors.nextSetBit(i + 1)) {
SsaBasicBlock successor = ssaMeth.getBlocks().get(i);
successor.forEachPhiInsn(visitor);
}
}
private BitSet queryBasedOnMatchedReferences(HollowObjectTypeReadState typeState, int referenceFieldPosition, BitSet matchedReferences) {
BitSet populatedOrdinals = typeState.getPopulatedOrdinals();
BitSet typeQueryMatches = new BitSet(populatedOrdinals.length());
int ordinal = populatedOrdinals.nextSetBit(0);
while(ordinal != -1) {
int refOrdinal = typeState.readOrdinal(ordinal, referenceFieldPosition);
if(refOrdinal != -1 && matchedReferences.get(refOrdinal))
typeQueryMatches.set(ordinal);
ordinal = populatedOrdinals.nextSetBit(ordinal+1);
}
return typeQueryMatches;
}
private String liveSetToString(BitSet liveSet) {
StringBuilder sb = new StringBuilder();
for (int i = liveSet.nextSetBit(0); i >= 0; i = liveSet.nextSetBit(i + 1)) {
StackInterval interval = getIntervalFromStackId(i);
sb.append(interval.getOperand()).append(" ");
}
return sb.toString();
}
/**
* Walks the basic block tree in depth-first order, calling the visitor
* method once for every block. This depth-first walk may be run forward
* from the method entry point or backwards from the method exit points.
*
* @param reverse true if this should walk backwards from the exit points
* @param v {@code non-null;} callback interface. {@code parent} is set
* unless this is the root node
*/
public void forEachBlockDepthFirst(boolean reverse,
SsaBasicBlock.Visitor v) {
BitSet visited = new BitSet(blocks.size());
// We push the parent first, then the child on the stack.
Stack<SsaBasicBlock> stack = new Stack<SsaBasicBlock>();
SsaBasicBlock rootBlock = reverse ? getExitBlock() : getEntryBlock();
if (rootBlock == null) {
// in the case there's no exit block
return;
}
stack.add(null); // Start with null parent.
stack.add(rootBlock);
while (stack.size() > 0) {
SsaBasicBlock cur = stack.pop();
SsaBasicBlock parent = stack.pop();
if (!visited.get(cur.getIndex())) {
BitSet children
= reverse ? cur.getPredecessors() : cur.getSuccessors();
for (int i = children.nextSetBit(0); i >= 0
; i = children.nextSetBit(i + 1)) {
stack.add(cur);
stack.add(blocks.get(i));
}
visited.set(cur.getIndex());
v.visitBlock(cur, parent);
}
}
}
/**
* Returns a GraphTaxonomy, with each taxon representing the vertices in a
* (weak) component.
* <p>
* This procedure is fundamentally linear, but may be slowed by construction
* of reporting structures. It is implemented as a breadth-first traversal.
* <p>
* @param graph The graph to get the components from.
* @param verticesToArrange a bit set specifying which vertices to arrange.
*
* @return a GraphTaxonomy, with each taxon representing the vertices in a
* (weak) component.
*/
@Deprecated
public static GraphTaxonomy getComponents(final GraphWriteMethods graph, final BitSet verticesToArrange) {
final Map<Integer, Set<Integer>> tax = new HashMap<>();
final BitSet tmp = new BitSet();
tmp.or(verticesToArrange);
for (int vxId = tmp.nextSetBit(0); vxId >= 0; vxId = tmp.nextSetBit(vxId + 1)) {
if (graph.getVertexNeighbourCount(vxId) == 0) {
// Short cut to avoid extra work.
final Set<Integer> s = new HashSet<>();
s.add(vxId);
tax.put(vxId, s);
tmp.clear(vxId);
} else {
final Set<Integer> component = getComponentContainingVertex(graph, vxId, tmp);
tax.put(component.iterator().next(), component);
// Clear the vertices in this component from the vertices BitSet.
for (int i : component) {
tmp.clear(i);
}
}
}
return new GraphTaxonomy(graph, tax);
}
/**
* Remove a collection of transactions from the graph.
*
* @param transactions the transaction to remove as a {@link STransaction}.
*/
public void removeTransactions(final SCollection transactions) {
final BitSet transactionIds = transactions.elementIds();
for (int transaction = transactionIds.nextSetBit(0); transaction >= 0; transaction = transactionIds.nextSetBit(transaction + 1)) {
getWritableGraph().removeTransaction(transaction);
}
}
List<Unit> asList(int fromIndex, int toIndex) {
BitSet bits = this;
if (universe.length < toIndex || toIndex < fromIndex || fromIndex < 0)
throw new IndexOutOfBoundsException();
if (fromIndex == toIndex) {
return emptyList();
}
if (fromIndex == toIndex - 1) {
if (bits.get(fromIndex)) {
return singletonList(universe[fromIndex]);
}
return emptyList();
}
int i = bits.nextSetBit(fromIndex);
if (i < 0 || i >= toIndex)
return emptyList();
if (i == toIndex - 1)
return singletonList(universe[i]);
List<Unit> elements = new ArrayList<Unit>(toIndex-i);
for (;;) {
int endOfRun = Math.min(toIndex, bits.nextClearBit(i+1));
do { elements.add(universe[i++]); }
while (i < endOfRun);
if (i >= toIndex)
break;
i = bits.nextSetBit(i+1);
if (i < 0 || i >= toIndex)
break;
}
return elements;
}
/**
* Performs a depth first search walking the normal byte code path starting
* at <code>index</code>, and adding each instruction encountered into the
* subroutine <code>sub</code>. After this walk is complete, iterates over
* the exception handlers to ensure that we also include those byte codes
* which are reachable through an exception that may be thrown during the
* execution of the subroutine. Invoked from <code>markSubroutines()</code>.
*
* @param sub
* the subroutine whose instructions must be computed.
* @param index
* an instruction of this subroutine.
* @param anyvisited
* indexes of the already visited instructions, i.e. marked as
* part of this subroutine or any previously computed subroutine.
*/
private void markSubroutineWalk(final BitSet sub, final int index,
final BitSet anyvisited) {
if (LOGGING) {
log("markSubroutineWalk: sub=" + sub + " index=" + index);
}
// First find those instructions reachable via normal execution
markSubroutineWalkDFS(sub, index, anyvisited);
// Now, make sure we also include any applicable exception handlers
boolean loop = true;
while (loop) {
loop = false;
for (Iterator<TryCatchBlockNode> it = tryCatchBlocks.iterator(); it
.hasNext();) {
TryCatchBlockNode trycatch = it.next();
if (LOGGING) {
// TODO use of default toString().
log("Scanning try/catch " + trycatch);
}
// If the handler has already been processed, skip it.
int handlerindex = instructions.indexOf(trycatch.handler);
if (sub.get(handlerindex)) {
continue;
}
int startindex = instructions.indexOf(trycatch.start);
int endindex = instructions.indexOf(trycatch.end);
int nextbit = sub.nextSetBit(startindex);
if (nextbit != -1 && nextbit < endindex) {
if (LOGGING) {
log("Adding exception handler: " + startindex + '-'
+ endindex + " due to " + nextbit + " handler "
+ handlerindex);
}
markSubroutineWalkDFS(sub, handlerindex, anyvisited);
loop = true;
}
}
}
}
/**
* Performs a depth first search walking the normal byte code path starting
* at <code>index</code>, and adding each instruction encountered into the
* subroutine <code>sub</code>. After this walk is complete, iterates over
* the exception handlers to ensure that we also include those byte codes
* which are reachable through an exception that may be thrown during the
* execution of the subroutine. Invoked from <code>markSubroutines()</code>.
*
* @param sub
* the subroutine whose instructions must be computed.
* @param index
* an instruction of this subroutine.
* @param anyvisited
* indexes of the already visited instructions, i.e. marked as
* part of this subroutine or any previously computed subroutine.
*/
private void markSubroutineWalk(final BitSet sub, final int index,
final BitSet anyvisited) {
if (LOGGING) {
log("markSubroutineWalk: sub=" + sub + " index=" + index);
}
// First find those instructions reachable via normal execution
markSubroutineWalkDFS(sub, index, anyvisited);
// Now, make sure we also include any applicable exception handlers
boolean loop = true;
while (loop) {
loop = false;
for (Iterator<TryCatchBlockNode> it = tryCatchBlocks.iterator(); it
.hasNext();) {
TryCatchBlockNode trycatch = it.next();
if (LOGGING) {
// TODO use of default toString().
log("Scanning try/catch " + trycatch);
}
// If the handler has already been processed, skip it.
int handlerindex = instructions.indexOf(trycatch.handler);
if (sub.get(handlerindex)) {
continue;
}
int startindex = instructions.indexOf(trycatch.start);
int endindex = instructions.indexOf(trycatch.end);
int nextbit = sub.nextSetBit(startindex);
if (nextbit != -1 && nextbit < endindex) {
if (LOGGING) {
log("Adding exception handler: " + startindex + '-'
+ endindex + " due to " + nextbit + " handler "
+ handlerindex);
}
markSubroutineWalkDFS(sub, handlerindex, anyvisited);
loop = true;
}
}
}
}
public static int getSize(BitSet set) {
int result = 0;
int size = set.length() + 1;
result += BitBuffer.getEliasDeltaSize(size + 1);
int cardinality = set.cardinality();
result += BitBuffer.getEliasDeltaSize(cardinality + 1);
int blockCount = (cardinality + BITS_PER_BLOCK - 1) / BITS_PER_BLOCK;
ArrayList<Integer> list = new ArrayList<Integer>();
int pos = set.nextSetBit(0);
for (int i = 0; i < blockCount; i++) {
list.add(pos);
for (int j = 0; j < BITS_PER_BLOCK; j++) {
pos = set.nextSetBit(pos + 1);
}
}
long blockCountScale = getScaleFactor(size, blockCount);
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < list.size(); i++) {
// int expected = (int) ((long) size * i / blockCount);
int expected = (int) ((i * blockCountScale) >>> 32);
int got = list.get(i);
int diff = got - expected;
list.set(i, diff);
minDiff = Math.min(minDiff, diff);
}
if (list.size() == 0) {
minDiff = 0;
}
result += BitBuffer.getEliasDeltaSize(BitBuffer.foldSigned(-minDiff) + 1);
int max = 0;
for (int i = 0; i < list.size(); i++) {
int x = list.get(i) - minDiff;
max = Math.max(max, x);
list.set(i, x);
}
int bitCount = 32 - Integer.numberOfLeadingZeros(max);
result += BitBuffer.getEliasDeltaSize(bitCount + 1);
result += bitCount * list.size();
result += size;
return result;
}
public LongBitSet(BitSet bitSet) {
this(bitSet.length());
for (int bit = bitSet.nextSetBit(0); bit >= 0; bit = bitSet.nextSetBit(bit + 1)) {
set(bit);
}
}