Attachment 254154 Details for Bug 460618 – Optimized utility function testing Comparator contract

Some Eclipse Foundation services are deprecated, or will be soon. Please ensure you've read this important communication.

Optimized utility function testing Comparator contract

file_460618.txt (text/plain), 7.16 KB, created by Timo Kinnunen

on 2015-06-05 14:08:37 EDT

(hide)

Description:

Filename:

MIME Type:

Creator: Timo Kinnunen

Created: 2015-06-05 14:08:37 EDT

Size: 7.16 KB

patch

obsolete

>package org.eclipse.jface.viewers;
>
>import java.util.Arrays;
>import java.util.Comparator;
>import java.util.function.BiFunction;
>import java.util.function.Consumer;
>import java.util.function.Function;
>import java.util.function.ToIntBiFunction;
>import java.util.stream.Stream;
>
>public class ComparatorContract {
>	public static void main(String[] args) {
>		int N = 1000;
>		Object[] a1 = Stream.iterate(N, x -> x - 1).limit(N).toArray();
>		Object[] a2 = a1.clone();
>		Object[] a3 = a1.clone();
>		Object[] a4 = a1.clone();
>		Object[] a5 = a1.clone();
>		Comparator<Object> sort0 = (x, y) -> (Integer) x == 10 ? 56 - (Integer) y : (Integer) x - (Integer) y;
>		Comparator<Object> sort1 = (x, y) -> (Integer) y == 10 && (Integer) x < 10 ? 0 : (Integer) x - (Integer) y;
>		Comparator<Object> sort = (x, y) -> (Integer) x - (Integer) y;
>		Runnable run1 = () -> Arrays.sort(a1, sort);
>		Runnable run2 = () -> ComparatorContract.enforce(a2, Object::toString, System.out::println, sort);
>		Runnable run3 = () -> ComparatorContract.enforce(a3, Object::toString, System.out::println, sort);
>		Runnable run4 =
>			() -> Arrays.sort(a4, ComparatorContract.enforce(a4, Object::toString, System.out::println, sort));
>		Runnable run5 =
>			() -> Arrays.sort(a5, ComparatorContract.enforce(a5, Object::toString, System.out::println, sort));
>		System.out.println(Arrays.asList(a1));
>		time("            sort: ", run1);
>		time("     1st enforce: ", run2);
>		time("     2nd enforce: ", run3);
>		time("enforce and sort: ", run4);
>		time("enforce and sort: ", run5);
>		System.out.println(Arrays.asList(a1));
>		System.out.println(Arrays.asList(a2));
>		System.out.println(Arrays.asList(a3));
>		System.out.println(Arrays.asList(a4));
>		System.out.println(Arrays.asList(a5));
>	}
>	static void time(String label, Runnable runnable) {
>		long start2 = System.currentTimeMillis();
>		long start = System.nanoTime();
>		runnable.run();
>		long end = System.nanoTime();
>		long end2 = System.currentTimeMillis();
>		long time = end - start;
>		long time2 = end2 - start2;
>		System.out.printf("%s%4dms %,20d ns%n", label, time2, time);
>	}
>	static <T> Comparator<T> enforce(T[] elements, Function<T, String> labeling, Consumer<String> out, Comparator<T> c) {
>		int length = elements.length;
>		T[] clone = elements.clone();
>		Comparator<T> byIdentity = Comparator.comparingInt(System::identityHashCode);
>		Arrays.sort(clone, byIdentity);
>		long[][] resultGTs = new long[length][];
>		long[][] resultEQs = new long[length][];
>		Function<T, String> id = o -> o == null ? "null" : labeling.apply(o) + " (" + o.getClass().getName() + ")";
>		for(int x = 0; x < length; x++) {
>			resultGTs[x] = new long[(int) ((((length + 63L) / 64) + 3) / 4 * 4)];
>			resultEQs[x] = new long[(int) ((((length + 63L) / 64) + 3) / 4 * 4)];
>		}
>		for(int x = 0; x < length; x++) {
>			T theX = clone[x];
>			for(int y = x; y < length; y++) {
>				T theY = clone[y];
>				int xy = Integer.signum(c.compare(theX, theY));
>				if(xy == 0) {
>					resultEQs[x][y / 64] |= 1L << (y % 64);
>				} else if(xy > 0) {
>					resultGTs[x][y / 64] |= 1L << (y % 64);
>				}
>				if(x == y) {
>					//The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.
>					if(xy != 0) {
>						String text = "compare(x, x) is not 0, it is %d.%nx was %s";
>						out.accept(String.format(text, xy, id.apply(theX)));
>					}
>				} else if(x > y) {
>					int yx = Integer.signum(c.compare(theY, theX));
>					if(yx == 0) {
>						resultEQs[y][x / 64] |= 1L << (x % 64);
>					} else if(yx > 0) {
>						resultGTs[y][x / 64] |= 1L << (x % 64);
>					}
>					//The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.
>					if(xy != -yx) {
>						String text = "compare(x, y) is %d but compare(y, x) is not %d, it is %d.%nx was %s,%ny was %s";
>						out.accept(String.format(text, xy, -xy, yx, id.apply(theX), id.apply(theY)));
>					}
>				}
>			}
>		}
>		ToIntBiFunction<Integer, Integer> results = (x, y) -> {
>			if((resultGTs[x][y / 64] & (1L << y % 64)) != 0) {
>				return 1;
>			} else if((resultEQs[x][y / 64] & (1L << y % 64)) != 0) {
>				return 0;
>			} else {
>				return -1;
>			}
>		};
>		BiFunction<long[], long[], long[]> and = (l, r) -> {
>			long[] a = l.clone();
>			for(int i = 0; i < a.length; i += 4) {
>				a[i + 0] &= r[i + 0];
>				a[i + 1] &= r[i + 1];
>				a[i + 2] &= r[i + 2];
>				a[i + 3] &= r[i + 3];
>			}
>			return a;
>		};
>		if(length <= 2000) {
>			for(int x = 0; x < length; x++) {
>				long[] gtX = resultGTs[x];
>				long[] eqX = resultEQs[x];
>				for(int y = 0; y < length; y++) {
>					if((gtX[y / 64] & (1L << y % 64)) != 0) {
>						long[] gtY = resultGTs[y];
>						long[] gtXandY = and.apply(gtX, gtY);
>						if(!Arrays.equals(gtY, gtXandY)) {
>							//The implementor must also ensure that the relation is transitive: 
>							//((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.
>							for(int z = 0; z < length; z++) {
>								int yz = results.applyAsInt(y, z);
>								int xz = results.applyAsInt(x, z);
>								if(yz > 0 && !(xz > 0)) {
>									String text =
>										"compare(x, y) and compare(y, z) are > 0 but compare(x, z) is not > 0, it is %d.%nx was %s,%ny was %s,%nz was %s";
>									String idX = id.apply(clone[x]), idY = id.apply(clone[y]), idZ = id.apply(clone[z]);
>									out.accept(String.format(text, xz, idX, idY, idZ));
>								}
>							}
>						}
>					}
>					if((eqX[y / 64] & (1L << y % 64)) != 0) {
>						long[] eqY = resultEQs[y];
>						long[] gtY = resultGTs[y];
>						if(!Arrays.equals(eqX, eqY) || !Arrays.equals(gtX, gtY)) {
>							//Finally, the implementor must ensure that 
>							//compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.
>							for(int z = 0; z < length; z++) {
>								int xz = results.applyAsInt(x, z);
>								int yz = results.applyAsInt(y, z);
>								if(xz != yz) {
>									String text =
>										"compare(x, y) is 0, but compare(x, z) and compare(y, z) are different: %d is not %d.%nx was %s,%ny was %s,%nz was %s";
>									String idX = id.apply(clone[x]), idY = id.apply(clone[y]), idZ = id.apply(clone[z]);
>									out.accept(String.format(text, xz, yz, idX, idY, idZ));
>								}
>							}
>						}
>					}
>				}
>			}
>		}
>		return (Comparator<T>) (theA, theB) -> {
>			int a = Arrays.binarySearch(clone, theA, byIdentity);
>			int b = Arrays.binarySearch(clone, theB, byIdentity);
>			if(a >= 0 && clone[a] != theA) {
>				a = Arrays.asList(clone).indexOf(theA);
>			}
>			if(b >= 0 && clone[b] != theB) {
>				b = Arrays.asList(clone).indexOf(theB);
>			}
>			if(a < 0) {
>				String text = "new object has been added to the array during sorting.%nit was %s";
>				out.accept(String.format(text, id.apply(theA)));
>			}
>			if(b < 0) {
>				String text = "new object has been added to the array during sorting.%nit was %s";
>				out.accept(String.format(text, id.apply(theB)));
>			}
>			int ab = results.applyAsInt(a, b);
>			int result = c.compare(theA, theB);
>			if(ab != Integer.signum(result)) {
>				String text = "compare(x, y) was %d earlier, but now it is %d.%nx was %s,%ny was %s";
>				out.accept(String.format(text, ab, result, id.apply(theA), id.apply(theB)));
>			}
>			return result;
>		};
>	}
>}

Actions: View

Attachments on bug 460618: 254118 | 254154 | 254160