@Override
    public List<Set<DirectedGraphNode>> 
        partition(Collection<DirectedGraphNode> nodeSet) {
        if (nodeSet.isEmpty()) {
            return Collections.<Set<DirectedGraphNode>>emptyList();
        }
        
        nodeSetBelongsToGraph(nodeSet);
        
        this.nodes = new Node[nodeSet.size()];
        List<Set<DirectedGraphNode>> partition = new ArrayList<>();
        
        int i = 0;
        
        for (final DirectedGraphNode node : nodeSet) {
            this.nodes[i++] = node;
        }
        
        Deque<Range> stack = new LinkedList<>();
        List<Range> resultRanges = new ArrayList<>();
        
        stack.add(new Range(0, nodes.length - 1, X));
        
        while (stack.isEmpty() == false) {
            Range r = stack.removeFirst();
            
            
            if (r.length() > this.maxNodesPerRegion) {
                // "r.to + 1" as the last index is exclusive.
                Arrays.sort(nodes, r.from, r.to + 1, (r.axis == X ? xcmp : ycmp));
                Range[] children = r.split();
                stack.addLast(children[0]);
                stack.addLast(children[1]);
            } else {
                resultRanges.add(r);
            }
        }
        
        for (final Range range : resultRanges) {
            Set<DirectedGraphNode> region = new HashSet<>(range.length());
            
            for (final int index : range) {
                region.add((DirectedGraphNode) nodes[index]);
            }
            
            partition.add(region);
        }
        
        return partition;
    }