Mercurial > hg4j

annotate hg4j-cli/src/main/java/org/tmatesoft/hg/console/Incoming.java @ 213:6ec4af642ba8 gradle

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }