Mercurial > jhg

comparison cmdline/org/tmatesoft/hg/console/Incoming.java @ 173:4bf061a7c001

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Test algorithm to build sequence of missing revisions
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Tue, 29 Mar 2011 02:20:02 +0200
parents 2c3e96674e2a
children b1de83ffa7f8
comparison
equal deleted inserted replaced
172:87f40938c9b2 173:4bf061a7c001
16 */ 16 */
17 package org.tmatesoft.hg.console; 17 package org.tmatesoft.hg.console;
18 18
19 import static org.tmatesoft.hg.core.Nodeid.NULL; 19 import static org.tmatesoft.hg.core.Nodeid.NULL;
20 20
21 import java.util.Arrays;
21 import java.util.Collection; 22 import java.util.Collection;
23 import java.util.Collections;
24 import java.util.Comparator;
22 import java.util.HashSet; 25 import java.util.HashSet;
26 import java.util.Iterator;
27 import java.util.LinkedHashMap;
23 import java.util.LinkedHashSet; 28 import java.util.LinkedHashSet;
24 import java.util.LinkedList; 29 import java.util.LinkedList;
25 import java.util.List; 30 import java.util.List;
31 import java.util.Map.Entry;
32
33 import junit.framework.Assert;
26 34
27 import org.tmatesoft.hg.core.Nodeid; 35 import org.tmatesoft.hg.core.Nodeid;
28 import org.tmatesoft.hg.repo.HgChangelog; 36 import org.tmatesoft.hg.repo.HgChangelog;
29 import org.tmatesoft.hg.repo.HgRemoteRepository.RemoteBranch; 37 import org.tmatesoft.hg.repo.HgRemoteRepository.RemoteBranch;
30 import org.tmatesoft.hg.repo.HgRepository; 38 import org.tmatesoft.hg.repo.HgRepository;
31 39
32 40
33 /** 41 /**
34 * WORK IN PROGRESS, DO NOT USE 42 * WORK IN PROGRESS, DO NOT USE
35 * hg in counterpart 43 * hg incoming counterpart
36 * 44 *
37 * @author Artem Tikhomirov 45 * @author Artem Tikhomirov
38 * @author TMate Software Ltd. 46 * @author TMate Software Ltd.
39 */ 47 */
40 public class Incoming { 48 public class Incoming {
41 49
42 public static void main(String[] args) throws Exception { 50 public static void main(String[] args) throws Exception {
51 if (Boolean.TRUE.booleanValue()) {
52 new SequenceConstructor().test();
53 return;
54 }
43 Options cmdLineOpts = Options.parse(args); 55 Options cmdLineOpts = Options.parse(args);
44 HgRepository hgRepo = cmdLineOpts.findRepository(); 56 HgRepository hgRepo = cmdLineOpts.findRepository();
45 if (hgRepo.isInvalid()) { 57 if (hgRepo.isInvalid()) {
46 System.err.printf("Can't find repository in: %s\n", hgRepo.getLocation()); 58 System.err.printf("Can't find repository in: %s\n", hgRepo.getLocation());
47 return; 59 return;
176 list.add(Nodeid.fromAscii(s.getBytes(), 0, 40)); 188 list.add(Nodeid.fromAscii(s.getBytes(), 0, 40));
177 } 189 }
178 return list; 190 return list;
179 } 191 }
180 192
193 private static class SequenceConstructor {
194
195 private int[] between(int root, int head) {
196 if (head <= (root+1)) {
197 return new int[0];
198 }
199 System.out.printf("[%d, %d]\t\t", root, head);
200 int size = 1 + (int) Math.floor(Math.log(head-root - 1) / Math.log(2));
201 int[] rv = new int[size];
202 for (int v = 1, i = 0; i < rv.length; i++) {
203 rv[i] = root + v;
204 v = v << 1;
205 }
206 System.out.println(Arrays.toString(rv));
207 return rv;
208 }
209
210 public void test() {
211 int root = 0, head = 1000;
212 int[] data = between(root, head); // max number of elements to recover is 2**(1+data.length)-1, need room for
213 // as much elements, hence 2**(data.length+1). In worst case, when there are onlu 2**data.length + 1 missing element,
214 // almost half of the finalSequence would be empty
215 int[] finalSequence = new int[1 << (data.length+1) >>> 5]; // div 32 - total bits to integers
216 int exactNumberOfElements = -1; // exact number of meaningful bits in finalSequence
217 LinkedHashMap<Integer, int[]> datas = new LinkedHashMap<Integer, int[]>();
218 datas.put(root, data);
219 int totalQueries = 1;
220 HashSet<Integer> queried = new HashSet<Integer>();
221 int[] checkSequence = null;
222 while(!datas.isEmpty()) {
223 LinkedList<int[]> toQuery = new LinkedList<int[]>();
224 do {
225 Iterator<Entry<Integer, int[]>> it = datas.entrySet().iterator();
226 Entry<Integer, int[]> next = it.next();
227 int r = next.getKey();
228 data = next.getValue();
229 it.remove();
230 populate(r, head, data, finalSequence);
231 if (checkSequence != null) {
232 boolean match = true;
233 // System.out.println("Try to match:");
234 for (int i = 0; i < checkSequence.length; i++) {
235 // System.out.println(i);
236 // System.out.println("control:" + toBinaryString(checkSequence[i], ' '));
237 // System.out.println("present:" + toBinaryString(finalSequence[i], ' '));
238 if (checkSequence[i] != finalSequence[i]) {
239 match = false;
240 } else {
241 match &= true;
242 }
243 }
244 System.out.println(match ? "Match, on query:" + totalQueries : "Didn't match");
245 }
246 if (data.length > 2) {
247 for (int x : data) {
248 if (!queried.contains(x) && head - x > 1) { /*queries for neighboring elements is senseless*/
249 toQuery.add(new int[] {x, head});
250 }
251 }
252 }
253 } while (!datas.isEmpty()) ;
254 if (!toQuery.isEmpty()) {
255 System.out.println();
256 totalQueries++;
257 }
258 Collections.sort(toQuery, new Comparator<int[]>() {
259
260 public int compare(int[] o1, int[] o2) {
261 return o1[0] < o2[0] ? -1 : (o1[0] == o2[0] ? 0 : 1);
262 }
263 });
264 for (int[] x : toQuery) {
265 if (!queried.contains(x[0])) {
266 queried.add(x[0]);
267 data = between(x[0], x[1]);
268 if (exactNumberOfElements == -1 && data.length == 1) {
269 exactNumberOfElements = x[0] + 1;
270 System.out.printf("On query %d found out exact number of missing elements: %d\n", totalQueries, exactNumberOfElements);
271 // get a bit sequence of exactNumberOfElements, 0111..110
272 // to 'and' it with finalSequence later
273 int totalInts = (exactNumberOfElements + 2 /*heading and tailing zero bits*/) >>> 5;
274 int trailingBits = (exactNumberOfElements + 2) & 0x1f;
275 if (trailingBits != 0) {
276 totalInts++;
277 }
278 checkSequence = new int[totalInts];
279 Arrays.fill(checkSequence, 0xffffffff);
280 checkSequence[0] &= 0x7FFFFFFF;
281 if (trailingBits == 0) {
282 checkSequence[totalInts-1] &= 0xFFFFFFFE;
283 } else if (trailingBits == 1) {
284 checkSequence[totalInts-1] = 0;
285 } else {
286 // trailingBits include heading and trailing zero bits
287 int mask = 0x80000000 >> trailingBits-2; // with sign!
288 checkSequence[totalInts - 1] &= mask;
289 }
290 for (int e : checkSequence) {
291 System.out.print(toBinaryString(e, ' '));
292 }
293 System.out.println();
294 }
295 datas.put(x[0], data);
296 }
297 }
298 }
299
300 System.out.println("Total queries:" + totalQueries);
301 for (int x : finalSequence) {
302 System.out.print(toBinaryString(x, ' '));
303 }
304 }
305
306 private void populate(int root, int head, int[] data, int[] finalSequence) {
307 for (int i = 1, x = 0; root+i < head; i = i << 1, x++) {
308 int value = data[x];
309 int value_check = root+i;
310 Assert.assertEquals(value, value_check);
311 int wordIx = (root + i) >>> 5;
312 int bitIx = (root + i) & 0x1f;
313 finalSequence[wordIx] |= 1 << (31-bitIx);
314 }
315 }
316
317 private static String toBinaryString(int x, char byteSeparator) {
318 StringBuilder sb = new StringBuilder(4*8+4);
319 sb.append(toBinaryString((byte) (x >>> 24)));
320 sb.append(byteSeparator);
321 sb.append(toBinaryString((byte) ((x & 0x00ff0000) >>> 16)));
322 sb.append(byteSeparator);
323 sb.append(toBinaryString((byte) ((x & 0x00ff00) >>> 8)));
324 sb.append(byteSeparator);
325 sb.append(toBinaryString((byte) (x & 0x00ff)));
326 sb.append(byteSeparator);
327 return sb.toString();
328 }
329
330 private static String toBinaryString(byte b) {
331 final String nibbles = "0000000100100011010001010110011110001001101010111100110111101111";
332 assert nibbles.length() == 16*4;
333 int x1 = (b >>> 4) & 0x0f, x2 = b & 0x0f;
334 x1 *= 4; x2 *= 4; // 4 characters per nibble
335 return nibbles.substring(x1, x1+4).concat(nibbles.substring(x2, x2+4));
336 }
337 }
181 } 338 }