# HG changeset patch
# User Artem Tikhomirov <tikhomirov.artem@gmail.com>
# Date 1301358002 -7200
# Node ID 4bf061a7c0018c677db89751b99c55ad5a64c81a
# Parent  87f40938c9b2947517f8485a38fe816db4f35206
Test algorithm to build sequence of missing revisions

diff -r 87f40938c9b2 -r 4bf061a7c001 cmdline/org/tmatesoft/hg/console/Incoming.java
--- a/cmdline/org/tmatesoft/hg/console/Incoming.java	Fri Mar 25 00:13:37 2011 +0100
+++ b/cmdline/org/tmatesoft/hg/console/Incoming.java	Tue Mar 29 02:20:02 2011 +0200
@@ -18,11 +18,19 @@
 
 import static org.tmatesoft.hg.core.Nodeid.NULL;
 
+import java.util.Arrays;
 import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.Map.Entry;
+
+import junit.framework.Assert;
 
 import org.tmatesoft.hg.core.Nodeid;
 import org.tmatesoft.hg.repo.HgChangelog;
@@ -32,7 +40,7 @@
 
 /**
  * WORK IN PROGRESS, DO NOT USE
- * hg in counterpart
+ * hg incoming counterpart
  * 
  * @author Artem Tikhomirov
  * @author TMate Software Ltd.
@@ -40,6 +48,10 @@
 public class Incoming {
 
 	public static void main(String[] args) throws Exception {
+		if (Boolean.TRUE.booleanValue()) {
+			new SequenceConstructor().test();
+			return;
+		}
 		Options cmdLineOpts = Options.parse(args);
 		HgRepository hgRepo = cmdLineOpts.findRepository();
 		if (hgRepo.isInvalid()) {
@@ -178,4 +190,149 @@
 		return list;
 	}
 
+	private static class SequenceConstructor {
+
+		private int[] between(int root, int head) {
+			if (head <= (root+1)) {
+				return new int[0];
+			}
+			System.out.printf("[%d, %d]\t\t", root, head);
+			int size = 1 + (int) Math.floor(Math.log(head-root - 1) / Math.log(2));
+			int[] rv = new int[size];
+			for (int v = 1, i = 0; i < rv.length; i++) {
+				rv[i] = root + v;
+				v = v << 1;
+			}
+			System.out.println(Arrays.toString(rv));
+			return rv;
+		}
+
+		public void test() {
+			int root = 0, head = 1000;
+			int[] data = between(root, head); // max number of elements to recover is 2**(1+data.length)-1, need room for 
+			// as much elements, hence 2**(data.length+1). In worst case, when there are onlu 2**data.length + 1 missing element,
+			// almost half of the finalSequence would be empty
+			int[] finalSequence = new int[1 << (data.length+1) >>> 5]; // div 32 - total bits to integers
+			int exactNumberOfElements = -1; // exact number of meaningful bits in finalSequence
+			LinkedHashMap<Integer, int[]> datas = new LinkedHashMap<Integer, int[]>();
+			datas.put(root, data);
+			int totalQueries = 1;
+			HashSet<Integer> queried = new HashSet<Integer>();
+			int[] checkSequence = null;
+			while(!datas.isEmpty()) {
+				LinkedList<int[]> toQuery = new LinkedList<int[]>();
+				do {
+					Iterator<Entry<Integer, int[]>> it = datas.entrySet().iterator();
+					Entry<Integer, int[]> next = it.next();
+					int r = next.getKey();
+					data = next.getValue();
+					it.remove();
+					populate(r, head, data, finalSequence);
+					if (checkSequence != null) {
+						boolean match = true;
+//						System.out.println("Try to match:");
+						for (int i = 0; i < checkSequence.length; i++) {
+//							System.out.println(i);
+//							System.out.println("control:" + toBinaryString(checkSequence[i], ' '));
+//							System.out.println("present:" + toBinaryString(finalSequence[i], ' '));
+							if (checkSequence[i] != finalSequence[i]) {
+								match = false;
+							} else {
+								match &= true;
+							}
+						}
+						System.out.println(match ? "Match, on query:" + totalQueries : "Didn't match");
+					}
+					if (data.length > 2) { 
+						for (int x : data) {
+							if (!queried.contains(x) && head - x > 1) { /*queries for neighboring elements is senseless*/
+								toQuery.add(new int[] {x, head});
+							}
+						}
+					}
+				} while (!datas.isEmpty()) ;
+				if (!toQuery.isEmpty()) {
+					System.out.println();
+					totalQueries++;
+				}
+				Collections.sort(toQuery, new Comparator<int[]>() {
+
+					public int compare(int[] o1, int[] o2) {
+						return o1[0] < o2[0] ? -1 : (o1[0] == o2[0] ? 0 : 1);
+					}
+				});
+				for (int[] x : toQuery) {
+					if (!queried.contains(x[0])) {
+						queried.add(x[0]);
+						data = between(x[0], x[1]);
+						if (exactNumberOfElements == -1 && data.length == 1) {
+							exactNumberOfElements = x[0] + 1;
+							System.out.printf("On query %d found out exact number of missing elements: %d\n", totalQueries, exactNumberOfElements);
+							// get a bit sequence of exactNumberOfElements, 0111..110
+							// to 'and' it with finalSequence later
+							int totalInts = (exactNumberOfElements + 2 /*heading and tailing zero bits*/) >>> 5;
+							int trailingBits = (exactNumberOfElements + 2) & 0x1f;
+							if (trailingBits != 0) {
+								totalInts++;
+							}
+							checkSequence = new int[totalInts];
+							Arrays.fill(checkSequence, 0xffffffff);
+							checkSequence[0] &= 0x7FFFFFFF;
+							if (trailingBits == 0) {
+								checkSequence[totalInts-1] &= 0xFFFFFFFE;
+							} else if (trailingBits == 1) {
+								checkSequence[totalInts-1] = 0;
+							} else {
+								// trailingBits include heading and trailing zero bits
+								int mask = 0x80000000 >> trailingBits-2; // with sign!
+								checkSequence[totalInts - 1] &= mask;
+							}
+							for (int e : checkSequence) {
+								System.out.print(toBinaryString(e, ' '));
+							}
+							System.out.println();
+						}
+						datas.put(x[0], data);
+					}
+				}
+			}
+
+			System.out.println("Total queries:" + totalQueries);
+			for (int x : finalSequence) {
+				System.out.print(toBinaryString(x, ' '));
+			}
+		}
+		
+		private void populate(int root, int head, int[] data, int[] finalSequence) {
+			for (int i = 1, x = 0; root+i < head; i = i << 1, x++) {
+				int value = data[x];
+				int value_check = root+i;
+				Assert.assertEquals(value, value_check);
+				int wordIx = (root + i) >>> 5;
+				int bitIx = (root + i) & 0x1f;
+				finalSequence[wordIx] |= 1 << (31-bitIx);
+			}
+		}
+		
+		private static String toBinaryString(int x, char byteSeparator) {
+			StringBuilder sb = new StringBuilder(4*8+4);
+			sb.append(toBinaryString((byte) (x >>> 24)));
+			sb.append(byteSeparator);
+			sb.append(toBinaryString((byte) ((x & 0x00ff0000) >>> 16)));
+			sb.append(byteSeparator);
+			sb.append(toBinaryString((byte) ((x & 0x00ff00) >>> 8)));
+			sb.append(byteSeparator);
+			sb.append(toBinaryString((byte) (x & 0x00ff)));
+			sb.append(byteSeparator);
+			return sb.toString();
+		}
+
+		private static String toBinaryString(byte b) {
+			final String nibbles = "0000000100100011010001010110011110001001101010111100110111101111";
+			assert nibbles.length() == 16*4;
+			int x1 = (b >>> 4) & 0x0f, x2 = b & 0x0f;
+			x1 *= 4; x2 *= 4; // 4 characters per nibble
+			return nibbles.substring(x1, x1+4).concat(nibbles.substring(x2, x2+4));
+		}
+	}
 }