/// Performs in-memory topological sort on a tree where
/// order is determined by every child being greater than their parent,
/// and every sibling being greater than previous siblings.
Performs in-memory topological sort on a tree where
order is determined by every child being greater than their parent,
and every sibling being greater than previous siblings.
Performs in - memory topological sort on a tree where order is determined by every child being greater than their parent and every sibling being greater than previous siblings .
pub fn sort<T, P, C>(nodes: &mut [T], parent: P, children: C)
    where P: Fn(&mut T) -> &mut Option<usize>,
          C: Fn(&mut T) -> &mut [usize]
{
    // This problem can be solved efficiently using Group Theory.
    // This avoids the need for cloning nodes into a new array,
    // while performing the minimum work to get a normalized tree.
    //
    // Create a group generator that is modified by swapping to find a solution.
    // The group generator keeps track of indices, such that child-parent relations
    // do not have to change until later.
    //
    // Use the order in the generator to detect whether a swap has been performed.
    // The condition for swapping `a, b` is `gen[a] > gen[b]`.
    let mut gen: Vec<usize> = (0..nodes.len()).collect();
    loop {
        let mut changed = false;
        for i in 0..nodes.len() {
            let children = children(&mut nodes[i]);
            for j in 0..children.len() {
                let a = children[j];
                // Store child after its parent.
                if gen[i] > gen[a] {
                    gen.swap(i, a);
                    changed = true;
                }
                // Check all pairs of children.
                for k in j + 1..children.len() {
                    let b = children[k];
                    // Store children in sorted order.
                    if gen[a] > gen[b] {
                        gen.swap(a, b);
                        changed = true;
                    }
                }
            }
        }
        if !changed {
            break;
        }
    }
    // Update the tree data with the new indices from the generator.
    // Do this before performing the actual swapping,
    // since the generator maps from old indices to new indices.
    for i in 0..nodes.len() {
        let p = parent(&mut nodes[i]);
        *p = p.map(|p| gen[p]);
        for ch in children(&mut nodes[i]) {
            *ch = gen[*ch]
        }
    }
    // Swap nodes using the group generator as guide.
    // When swapping has been performed, update the generator to keep track of state.
    // This is because multiple swaps sharing elements might require multiple steps.
    //
    // The order which swaps are retraced might be different than the solving phase:
    //
    // `a, b, c` => `a, (c, b)` => `(c, a), b` => `c, a, b` (solving phase)
    // `c, a, b` => `(b), a, (c)` => `(a, b), c` => `a, b, c` (retrace phase)
    //
    // However, since the generator solution is produced by swapping operations,
    // it is guaranteed to be restorable to the identity generator when retracing.
    // In fact, it works for any permutation of the identity generator.
    //
    // There is no need to loop more than once because each index is stored uniquely by lookup,
    // such that if `g[i] = i` then there exists no `j != i` such that `g[j] = i`.
    //
    // Retrace by putting nodes where they belong (`g[i]`).
    // Once a node is put where it belongs, no need further work is needed for `g[i]`.
    // It means that the problem has been reduced from size `n` to `n-1`.
    //
    // However, in order to put one node from `i` to where it belongs `g[i]`,
    // one must also keep track of the node who occupied the previous `j = g[i]`.
    // Not only keep track of the node data, but where it belongs `g[j]` too.
    //
    // Fortunately, the old position (`i`) is free as a temporary location.
    // This is why `i` and `g[i]` are swapped.
    // The same swap is done in the group generator to track where the new node belongs:
    // `gen[j] => gen[i]`
    //
    // This procedure is repeated for the new node `i`,
    // putting it where it belongs `g[i]`, and in return receive a new task `gen[j] => gen[i]`.
    // The task is repeated until `i` belongs to where it should be,
    // then it goes to the next step, where the same procedure is repeated.
    // All nodes which have previously been put where they belong does not need any work,
    // and there is no need to go back, since no node will be swapped with an earlier location.
    for i in 0..nodes.len() {
        while gen[i] != i {
            let j = gen[i];
            nodes.swap(i, j);
            gen.swap(i, j);
        }
    }
}
pub fn sort < T , P , C > ( nodes : & mut [ T ] , parent : P , children : C ) where P : Fn ( & mut T ) -> & mut Option < usize > , C : Fn ( & mut T ) -> & mut [ usize ] { // This problem can be solved efficiently using Group Theory. // This avoids the need for cloning nodes into a new array, // while performing the minimum work to get a normalized tree. // // Create a group generator that is modified by swapping to find a solution. // The group generator keeps track of indices, such that child-parent relations // do not have to change until later. // // Use the order in the generator to detect whether a swap has been performed. // The condition for swapping `a, b` is `gen[a] > gen[b]`. let mut gen : Vec < usize > = ( 0 .. nodes . len ( ) ) . collect ( ) ; loop { let mut changed = false ; for i in 0 .. nodes . len ( ) { let children = children ( & mut nodes [ i ] ) ; for j in 0 .. children . len ( ) { let a = children [ j ] ; // Store child after its parent. if gen [ i ] > gen [ a ] { gen . swap ( i , a ) ; changed = true ; } // Check all pairs of children. for k in j + 1 .. children . len ( ) { let b = children [ k ] ; // Store children in sorted order. if gen [ a ] > gen [ b ] { gen . swap ( a , b ) ; changed = true ; } } } } if ! changed { break ; } } // Update the tree data with the new indices from the generator. // Do this before performing the actual swapping, // since the generator maps from old indices to new indices. for i in 0 .. nodes . len ( ) { let p = parent ( & mut nodes [ i ] ) ; * p = p . map ( | p | gen [ p ] ) ; for ch in children ( & mut nodes [ i ] ) { * ch = gen [ * ch ] } } // Swap nodes using the group generator as guide. // When swapping has been performed, update the generator to keep track of state. // This is because multiple swaps sharing elements might require multiple steps. // // The order which swaps are retraced might be different than the solving phase: // // `a, b, c` => `a, (c, b)` => `(c, a), b` => `c, a, b` (solving phase) // `c, a, b` => `(b), a, (c)` => `(a, b), c` => `a, b, c` (retrace phase) // // However, since the generator solution is produced by swapping operations, // it is guaranteed to be restorable to the identity generator when retracing. // In fact, it works for any permutation of the identity generator. // // There is no need to loop more than once because each index is stored uniquely by lookup, // such that if `g[i] = i` then there exists no `j != i` such that `g[j] = i`. // // Retrace by putting nodes where they belong (`g[i]`). // Once a node is put where it belongs, no need further work is needed for `g[i]`. // It means that the problem has been reduced from size `n` to `n-1`. // // However, in order to put one node from `i` to where it belongs `g[i]`, // one must also keep track of the node who occupied the previous `j = g[i]`. // Not only keep track of the node data, but where it belongs `g[j]` too. // // Fortunately, the old position (`i`) is free as a temporary location. // This is why `i` and `g[i]` are swapped. // The same swap is done in the group generator to track where the new node belongs: // `gen[j] => gen[i]` // // This procedure is repeated for the new node `i`, // putting it where it belongs `g[i]`, and in return receive a new task `gen[j] => gen[i]`. // The task is repeated until `i` belongs to where it should be, // then it goes to the next step, where the same procedure is repeated. // All nodes which have previously been put where they belong does not need any work, // and there is no need to go back, since no node will be swapped with an earlier location. for i in 0 .. nodes . len ( ) { while gen [ i ] != i { let j = gen [ i ] ; nodes . swap ( i , j ) ; gen . swap ( i , j ) ; } } }
Performs in-memory topological sort on a tree where
order is determined by every child being greater than their parent,
and every sibling being greater than previous siblings.
Performs in - memory topological sort on a tree where order is determined by every child being greater than their parent and every sibling being greater than previous siblings .
nodes
&mut [T]
parent
P
children
C