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; }
/** 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 ] ]; }
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 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); }
@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 ] ); }