/*
Cascading cut until a root or an unmarked node is found.
172137
private void cascadingCut(Node<K, V> y) {
        Node<K, V> z;
        while ((z = y.parent) != null) {
            if (!y.mark) {
                y.mark = true;
                break;
            }
            cut(y, z);
            y = z;
        }
    }
1301145
function findNode(firstNode, predicate) {
    let curNode = firstNode;
    while (curNode != null) {
        if (predicate(curNode.value))
            return curNode;
        curNode = curNode.next;
    }
}
985389
private Node<K, V> cutChildren(Node<K, V> n) {
        Node<K, V> child = n.o_c;
        n.o_c = null;
        if (child != null) {
            child.o_s = null;
        }
        return child;
    }
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;
    }
317875
function(tree, alsoRemovecoplanarFront) {
            alsoRemovecoplanarFront = alsoRemovecoplanarFront ? true : false;
            this.rootnode.clipTo(tree, alsoRemovecoplanarFront);
        }
818013
function nodeBeforeLocation(location) {
        var node;
        exports.root.each(function each(n) {
            if (!n.location || location < n.location) {
                return true;
            }
            if (!node || node.location < n.location) {
                node = n;
            }
        });
        return node;
    }
1197853
private final BinTreeNode<K,V> extract_next(BinTreeNode<K,V> node) {
	BinTreeNode<K,V> prev = node.right;
	BinTreeNode<K,V> curr = prev.left;

	if(curr == null) {
	    node.right = node.right.right;
	    return prev;
	}

	while(curr.left != null) {
	    prev = curr;
	    curr = curr.left;
	}

	prev.left = curr.right;
	return curr;
    }
777523
function traverseRecursive(rootNode, options) {
  options = extend({
    subnodesAccessor: function(node) { return node.subnodes; },
    onNode: function(node, callback, userdata) {},
    onComplete: function(rootNode) {},
    userdata: null
  }, options);

  (function visitNode(node, callback) {
    var subnodes = options.subnodesAccessor(node);
    async.eachSeries(subnodes, function(subnode, next) {
      visitNode(subnode, function() {
        async.setImmediate(next);
      });
    },
    function() {
      options.onNode(node, function() {
        async.setImmediate(callback);
      }, options.userdata);
    });
  })(rootNode, function() {
    options.onComplete(rootNode);
  });
}
254208
function traverseDepthFirst(rootNode, options) {
  options = extend({
    subnodesAccessor: function(node) { return node.subnodes; },
    userdataAccessor: function(node, userdata) { return userdata; },
    onNode: function(node, callback, userdata) { callback(); },
    onComplete: function(rootNode) {},
    userdata: null
  }, options);

  var stack = [];
  stack.push([rootNode, options.userdata]);

  (function next() {
    if (stack.length == 0) {
      options.onComplete(rootNode);
      return;
    }

    var top = stack.pop();
    var node = top[0];
    var data = top[1];

    options.onNode(node, function() {
      var subnodeData = options.userdataAccessor(node, data);
      var subnodes = options.subnodesAccessor(node);
      async.eachSeries(subnodes,
        function(subnode, nextNode) {
          stack.push([subnode, subnodeData]);
          async.setImmediate(nextNode);
        },
        function() {
          async.setImmediate(next);
        }
      );
    }, data);
  })();
}
411757
private final V remove_node(BinTreeNode<K,V> node, BinTreeNode<K,V> prev, int son) {
	if(node.left == null)
	    return remove_semi_leaf(node, prev, son, node.right);
	if(node.right == null)
	    return remove_semi_leaf(node, prev, son, node.left);

	// The BinTreeNode to replace node in the tree. This is either the
	// next or the precedent node (in the order of the hashCode's.
	// We decide a bit randomly, to gain some balanceness.
	BinTreeNode<K,V> m = 
	    (node.keyHashCode % 2 == 0) ?
	    extract_next(node) : extract_prev(node);

	return finish_removal(node, prev, son, m);
    }
1261609
final Node<E> succ(Node<E> p) {
        // TODO: should we skip deleted nodes here?
        if (p == (p = p.next))
            p = first();
        return p;
    }
1232444
private Node getNextSibling(Node node) {

		if (node == null || node == root)
			return null;

		Node newNode = node.getNextSibling();
		if (newNode == null) {
			newNode = node.getParentNode();
			if (newNode == null || node == root)
				return null;
			int parentAccept = acceptNode(newNode);
			if (parentAccept == NodeFilter.FILTER_SKIP) {
				return getNextSibling(newNode);
			}
			return null;
		}

		int accept = acceptNode(newNode);

		if (accept == NodeFilter.FILTER_ACCEPT)
			return newNode;
		else if (accept == NodeFilter.FILTER_SKIP) {
			Node fChild = getFirstChild(newNode);
			if (fChild == null)
				return getNextSibling(newNode);

			return fChild;
		} else
			// if (accept == NodeFilter.REJECT_NODE)
			return getNextSibling(newNode);

	}
550855
private void cutAndMakeRoot(Entry entry) {
        Entry oParent = entry.oParent;
        if (oParent == null) return;  // already a root

        oParent.degree--;
        entry.isMarked = false;

        // update parent's `oFirstChild` pointer
        Entry oFirstChild = oParent.oFirstChild;
        assert oFirstChild != null;

        if (oFirstChild.equals(entry)) {
            if (oParent.degree == 0) {
                oParent.oFirstChild = null;
            }
            else {
                oParent.oFirstChild = entry.next;
            }
        }

        entry.oParent = null;
        unlinkFromNeighbors(entry);

        // add to root list
        mergeLists(entry, oMinEntry);
        if (oParent.oParent != null) {
            if (oParent.isMarked) {
                cutAndMakeRoot(oParent);
            }
            else {
                oParent.isMarked = true;
            }
        }
    }
727790
def mend(self, length):
        """"""
        if length == 0: raise Exception("Can't mend the root !")
        if length == 1: return
        self.children = OrderedDict((node.name, node) for node in self.get_level(length))
        for child in self.children.values(): child.parent = self
231761
Node getNode(Node root) {
        if (isRoot()) {
            return root;
        }

        Node startNode = root;
        Matcher pathMatcher = dotWithPreviousChar.matcher(path);
        int pos = 0;
        while (pathMatcher.find()) {
            String step = path.substring(pos, pathMatcher.end() - 1);
            pos = pathMatcher.end();
            startNode = doStep(step, startNode);
        }
        startNode = doStep(path.substring(pos), startNode);
        return startNode;
    }
1348913
function(tree, alsoRemovecoplanarFront) {
            var node = this, stack = [];
            do {
                if(node.polygontreenodes.length > 0) {
                    tree.rootnode.clipPolygons(node.polygontreenodes, alsoRemovecoplanarFront);
                }
                if(node.front) stack.push(node.front);
                if(node.back) stack.push(node.back);
                node = stack.pop();
            } while(typeof(node) !== 'undefined');
        }
545836
static List<Fragment> greedyTraversal(Arborescence<Node> arborescence,
                                                  Map<NodeId, Node> nodes,
                                                  Map<Node, Map<Node, Fragment>> edgeFragmentChildToParent) {

        List<Fragment> plan = new LinkedList<>();

        Map<Node, Set<Node>> edgesParentToChild = new HashMap<>();
        arborescence.getParents().forEach((child, parent) -> {
            if (!edgesParentToChild.containsKey(parent)) {
                edgesParentToChild.put(parent, new HashSet<>());
            }
            edgesParentToChild.get(parent).add(child);
        });

        Node root = arborescence.getRoot();

        Set<Node> reachableNodes = Sets.newHashSet(root);
        // expanding from the root until all nodes have been visited
        while (!reachableNodes.isEmpty()) {

            Node nodeWithMinCost = reachableNodes.stream().min(Comparator.comparingDouble(node ->
                    branchWeight(node, arborescence, edgesParentToChild, edgeFragmentChildToParent))).orElse(null);

            assert nodeWithMinCost != null : "reachableNodes is never empty, so there is always a minimum";

            // add edge fragment first, then node fragment
            Fragment fragment = getEdgeFragment(nodeWithMinCost, arborescence, edgeFragmentChildToParent);
            if (fragment != null) plan.add(fragment);

            plan.addAll(nodeToPlanFragments(nodeWithMinCost, nodes, true));

            reachableNodes.remove(nodeWithMinCost);
            if (edgesParentToChild.containsKey(nodeWithMinCost)) {
                reachableNodes.addAll(edgesParentToChild.get(nodeWithMinCost));
            }
        }

        return plan;
    }