Java 类it.unimi.dsi.fastutil.ints.IntArrays 实例源码

private HdfsBVGraphNodeIterator(  final int from, final int upperBound, final InputBitStream ibs, final int[][] window, final int[] outd ) throws IOException {
    if ( from < 0 || from > n ) throw new IllegalArgumentException( "Node index out of range: " + from );
    this.from = from;
    this.ibs = ibs == null ? new InputBitStream(openFile(basename + GRAPH_EXTENSION), 0 ) : ibs;
    if ( window != null ) {
        for ( int i = 0; i < window.length; i++ ) System.arraycopy( window[ i ], 0, this.window[ i ] = IntArrays.grow( this.window[ i ], outd[ i ], 0 ), 0, outd[ i ] );
        System.arraycopy( outd, 0, this.outd, 0, outd.length );
    } else if ( from != 0 ) {
        int pos;
        for( int i = 1; i < Math.min( from + 1, cyclicBufferSize ); i++ ) {
            pos = ( from - i + cyclicBufferSize ) % cyclicBufferSize;
            this.outd[ pos ] = HdfsBVGraph.this.outdegreeInternal( from - i );
            System.arraycopy( successorArray( from - i ), 0, this.window[ pos ] = IntArrays.grow( this.window[ pos ], this.outd[ pos ], 0 ), 0, this.outd[ pos ] );
        }
        this.ibs.position( offsets.getLong( from ) ); // We must fix the bit stream position so that we are *before* the outdegree.
    }
    curr = from - 1;
    this.upperBound = upperBound;
}

@Test
public void testBlocking() throws InterruptedException {
    for(final int size: new int[] { 10, 100, 128, 256 }) {
        for(final int d: new int[] { 1, 2, 3, 4 }) {
            final ReorderingBlockingQueue<Integer> q = new ReorderingBlockingQueue<>(size / d);
            final int[] perm = Util.identity(size);
            IntArrays.shuffle(perm, new XoRoShiRo128PlusRandom());
            for(int i = perm.length; i-- != 0;) {
                final int t = perm[i];
                new Thread() {
                    @Override
                    public void run() {
                        try {
                            q.put(Integer.valueOf(t), t);
                        }
                        catch (final InterruptedException e) {
                            throw new RuntimeException(e.getMessage(), e);
                        }
                    }
                }.start();
            }
            for(int i = 0; i < perm.length; i++) assertEquals(i, q.take().intValue());
            assertEquals(0, q.size());
        }
    }
}

private List<ME> prep_uncovered_zeros(int[] col_indexes, int[] row_indexes) {
    for(int i = 0; i < col_indexes.length; i++) {
        col_indexes[i] = i;
    }
    for(int i = 0; i < row_indexes.length; i++) {
        row_indexes[i] = i;
    }
    IntArrays.quickSort(row_indexes, new Compare(row_mod, 1));
    IntArrays.quickSort(col_indexes, new Compare(col_mod, -1));
    List<ME> zeros = new ArrayList<>();
    for(ME me : matrix.all()) {
        if(cost(me) == 0) {
            zeros.add(me);
        }
    }
    return zeros;
}

public void learnNPassShuffled(int n) throws ReflectiveOperationException, IOException {
    pl.info = classifier.shortStats();
    pl.expectedUpdates = graph.numArcs() * 2 * n;
    pl.start();

    for (int pass = 0; pass < n; pass++) {
        LOGGER.info("Starting learning pass #"+(pass+1)+"...");
        int[] nodes = MathArrays.natural(numNodes);
        nodes = IntArrays.shuffle(nodes, rnd);

        for (int node : nodes)
            learnNode(node, new IntOpenHashSet(
                    graph.successorArray(node), 0, graph.outdegree(node)
                    ));

        save(pass+1);

    }

    pl.done();
}

public int[] createTestingSet(int numOfSamples) {
    numOfSamples = Math.min(numOfSamples, numNodes);

    if (verbose) LOGGER.info("Creating test set with "+numOfSamples+" nodes...");
    if (numOfSamples >= (numNodes/2)) {
        final Random rnd = RandomSingleton.get();
        int[] samples = MathArrays.natural(numNodes);
        IntArrays.shuffle(samples, rnd);
        return IntArrays.trim(samples, numOfSamples);
    } else {
        IntSet set = new IntOpenHashSet();
        while (set.size() < numOfSamples) {
            set.add(rnd.nextInt(numNodes));
        }
        int[] r = set.toIntArray();
        return r;
    }
}

/**
 * Indirect sort descendingly.
 *
 * @param cnt Count array
 * @return Permutation, largest first
 */
private static int[] indirectSort(long[] cnt) {
  int[] tmp = new int[cnt.length];
  for(int i = 0; i < tmp.length; i++) {
    tmp[i] = i;
  }
  // Indirect sort, descending (no need to sort 0):
  IntArrays.quickSort(tmp, 1, tmp.length, new AbstractIntComparator() {
    private static final long serialVersionUID = 1L;

    @Override
    public int compare(int k1, int k2) {
      return Long.compare(cnt[k2], cnt[k1]);
    }
  });
  return tmp;
}

private void fillCache( int x ) {
    if ( x == cachedNode ) return; 
    MergedIntIterator merge = new MergedIntIterator( x < n0? g0.successors( x ) : LazyIntIterators.EMPTY_ITERATOR, x < n1? g1.successors( x ) : LazyIntIterators.EMPTY_ITERATOR );
    outdegree = 0;
    cache = new int[ INITIAL_ARRAY_SIZE ];
    outdegree += LazyIntIterators.unwrap( merge, cache );
    int upto, t;
    while ( ( t = merge.nextInt() ) != -1 ) {
        upto = cache.length;
        cache = IntArrays.grow( cache, upto + 1 );
        cache[ upto++] = t;
        outdegree++;
        outdegree += LazyIntIterators.unwrap( merge, cache, upto, cache.length - upto );
    }
    cachedNode = x;
}

public BVGraphNodeIterator( final InputBitStream ibs, final int from ) throws IOException {
    if ( from < 0 || from > n ) throw new IllegalArgumentException( "Node index out of range: " + from );
    this.from = from;
    this.ibs = ibs;
    if ( from != 0 ) {
        if ( offsetType <= 0 ) throw new IllegalStateException( "You cannot iterate from a chosen node without offsets" );

        int pos;
        for( int i = 1; i < Math.min( from + 1, cyclicBufferSize ); i++ ) {
            pos = ( from - i + cyclicBufferSize ) % cyclicBufferSize;
            outd[ pos ] = BVGraph.this.outdegreeInternal( from - i );
            System.arraycopy( BVGraph.this.successorArray( from - i ), 0, window[ pos ] = IntArrays.grow( window[ pos ], outd[ pos ], 0 ), 0, outd[ pos ] );
        }
        ibs.position( offsets.getLong( from ) ); // We must fix the bit stream position so that we are *before* the outdegree.
    }
    curr = from - 1;
}

private int[] distancesFrom( final ImmutableGraph graph, final int from ) {
    final IntArrayFIFOQueue queue = new IntArrayFIFOQueue();
    final int n = graph.numNodes();
    final int[] dist = new int[ n ];
    IntArrays.fill( dist, Integer.MAX_VALUE ); // Initially, all distances are infinity.

    queue.enqueue( from );
    dist[ from ] = 0;

    LazyIntIterator successors;

    while( ! queue.isEmpty() ) {
        int curr = queue.dequeueInt();
        successors = graph.successors( curr );
        int d = graph.outdegree( curr );
        while( d-- != 0 ) {
            int succ = successors.nextInt();
            if ( dist[ succ ] == Integer.MAX_VALUE ) {
                dist[ succ ] = dist[ curr ] + 1;
                queue.enqueue( succ );
            }
        }
    }

    return dist;        
}

public BottomSketch(String str, int nGramSize, int k, boolean doReverseCompliment)
{
    int[] hashes = HashUtils.computeSequenceHashes(str, nGramSize, doReverseCompliment);

    k = Math.min(k, hashes.length);

    int[] perm = new int[hashes.length];
    for (int iter=0; iter<hashes.length; iter++)
        perm[iter] = iter;

    //sort the array
    IntArrays.radixSortIndirect(perm, hashes, true);

    hashPositions = new int[k];

    for (int iter=0; iter<k; iter++)
    {
        int index = perm[iter];
        hashPositions[iter] = hashes[index]; 
    }

}

private void visitDictionary(Visitor<Text> visitor, VisitorContextImpl context
                    ) throws IOException {
    int[] keysArray = null;
    if (sortKeys) {
      keysArray = new int[numElements];
      for (int idx = 0; idx < numElements; idx++) {
        keysArray[idx] = idx + 1;
      }
      IntArrays.quickSort(keysArray, new TextPositionComparator());
    }

    for (int pos = 0; pos < numElements; pos++) {
      context.setOriginalPosition(keysArray == null? pos + 1: keysArray[pos]);
      visitor.visit(context);
    }
    keysArray = null;
}

/**
 * Given an IntArrayList object, sort it, and return an integer array, containing the sorted elements
 * @param intList: the input list to be sorted
 * @return a sorted integer array
 */
public static int [] sort(IntArrayList intList){
    // Sort the indices and return them
    int [] sorted = new int[intList.size()];
    for (int i = 0; i < intList.size(); i++){
        sorted[i] = intList.getInt(i);
    }
    IntArrays.quickSort(sorted);

    return sorted;
}

@Test
public void testNoBlocking() throws InterruptedException {
    for(final int size: new int[] { 1, 10, 100, 128, 256 }) {
        final ReorderingBlockingQueue<Integer> q = new ReorderingBlockingQueue<>(size);
        final int[] perm = Util.identity(size);
        IntArrays.shuffle(perm, new XoRoShiRo128PlusRandom());
        for(int i = perm.length; i-- != 0;) q.put(Integer.valueOf(perm[i]), perm[i]);
        for(int i = 0; i < perm.length; i++) assertEquals(i, q.take().intValue());
        assertEquals(0, q.size());
    }
}

/**
 * Returns a copy of this table sorted using the given comparator
 */
public Table sortOn(IntComparator rowComparator) {
    Table newTable = emptyCopy(rowCount());

    int[] newRows = rows();
    IntArrays.parallelQuickSort(newRows, rowComparator);

    Rows.copyRowsToTable(IntArrayList.wrap(newRows), this, newTable);
    return newTable;
}

@CommandLine(argNames={"graph", "milestones"})
public HittingDistanceMinimizer(ImmutableGraph graph, IntSet milestones) {
    this.graph = Transform.transpose(graph);
    this.milestones = milestones;
    minMilestoneDistance = new int[graph.numNodes()];
    IntArrays.fill(minMilestoneDistance, Integer.MAX_VALUE);
    closestMilestone = new int[graph.numNodes()];
    IntArrays.fill(closestMilestone, -1);
    milestoneQueue = new IntArrayPriorityQueue(milestones.toIntArray());
    runningVisitors = new ObjectOpenHashSet<Visitor>();
    pl  = new ProgressLogger(LOGGER, "milestones");
    pl.expectedUpdates = milestones.size();

}

@Override
public void run() {
    final IntArrayFIFOQueue queue = new IntArrayFIFOQueue();

    IntArrays.fill( dists, Integer.MAX_VALUE ); // Initially, all distances are infinity.

    int curr, succ;
    queue.enqueue( start );
    dists[ start ] = 0;

    LazyIntIterator successors;

    while( ! queue.isEmpty() ) {
        curr = queue.dequeueInt();
        successors = graph.successors( curr );
        int d = graph.outdegree( curr );
        while( d-- != 0 ) {
            succ = successors.nextInt();
            if ( dists[ succ ] == Integer.MAX_VALUE  ) {
                dists[ succ ] = dists[ curr ] + 1;
                queue.enqueue( succ );
            }
        }
    }

    startNewThreadAfter(this);
}

public IntSet getTop(int k) {
    if (k > graph.numNodes())
        LOGGER.warn("Warning: " + k + " categories were asked, but the graph contains " + graph.numNodes());

    LOGGER.info("Computing top-"+k+" categories...");
    IntSet okIds = new IntOpenHashSet(IntArrays.trim(positions, k));
    LOGGER.info("Top-"+k+" categories computed.");
    return okIds;
}

/**
 * Returns a copy of this table sorted using the given comparator
 */
public Table sortOn(IntComparator rowComparator) {
    Table newTable = emptyCopy(rowCount());

    int[] newRows = rows();
    IntArrays.parallelQuickSort(newRows, rowComparator);

    Rows.copyRowsToTable(IntArrayList.wrap(newRows), this, newTable);
    return newTable;
}

/** Unwraps the elements returned by a lazy iterator into a new array.
 * 
 * <p>If you need the resulting array to contain the
 * elements returned by <code>lazyIntIterator</code>, but some more elements set to zero
 * would cause no harm, consider using {@link #unwrapLoosely(LazyIntIterator)}, which
 * usually avoids a final call to {@link IntArrays#trim(int[], int)}.
 * 
 * @param lazyIntIterator a lazy integer iterator.
 * @return an array containing the elements returned by <code>lazyIntIterator</code>.
 * @see #unwrapLoosely(LazyIntIterator) 
 */
public static int[] unwrap( final LazyIntIterator lazyIntIterator ) {
    int array[] = new int[ 16 ];
    int j = 0, t;

    while( ( t = lazyIntIterator.nextInt() ) != -1  ) {
        if ( j == array.length ) array = IntArrays.grow( array, j + 1 );
        array[ j++ ] = t;
    }

    return IntArrays.trim( array, j );
}

/** Creates a new immutable subgraph using a given backing node array.
 * 
 * <P>Note that <code>subgraphNode</code> is <em>not</em> copied: thus, it must not
 * be modified until this subgraph is no longer in use.
 * 
 * @param supergraph the supergraph.
 * @param subgraphNode an increasing array containing the nodes defining the induced subgraph. 
 */
public ImmutableSubgraph( final ImmutableGraph supergraph, final int subgraphNode[] ) {
    this.supergraph = supergraph;
    this.supergraphAsSubgraph = supergraph instanceof ImmutableSubgraph ? (ImmutableSubgraph)supergraph : null;
    this.subgraphNode = subgraphNode;
    this.subgraphSize = subgraphNode.length;
    this.supergraphNumNodes = supergraph.numNodes();
    this.supergraphNode = new int[ supergraphNumNodes ];
    IntArrays.fill( supergraphNode, -1 );
    for( int i = subgraphSize; i-- != 0; ) supergraphNode[ subgraphNode[ i ] ] = i;
    for ( int i = 1; i < subgraphSize; i++ )
        if ( subgraphNode[ i - 1 ] >= subgraphNode[ i ] )
            throw new IllegalArgumentException( "The provided integer array is not strictly increasing: " + (i-1) + "-th element is " + subgraphNode[ i - 1 ] + ", " + i + "-th element is " + subgraphNode[ i ] );
    if ( subgraphSize > 0 && subgraphNode[ subgraphSize - 1 ] >= supergraphNumNodes ) throw new IllegalArgumentException( "Subnode index out of bounds: " + subgraphNode[ subgraphSize - 1 ] );
}

public NodeIterator nodeIterator() {
    return new NodeIterator() {
        final NodeIterator nodeIterator = graph.nodeIterator();
        @SuppressWarnings("hiding") int[] succ = IntArrays.EMPTY_ARRAY;
        int outdegree = -1;

        public int outdegree() {
            if ( outdegree == -1 ) throw new IllegalStateException();
            return outdegree;
        }

        public int nextInt() {
            final int currNode = nodeIterator.nextInt();
            final int oldOutdegree = nodeIterator.outdegree();
            int[] oldSucc = nodeIterator.successorArray();
            succ = IntArrays.ensureCapacity( succ, oldOutdegree, 0 );
            outdegree = 0;
            for( int i = 0; i < oldOutdegree; i++ ) if ( filter.accept( currNode, oldSucc[ i ] ) ) succ[ outdegree++ ] = oldSucc[ i ];
            return currNode;
        }

        public int[] successorArray() {
            if ( outdegree == -1 ) throw new IllegalStateException();
            return succ;
        }

        public boolean hasNext() {
            return nodeIterator.hasNext();
        }
    };
}

/** Returns an immutable view of this mutable graph.
 * 
 * <P>The view can be used until this mutable graph is modified. Attempt to use
 * the view after modifying this mutable graph will cause a {@link ConcurrentModificationException}.
 * After modification, a new call to this method will return a new immutable view.
 * 
 * @return an immutable view of this mutable graph.
 */
public ImmutableGraph immutableView() {
    if ( modificationCount != lastModificationCount ) {
        for( int i = n; i-- != 0; ) IntArrays.quickSort( successors[ i ].elements(), 0, successors[ i ].size() );
        immutableView = new ImmutableView( this );
    }
    lastModificationCount = modificationCount;
    return immutableView;
}

/**
 * Renumbers by decreasing size the components of this set.
 * 
 * <p>After a call to this method, both the internal status of this class and the argument array
 * are permuted so that the sizes of connected components are decreasing in the component index.
 * 
 * @param size the components sizes, as returned by {@link #computeSizes()}.
 */
public void sortBySize( final int[] size ) {
    final int[] perm = Util.identity( size.length );
    IntArrays.quickSort( perm, 0, perm.length, new AbstractIntComparator() {
        public int compare( final int x, final int y ) {
            return size[ y ] - size[ x ];
        }
    } );
    final int[] copy = size.clone();
    for ( int i = size.length; i-- != 0; )
        size[ i ] = copy[ perm[ i ] ];
    Util.invertPermutationInPlace( perm );
    for ( int i = component.length; i-- != 0; )
        component[ i ] = perm[ component[ i ] ];
}

/** Renumbers by decreasing size the components of this set.
 *
 * <p>After a call to this method, both the internal status of this class and the argument
 * array are permuted so that the sizes of strongly connected components are decreasing
 * in the component index.
 *
 *  @param size the components sizes, as returned by {@link #computeSizes()}.
 */
public void sortBySize( final int[] size ) {
    final int[] perm = Util.identity( size.length );
    IntArrays.quickSort( perm, 0, perm.length, new AbstractIntComparator() {
        public int compare( final int x, final int y ) {
            return size[ y ] - size[ x ]; 
        }
    });
    final int[] copy = size.clone();
    for ( int i = size.length; i-- != 0; ) size[ i ] = copy[ perm[ i ] ];
    Util.invertPermutationInPlace( perm );
    for( int i = component.length; i-- != 0; ) component[ i ] = perm[ component[ i ] ];
}

/** Renumbers by decreasing size the components of this set.
 *
 * <p>After a call to this method, both the internal status of this class and the argument
 * array are permuted so that the sizes of strongly connected components are decreasing
 * in the component index.
 *
 *  @param size the components sizes, as returned by {@link #computeSizes()}.
 */
public void sortBySize( final int[] size ) {
    final int[] perm = Util.identity( size.length );
    IntArrays.quickSort( perm, 0, perm.length, new AbstractIntComparator() {
        public int compare( final int x, final int y ) {
            return size[ y ] - size[ x ]; 
        }
    });
    final int[] copy = size.clone();
    for ( int i = size.length; i-- != 0; ) size[ i ] = copy[ perm[ i ] ];
    Util.invertPermutationInPlace( perm );
    for( int i = component.length; i-- != 0; ) component[ i ] = perm[ component[ i ] ];
}

public BottomOverlapSketch(String seq, int kmerSize, int sketchSize, boolean doReverseCompliment) throws ZeroNGramsFoundException
{
    this.kmerSize = kmerSize;
    this.seqLength = seq.length() - kmerSize + 1;

    if (this.seqLength<=0)
        throw new ZeroNGramsFoundException("Sequence length must be greater or equal to n-gram size "+kmerSize+".", seq);

    // compute just direct hash of sequence
    int[] hashes = HashUtils.computeSequenceHashes(seq, kmerSize, doReverseCompliment);

    int[] perm = new int[hashes.length];

    //init the array
    for (int iter = 0; iter < hashes.length; iter++)
        perm[iter] = iter;

    //sort the array
    IntArrays.radixSortIndirect(perm, hashes, true);

    //sketchSize = (int)Math.round(0.25*(double)this.seqLength);

    //find the largest storage value
    int k = Math.min(sketchSize, hashes.length);

    //allocate the memory
    this.orderedHashes = new int[k][2];

    for (int iter = 0; iter < this.orderedHashes.length; iter++)
    {
        int index = perm[iter];
        this.orderedHashes[iter][0] = hashes[index];
        this.orderedHashes[iter][1] = index;
    }
}

public void visitDictionary(Visitor<Long> visitor, IntDictionaryEncoderVisitorContext context) throws IOException {
    int[] keysArray = null;
    if (sortKeys) {
      keysArray = new int[numElements];
      for (int idx = 0; idx < numElements; idx++) {
        keysArray[idx] = idx;
      }
      IntArrays.quickSort(keysArray, new LongPositionComparator());
    }
    for (int pos = 0; pos < numElements; pos++) {
      context.setOriginalPosition(keysArray == null? pos : keysArray[pos]);
      visitor.visit(context);
    }
}

@Override
public void sortDescending() {
    IntArrays.parallelQuickSort(data.elements(), reverseIntComparator);
}

@Override
public void sortDescending() {
    IntArrays.parallelQuickSort(data.elements(), reverseIntComparator);
}

@Override
public void sortAscending() {
    IntArrays.parallelQuickSort(values.elements(), dictionarySortComparator);
}

@Override
public void sortDescending() {
    IntArrays.parallelQuickSort(values.elements(), reverseDictionarySortComparator);
}

@Override
public void sortDescending() {
    IntArrays.parallelQuickSort(data.elements(), ReverseIntComparator.instance());
}

@Override
@SuppressWarnings("unchecked")
protected void compute() {
 final K[] x = this.x;
 final int len = to - from;
 if ( len < PARALLEL_QUICKSORT_NO_FORK ) {
  quickSortIndirect( perm, x, from, to );
  return;
 }
 // Choose a partition element, v
 int m = from + len / 2;
 int l = from;
 int n = to - 1;
 int s = len / 8;
 l = med3Indirect( perm, x, l, l + s, l + 2 * s );
 m = med3Indirect( perm, x, m - s, m, m + s );
 n = med3Indirect( perm, x, n - 2 * s, n - s, n );
 m = med3Indirect( perm, x, l, m, n );
 final K v = x[ perm[ m ] ];
 // Establish Invariant: v* (<v)* (>v)* v*
 int a = from, b = a, c = to - 1, d = c;
 while ( true ) {
  int comparison;
  while ( b <= c && ( comparison = ( ((Comparable<K>)(x[ perm[ b ] ])).compareTo(v) ) ) <= 0 ) {
   if ( comparison == 0 ) IntArrays.swap( perm, a++, b );
   b++;
  }
  while ( c >= b && ( comparison = ( ((Comparable<K>)(x[ perm[ c ] ])).compareTo(v) ) ) >= 0 ) {
   if ( comparison == 0 ) IntArrays.swap( perm, c, d-- );
   c--;
  }
  if ( b > c ) break;
  IntArrays.swap( perm, b++, c-- );
 }
 // Swap partition elements back to middle
 int t;
 s = Math.min( a - from, b - a );
 IntArrays.swap( perm, from, b - s, s );
 s = Math.min( d - c, to - d - 1 );
 IntArrays.swap( perm, b, to - s, s );
 // Recursively sort non-partition-elements
 s = b - a;
 t = d - c;
 if ( s > 1 && t > 1 ) invokeAll( new ForkJoinQuickSortIndirect <K>( perm, x, from, from + s ), new ForkJoinQuickSortIndirect <K>( perm, x, to - t, to ) );
 else if ( s > 1 ) invokeAll( new ForkJoinQuickSortIndirect <K>( perm, x, from, from + s ) );
 else invokeAll( new ForkJoinQuickSortIndirect <K>( perm, x, to - t, to ) );
}

@Override

 protected void compute() {
  final long[] x = this.x;
  final int len = to - from;
  if ( len < PARALLEL_QUICKSORT_NO_FORK ) {
   quickSortIndirect( perm, x, from, to );
   return;
  }
  // Choose a partition element, v
  int m = from + len / 2;
  int l = from;
  int n = to - 1;
  int s = len / 8;
  l = med3Indirect( perm, x, l, l + s, l + 2 * s );
  m = med3Indirect( perm, x, m - s, m, m + s );
  n = med3Indirect( perm, x, n - 2 * s, n - s, n );
  m = med3Indirect( perm, x, l, m, n );
  final long v = x[ perm[ m ] ];
  // Establish Invariant: v* (<v)* (>v)* v*
  int a = from, b = a, c = to - 1, d = c;
  while ( true ) {
   int comparison;
   while ( b <= c && ( comparison = ( Long.compare((x[ perm[ b ] ]),(v)) ) ) <= 0 ) {
    if ( comparison == 0 ) IntArrays.swap( perm, a++, b );
    b++;
   }
   while ( c >= b && ( comparison = ( Long.compare((x[ perm[ c ] ]),(v)) ) ) >= 0 ) {
    if ( comparison == 0 ) IntArrays.swap( perm, c, d-- );
    c--;
   }
   if ( b > c ) break;
   IntArrays.swap( perm, b++, c-- );
  }
  // Swap partition elements back to middle
  int t;
  s = Math.min( a - from, b - a );
  IntArrays.swap( perm, from, b - s, s );
  s = Math.min( d - c, to - d - 1 );
  IntArrays.swap( perm, b, to - s, s );
  // Recursively sort non-partition-elements
  s = b - a;
  t = d - c;
  if ( s > 1 && t > 1 ) invokeAll( new ForkJoinQuickSortIndirect ( perm, x, from, from + s ), new ForkJoinQuickSortIndirect ( perm, x, to - t, to ) );
  else if ( s > 1 ) invokeAll( new ForkJoinQuickSortIndirect ( perm, x, from, from + s ) );
  else invokeAll( new ForkJoinQuickSortIndirect ( perm, x, to - t, to ) );
 }

@Override
public int[] successorArray( final int x ) { 
    int[] succ = map.get(x).toIntArray();
    IntArrays.quickSort(succ);
    return succ;
}

/**
 * @return at most <i>howMany</i> out-links of node, ordered by their unexpected (most unexpected first)
 */
public int[] results(int node, int howMany) {
    return IntArrays.trim(results(node), howMany);
}

public CategoryGraphCentralityRanker(ImmutableGraph g, double[] rank) {
    this.graph = g;
    this.rank = rank;
    positions = MathArrays.natural(graph.numNodes());
    IntArrays.quickSort(positions, ArrayUtils.reverseIndirectComparator(rank));
}

@Override
public void shuffle() {
    IntArrays.shuffle(uidxs.elements(), 0, uidxs.size(), rnd);
}

@Override
public void shuffle() {
    IntArrays.shuffle(uidxs.elements(), 0, uidxs.size(), rnd);
}

@Test
public void testRadixSortIndirectStable() {
    double[] d = { 2, 1, 0, 4 };
    int[] perm = it.unimi.dsi.fastutil.ints.IntArraysTest.identity( d.length );
    DoubleArrays.radixSortIndirect( perm, d, true );
    for( int i = d.length - 1; i-- != 0; ) assertTrue( d[ perm[ i ] ] <= d[ perm[ i + 1 ] ] );

    d = new double[ d.length ];
    perm = it.unimi.dsi.fastutil.ints.IntArraysTest.identity( d.length );
    DoubleArrays.radixSortIndirect( perm, d, true );
    for( int i = d.length - 1; i-- != 0; ) assertEquals( i, perm[ i ] );

    d = new double[] { 2, -1, 0, -4 };
    perm = it.unimi.dsi.fastutil.ints.IntArraysTest.identity( d.length );
    DoubleArrays.radixSortIndirect( perm, d, true );
    for( int i = d.length - 1; i-- != 0; ) assertTrue( d[ perm[ i ] ] <= d[ perm[ i + 1 ] ] );

    d = DoubleArrays.shuffle( identity( 100 ), new Random( 0 ) );
    perm = it.unimi.dsi.fastutil.ints.IntArraysTest.identity( d.length );
    DoubleArrays.radixSortIndirect( perm, d, true );
    for( int i = d.length - 1; i-- != 0; ) assertTrue( d[ perm[ i ] ] <= d[ perm[ i + 1 ] ] );

    d = new double[ 100 ];
    perm = it.unimi.dsi.fastutil.ints.IntArraysTest.identity( d.length );
    Random random = new Random( 0 );
    for( int i = d.length; i-- != 0; ) d[ i ] = random.nextInt();
    DoubleArrays.radixSortIndirect( perm, d, true );
    for( int i = d.length - 1; i-- != 0; ) assertTrue( d[ perm[ i ] ] <= d[ perm[ i + 1 ] ] );

    d = new double[ d.length ];
    perm = it.unimi.dsi.fastutil.ints.IntArraysTest.identity( d.length );
    DoubleArrays.radixSortIndirect( perm, d, true );
    for( int i = d.length - 1; i-- != 0; ) assertEquals( i, perm[ i ] );

    d = new double[ d.length ];
    for( int i = 0; i < d.length; i++ ) d[ i ] = random.nextInt( 4 ); 
    perm = it.unimi.dsi.fastutil.ints.IntArraysTest.identity( d.length );
    DoubleArrays.radixSortIndirect( perm, d, true );
    for( int i = d.length - 1; i-- != 0; ) if ( d[ perm[ i ] ] == d[ perm[ i + 1 ] ] ) assertTrue( perm[ i ] < perm[ i + 1 ] );

    d = new double[ 100 ];
    perm = it.unimi.dsi.fastutil.ints.IntArraysTest.identity( d.length );
    random = new Random( 0 );
    for( int i = d.length; i-- != 0; ) d[ i ] = random.nextInt();
    DoubleArrays.radixSortIndirect( perm, d, 10, 90, true );
    for( int i = 10; i < 89; i++ ) assertTrue( Integer.toString( i ), d[ perm[ i ] ] <= d[ perm[ i + 1 ] ] );
    for( int i = 0; i < 10; i++ ) assertEquals( i, perm[ i ] );
    for( int i = 90; i < 100; i++ ) assertEquals( i, perm[ i ] );

    d = new double[ 100000 ];
    perm = it.unimi.dsi.fastutil.ints.IntArraysTest.identity( d.length );
    random = new Random( 0 );
    for( int i = d.length; i-- != 0; ) d[ i ] = random.nextInt();
    DoubleArrays.radixSortIndirect( perm, d, true );
    for( int i = d.length - 1; i-- != 0; ) assertTrue( Integer.toString( i ), d[ perm[ i ] ] <= d[ perm[ i + 1 ] ] );

    IntArrays.shuffle( perm, new Random( 0 ) );
    DoubleArrays.radixSortIndirect( perm, d, true );
    for( int i = d.length - 1; i-- != 0; ) assertTrue( Integer.toString( i ), d[ perm[ i ] ] <= d[ perm[ i + 1 ] ] );

    d = new double[ 10000000 ];
    perm = it.unimi.dsi.fastutil.ints.IntArraysTest.identity( d.length );
    random = new Random( 0 );
    for( int i = d.length; i-- != 0; ) d[ i ] = random.nextInt();
    DoubleArrays.radixSortIndirect( perm, d, true );
    for( int i = d.length - 1; i-- != 0; ) assertTrue( d[ perm[ i ] ] <= d[ perm[ i + 1 ] ] );

    d = new double[ d.length ];
    perm = it.unimi.dsi.fastutil.ints.IntArraysTest.identity( d.length );
    DoubleArrays.radixSortIndirect( perm, d, true );
    for( int i = d.length - 1; i-- != 0; ) assertEquals( i, perm[ i ] );

    d = new double[ d.length ];
    for( int i = 0; i < d.length; i++ ) d[ i ] = random.nextInt( 8 ); 
    perm = it.unimi.dsi.fastutil.ints.IntArraysTest.identity( d.length );
    DoubleArrays.radixSortIndirect( perm, d, true );
    for( int i = d.length - 1; i-- != 0; ) if ( d[ perm[ i ] ] == d[ perm[ i + 1 ] ] ) assertTrue( perm[ i ] < perm[ i + 1 ] );
}