Attachment 254160 Details for Bug 460618 – Fixed and improved utility function testing Comparator contract

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

Fixed and improved utility function testing Comparator contract

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

on 2015-06-06 08:47:32 EDT

(hide)

Description:

Filename:

MIME Type:

Creator: Timo Kinnunen

Created: 2015-06-06 08:47:32 EDT

Size: 7.94 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 -> {
>			int index = length - 1;
>			while(index >= 0 && elements[index] != o) {
>				index--;
>			}
>			return o == null ? "null" : labeling.apply(o) + " (" + o.getClass().getName() + ") at " + index;
>		};
>		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)];
>		}
>		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;
>			}
>		};
>		for(int x = 0; x < length; x++) {
>			T theX = clone[x];
>			for(int y = 0; y <= x; y++) {
>				T theY = clone[y];
>				int xy = Integer.signum(c.compare(theX, theY));
>				int xy2 = Integer.signum(c.compare(theX, theY));
>				if(xy != xy2) {
>					String text = "compare(x, y) changed from %d to %d on 2nd call.%nx was %s,%ny was %s";
>					out.accept(String.format(text, xy, xy2, id.apply(theX), id.apply(theY)));
>				}
>				if(xy == 0) {
>					resultEQs[x][y / 64] |= 1L << (y % 64);
>				} else if(xy > 0) {
>					resultGTs[x][y / 64] |= 1L << (y % 64);
>				}
>				if(results.applyAsInt(x, y) != xy) {
>					out.accept("ASSERT 1");
>				}
>				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));
>					int yx2 = Integer.signum(c.compare(theY, theX));
>					if(yx != yx2) {
>						String text = "compare(y, x) changed from %d to %d on 2nd call.%ny was %s,%nx was %s";
>						out.accept(String.format(text, yx, yx2, id.apply(theY), id.apply(theX)));
>					}
>					if(yx == 0) {
>						resultEQs[y][x / 64] |= 1L << (x % 64);
>					} else if(yx > 0) {
>						resultGTs[y][x / 64] |= 1L << (x % 64);
>					}
>					if(results.applyAsInt(y, x) != yx) {
>						out.accept("ASSERT 2");
>					}
>					//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)));
>					}
>				}
>			}
>		}
>		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