下面列出了java.util.LinkedList#offer ( ) 实例代码,或者点击链接到github查看源代码,也可以在右侧发表评论。
private void build(Collection<NBuildSourceInfo> buildSourceInfos, SegmentInfo seg, SpanningTree st) {
List<NBuildSourceInfo> theFirstLevelBuildInfos = buildLayer(buildSourceInfos, seg, st);
LinkedList<List<NBuildSourceInfo>> queue = new LinkedList<>();
if (!theFirstLevelBuildInfos.isEmpty()) {
queue.offer(theFirstLevelBuildInfos);
}
while (!queue.isEmpty()) {
List<NBuildSourceInfo> buildInfos = queue.poll();
List<NBuildSourceInfo> theNextLayer = buildLayer(buildInfos, seg, st);
if (!theNextLayer.isEmpty()) {
queue.offer(theNextLayer);
}
}
}
@Override
public String toString() {
LinkedList<TreeNode> list = new LinkedList<>();
list.offer(this);
ArrayList<Integer> res = new ArrayList<>();
while (!list.isEmpty()) {
TreeNode node = list.poll();
res.add(node.val);
if (node.left != null) {
list.offer(node.left);
}
if (node.right != null) {
list.offer(node.right);
}
}
return res.toString();
}
/**
* 二叉树的层序遍历 借助于队列来实现 借助队列的先进先出的特性
*
* 首先将根节点入队列 然后遍历队列。
* 首先将根节点打印出来,接着判断左节点是否为空 不为空则加入队列
* @param node
*/
public void levelIterator(BinaryNode node){
LinkedList<BinaryNode> queue = new LinkedList<>() ;
//先将根节点入队
queue.offer(node) ;
BinaryNode current ;
while (!queue.isEmpty()){
current = queue.poll();
System.out.print(current.data+"--->");
if (current.getLeft() != null){
queue.offer(current.getLeft()) ;
}
if (current.getRight() != null){
queue.offer(current.getRight()) ;
}
}
}
public static void visitByLevel(TreeNode root) {
LinkedList<TreeNode> nodeQueue = new LinkedList<>();
if (root != null) nodeQueue.offer(root);
int currLevelNum = 1;
int nextLevelNum = 0;
while (!nodeQueue.isEmpty()) {
TreeNode currNode = nodeQueue.poll();
if (currNode.left != null) {
nodeQueue.offer(currNode.left);
nextLevelNum ++;
}
if (currNode.right != null) {
nodeQueue.offer(currNode.right);
nextLevelNum ++;
}
System.out.print(currNode.val + "\t");
currLevelNum --;
if (currLevelNum == 0) {
System.out.println();
currLevelNum = nextLevelNum;
nextLevelNum = 0;
}
}
}
public int minDepth(TreeNode root) {
if (root == null) return 0;
// if (root.left == null || root.right == null) return 1;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int level = 0;
while (!queue.isEmpty()){
level ++;
int len = queue.size();
for (int i = 0; i < len; i ++){
TreeNode currNode = queue.poll();
if (currNode.left == null && currNode.right == null)
return level;
if (currNode.left != null) queue.offer(currNode.left);
if (currNode.right != null) queue.offer(currNode.right);
}
}
return level;
}
/**
* Searches the given collection of strings and returns a collection of at
* most <code>n</code> strings that have the lowest Levenshtein distance
* to a given string <code>t</code>. The returned collection will be
* sorted according to the distance with the string with the lowest
* distance at the first position.
* @param <T> the type of the strings in the given collection
* @param ss the collection to search
* @param t the string to compare to
* @param n the maximum number of strings to return
* @param threshold a threshold for individual item distances. Only items
* with a distance below this threshold will be included in the result.
* @return the strings with the lowest Levenshtein distance
*/
public static <T extends CharSequence> Collection<T> findMinimum(
Collection<T> ss, CharSequence t, int n, int threshold) {
LinkedList<Item<T>> result = new LinkedList<>();
for (T s : ss) {
int d = LevenshteinDistance.getDefaultInstance().apply(s, t);
if (d < threshold) {
result.offer(new Item<>(s, d));
if (result.size() > n + 10) {
// resort, but not too often
Collections.sort(result);
while (result.size() > n) result.removeLast();
}
}
}
Collections.sort(result);
while (result.size() > n) result.removeLast();
List<T> arr = new ArrayList<>(n);
for (Item<T> i : result) {
arr.add(i.str);
}
return arr;
}
/**
* 二叉树的层序遍历 借助于队列来实现 借助队列的先进先出的特性
*
* 首先将根节点入队列 然后遍历队列。
* 首先将根节点打印出来,接着判断左节点是否为空 不为空则加入队列
* @param node
*/
public void levelIterator(BinaryNode node){
LinkedList<BinaryNode> queue = new LinkedList<>() ;
//先将根节点入队
queue.offer(node) ;
BinaryNode current ;
while (!queue.isEmpty()){
current = queue.poll();
System.out.print(current.data+"--->");
if (current.getLeft() != null){
queue.offer(current.getLeft()) ;
}
if (current.getRight() != null){
queue.offer(current.getRight()) ;
}
}
}
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
LinkedList<TreeNode> queue = new LinkedList<>();
if (root == null) return result;
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new LinkedList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node != null) {
list.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
}
result.add(list);
}
return result;
}
/**
* @description Build a sequence binary tree through an array
* @param nums
*/
TreeNode(int[] nums) {
this.val = nums[0];
LinkedList<TreeNode> list = new LinkedList<>();
list.offer(this);
for (int i = 1; i < nums.length - 1; i += 2) {
TreeNode node = list.poll();
node.left = new TreeNode(nums[i]);
node.right = new TreeNode(nums[i+1]);
list.offer(node.left);
list.offer(node.right);
}
}
@Test
public void test(){
BinTreeNode62 node1 = new BinTreeNode62(1);
BinTreeNode62 node2 = new BinTreeNode62(2);
BinTreeNode62 node3 = new BinTreeNode62(3);
BinTreeNode62 node4 = new BinTreeNode62(4);
BinTreeNode62 node5 = new BinTreeNode62(5);
BinTreeNode62 node6 = new BinTreeNode62(6);
node1.setChildren(node2, node3);
node2.setChildren(node4, null);
node3.setChildren(node5, node6);
String sequence = serializeToString(node1);
System.out.println(sequence); // 1,2,4,#,#,#,3,5,#,#,6,#,#
BinTreeNode62 root = deserializeToBinTree(sequence);
System.out.println("-------------------");
System.out.println(root.value);
System.out.println(root.left.value);
System.out.println(root.left.left.value);
System.out.println(root.right.value);
System.out.println(root.right.left.value);
System.out.println(root.right.right.value);
LinkedList<BinTreeNode62> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
BinTreeNode62 node = queue.poll();
System.out.print(node.value + "\t");
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int currLevelNum = 1;
int nextLevelNum = 0;
LinkedList<Integer> currLineResult = new LinkedList<>();
while (!queue.isEmpty()) {
TreeNode head = queue.poll();
if (head.left != null) {
queue.offer(head.left);
nextLevelNum ++;
}
if (head.right != null) {
queue.offer(head.right);
nextLevelNum ++;
}
currLineResult.add(head.val);
currLevelNum --;
if (currLevelNum == 0) {
result.add(currLineResult);
currLineResult = new LinkedList<>();
currLevelNum = nextLevelNum;
nextLevelNum = 0;
}
}
return result;
}
private void _iteratorProto(File dir, LinkedList<File> ls){
File[] arr = dir.listFiles();
int len = arr.length;
for(int i=0; i<len; ++i){
File f = arr[i];
if(f.isFile()){
if(_isProtoFile(f)){
ls.offer(f);
}
}else{
_iteratorProto(f, ls);
}
}
}
public static void main(String[] args) throws IOException {
LinkedList<String> list = new LinkedList<String>();
list.offer("123");
list.offer("234");
String peek = list.peek();
String peek2 = list.peek();
logger.info("peak:"+peek+" "+peek2);
}
private <T extends ILocatable> void removePositionTo(ShortPoint2D pos, LinkedList<T> fromList, LinkedList<T> toList, boolean newHasSamePlayer) {
Iterator<T> iter = fromList.iterator();
while (iter.hasNext()) {
T curr = iter.next();
if (curr.getPosition().equals(pos)) {
iter.remove();
if (newHasSamePlayer) {
toList.offer(curr);
}
}
}
}
/**
* Generates and prints out random test data for the gridGraph in question. <br>
* Note: the algorithm used is the one specified in the algoFunction.
* Use setDefaultAlgoFunction to choose the algorithm.
* @param gridGraph the grid to test.
*/
private static void generateRandomTestDataAndPrint(GridGraph gridGraph) {
AlgoFunction algo = AnyAnglePathfinding.setDefaultAlgoFunction();
ArrayList<Point> points = ReachableNodes.computeReachable(gridGraph, 5, 5);
LinkedList<Integer> startX = new LinkedList<>();
LinkedList<Integer> startY = new LinkedList<>();
LinkedList<Integer> endX = new LinkedList<>();
LinkedList<Integer> endY = new LinkedList<>();
LinkedList<Double> length = new LinkedList<>();
int size = points.size();
System.out.println("Points: " + size);
for (int i=0; i<100; i++) {
Random random = new Random();
int first = random.nextInt(size);
int last = random.nextInt(size-1);
if (last == first) last = size-1; // prevent first and last from being the same
Point s = points.get(first);
Point f = points.get(last);
int[][] path = Utility.generatePath(algo, gridGraph, s.x, s.y, f.x, f.y);
if (path.length >= 2) {
double len = Utility.computePathLength(gridGraph, path);
startX.offer(s.x);
startY.offer(s.y);
endX.offer(f.x);
endY.offer(f.y);
length.offer(len);
}
if (i%10 == 0) System.out.println("Computed: " + i);
}
System.out.println(startX);
System.out.println(startY);
System.out.println(endX);
System.out.println(endY);
System.out.println(length);
}
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return Collections.singletonList(0);
if (n == 2) return Arrays.asList(0, 1);
// build graph
List<Set<Integer>> adj = new ArrayList<>(n);
for (int i = 0; i < n; i++) adj.add(new HashSet<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
// find leaves
LinkedList<Integer> leaves = new LinkedList<>(); // better memory usage
for (int i = 0; i < n; i++) {
if (adj.get(i).size() == 1) leaves.offer(i);
}
while (n > 2) {
int numLeaf = leaves.size();
n -= numLeaf;
for (int i = 0; i < numLeaf; i++) {
// update graph
int curNode = leaves.poll();
int j = adj.get(curNode).iterator().next();
adj.get(j).remove(curNode);
if (adj.get(j).size() == 1) leaves.offer(j); // new leaves
}
}
return leaves;
}
/**
* This method will find all reachable states that will be used by the {@link #runVI()} method and will cache all the transition dynamics.
* This method will not do anything if all reachable states from the input state have been discovered from previous calls to this method.
* @param si the source state from which all reachable states will be found
* @return true if a reachability analysis had never been performed from this state; false otherwise.
*/
public boolean performReachabilityFrom(State si){
HashableState sih = this.stateHash(si);
//if this is not a new state and we are not required to perform a new reachability analysis, then this method does not need to do anything.
if(valueFunction.containsKey(sih) && this.foundReachableStates){
return false; //no need for additional reachability testing
}
DPrint.cl(this.debugCode, "Starting reachability analysis");
//add to the open list
LinkedList <HashableState> openList = new LinkedList<HashableState>();
Set <HashableState> openedSet = new HashSet<HashableState>();
openList.offer(sih);
openedSet.add(sih);
while(!openList.isEmpty()){
HashableState sh = openList.poll();
//skip this if it's already been expanded
if(valueFunction.containsKey(sh)){
continue;
}
//do not need to expand from terminal states if set to prune
if(this.model.terminal(sh.s()) && stopReachabilityFromTerminalStates){
continue;
}
this.valueFunction.put(sh, this.valueInitializer.value(sh.s()));
List<Action> actions = this.applicableActions(sh.s());
for(Action a : actions){
List<TransitionProb> tps = ((FullModel)model).transitions(sh.s(), a);
for(TransitionProb tp : tps){
HashableState tsh = this.stateHash(tp.eo.op);
if(!openedSet.contains(tsh) && !valueFunction.containsKey(tsh)){
openedSet.add(tsh);
openList.offer(tsh);
}
}
}
}
DPrint.cl(this.debugCode, "Finished reachability analysis; # states: " + valueFunction.size());
this.foundReachableStates = true;
this.hasRunVI = false;
return true;
}
/**
* This method will find all reachable states that will be used when computing the value function.
* This method will not do anything if all reachable states from the input state have been discovered from previous calls to this method.
* @param si the source state from which all reachable states will be found
* @return true if a reachability analysis had never been performed from this state; false otherwise.
*/
public boolean performReachabilityFrom(State si){
HashableState sih = this.stateHash(si);
//if this is not a new state and we are not required to perform a new reachability analysis, then this method does not need to do anything.
if(valueFunction.containsKey(sih)){
return false; //no need for additional reachability testing
}
DPrint.cl(this.debugCode, "Starting reachability analysis");
//add to the open list
LinkedList<HashableState> openList = new LinkedList<HashableState>();
Set<HashableState> openedSet = new HashSet<HashableState>();
openList.offer(sih);
openedSet.add(sih);
while(!openList.isEmpty()){
HashableState sh = openList.poll();
//skip this if it's already been expanded
if(valueFunction.containsKey(sh)){
continue;
}
//do not need to expand from terminal states
if(model.terminal(sh.s())){
continue;
}
valueFunction.put(sh, this.valueInitializer.value(sh.s()));
List<Action> actions = this.applicableActions(sh.s());
for(Action a : actions){
List<TransitionProb> tps = ((FullModel)model).transitions(sh.s(), a);
for(TransitionProb tp : tps){
HashableState tsh = this.stateHash(tp.eo.op);
if(!openedSet.contains(tsh) && !valueFunction.containsKey(tsh)){
openedSet.add(tsh);
openList.offer(tsh);
}
}
}
}
DPrint.cl(this.debugCode, "Finished reachability analysis; # states: " + valueFunction.size());
return true;
}
/**
* This method will find all reachable states that will be used when computing the value function.
* This method will not do anything if all reachable states from the input state have been discovered from previous calls to this method.
* @param si the source state from which all reachable states will be found
* @return true if a reachability analysis had never been performed from this state; false otherwise.
*/
public boolean performReachabilityFrom(State si){
HashableState sih = this.stateHash(si);
//if this is not a new state and we are not required to perform a new reachability analysis, then this method does not need to do anything.
if(valueFunction.containsKey(sih) && this.foundReachableStates){
return false; //no need for additional reachability testing
}
DPrint.cl(this.debugCode, "Starting reachability analysis");
//add to the open list
LinkedList <HashableState> openList = new LinkedList<HashableState>();
Set <HashableState> openedSet = new HashSet<HashableState>();
openList.offer(sih);
openedSet.add(sih);
while(!openList.isEmpty()){
HashableState sh = openList.poll();
//skip this if it's already been expanded
if(valueFunction.containsKey(sh)){
continue;
}
//do not need to expand from terminal states
if(model.terminal(sh.s())){
continue;
}
valueFunction.put(sh, valueInitializer.value(sh.s()));
List<Action> actions = this.applicableActions(sh.s());
for(Action a : actions){
List<TransitionProb> tps = ((FullModel)model).transitions(sh.s(), a);
for(TransitionProb tp : tps){
HashableState tsh = this.stateHash(tp.eo.op);
if(!openedSet.contains(tsh) && !valueFunction.containsKey(tsh)){
openedSet.add(tsh);
openList.offer(tsh);
}
}
}
}
DPrint.cl(this.debugCode, "Finished reachability analysis; # states: " + valueFunction.size());
this.foundReachableStates = true;
return true;
}
/**
*
* @param baseDescriptor
* @param intrinsicEntity defines the Entity Object that contains embedded
* Object where Entity object will be intrinsicEntity and Embeddable object
* will be descriptorManagedClass
* @param intrinsicAttribute
*/
protected void postInitTableSchema(ClassDescriptor baseDescriptor, LinkedList<Entity> intrinsicEntity, LinkedList<Attribute> intrinsicAttribute) {
DBRelationalDescriptor descriptor = (DBRelationalDescriptor) baseDescriptor;
ManagedClass descriptorManagedClass = null;
if (intrinsicEntity == null) {
if (descriptor.getAccessor() instanceof EntitySpecAccessor) {
intrinsicEntity = new LinkedList<>();
intrinsicAttribute = new LinkedList<>();
intrinsicEntity.offer(((EntitySpecAccessor) descriptor.getAccessor()).getEntity());
descriptorManagedClass = intrinsicEntity.peek();
} else {
throw new IllegalStateException(descriptor.getAccessor() + " not supported");
}
} else if (descriptor.getAccessor() instanceof EmbeddableSpecAccessor) {
descriptorManagedClass = ((EmbeddableSpecAccessor) descriptor.getAccessor()).getEmbeddable();
} else if (descriptor.getAccessor() instanceof DefaultClassSpecAccessor) {
// descriptorManagedClass = ((DefaultClassSpecAccessor) descriptor.getAccessor()).getDefaultClass();
} else {
throw new IllegalStateException(descriptor.getAccessor() + " not supported");
}
for (DatabaseMapping mapping : descriptor.getMappings()) {
ManagedClass managedClass = descriptorManagedClass;
Attribute managedAttribute = (Attribute) mapping.getProperty(Attribute.class);
Boolean isInherited = (Boolean) mapping.getProperty(Inheritance.class);
isInherited = isInherited == null ? false : isInherited;
if (intrinsicAttribute.peek() == null) {
intrinsicAttribute.offer(managedAttribute);
}
if(managedAttribute instanceof RelationAttribute && !((RelationAttribute)managedAttribute).isOwner()){
//skip non-owner
} else if (descriptor.isChildDescriptor() && descriptor.getInheritancePolicy().getParentDescriptor().getMappingForAttributeName(mapping.getAttributeName()) != null) {
// If we are an inheritance subclass, do nothing. That is, don't
// generate mappings that will be generated by our parent,
// otherwise the fields for that mapping will be generated n
// times for the same table.
} else if (mapping.isManyToManyMapping()) {
buildRelationTableDefinition(managedClass, managedAttribute, intrinsicEntity, intrinsicAttribute, isInherited, (ManyToManyMapping) mapping, ((ManyToManyMapping) mapping).getRelationTableMechanism(), ((ManyToManyMapping) mapping).getListOrderField(), mapping.getContainerPolicy());
} else if (mapping.isDirectCollectionMapping()) {
buildDirectCollectionTableDefinition(managedClass, managedAttribute, intrinsicEntity, intrinsicAttribute, isInherited, (DirectCollectionMapping) mapping, descriptor);
} else if (mapping.isDirectToFieldMapping()) {
Converter converter = ((DirectToFieldMapping) mapping).getConverter();
if (converter != null) {
if (converter instanceof TypeConversionConverter) {
resetFieldTypeForLOB((DirectToFieldMapping) mapping);
}
// uncomment on upgrade to eclipselink v2.7.2+
// if (converter instanceof SerializedObjectConverter) {
// //serialized object mapping field should be BLOB/IMAGE
// getFieldDefFromDBField(mapping.getField()).setType(((SerializedObjectConverter) converter).getSerializer().getType());
// }
}
} else if (mapping.isAggregateCollectionMapping()) {
//need to figure out the target foreign key field and add it into the aggregate target table
// if(managedAttribute instanceof ElementCollection || ((ElementCollection)managedAttribute).getConnectedClass()!=null){
// ClassDescriptor refDescriptor = mapping.getReferenceDescriptor();
// Attribute attribute = getManagedAttribute(refDescriptor, dbField, intrinsicAttribute);//TODO intrinsicAttribute nested path/attribute not set
//
// }
createAggregateTargetTable(managedClass, managedAttribute, intrinsicEntity, intrinsicAttribute, isInherited, (AggregateCollectionMapping) mapping);
} else if (mapping.isForeignReferenceMapping()) {
if (mapping.isOneToOneMapping()) {
RelationTableMechanism relationTableMechanism = ((OneToOneMapping) mapping).getRelationTableMechanism();
if (relationTableMechanism == null) {
addForeignKeyFieldToSourceTargetTable(managedClass, managedAttribute, intrinsicEntity, intrinsicAttribute, isInherited, (OneToOneMapping) mapping);
} else {
buildRelationTableDefinition(managedClass, managedAttribute, intrinsicEntity, intrinsicAttribute, isInherited, (OneToOneMapping) mapping, relationTableMechanism, null, null);
}
} else if (mapping.isOneToManyMapping()) {
addForeignKeyFieldToSourceTargetTable(managedClass, managedAttribute, intrinsicEntity, intrinsicAttribute, isInherited, (OneToManyMapping) mapping);
TableDefinition targTblDef = getTableDefFromDBTable(((OneToManyMapping) mapping).getReferenceDescriptor().getDefaultTable());//TODO pass entity
addFieldsForMappedKeyMapContainerPolicy(managedClass, managedAttribute, intrinsicEntity, intrinsicAttribute, isInherited, mapping.getContainerPolicy(), targTblDef);
}
} else if (mapping.isTransformationMapping()) {
resetTransformedFieldType((TransformationMapping) mapping);
} else if (mapping.isAggregateObjectMapping()) {
postInitTableSchema(((AggregateObjectMapping) mapping).getReferenceDescriptor(), new LinkedList<>(intrinsicEntity), new LinkedList<>(intrinsicAttribute));
}
intrinsicAttribute.clear();
}
processAdditionalTablePkFields(intrinsicEntity, descriptor);
intrinsicEntity.clear();
}