Mercurial > jhg
annotate hg4j-cli/src/main/java/org/tmatesoft/hg/console/Incoming.java @ 213:6ec4af642ba8 gradle
Project uses Gradle for build - actual changes
author | Alexander Kitaev <kitaev@gmail.com> |
---|---|
date | Tue, 10 May 2011 10:52:53 +0200 |
parents | |
children |
rev | line source |
---|---|
213
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
1 /* |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
2 * Copyright (c) 2011 TMate Software Ltd |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
3 * |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
4 * This program is free software; you can redistribute it and/or modify |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
5 * it under the terms of the GNU General Public License as published by |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
6 * the Free Software Foundation; version 2 of the License. |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
7 * |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
8 * This program is distributed in the hope that it will be useful, |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
11 * GNU General Public License for more details. |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
12 * |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
13 * For information on how to redistribute this software under |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
14 * the terms of a license other than GNU General Public License |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
15 * contact TMate Software at support@hg4j.com |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
16 */ |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
17 package org.tmatesoft.hg.console; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
18 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
19 import java.util.Arrays; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
20 import java.util.Collections; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
21 import java.util.Comparator; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
22 import java.util.HashSet; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
23 import java.util.Iterator; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
24 import java.util.LinkedHashMap; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
25 import java.util.LinkedList; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
26 import java.util.List; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
27 import java.util.Map.Entry; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
28 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
29 import org.tmatesoft.hg.core.HgIncomingCommand; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
30 import org.tmatesoft.hg.core.HgRepoFacade; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
31 import org.tmatesoft.hg.core.Nodeid; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
32 import org.tmatesoft.hg.repo.HgLookup; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
33 import org.tmatesoft.hg.repo.HgRemoteRepository; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
34 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
35 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
36 /** |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
37 * <em>hg incoming</em> counterpart |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
38 * |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
39 * @author Artem Tikhomirov |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
40 * @author TMate Software Ltd. |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
41 */ |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
42 public class Incoming { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
43 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
44 public static void main(String[] args) throws Exception { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
45 if (Boolean.FALSE.booleanValue()) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
46 new SequenceConstructor().test(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
47 return; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
48 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
49 Options cmdLineOpts = Options.parse(args); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
50 HgRepoFacade hgRepo = new HgRepoFacade(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
51 if (!hgRepo.init(cmdLineOpts.findRepository())) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
52 System.err.printf("Can't find repository in: %s\n", hgRepo.getRepository().getLocation()); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
53 return; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
54 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
55 HgRemoteRepository hgRemote = new HgLookup().detectRemote(cmdLineOpts.getSingle(""), hgRepo.getRepository()); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
56 if (hgRemote.isInvalid()) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
57 System.err.printf("Remote repository %s is not valid", hgRemote.getLocation()); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
58 return; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
59 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
60 HgIncomingCommand cmd = hgRepo.createIncomingCommand(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
61 cmd.against(hgRemote); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
62 // |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
63 List<Nodeid> missing = cmd.executeLite(null); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
64 Collections.reverse(missing); // useful to test output, from newer to older |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
65 Outgoing.dump("Nodes to fetch:", missing); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
66 System.out.printf("Total: %d\n\n", missing.size()); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
67 // |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
68 // Complete |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
69 final ChangesetDumpHandler h = new ChangesetDumpHandler(hgRepo.getRepository()); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
70 h.complete(false); // this option looks up index of parent revision, done via repo.changelog (which doesn't have any of these new revisions) |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
71 // this can be fixed by tracking all nodeid->revision idx inside ChangesetDumpHandler, and refer to repo.changelog only when that mapping didn't work |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
72 h.verbose(cmdLineOpts.getBoolean("-v", "--verbose")); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
73 cmd.executeFull(h); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
74 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
75 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
76 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
77 /* |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
78 * This is for investigation purposes only |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
79 */ |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
80 private static class SequenceConstructor { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
81 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
82 private int[] between(int root, int head) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
83 if (head <= (root+1)) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
84 return new int[0]; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
85 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
86 System.out.printf("[%d, %d]\t\t", root, head); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
87 int size = 1 + (int) Math.floor(Math.log(head-root - 1) / Math.log(2)); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
88 int[] rv = new int[size]; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
89 for (int v = 1, i = 0; i < rv.length; i++) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
90 rv[i] = root + v; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
91 v = v << 1; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
92 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
93 System.out.println(Arrays.toString(rv)); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
94 return rv; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
95 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
96 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
97 public void test() { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
98 int root = 0, head = 126; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
99 int[] data = between(root, head); // max number of elements to recover is 2**data.length-1, when head is exactly |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
100 // 2**data.length element of the branch. |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
101 // In such case, total number of elements in the branch (including head and root, would be 2**data.length+1 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
102 int[] finalSequence = new int[1 + (1 << data.length >>> 5)]; // div 32 - total bits to integers, +1 for possible modulus |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
103 int exactNumberOfElements = -1; // exact number of meaningful bits in finalSequence |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
104 LinkedHashMap<Integer, int[]> datas = new LinkedHashMap<Integer, int[]>(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
105 datas.put(root, data); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
106 int totalQueries = 1; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
107 HashSet<Integer> queried = new HashSet<Integer>(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
108 int[] checkSequence = null; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
109 while(!datas.isEmpty()) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
110 LinkedList<int[]> toQuery = new LinkedList<int[]>(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
111 do { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
112 Iterator<Entry<Integer, int[]>> it = datas.entrySet().iterator(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
113 Entry<Integer, int[]> next = it.next(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
114 int r = next.getKey(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
115 data = next.getValue(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
116 it.remove(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
117 populate(r, head, data, finalSequence); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
118 if (checkSequence != null) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
119 boolean match = true; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
120 // System.out.println("Try to match:"); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
121 for (int i = 0; i < checkSequence.length; i++) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
122 // System.out.println(i); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
123 // System.out.println("control:" + toBinaryString(checkSequence[i], ' ')); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
124 // System.out.println("present:" + toBinaryString(finalSequence[i], ' ')); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
125 if (checkSequence[i] != finalSequence[i]) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
126 match = false; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
127 } else { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
128 match &= true; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
129 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
130 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
131 System.out.println(match ? "Match, on query:" + totalQueries : "Didn't match"); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
132 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
133 if (data.length > 1) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
134 /*queries for elements next to head is senseless, hence data.length check above and head-x below*/ |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
135 for (int x : data) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
136 if (!queried.contains(x) && head - x > 1) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
137 toQuery.add(new int[] {x, head}); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
138 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
139 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
140 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
141 } while (!datas.isEmpty()) ; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
142 if (!toQuery.isEmpty()) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
143 System.out.println(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
144 totalQueries++; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
145 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
146 Collections.sort(toQuery, new Comparator<int[]>() { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
147 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
148 public int compare(int[] o1, int[] o2) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
149 return o1[0] < o2[0] ? -1 : (o1[0] == o2[0] ? 0 : 1); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
150 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
151 }); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
152 for (int[] x : toQuery) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
153 if (!queried.contains(x[0])) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
154 queried.add(x[0]); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
155 data = between(x[0], x[1]); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
156 if (exactNumberOfElements == -1 && data.length == 1) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
157 exactNumberOfElements = x[0] + 1; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
158 System.out.printf("On query %d found out exact number of missing elements: %d\n", totalQueries, exactNumberOfElements); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
159 // get a bit sequence of exactNumberOfElements, 0111..110 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
160 // to 'and' it with finalSequence later |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
161 int totalInts = (exactNumberOfElements + 2 /*heading and tailing zero bits*/) >>> 5; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
162 int trailingBits = (exactNumberOfElements + 2) & 0x1f; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
163 if (trailingBits != 0) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
164 totalInts++; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
165 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
166 checkSequence = new int[totalInts]; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
167 Arrays.fill(checkSequence, 0xffffffff); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
168 checkSequence[0] &= 0x7FFFFFFF; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
169 if (trailingBits == 0) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
170 checkSequence[totalInts-1] &= 0xFFFFFFFE; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
171 } else if (trailingBits == 1) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
172 checkSequence[totalInts-1] = 0; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
173 } else { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
174 // trailingBits include heading and trailing zero bits |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
175 int mask = 0x80000000 >> trailingBits-2; // with sign! |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
176 checkSequence[totalInts - 1] &= mask; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
177 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
178 for (int e : checkSequence) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
179 System.out.print(toBinaryString(e, ' ')); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
180 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
181 System.out.println(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
182 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
183 datas.put(x[0], data); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
184 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
185 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
186 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
187 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
188 System.out.println("Total queries:" + totalQueries); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
189 for (int x : finalSequence) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
190 System.out.print(toBinaryString(x, ' ')); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
191 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
192 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
193 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
194 private void populate(int root, int head, int[] data, int[] finalSequence) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
195 for (int i = 1, x = 0; root+i < head; i = i << 1, x++) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
196 int value = data[x]; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
197 int value_check = root+i; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
198 if (value != value_check) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
199 throw new IllegalStateException(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
200 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
201 int wordIx = (root + i) >>> 5; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
202 int bitIx = (root + i) & 0x1f; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
203 finalSequence[wordIx] |= 1 << (31-bitIx); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
204 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
205 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
206 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
207 private static String toBinaryString(int x, char byteSeparator) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
208 StringBuilder sb = new StringBuilder(4*8+4); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
209 sb.append(toBinaryString((byte) (x >>> 24))); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
210 sb.append(byteSeparator); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
211 sb.append(toBinaryString((byte) ((x & 0x00ff0000) >>> 16))); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
212 sb.append(byteSeparator); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
213 sb.append(toBinaryString((byte) ((x & 0x00ff00) >>> 8))); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
214 sb.append(byteSeparator); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
215 sb.append(toBinaryString((byte) (x & 0x00ff))); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
216 sb.append(byteSeparator); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
217 return sb.toString(); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
218 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
219 |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
220 private static String toBinaryString(byte b) { |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
221 final String nibbles = "0000000100100011010001010110011110001001101010111100110111101111"; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
222 assert nibbles.length() == 16*4; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
223 int x1 = (b >>> 4) & 0x0f, x2 = b & 0x0f; |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
224 x1 *= 4; x2 *= 4; // 4 characters per nibble |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
225 return nibbles.substring(x1, x1+4).concat(nibbles.substring(x2, x2+4)); |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
226 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
227 } |
6ec4af642ba8
Project uses Gradle for build - actual changes
Alexander Kitaev <kitaev@gmail.com>
parents:
diff
changeset
|
228 } |