Synchronously calculates the hash for all the parent nodes of the
node referenced by {@code leafOrder} up to the root node.

@param leafOrder The order of node
325961
private void updateBranch(int leafOrder) {
        int nodeOrder = MerkleTreeUtil.getParentOrder(leafOrder);

        for (int level = leafLevel; level > 0; level--) {
            int leftChildOrder = MerkleTreeUtil.getLeftChildOrder(nodeOrder);
            int rightChildOrder = MerkleTreeUtil.getRightChildOrder(nodeOrder);

            int leftChildHash = getNodeHash(leftChildOrder);
            int rightChildHash = getNodeHash(rightChildOrder);

            int newNodeHash = MerkleTreeUtil.sumHash(leftChildHash, rightChildHash);
            setNodeHash(nodeOrder, newNodeHash);

            nodeOrder = MerkleTreeUtil.getParentOrder(nodeOrder);
        }
    }
901523
public synchronized TreeEntry<K, V> lastEntry() {
		if (!validState) {
			throw new InvalidStateException();
		}
		final LeafNode<K, V> node = findSideLeafNode(false);
		if (node == null) {
			return null;
		}
		final int slot = node.allocated - 1;
		final K key = node.keys[slot];
		final V value = node.values[slot];
		return ((key == null) ? null : new TreeEntry<K, V>(key, value));
	}
409097
protected void layout(TreeNode node) {
    if (node != null) {
      TreeNode child = node.child;

      while (child != null) {
        layout(child);
        child = child.next;
      }

      if (node.child != null) {
        attachParent(node, join(node));
      } else {
        layoutLeaf(node);
      }
    }
  }
1039719
def _iter_descendants_levelorder(self, is_leaf_fn=None):
        
        tovisit = deque([self])
        while len(tovisit) > 0:
            node = tovisit.popleft()
            yield node
            if not is_leaf_fn or not is_leaf_fn(node):
                tovisit.extend(node.children)
1117047
function treeSorter(node) {
    if(node[options.childsProp]) {
      node[options.childsProp].forEach(function(node) {
        treeSorter(node);
      });
      node[options.childsProp].sort(function childSorter(a, b) {
        var result;
        if('undefined' === typeof a[options.sortProp]) {
          result = (options.sortDesc ? 1 : -1);
        } else if('undefined' === typeof b[options.sortProp]) {
          result = (options.sortDesc ? -1 : 1);
        } else {
          result = a[options.sortProp] > b[options.sortProp] ?
            (options.sortDesc ? -1 : 1) : (options.sortDesc ? 1 : -1);
        }
        return result;
      });
    }
  }
1247455
public static Iterator<Node> iterator(Node parent) {
        return parent != null ? new JsArrayNodeIterator(parent) : emptyIterator();
    }
1042967
Node<K, V> find(K key, boolean create) {
    Comparator<? super K> comparator = this.comparator;
    Node<K, V>[] table = this.table;
    int hash = secondaryHash(key.hashCode());
    int index = hash & (table.length - 1);
    Node<K, V> nearest = table[index];
    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, hash, header, header.prev);
      table[index] = created;
    } else {
      created = new Node<K, V>(nearest, key, hash, 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);
    }

    if (size++ > threshold) {
      doubleCapacity();
    }
    modCount++;

    return created;
  }
619109
def traverse_levelorder(self, leaves=True, internal=True):
        ''''''
        for node in self.root.traverse_levelorder(leaves=leaves, internal=internal):
            yield node
1277720
public void sortChildrenByContent(Comparator<? super T> comparator) {
		Comparator<TreeNode<T>> byContent = Comparator.comparing(TreeNode::getContent, comparator);
		sortChildrenByNode(byContent);
	}
217344
private void initOrderedIterator()
   {
      if (orderedNodes != null)
      {
         return;
      }
      long time = 0;
      if (LOG.isDebugEnabled())
      {
         time = System.currentTimeMillis();
      }
      ScoreNode[][] nodes = (ScoreNode[][])scoreNodes.toArray(new ScoreNode[scoreNodes.size()][]);

      final Set<String> invalidIDs = new HashSet<String>(2);

      /** Cache for Nodes obtainer during the order (comparator work) */
      final Map<String, NodeData> lcache = new HashMap<String, NodeData>();
      do
      {
         if (invalidIDs.size() > 0)
         {
            // previous sort run was not successful -> remove failed uuids
            List<ScoreNode[]> tmp = new ArrayList<ScoreNode[]>();
            for (int i = 0; i < nodes.length; i++)
            {
               if (!invalidIDs.contains(nodes[i][selectorIndex].getNodeId()))
               {
                  tmp.add(nodes[i]);
               }
            }
            nodes = (ScoreNode[][])tmp.toArray(new ScoreNode[tmp.size()][]);
            invalidIDs.clear();
         }

         try
         {
            // sort the uuids
            Arrays.sort(nodes, new ScoreNodeComparator(lcache, invalidIDs));
         }
         catch (SortFailedException e)
         {
            if (LOG.isTraceEnabled())
            {
               LOG.trace("An exception occurred: " + e.getMessage());
            }
         }

      }
      while (invalidIDs.size() > 0);

      if (LOG.isDebugEnabled())
      {
         LOG.debug("" + nodes.length + " node(s) ordered in " + (System.currentTimeMillis() - time) + " ms");
      }

      orderedNodes = new ScoreNodeIteratorImpl(nodes);
   }
543340
public Iterator<Compound> toRootOrder(final Compound c) {
        return new Iterator<Compound>() {

            Compound curr;
            TreeNode n = node(c);
            Compound parent = c;

            public boolean hasNext() {
                return !n.isRoot();
            }

            public Compound next() {
                if (hasNext()) {
                    curr = parent;
                    parent = n.parent;
                    n = node(n.parent);
                    return curr;
                } else {
                    throw new NoSuchElementException();
                }
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
661179
public static SiblingCounter create( final CachedNode node,
                                         final NodeCache cache ) {
        assert node != null;
        assert cache != null;
        return new SiblingCounter() {
            @Override
            public int countSiblingsNamed( Name childName ) {
                return node.getChildReferences(cache).getChildCount(childName);
            }
        };
    }
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;
    }
321045
public Object preOrder(NodeVisitor nodeVisitor, Node root) {
        return preOrder(nodeVisitor, Collections.singleton(root));
    }
502813
@Override
    protected Node<K, V> unionWithComparator(Node<K, V> root1, Node<K, V> root2) {
        if (root1 == null) {
            return root2;
        } else if (root2 == null) {
            return root1;
        }

        Node<K, V> newRoot;
        Deque<LeftistNode<K, V>> path = new LinkedList<LeftistNode<K, V>>();

        // find initial
        int c = comparator.compare(root1.key, root2.key);
        if (c <= 0) {
            newRoot = root1;
            root1 = unlinkRightChild(root1);
        } else {
            newRoot = root2;
            root2 = unlinkRightChild(root2);
        }
        Node<K, V> cur = newRoot;
        path.push((LeftistNode<K, V>) cur);

        // merge
        while (root1 != null && root2 != null) {
            c = comparator.compare(root1.key, root2.key);
            if (c <= 0) {
                // link as right child of cur
                if (cur.o_c == null) {
                    cur.o_c = root1;
                } else {
                    cur.o_c.y_s = root1;
                }
                root1.y_s = cur;
                cur = root1;
                path.push((LeftistNode<K, V>) cur);
                root1 = unlinkRightChild(root1);
            } else {
                // link as right child of cur
                if (cur.o_c == null) {
                    cur.o_c = root2;
                } else {
                    cur.o_c.y_s = root2;
                }
                root2.y_s = cur;
                cur = root2;
                path.push((LeftistNode<K, V>) cur);
                root2 = unlinkRightChild(root2);
            }
        }

        if (root1 != null) {
            // link as right child of cur
            if (cur.o_c == null) {
                cur.o_c = root1;
            } else {
                cur.o_c.y_s = root1;
            }
            root1.y_s = cur;
        }

        if (root2 != null) {
            // link as right child of cur
            if (cur.o_c == null) {
                cur.o_c = root2;
            } else {
                cur.o_c.y_s = root2;
            }
            root2.y_s = cur;
        }

        /*
         * Traverse path upwards, update null path length and swap if needed.
         */
        while (!path.isEmpty()) {
            LeftistNode<K, V> n = path.pop();

            if (n.o_c != null) {
                // at least on child
                LeftistNode<K, V> nLeft = (LeftistNode<K, V>) n.o_c;
                int nplLeft = nLeft.npl;
                int nplRight = -1;
                if (nLeft.y_s != n) {
                    // two children
                    LeftistNode<K, V> nRight = (LeftistNode<K, V>) nLeft.y_s;
                    nplRight = nRight.npl;
                }
                n.npl = 1 + Math.min(nplLeft, nplRight);

                if (nplLeft < nplRight) {
                    // swap
                    swapChildren(n);
                }

            } else {
                // no children
                n.npl = 0;
            }

        }

        return newRoot;
    }
369327
private void addElementsToSortOrderMap(final Element element, int baseSortOrder) {
        elementSortOrderMap.addElement(element, baseSortOrder);
        final List<Element> castToChildElementList = castToChildElementList(element);
        // Increments the sort order index for each element
        int sortOrder = baseSortOrder;
        for (Element child : castToChildElementList) {
            sortOrder += SORT_ORDER_INCREMENT;
            addElementsToSortOrderMap(child, sortOrder);
        }
    }
719707
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }