Find b-order for a blockSize of this tree

@param node of type Leaf or Integernal
@return integer with b-order
492282
private int findOptimalNodeOrder(final Node<K, V> node) {
		int low = MIN_B_ORDER; // minimal b-order
		int high = (blockSize / node.getStructEstimateSize(1)) << 2; // estimate high b-order

		while (low <= high) {
			int mid = ((low + high) >>> 1);
			mid += (1 - (mid % 2));
			int nodeSize = node.getStructEstimateSize(mid);

			if (log.isDebugEnabled()) {
				log.debug(this.getClass().getName() + "::findOptimalNodeOrder(" + node.getClass().getName()
						+ ") blockSize=" + blockSize + " nodeSize=" + nodeSize + " b_low=" + low
						+ " b_order=" + mid + " b_high=" + high);
			}

			if (nodeSize < blockSize) {
				low = mid + 2;
			} else if (nodeSize > blockSize) {
				high = mid - 2;
			} else {
				return mid;
			}
		}
		return low - 2;
	}
47229
public static int firstStatPos(JCTree tree) {
        if (tree.hasTag(BLOCK) && ((JCBlock) tree).stats.nonEmpty())
            return ((JCBlock) tree).stats.head.pos;
        else
            return tree.pos;
    }
887929
public IntArrayList bfs(int root, boolean isRootT1, boolean[] marked1, boolean[] marked2) {
        IntArrayList ccorder = new IntArrayList();
        Queue<Integer> qNode = new ArrayDeque<>();
        Queue<Boolean> qIsT1 = new ArrayDeque<>();
        qNode.add(root);
        qIsT1.add(isRootT1);

        while (!qNode.isEmpty()) {
            // Process the next node in the queue.
            int parent = qNode.remove();
            boolean isT1 = qIsT1.remove();

            if (isT1) {
                // Visit node only if not marked.
                if (!marked1[parent]) {
                    log.trace("Visiting node {} of type T1", parent);
                    // For each neighbor...
                    for (int nb = 0; nb < this.numNbsT1(parent); nb++) {
                        int e = this.edgeT1(parent, nb);
                        int child = this.childE(e);
                        if (!marked2[child]) {
                            // If the neighbor is not marked, queue the node and add the edge to
                            // the order.
                            qNode.add(child);
                            qIsT1.add(false);
                            ccorder.add(e);
                        }
                    }
                    // Mark the node as visited.
                    marked1[parent] = true;
                }
            } else {
                // Visit node only if not marked.
                if (!marked2[parent]) {
                    log.trace("Visiting node {} of type T2", parent);
                    // For each neighbor...
                    for (int nb = 0; nb < this.numNbsT2(parent); nb++) {
                        int e = this.edgeT2(parent, nb);
                        int child = this.childE(e);
                        if (!marked1[child]) {
                            // If the neighbor is not marked, queue the node and add the edge to
                            // the order.
                            qNode.add(child);
                            qIsT1.add(true);
                            ccorder.add(e);
                        }
                    }
                    // Mark the node as visited.
                    marked2[parent] = true;
                }
            }
        }
        return ccorder;
    }
1129730
Node<K, V> find(K key, boolean create) {
    Comparator<? super K> comparator = this.comparator;
    Node<K, V> nearest = root;
    int comparison = 0;

    if (nearest != null) {
      // Micro-optimization: avoid polymorphic calls to Comparator.compare().
      @SuppressWarnings("unchecked") // Throws a ClassCastException below if there's trouble.
          Comparable<Object> comparableKey = (comparator == NATURAL_ORDER)
          ? (Comparable<Object>) key
          : null;

      while (true) {
        comparison = (comparableKey != null)
            ? comparableKey.compareTo(nearest.key)
            : comparator.compare(key, nearest.key);

        // We found the requested key.
        if (comparison == 0) {
          return nearest;
        }

        // If it exists, the key is in a subtree. Go deeper.
        Node<K, V> child = (comparison < 0) ? nearest.left : nearest.right;
        if (child == null) {
          break;
        }

        nearest = child;
      }
    }

    // The key doesn't exist in this tree.
    if (!create) {
      return null;
    }

    // Create the node and add it to the tree or the table.
    Node<K, V> header = this.header;
    Node<K, V> created;
    if (nearest == null) {
      // Check that the value is comparable if we didn't do any comparisons.
      if (comparator == NATURAL_ORDER && !(key instanceof Comparable)) {
        throw new ClassCastException(key.getClass().getName() + " is not Comparable");
      }
      created = new Node<K, V>(nearest, key, header, header.prev);
      root = created;
    } else {
      created = new Node<K, V>(nearest, key, header, header.prev);
      if (comparison < 0) { // nearest.key is higher
        nearest.left = created;
      } else { // comparison > 0, nearest.key is lower
        nearest.right = created;
      }
      rebalance(nearest, true);
    }
    size++;
    modCount++;

    return created;
  }
152832
public final int next(int node) {
        final int right = right(node);
        if (right != NIL) {
            return first(right);
        } else {
            int parent = parent(node);
            while (parent != NIL && node == right(parent)) {
                node = parent;
                parent = parent(parent);
            }
            return parent;
        }
    }
900206
public int getCornerIndex( SquareNode node ) {
		int index = nodes.indexOf(node);

		int x = index%columns;
		int y = index/columns;

		if( x <= 0 && y <= 0 ) {
			return 0;
		} else if( x > 0 && y <= 0 ) {
			return 1;
		} else if( x > 0 && y > 0 ) {
			return 2;
		} else if( x <= 0 && y > 0 ) {
			return 3;
		} else {
			throw new RuntimeException("Not corner!");
		}
	}
1033574
private boolean checkBlockSize(Block block, INodeFile inode) {
    if (block.getNumBytes() < 0) {
      return false;
    }
    BlockInfo[] blocks = inode.getBlocks();
    if (blocks.length == 0) {
      return false;
    }
    return block.getNumBytes() <= inode.getPreferredBlockSize();
  }
368560
def _get_node_type(self, node):
        
        if node == BLANK_NODE:
            return NODE_TYPE_BLANK

        if len(node) == 2:
            nibbles = unpack_to_nibbles(node[0])
            has_terminator = (nibbles and nibbles[-1] == NIBBLE_TERMINATOR)
            return NODE_TYPE_LEAF if has_terminator\
                else NODE_TYPE_EXTENSION
        if len(node) == 17:
            return NODE_TYPE_BRANCH
865996
public Node<T> getNext(Node<T> node) {
    	if (node.right != null) {
    		node = node.right;
    		while (node.left != null) node = node.left;
    		return node;
    	}
    	// nothing at right, it may be the parent node if the node is at the left
    	if (node == last) return null;
    	return getNext(root, node.value);
    }
1113269
def get_size(node)
      case get_node_type(node)
      when :branch
        sizes = node[0,BRANCH_CARDINAL].map {|n| get_size decode_to_node(n) }
        sizes.push(node.last.false? ? 0 : 1)
        sizes.reduce(0, &:+)
      when :extension
        get_size decode_to_node(node[1])
      when :leaf
        1
      when :blank
        0
      end
    end
1227321
private boolean getGoodNode(
      HashMap<String, HashSet<Node>> candidateNodesByRacks,
      boolean considerLoad,
      long blockSize,
      List<DatanodeDescriptor> results) {
    List<Map.Entry<String, HashSet<Node>>> sorted =
      new ArrayList<Map.Entry<String, HashSet<Node>>>();
    for (Map.Entry<String, HashSet<Node>> entry :
           candidateNodesByRacks.entrySet()) {
      sorted.add(entry);
    }
    Collections.sort(sorted, new RackComparator(blockSize));
    int count = sorted.size() / 4;
    Collections.shuffle(sorted.subList(0, count));
    for (Map.Entry<String, HashSet<Node>> e : sorted) {
      if (getGoodNode(e.getValue(), considerLoad, blockSize, results)) {
        return true;
      }
    }
    return false;
  }
1279468
private int inOrderAnalyse(StructuralNode node) {
        int subtreeNodes = 0;

        if (isStop) {
            return 0;
        }

        if (node == null) {
            return 0;
        }

        // analyse entity if not root and not leaf.
        // Leaf is not analysed because only folder entity is used to determine if path exist.
        try {
            if (!node.isRoot()) {
                if (!node.isLeaf() || node.isLeaf() && node.getParent().isRoot()) {
                    analyse(node);
                    
                } else {
                    //ZAP: it's a Leaf then no children are available
                    return 1;
                }
            }
            
        } catch (Exception e) {
        }

        Iterator<StructuralNode> iter = node.getChildIterator();
        while (iter.hasNext()) {
            subtreeNodes += inOrderAnalyse(iter.next());
        }
        
        return subtreeNodes + 1;
    }
482191
BlocksWithLocations getBlocks(DatanodeID datanode, long size)
    throws IOException {
    readLock();
    try {
      checkSuperuserPrivilege();

      DatanodeDescriptor node = getDatanode(datanode);
      if (node == null) {
        NameNode.stateChangeLog.warn("BLOCK* NameSystem.getBlocks: "
          + "Asking for blocks from an unrecorded node " + datanode.getName());
        throw new IllegalArgumentException(
          "Unexpected exception.  Got getBlocks message for datanode " +
            datanode.getName() + ", but there is no info for it");
      }

      int numBlocks = node.numBlocks();
      if (numBlocks == 0) {
        return new BlocksWithLocations(new BlockWithLocations[0]);
      }
      Iterator<BlockInfo> iter = node.getBlockIterator();
      int startBlock = r.nextInt(numBlocks); // starting from a random block
      // skip blocks
      for (int i = 0; i < startBlock; i++) {
        iter.next();
      }
      List<BlockWithLocations> results = new ArrayList<BlockWithLocations>();
      long totalSize = 0;
      while (totalSize < size && iter.hasNext()) {
        totalSize += addBlock(iter.next(), results);
      }
      if (totalSize < size) {
        iter = node.getBlockIterator(); // start from the beginning
        for (int i = 0; i < startBlock && totalSize < size; i++) {
          totalSize += addBlock(iter.next(), results);
        }
      }

      return new BlocksWithLocations(
        results.toArray(new BlockWithLocations[results.size()]));
    } finally {
      readUnlock();
    }
  }
576544
public int getNodeIndex(final Node node) {
        for (int i = 0; i < nodeList.size(); i++) {
            if (nodeList.get(i).equals(node)) {
                return i;
            }
        }
        return -1;
    }
1177220
@Pure
	public static Rectangle2d getNodeBuildingBounds(AbstractGISTreeSetNode<?, ?> node) {
		assert node != null;
		final double w = node.nodeWidth / 2.;
		final double h = node.nodeHeight / 2.;
		final IcosepQuadTreeZone zone = node.getZone();
		final double lx;
		final double ly;
		if (zone == null) {
			// Is root node
			lx = node.verticalSplit - w;
			ly = node.horizontalSplit - h;
		} else {
			switch (zone) {
			case SOUTH_EAST:
				lx = node.verticalSplit;
				ly = node.horizontalSplit - h;
				break;
			case SOUTH_WEST:
				lx = node.verticalSplit - w;
				ly = node.horizontalSplit - h;
				break;
			case NORTH_EAST:
				lx = node.verticalSplit;
				ly = node.horizontalSplit;
				break;
			case NORTH_WEST:
				lx = node.verticalSplit - w;
				ly = node.horizontalSplit;
				break;
			case ICOSEP:
				return getNodeBuildingBounds(node.getParentNode());
			default:
				throw new IllegalStateException();
			}
		}
		return new Rectangle2d(lx, ly, node.nodeWidth, node.nodeHeight);
	}
1374408
boolean orderNodes( FastQueue<Node> corners , GridInfo info ) {

		// Find a node with just two edges. This is a corner and will be the arbitrary origin in our graph
		Node seed = null;
		for (int i = 0; i < corners.size; i++) {
			Node n = corners.get(i);
			if( n.countEdges() == 2 ) {
				seed = n;
				break;
			}
		}
		if( seed == null ) {
			if( verbose != null ) verbose.println("Can't find a corner with just two edges. Aborting");
			return false;
		}

		// find one edge and mark that as the row direction
		int rowEdge = 0;
		while( seed.edges[rowEdge] == null )
			rowEdge = (rowEdge+1)%4;
		int colEdge = (rowEdge+1)%4;
		while( seed.edges[colEdge] == null )
			colEdge = (colEdge+2)%4;

		// if it's left handed swap the row and column direction
		if( !isRightHanded(seed,rowEdge,colEdge)) {
			int tmp = rowEdge;
			rowEdge = colEdge;
			colEdge = tmp;
		}

		// add the corns to list in a row major order
		while( seed != null ) {
			int before = info.nodes.size();
			Node n = seed;
			do {
				info.nodes.add(n);
				n = n.edges[colEdge];
			} while( n != null );

			seed = seed.edges[rowEdge];

			if( info.cols == -1 ) {
				info.cols = info.nodes.size();
			} else {
				int columnsInRow = info.nodes.size()-before;
				if( columnsInRow != info.cols ) {
					if( verbose != null ) verbose.println("Number of columns in each row is variable");
					return false;
				}
			}
		}
		info.rows = info.nodes.size()/info.cols;
		return true;
	}
529591
public static int getMaxRicePartitionOrderFromBlocksize(int blocksize) {
        int maxRicePartitionOrder = 0;
        while ((blocksize & 1) == 0) {
            maxRicePartitionOrder++;
            blocksize >>= 1;
        }
        return Math.min(Constants.MAX_RICE_PARTITION_ORDER, maxRicePartitionOrder);
    }