WT*

List ranking

Given is an array S that represents the successors in a linked list: a list 2 -> 3 -> 0 -> 4 -> 5 -> 1 is represented by an array

`i`	0	1	2	3	4	5
`S[i]`	4	2	3	0	5	1

The task is to compute, for each element in the list, its distance from the end of the list, i.e. to produce an array R:

`i`	0	1	2	3	4	5
`R[i]`	3	0	5	4	2	1

A simple technique called pointer jumping works as follows:

input int S[_];
int n = S.size;

output int R[n];

pardo(i : n) {
  R[i] = 1;
  if (S[i] == i) R[i] = 0;
}

for (int t = 0; 2 ^ t < n; t++)
    pardo(i : n) {
        R[i] += R[S[i]];
        S[i] = S[S[i]];
    }

Time is logarithmic, but the work is of the order O(n log n).