public static void selectionSort(int[] a, int[] y, int from, int to, IntComparator comp) { for (int i = from; i < to - 1; ++i) { int m = i; int u; for (u = i + 1; u < to; ++u) { if (comp.compare(a[u], a[m]) < 0) { m = u; } } if (m != i) { u = a[i]; a[i] = a[m]; a[m] = u; u = y[i]; y[i] = y[m]; y[m] = u; } } }
public int compare(Integer o1, Integer o2) throws UnsupportedOperationException { if (!this.isLocked) { this.checkChainIntegrity(); this.isLocked = true; } Iterator<IntComparator> comparators = this.comparatorChain.iterator(); for (int comparatorIndex = 0; comparators.hasNext(); ++comparatorIndex) { IntComparator comparator = comparators.next(); int retval = comparator.compare(o1, o2); if (retval != 0) { if (this.orderingBits.get(comparatorIndex)) { if (retval > 0) { retval = -1; } else { retval = 1; } } return retval; } } return 0; }
public int compare(int o1, int o2) throws UnsupportedOperationException { if (!this.isLocked) { this.checkChainIntegrity(); this.isLocked = true; } Iterator<IntComparator> comparators = this.comparatorChain.iterator(); for (int comparatorIndex = 0; comparators.hasNext(); ++comparatorIndex) { IntComparator comparator = comparators.next(); int retval = comparator.compare(o1, o2); if (retval != 0) { if (this.orderingBits.get(comparatorIndex)) { if (retval > 0) { retval = -1; } else { retval = 1; } } return retval; } } return 0; }
/** * Performs a binary search on an already-sorted range: finds the first position where an * element can be inserted without violating the ordering. Sorting is by a user-supplied * comparison function. * * @param from the index of the first element (inclusive) to be included in the binary search. * @param to the index of the last element (exclusive) to be included in the binary search. * @param pos the position of the element to be searched for. * @param comp the comparison function. * @return the largest index i such that, for every j in the range <code>[first..i)</code>, * <code>comp.compare(j, pos)</code> is <code>true</code>. */ private static int lowerBound( int from, final int to, final int pos, final IntComparator comp ) { // if (comp==null) throw new NullPointerException(); int len = to - from; while ( len > 0 ) { int half = len / 2; int middle = from + half; if ( comp.compare( middle, pos ) < 0 ) { from = middle + 1; len -= half + 1; } else { len = half; } } return from; }
/** * Performs a binary search on an already sorted range: finds the last position where an element * can be inserted without violating the ordering. Sorting is by a user-supplied comparison * function. * * @param from the index of the first element (inclusive) to be included in the binary search. * @param to the index of the last element (exclusive) to be included in the binary search. * @param pos the position of the element to be searched for. * @param comp the comparison function. * @return The largest index i such that, for every j in the range <code>[first..i)</code>, * <code>comp.compare(pos, j)</code> is <code>false</code>. */ private static int upperBound( int from, final int mid, final int pos, final IntComparator comp ) { // if (comp==null) throw new NullPointerException(); int len = mid - from; while ( len > 0 ) { int half = len / 2; int middle = from + half; if ( comp.compare( pos, middle ) < 0 ) { len = half; } else { from = middle + 1; len -= half + 1; } } return from; }
private static IntComparator IntBlockCompare(Type type, Block block) { return new AbstractIntComparator() { @Override public int compare(int left, int right) { if (block.isNull(left) && block.isNull(right)) { return 0; } if (block.isNull(left)) { return -1; } if (block.isNull(right)) { return 1; } return type.compareTo(block, left, block, right); } }; }
private void attachRoutesForClass(Router router, Class<? extends ServerResource> clazz) { TreeSet<String> pathsOrderedByLength = new TreeSet<String>(ComparatorUtils.chainedComparator(new Comparator<String>() { private IntComparator _intComparator = IntComparators.NATURAL_COMPARATOR; @Override public int compare(String o1, String o2) { return _intComparator.compare(o1.length(), o2.length()); } }, ComparatorUtils.NATURAL_COMPARATOR)); for (Method method : clazz.getDeclaredMethods()) { Annotation annotationInstance = method.getAnnotation(Paths.class); if (annotationInstance != null) { pathsOrderedByLength.addAll(Arrays.asList(((Paths) annotationInstance).value())); } } for (String routePath : pathsOrderedByLength) { LOGGER.info("Attaching route {} -> {}", routePath, clazz.getSimpleName()); router.attach(routePath, new AddHeaderFilter(getContext(), createFinder(clazz))); } }
/** */ public Table sortOn(Sort key) { Preconditions.checkArgument(!key.isEmpty()); if (key.size() == 1) { IntComparator comparator = getComparator(key); return sortOn(comparator); } IntComparatorChain chain = getChain(key); return sortOn(chain); }
/** * Returns a comparator chain for sorting according to the given key */ private IntComparatorChain getChain(Sort key) { Iterator<Map.Entry<String, Sort.Order>> entries = key.iterator(); Map.Entry<String, Sort.Order> sort = entries.next(); IntComparator comparator = rowComparator(sort.getKey(), sort.getValue()); IntComparatorChain chain = new IntComparatorChain(comparator); while (entries.hasNext()) { sort = entries.next(); chain.addComparator(rowComparator(sort.getKey(), sort.getValue())); } return chain; }
/** * 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; }
public IntComparatorChain(IntComparator comparator, boolean reverse) { this.orderingBits = null; this.isLocked = false; this.comparatorChain = new ArrayList<>(1); this.comparatorChain.add(comparator); this.orderingBits = new BitSet(1); if (reverse) { this.orderingBits.set(0); } }
public void addComparator(IntComparator comparator, boolean reverse) { this.checkLocked(); this.comparatorChain.add(comparator); if (reverse) { this.orderingBits.set(this.comparatorChain.size() - 1); } }
public void setComparator(int index, IntComparator comparator, boolean reverse) { this.checkLocked(); this.comparatorChain.set(index, comparator); if (reverse) { this.orderingBits.set(index); } else { this.orderingBits.clear(index); } }
/** * Returns the index of the median of the three indexed chars. */ private static int med3( final int a, final int b, final int c, final IntComparator comp ) { int ab = comp.compare( a, b ); int ac = comp.compare( a, c ); int bc = comp.compare( b, c ); return ( ab < 0 ? ( bc < 0 ? b : ac < 0 ? c : a ) : ( bc > 0 ? b : ac > 0 ? c : a ) ); }
/** Sorts the specified range of elements using the specified swapper and according to the order induced by the specified * comparator using mergesort. * * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not be reordered as a result * of the sort. The sorting algorithm is an in-place mergesort that is significantly slower than a * standard mergesort, as its running time is <i>O</i>(<var>n</var> (log <var>n</var>)<sup>2</sup>), but it does not allocate additional memory; as a result, it can be * used as a generic sorting algorithm. * * @param from the index of the first element (inclusive) to be sorted. * @param to the index of the last element (exclusive) to be sorted. * @param c the comparator to determine the order of the generic data (arguments are positions). * @param swapper an object that knows how to swap the elements at any two positions. */ public static void mergeSort( final int from, final int to, final IntComparator c, final Swapper swapper ) { /* * We retain the same method signature as quickSort. Given only a comparator and swapper we * do not know how to copy and move elements from/to temporary arrays. Hence, in contrast to * the JDK mergesorts this is an "in-place" mergesort, i.e. does not allocate any temporary * arrays. A non-inplace mergesort would perhaps be faster in most cases, but would require * non-intuitive delegate objects... */ final int length = to - from; // Insertion sort on smallest arrays if ( length < MERGESORT_NO_REC ) { for ( int i = from; i < to; i++ ) { for ( int j = i; j > from && ( c.compare( j - 1, j ) > 0 ); j-- ) { swapper.swap( j, j - 1 ); } } return; } // Recursively sort halves int mid = ( from + to ) >>> 1; mergeSort( from, mid, c, swapper ); mergeSort( mid, to, c, swapper ); // If list is already sorted, nothing left to do. This is an // optimization that results in faster sorts for nearly ordered lists. if ( c.compare( mid - 1, mid ) <= 0 ) return; // Merge sorted halves inPlaceMerge( from, mid, to, c, swapper ); }
public static IntComparator comparatorPuttingLargestMappedValueFirst(final Int2DoubleMap map) { return new IntComparator() { public int compare(Integer o1, Integer o2) { return compare(o1.intValue(), o2.intValue()); } public int compare(int k1, int k2) { return Double.compare(map.get(k2), map.get(k1)); } }; }
public static IntComparator comparatorPuttingLargestMappedValueFirstExceptNaN(final Int2DoubleMap map) { return new IntComparator() { public int compare(Integer o1, Integer o2) { return compare(o1.intValue(), o2.intValue()); } public int compare(int k1, int k2) { double d2 = map.get(k2); double d1 = map.get(k1); if (Double.isNaN(d2)) d2 = Double.NEGATIVE_INFINITY; if (Double.isNaN(d1)) d1 = Double.NEGATIVE_INFINITY; return Double.compare(d2, d1); } }; }
public static IntComparator comparatorPuttingSmallestMappedValueFirst(final Int2DoubleMap map) { return new IntComparator() { public int compare(Integer o1, Integer o2) { return compare(o1.intValue(), o2.intValue()); } public int compare(int k1, int k2) { return Double.compare(map.get(k1), map.get(k2)); } }; }
public static IntComparator reverseIndirectComparator(final double[] x) { return new AbstractIntComparator(){ @Override public int compare(int k1, int k2) { return Double.compare(x[k2], x[k1]); } }; }
public static IntComparator indirectComparator(final double[] x) { return new AbstractIntComparator(){ @Override public int compare(int k1, int k2) { return Double.compare(x[k1], x[k2]); } }; }
/** Sorts the specified range of elements using the specified swapper and according to the order induced by the specified * comparator using mergesort. * * <p>This sort is guaranteed to be <i>stable</i>: equal elements will not be reordered as a result * of the sort. The sorting algorithm is an in-place mergesort that is significantly slower than a * standard mergesort, as its running time is <i>O</i>(<var>n</var> (log <var>n</var>)<sup>2</sup>), but it does not allocate additional memory; as a result, it can be * used as a generic sorting algorithm. * * @param from the index of the first element (inclusive) to be sorted. * @param to the index of the last element (exclusive) to be sorted. * @param c the comparator to determine the order of the generic data (arguments are positions). * @param swapper an object that knows how to swap the elements at any two positions. */ public static void mergeSort( final int from, final int to, final IntComparator c, final Swapper swapper ) { /* * We retain the same method signature as quickSort. Given only a comparator and swapper we * do not know how to copy and move elements from/to temporary arrays. Hence, in contrast to * the JDK mergesorts this is an "in-place" mergesort, i.e. does not allocate any temporary * arrays. A non-inplace mergesort would perhaps be faster in most cases, but would require * non-intuitive delegate objects... */ final int length = to - from; // Insertion sort on smallest arrays if ( length < SMALL ) { for ( int i = from; i < to; i++ ) { for ( int j = i; j > from && ( c.compare( j - 1, j ) > 0 ); j-- ) { swapper.swap( j, j - 1 ); } } return; } // Recursively sort halves int mid = ( from + to ) >>> 1; mergeSort( from, mid, c, swapper ); mergeSort( mid, to, c, swapper ); // If list is already sorted, nothing left to do. This is an // optimization that results in faster sorts for nearly ordered lists. if ( c.compare( mid - 1, mid ) <= 0 ) return; // Merge sorted halves inPlaceMerge( from, mid, to, c, swapper ); }
public IntTreeTopK(final int maxSize, final IntComparator greater) { this.maxSize = maxSize; this.size = 0; this.greater = greater; this.data = new Int2ObjectRBTreeMap<MutableInteger>(this.greater); }
@Override public IntComparator rowComparator() { return comparator; }