下面列出了java.util.Queue#size ( ) 实例代码,或者点击链接到github查看源代码,也可以在右侧发表评论。
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode curNode = queue.poll();
// 如果写成 i == 0 就得到左边的视图
if (i == size - 1) {
res.add(curNode.val);
}
if (curNode.left != null) {
queue.add(curNode.left);
}
if (curNode.right != null) {
queue.add(curNode.right);
}
}
}
return res;
}
public void walk(Object element) throws Exception {
if (element != null) {
Collection<java.lang.Class<?>> types = new LinkedList<Class<?>>();
types.add(element.getClass());
Queue<java.lang.Class<?>> interfaces = new ConcurrentLinkedQueue<java.lang.Class<?>>(types);
Collection<java.lang.Class<?>> visitedTypes = new LinkedList<java.lang.Class<?>>();
while (interfaces.size() > 0) {
java.lang.Class<?> type = interfaces.poll();
if (visitedTypes.add(type)) {
try {
Method m = this.getClass().getMethod("accept", type);
m.invoke(this, element);
interfaces.addAll(Arrays.asList(type.getInterfaces()));
} catch (NoSuchMethodException e) {
}
}
}
}
}
public static <T extends Comparable<T>> Queue<T> sort(Queue<T> input) {
Queue<T> output = new LinkedList<T>();
Queue<T> tempArray1 = new LinkedList<T>();
Queue<T> tempArray2 = new LinkedList<T>();
while (input.size() > 0) {
while (input.size() > 0) {
merge(input, output, tempArray1);
merge(input, output, tempArray2);
}
while (tempArray1.size() > 0 || tempArray2.size() > 0) {
merge(tempArray1, tempArray2, output);
merge(tempArray1, tempArray2, input);
}
}
return output;
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new LinkedList<>();
if (root == null) return list;
Queue<TreeNode> q = new LinkedList<>();
List<Integer> l = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode t = q.poll();
l.add(t.val);
if (t.left != null) q.offer(t.left);
if (t.right != null) q.offer(t.right);
}
list.add(l);
l = new LinkedList<>();
}
return list;
}
/**
* Use a level list to store the nodes of this level
* addRecursive root to it to begin
* Build next level with current level, add current level value to result
* Assign next level to current level
* addRecursive curLevel to first of result each time to get reverse order
*/
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new LinkedList<List<Integer>>();
if (root == null) return res;
/*store the nodes of thie level*/
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> curLevel = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode n = q.poll();
curLevel.add(n.val);
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
res.add(0, curLevel);
}
return res;
}
private void receiveDeserializeProgress(Queue<InMessage> msgQueue, int receiveId) {
InMessage currentMessage = msgQueue.peek();
if (currentMessage == null) {
return;
}
if (currentMessage.getReceivedState() == InMessage.ReceivedState.INIT
|| currentMessage.getReceivedState() == InMessage.ReceivedState.BUILDING) {
if (currentMessage.getReceivedState() == InMessage.ReceivedState.INIT) {
Queue<InMessage> pendingReceiveMessages =
pendingReceiveMessagesPerSource.get(currentMessage.getHeader().getSourceId());
if (!pendingReceiveMessages.offer(currentMessage)) {
throw new RuntimeException(executor + " We should have enough space: "
+ pendingReceiveMessages.size());
}
currentMessage.setReceivedState(InMessage.ReceivedState.BUILDING);
}
messageDeSerializer.get(receiveId).build(currentMessage,
currentMessage.getHeader().getEdge());
// lets check weather we have read everythong
int readObjectNumber = currentMessage.getUnPkNumberObjects();
// we need to get number of tuples and get abs because we are using -1 for single messages
if (readObjectNumber == Math.abs(currentMessage.getHeader().getNumberTuples())) {
currentMessage.setReceivedState(InMessage.ReceivedState.BUILT);
}
}
// we remove only when the unpacking is complete and ready to receive
if (currentMessage.getReceivedState() == InMessage.ReceivedState.BUILT
|| currentMessage.getReceivedState() == InMessage.ReceivedState.RECEIVE
|| currentMessage.getReceivedState() == InMessage.ReceivedState.DONE) {
msgQueue.poll();
}
}
protected boolean doNextRunnable(Queue<Runnable> runnables) {
if (runnables.size() > 0) {
Runnable r = runnables.poll();
r.run();
return true;
}
return false;
}
@Override
public void onReceiveComplete(int id, int e, DataBuffer buffer) {
// we need to try to build the message here, we may need many more messages to complete
ByteBuffer byteBuffer = buffer.getByteBuffer();
byteBuffer.position(buffer.getSize());
byteBuffer.flip();
// we have the source of the message at 0th position as an integer
int source = byteBuffer.getInt(0);
InMessage currentMessage = currentMessages.get(source);
if (currentMessage == null) {
MessageHeader header = messageDeSerializer.get(source).buildHeader(buffer, e);
MessageType recvDType = receiveDataType;
MessageType recvKType = receiveKeyType;
if ((header.getFlags() & MessageFlags.SYNC_BARRIER) == MessageFlags.SYNC_BARRIER) {
recvDType = MessageTypes.BYTE_ARRAY;
recvKType = MessageTypes.EMPTY;
}
currentMessage = new InMessage(id, recvDType, this, header);
if (isKeyed) {
currentMessage.setKeyType(recvKType);
}
if (!currentMessage.addBufferAndCalculate(buffer)) {
currentMessages.put(source, currentMessage);
}
// we add the message immediately to the deserialization as we can deserialize partially
Queue<InMessage> deserializeQueue = pendingReceiveDeSerializations.get(source);
if (!deserializeQueue.offer(currentMessage)) {
throw new RuntimeException(executor + " We should have enough space: "
+ deserializeQueue.size());
}
} else {
if (currentMessage.addBufferAndCalculate(buffer)) {
currentMessages.remove(source);
}
}
}
/**
* Progress deserialize
* @param receiveId
*/
public void receiveDeserializeProgress(int receiveId) {
Queue<InMessage> msgQueue = pendingReceiveDeSerializations.get(receiveId);
InMessage currentMessage = msgQueue.peek();
if (currentMessage == null) {
return;
}
if (currentMessage.getReceivedState() == InMessage.ReceivedState.INIT
|| currentMessage.getReceivedState() == InMessage.ReceivedState.BUILDING) {
if (currentMessage.getReceivedState() == InMessage.ReceivedState.INIT) {
Queue<InMessage> pendingReceiveMessages =
pendingReceiveMessagesPerSource.get(currentMessage.getHeader().getSourceId());
if (!pendingReceiveMessages.offer(currentMessage)) {
throw new RuntimeException(executor + " We should have enough space: "
+ pendingReceiveMessages.size());
}
currentMessage.setReceivedState(InMessage.ReceivedState.BUILDING);
}
messageDeSerializer.get(receiveId).build(currentMessage,
currentMessage.getHeader().getEdge());
// lets check weather we have read everythong
int readObjectNumber = currentMessage.getUnPkNumberObjects();
// we need to get number of tuples and get abs because we are using -1 for single messages
if (readObjectNumber == Math.abs(currentMessage.getHeader().getNumberTuples())) {
currentMessage.setReceivedState(InMessage.ReceivedState.BUILT);
}
}
// we remove only when the unpacking is complete and ready to receive
if (currentMessage.getReceivedState() == InMessage.ReceivedState.BUILT
|| currentMessage.getReceivedState() == InMessage.ReceivedState.RECEIVE
|| currentMessage.getReceivedState() == InMessage.ReceivedState.DONE) {
msgQueue.poll();
}
}
/**
* 题目地址:https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
* -------------------------------------------------------------------
* 思考:
* -------------------------------------------------------------------
* 思路:
* -------------------------------------------------------------------
* 时间复杂度:
* 空间复杂度:
*/
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null)
return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
// 遍历每层的数据
int size = queue.size();
List<Integer> list = new ArrayList<>();
while (size > 0) {
root = queue.poll();
list.add(root.val);
if (root.left != null) {
queue.add(root.left);
}
if (root.right != null) {
queue.add(root.right);
}
size--;
}
result.add(list);
}
return result;
}
@Override
protected boolean sendToTarget(int target, boolean sync) {
Queue<Object> reducedValues = this.reducedValuesMap.get(target);
while (reducedValues.size() > 0) {
Object previous = reducedValues.peek();
boolean handle = handleMessage(target, previous, 0, destination);
if (handle) {
reducedValues.poll();
} else {
return false;
}
}
return true;
}
public int widthOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> levelQueue = new LinkedList<>();
LinkedList<Integer> levelLocal = new LinkedList<>();
levelQueue.add(root);
levelLocal.add(1);
// 结果至少为 1
int res = 1;
while (!levelQueue.isEmpty()) {
// levelQueue 的大小就是当前层所有结点数目
int count = levelQueue.size();
// 遍历当前层所以结点,然后将他们的左右孩子结点加入
for (int i = 0; i < count; i++) {
TreeNode curNode = levelQueue.poll();
Integer curIndex = levelLocal.removeFirst();
if (curNode.left != null) {
levelQueue.offer(curNode.left);
levelLocal.add(curIndex * 2);
}
if (curNode.right != null) {
levelQueue.offer(curNode.right);
levelLocal.add(curIndex * 2 + 1);
}
}
// 如果队列中只有一个元素(这行只有一个元素),则无需判断
if (levelLocal.size() >= 2) {
res = Math.max(res, levelLocal.getLast() - levelLocal.getFirst() + 1);
}
}
return res;
}
protected void queueVariableEvent(VariableEvent variableEvent, boolean includeCustomerListeners) {
Queue<VariableEvent> variableEventsQueue = getVariableEventQueue();
variableEventsQueue.add(variableEvent);
// if this is the first event added, trigger listener invocation
if (variableEventsQueue.size() == 1) {
invokeVariableListeners(includeCustomerListeners);
}
}
/**
* Merge sort a queue of sorted queues,
*
* This method is thread-safe
*
* algorithm:
* 1. extract(poll) n queues from queueOfSortedQueues and put them into listOfSortedQueues, 2 <= n <= maxWays,
* 2. merge sort listOfSortedQueues using nWayMerageSort method above, and return the result queue into queueOfSortedQueue again,
* 3. repeat 1 & 2 until there is only one queue left in queueOfSortedQueues, that's the final sorted queue.
*
* @param queueOfSortedQueues a queue of sorted sub-queues
* @param maxWays max allowed ways to merge sort
* @throws IOException exception thrown if there is IO error during the operation
*/
public static void mergeSort(Queue<IBigQueue> queueOfSortedQueues, int maxWays) throws IOException {
List<IBigQueue> listOfSortedQueues = new ArrayList<IBigQueue>();
// repeat until there is only one left in queueOfSortedQueue
while(queueOfSortedQueues.size() > 1) {
listOfSortedQueues.clear();
int count = 0;
while(!queueOfSortedQueues.isEmpty() && count < maxWays) {
IBigQueue sortedQueue = queueOfSortedQueues.poll();
if (sortedQueue != null) { // null only happen in multi-threads case
listOfSortedQueues.add(sortedQueue);
count++;
}
}
if (listOfSortedQueues.size() > 1) { // grabbed enough to do n way mergesort
// n way merge sort
IBigQueue targetSortedQueue = nWayMergeSort(listOfSortedQueues);
// return the result queue into queueOfSortedQueues
queueOfSortedQueues.offer(targetSortedQueue);
} else if (listOfSortedQueues.size() == 1) { // 1 only happen in multi-threads case
// grabbed one, but can't do n way meragesort, so just return and try again
queueOfSortedQueues.offer(listOfSortedQueues.remove(0));
} else { // only happen in multi-threads case
// grabbed nothing, retry
}
}
}
private static void waitForSome(Queue<ListenableFuture<?>> futures) throws Exception {
while (futures.size() > 1000) {
futures.remove().get();
}
}
/**
* Navigate flow processors. Flow is equivalent of a resource in Ballerina
*
* @param flow
*/
@Override
public void visit(Flow flow) {
logger.debug("--SFlow");
int i = 0;
int flowSize = flow.getFlowProcessors().size();
for (Processor processor : flow.getFlowProcessors()) {
processor.accept(this);
i++;
//If end of flow
if (flowSize == i) {
ballerinaASTAPI.createNameReference(null, outboundMsg);
ballerinaASTAPI.createVariableRefExpr();
ballerinaASTAPI.createReplyStatement();
ballerinaASTAPI.endCallableBody();
//Workers should be declared after reply statement but before end of resource
if (mRoot.getAsyncTaskList() != null) {
for (AsynchronousTask asynchronousTask : mRoot.getAsyncTaskList()) {
ballerinaASTAPI.enterWorkerDeclaration();
ballerinaASTAPI.createWorkerDefinition(asynchronousTask.getName());
ballerinaASTAPI.addTypes(Constant.BLANG_TYPE_MESSAGE);
ballerinaASTAPI.createVariable(Constant.BLANG_VAR_WORKER_MSG, false);
ballerinaASTAPI.startExprList();
ballerinaASTAPI.createNameReference(null, Constant.BLANG_VAR_WORKER_MSG);
ballerinaASTAPI.createVariableRefExpr();
ballerinaASTAPI.endExprList(1);
ballerinaASTAPI.exitWorkerReply(Constant.BLANG_VAR_DEFAULT_WORKER);
outboundMsg = Constant.BLANG_VAR_WORKER_MSG;
for (Processor asyncProcessor : asynchronousTask.getAsyncProcessors()) {
asyncProcessor.accept(this);
}
ballerinaASTAPI.exitWorkerDeclaration(asynchronousTask.getName());
}
mRoot.getAsyncTaskList().clear();
}
String resourceName = Constant.BLANG_RESOURCE_NAME + ++resourceCounter;
ballerinaASTAPI.endOfResource(resourceName, resourceAnnotationCount); //End of resource
resourceAnnotationCount = 0;
logger.debug("--EFlow");
/* At the end of each flow get the flow queue associate with its config and
* remove this flow from the queue, so that when there are no flows (resources) associate with a config
* (service) we can close the service
*/
if (mRoot.getServiceMap() != null) {
Queue<Flow> flows = mRoot.getServiceMap().get(inboundName);
if (flows != null) {
flows.remove();
if (flows.size() == 0) { //If no more resources
String serviceName = Constant.BLANG_SERVICE_NAME + ++serviceCounter;
ballerinaASTAPI.endOfService(serviceName); //End of service
}
}
}
}
}
}
/**
* <p>
* Generate suggestions by breaking the passed-in term into multiple words.
* The scores returned are equal to the number of word breaks needed so a
* lower score is generally preferred over a higher score.
* </p>
*
* @param suggestMode
* - default = {@link SuggestMode#SUGGEST_WHEN_NOT_IN_INDEX}
* @param sortMethod
* - default =
* {@link BreakSuggestionSortMethod#NUM_CHANGES_THEN_MAX_FREQUENCY}
* @return one or more arrays of words formed by breaking up the original term
* @throws IOException If there is a low-level I/O error.
*/
public SuggestWord[][] suggestWordBreaks(Term term, int maxSuggestions,
IndexReader ir, SuggestMode suggestMode,
BreakSuggestionSortMethod sortMethod) throws IOException {
if (maxSuggestions < 1) {
return new SuggestWord[0][0];
}
if (suggestMode == null) {
suggestMode = SuggestMode.SUGGEST_WHEN_NOT_IN_INDEX;
}
if (sortMethod == null) {
sortMethod = BreakSuggestionSortMethod.NUM_CHANGES_THEN_MAX_FREQUENCY;
}
int queueInitialCapacity = maxSuggestions > 10 ? 10 : maxSuggestions;
Comparator<SuggestWordArrayWrapper> queueComparator = sortMethod == BreakSuggestionSortMethod.NUM_CHANGES_THEN_MAX_FREQUENCY ? new LengthThenMaxFreqComparator()
: new LengthThenSumFreqComparator();
Queue<SuggestWordArrayWrapper> suggestions = new PriorityQueue<>(
queueInitialCapacity, queueComparator);
int origFreq = ir.docFreq(term);
if (origFreq > 0 && suggestMode == SuggestMode.SUGGEST_WHEN_NOT_IN_INDEX) {
return new SuggestWord[0][];
}
int useMinSuggestionFrequency = minSuggestionFrequency;
if (suggestMode == SuggestMode.SUGGEST_MORE_POPULAR) {
useMinSuggestionFrequency = (origFreq == 0 ? 1 : origFreq);
}
generateBreakUpSuggestions(term, ir, 1, maxSuggestions,
useMinSuggestionFrequency, new SuggestWord[0], suggestions, 0,
sortMethod);
SuggestWord[][] suggestionArray = new SuggestWord[suggestions.size()][];
for (int i = suggestions.size() - 1; i >= 0; i--) {
suggestionArray[i] = suggestions.remove().suggestWords;
}
return suggestionArray;
}
public static void drawViewOutlines( final Graphics2D g, final Dimensions dims, final AffineTransform3D transfrom, final Color color )
{
final int n = dims.numDimensions();
final Queue< List< Boolean > > worklist = new LinkedList<>();
// add 0,0,..
final List< Boolean > origin = new ArrayList<>();
for (int d = 0; d < n; d++)
origin.add( false );
worklist.add( origin );
while ( worklist.size() > 0 )
{
final List< Boolean > vertex1 = worklist.poll();
final List< List< Boolean > > neighbors = getHigherVertices( vertex1 );
worklist.addAll( neighbors );
for (final List<Boolean> vertex2 : neighbors)
{
final double[] v1Pos = new double[ n ];
final double[] v2Pos = new double[ n ];
for (int d = 0; d < n; d++)
{
// the outline goes from -0.5 to dimension(d) - 0.5 (compared to the actual range of (0, dim(d)-1))
// this is because BDV (correctly) draws pixels with center at pixel location
v1Pos[d] = vertex1.get( d ) ? dims.dimension( d ) - 0.5 : -0.5;
v2Pos[d] = vertex2.get( d ) ? dims.dimension( d ) - 0.5 : -0.5;
}
transfrom.apply( v1Pos, v1Pos );
transfrom.apply( v2Pos, v2Pos );
g.setColor( color );
g.setStroke( new BasicStroke( 1.0f ) );
g.drawLine((int) v1Pos[0],(int) v1Pos[1],(int) v2Pos[0],(int) v2Pos[1] );
}
}
}
private Request parseRequest(int fromVmId, Queue<String> lineitems) {
if(lineitems.size() <= 0)
{
System.err.println("No REQUEST! ERROR");
return null;
}
long cloudletLen = Long.parseLong(lineitems.poll());
cloudletLen*=Configuration.CPU_SIZE_MULTIPLY;
Request req = new Request(userId);
Cloudlet cl = generateCloudlet(req.getRequestId(), fromVmId, (int) cloudletLen);
//this.parsedCloudlets.add(cl);
Processing proc = new Processing(cl);
req.addActivity(proc);
if(lineitems.size() != 0) {
// Has more requests after this. Create a transmission and add
String linkName = lineitems.poll();
Integer flowId = this.flowNames.get(linkName);
if(flowId == null) {
throw new IllegalArgumentException("No such link name in virtual.json:"+linkName);
}
String vmName = lineitems.poll();
int toVmId = getVmId(vmName);
long pktSize = Long.parseLong(lineitems.poll());
pktSize*=Configuration.NETWORK_PACKET_SIZE_MULTIPLY;
if(pktSize<0)
pktSize=0;
Request nextReq = parseRequest(toVmId, lineitems);
Transmission trans = new Transmission(fromVmId, toVmId, pktSize, flowId, nextReq);
req.addActivity(trans);
} else {
// this is the last request.
}
return req;
}
/**
* Assign the states to the instances listed in the preference list according to inputs.
* Note that when we choose the top-state (e.g. MASTER) replica for a partition, we prefer to
* choose it from these replicas which are already in the secondary states (e.g, SLAVE) instead
* of in lower-state. This is because a replica in secondary state will take shorter time to
* transition to the top-state, which could minimize the impact to the application's availability.
* To achieve that, we sort the preferenceList based on CurrentState, by treating top-state and
* second-states with same priority and rely on the fact that Collections.sort() is stable.
*/
private void assignStatesToInstances(final List<String> preferenceList,
final StateModelDefinition stateModelDef, final Map<String, String> currentStateMap,
final Set<String> liveInstances, final Set<String> disabledInstancesForPartition,
Map<String, String> bestPossibleStateMap) {
// Record the assigned instances to avoid double calculating or conflict assignment.
Set<String> assignedInstances = new HashSet<>();
Set<String> liveAndEnabled =
liveInstances.stream().filter(instance -> !disabledInstancesForPartition.contains(instance))
.collect(Collectors.toSet());
Queue<String> preferredActiveInstanceQueue = new LinkedList<>(preferenceList);
preferredActiveInstanceQueue.retainAll(liveAndEnabled);
int totalCandidateCount = preferredActiveInstanceQueue.size();
// Sort the preferred instances based on replicas' state priority in the current state.
// Note that if one instance exists in the current states but not in the preference list, then
// it won't show in the prioritized list.
List<String> currentStatePrioritizedList = new ArrayList<>(preferredActiveInstanceQueue);
currentStatePrioritizedList.sort(new StatePriorityComparator(currentStateMap, stateModelDef));
Iterator<String> currentStatePrioritizedInstanceIter = currentStatePrioritizedList.iterator();
// Assign the states to the instances that appear in the preference list.
for (String state : stateModelDef.getStatesPriorityList()) {
int stateCount =
getStateCount(state, stateModelDef, liveAndEnabled.size(), preferenceList.size());
while (!preferredActiveInstanceQueue.isEmpty()) {
if (stateCount <= 0) {
break; // continue assigning for the next state
}
String peekInstance = preferredActiveInstanceQueue.peek();
if (assignedInstances.contains(peekInstance)) {
preferredActiveInstanceQueue.poll();
continue; // continue checking for the next available instance
}
String proposedInstance = adjustInstanceIfNecessary(state, peekInstance,
currentStateMap.getOrDefault(peekInstance, stateModelDef.getInitialState()),
stateModelDef, assignedInstances, totalCandidateCount - assignedInstances.size(),
stateCount, currentStatePrioritizedInstanceIter);
if (proposedInstance.equals(peekInstance)) {
// If the peeked instance is the final decision, then poll it from the queue.
preferredActiveInstanceQueue.poll();
}
// else, if we found a different instance for the partition placement, then we need to
// check the same instance again or it will not be assigned with any partitions.
// Assign the desired state to the proposed instance if not on ERROR state.
if (HelixDefinedState.ERROR.toString().equals(currentStateMap.get(proposedInstance))) {
bestPossibleStateMap.put(proposedInstance, HelixDefinedState.ERROR.toString());
} else {
bestPossibleStateMap.put(proposedInstance, state);
stateCount--;
}
// Note that in either case, the proposed instance is considered to be assigned with a state
// by now.
if (!assignedInstances.add(proposedInstance)) {
throw new AssertionError(String
.format("The proposed instance %s has been already assigned before.",
proposedInstance));
}
}
}
}