tikhomirov@31: /* tikhomirov@74: * Copyright (c) 2011 TMate Software Ltd tikhomirov@74: * tikhomirov@74: * This program is free software; you can redistribute it and/or modify tikhomirov@74: * it under the terms of the GNU General Public License as published by tikhomirov@74: * the Free Software Foundation; version 2 of the License. tikhomirov@74: * tikhomirov@74: * This program is distributed in the hope that it will be useful, tikhomirov@74: * but WITHOUT ANY WARRANTY; without even the implied warranty of tikhomirov@74: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the tikhomirov@74: * GNU General Public License for more details. tikhomirov@74: * tikhomirov@74: * For information on how to redistribute this software under tikhomirov@74: * the terms of a license other than GNU General Public License tikhomirov@102: * contact TMate Software at support@hg4j.com tikhomirov@31: */ tikhomirov@74: package org.tmatesoft.hg.console; tikhomirov@31: tikhomirov@171: import static org.tmatesoft.hg.core.Nodeid.NULL; tikhomirov@171: tikhomirov@176: import java.io.File; tikhomirov@176: import java.net.URL; tikhomirov@178: import java.util.ArrayList; tikhomirov@173: import java.util.Arrays; tikhomirov@173: import java.util.Collections; tikhomirov@173: import java.util.Comparator; tikhomirov@177: import java.util.HashMap; tikhomirov@31: import java.util.HashSet; tikhomirov@173: import java.util.Iterator; tikhomirov@173: import java.util.LinkedHashMap; tikhomirov@31: import java.util.LinkedList; tikhomirov@31: import java.util.List; tikhomirov@178: import java.util.ListIterator; tikhomirov@177: import java.util.Map; tikhomirov@173: import java.util.Map.Entry; tikhomirov@173: tikhomirov@176: import org.tmatesoft.hg.core.HgBadStateException; tikhomirov@176: import org.tmatesoft.hg.core.HgException; tikhomirov@74: import org.tmatesoft.hg.core.Nodeid; tikhomirov@176: import org.tmatesoft.hg.internal.ConfigFile; tikhomirov@176: import org.tmatesoft.hg.internal.Internals; tikhomirov@97: import org.tmatesoft.hg.repo.HgChangelog; tikhomirov@176: import org.tmatesoft.hg.repo.HgLookup; tikhomirov@176: import org.tmatesoft.hg.repo.HgRemoteRepository; tikhomirov@177: import org.tmatesoft.hg.repo.HgRemoteRepository.Range; tikhomirov@171: import org.tmatesoft.hg.repo.HgRemoteRepository.RemoteBranch; tikhomirov@74: import org.tmatesoft.hg.repo.HgRepository; tikhomirov@74: tikhomirov@31: tikhomirov@31: /** tikhomirov@74: * WORK IN PROGRESS, DO NOT USE tikhomirov@173: * hg incoming counterpart tikhomirov@74: * tikhomirov@74: * @author Artem Tikhomirov tikhomirov@74: * @author TMate Software Ltd. tikhomirov@31: */ tikhomirov@31: public class Incoming { tikhomirov@31: tikhomirov@31: public static void main(String[] args) throws Exception { tikhomirov@176: if (Boolean.FALSE.booleanValue()) { tikhomirov@173: new SequenceConstructor().test(); tikhomirov@173: return; tikhomirov@173: } tikhomirov@74: Options cmdLineOpts = Options.parse(args); tikhomirov@74: HgRepository hgRepo = cmdLineOpts.findRepository(); tikhomirov@31: if (hgRepo.isInvalid()) { tikhomirov@31: System.err.printf("Can't find repository in: %s\n", hgRepo.getLocation()); tikhomirov@31: return; tikhomirov@31: } tikhomirov@176: String key = "svnkit"; tikhomirov@176: ConfigFile cfg = new Internals().newConfigFile(); tikhomirov@176: cfg.addLocation(new File(System.getProperty("user.home"), ".hgrc")); tikhomirov@176: String server = cfg.getSection("paths").get(key); tikhomirov@176: if (server == null) { tikhomirov@176: throw new HgException(String.format("Can't find server %s specification in the config", key)); tikhomirov@176: } tikhomirov@176: HgRemoteRepository hgRemote = new HgLookup().detect(new URL(server)); tikhomirov@176: // tikhomirov@31: // in fact, all we need from changelog is set of all nodeids. However, since ParentWalker reuses same Nodeids, it's not too expensive tikhomirov@31: // to reuse it here, XXX although later this may need to be refactored tikhomirov@98: final HgChangelog.ParentWalker pw = hgRepo.getChangelog().new ParentWalker(); tikhomirov@31: pw.init(); tikhomirov@31: // tikhomirov@178: List missingBranches0 = calculateMissingBranches(pw, hgRemote); tikhomirov@178: for (BranchChain bc : missingBranches0) { tikhomirov@178: bc.dump(); tikhomirov@178: tikhomirov@178: List missing = visitBranches(hgRemote, bc); tikhomirov@178: // Collections.reverse(missing); // useful to test output, from newer to older tikhomirov@178: for (Nodeid n : missing) { tikhomirov@178: if (pw.knownNode(n)) { tikhomirov@178: System.out.println("Erroneous to fetch:" + n); tikhomirov@178: } else { tikhomirov@178: System.out.println(n); tikhomirov@178: } tikhomirov@178: } tikhomirov@178: System.out.println("Branch done"); tikhomirov@31: } tikhomirov@178: tikhomirov@178: } tikhomirov@178: tikhomirov@178: private static class BranchChain { tikhomirov@178: // when we construct a chain, we know head which is missing locally, hence init it right away. tikhomirov@178: // as for root (branch unknown start), we might happen to have one locally, and need further digging to find out right branch start tikhomirov@178: public final Nodeid branchHead; tikhomirov@178: public Nodeid branchRoot; tikhomirov@178: // either of these can be null, or both. tikhomirov@178: // although RemoteBranch has either both parents null, or both non-null, when we construct a chain tikhomirov@178: // we might encounter that we locally know one of branch's parent, hence in the chain corresponding field will be blank. tikhomirov@178: public BranchChain p1; tikhomirov@178: public BranchChain p2; tikhomirov@178: tikhomirov@178: public BranchChain(Nodeid head) { tikhomirov@178: assert head != null; tikhomirov@178: branchHead = head; tikhomirov@178: } tikhomirov@178: public boolean isTerminal() { tikhomirov@178: return p1 == null || p2 == null; tikhomirov@178: } tikhomirov@178: tikhomirov@178: @Override tikhomirov@178: public String toString() { tikhomirov@178: return String.format("BranchChain [%s, %s]", branchRoot, branchHead); tikhomirov@178: } tikhomirov@178: void dump() { tikhomirov@178: System.out.println(toString()); tikhomirov@178: internalDump(" "); tikhomirov@178: } tikhomirov@178: void internalDump(String prefix) { tikhomirov@178: if (p1 != null) { tikhomirov@178: System.out.println(prefix + p1.toString()); tikhomirov@178: } tikhomirov@178: if (p2 != null) { tikhomirov@178: System.out.println(prefix + p2.toString()); tikhomirov@178: } tikhomirov@178: prefix += " "; tikhomirov@178: if (p1 != null) { tikhomirov@178: p1.internalDump(prefix); tikhomirov@178: } tikhomirov@178: if (p2 != null) { tikhomirov@178: p2.internalDump(prefix); tikhomirov@31: } tikhomirov@31: } tikhomirov@31: } tikhomirov@176: tikhomirov@178: private static List visitBranches(HgRemoteRepository hgRemote, BranchChain bc) throws HgException { tikhomirov@178: if (bc == null) { tikhomirov@178: return Collections.emptyList(); tikhomirov@178: } tikhomirov@178: List mine = completeBranch(hgRemote, bc.branchRoot, bc.branchHead); tikhomirov@178: if (bc.isTerminal()) { tikhomirov@178: return mine; tikhomirov@178: } tikhomirov@178: List parentBranch1 = visitBranches(hgRemote, bc.p1); tikhomirov@178: List parentBranch2 = visitBranches(hgRemote, bc.p2); tikhomirov@178: // merge tikhomirov@178: LinkedList merged = new LinkedList(); tikhomirov@178: ListIterator i1 = parentBranch1.listIterator(), i2 = parentBranch2.listIterator(); tikhomirov@178: while (i1.hasNext() && i2.hasNext()) { tikhomirov@178: Nodeid n1 = i1.next(); tikhomirov@178: Nodeid n2 = i2.next(); tikhomirov@178: if (n1.equals(n2)) { tikhomirov@178: merged.addLast(n1); tikhomirov@178: } else { tikhomirov@178: // first different => add both, and continue adding both tails sequentially tikhomirov@178: merged.add(n2); tikhomirov@178: merged.add(n1); tikhomirov@178: break; tikhomirov@178: } tikhomirov@178: } tikhomirov@178: // copy rest of second parent branch tikhomirov@178: while (i2.hasNext()) { tikhomirov@178: merged.add(i2.next()); tikhomirov@178: } tikhomirov@178: // copy rest of first parent branch tikhomirov@178: while (i1.hasNext()) { tikhomirov@178: merged.add(i1.next()); tikhomirov@178: } tikhomirov@31: // tikhomirov@178: ArrayList rv = new ArrayList(mine.size() + merged.size()); tikhomirov@178: rv.addAll(merged); tikhomirov@178: rv.addAll(mine); tikhomirov@178: return rv; tikhomirov@178: } tikhomirov@178: tikhomirov@178: // somewhat similar to Outgoing.findCommonWithRemote() tikhomirov@178: private static List calculateMissingBranches(HgChangelog.ParentWalker pwLocal, HgRemoteRepository hgRemote) throws HgException { tikhomirov@178: List remoteHeads = hgRemote.heads(); tikhomirov@178: LinkedList common = new LinkedList(); // these remotes are known in local tikhomirov@178: LinkedList toQuery = new LinkedList(); // these need further queries to find common tikhomirov@178: for (Nodeid rh : remoteHeads) { tikhomirov@178: if (pwLocal.knownNode(rh)) { tikhomirov@178: common.add(rh); tikhomirov@178: } else { tikhomirov@178: toQuery.add(rh); tikhomirov@178: } tikhomirov@178: } tikhomirov@178: if (toQuery.isEmpty()) { tikhomirov@178: return Collections.emptyList(); // no incoming changes tikhomirov@178: } tikhomirov@178: LinkedList branches2load = new LinkedList(); // return value tikhomirov@178: // detailed comments are in Outgoing.findCommonWithRemote tikhomirov@178: LinkedList checkUp2Head = new LinkedList(); tikhomirov@178: // records relation between branch head and its parent branch, if any tikhomirov@178: HashMap head2chain = new HashMap(); tikhomirov@178: while (!toQuery.isEmpty()) { tikhomirov@178: List remoteBranches = hgRemote.branches(toQuery); //head, root, first parent, second parent tikhomirov@178: toQuery.clear(); tikhomirov@178: while(!remoteBranches.isEmpty()) { tikhomirov@178: RemoteBranch rb = remoteBranches.remove(0); tikhomirov@178: BranchChain chainElement = head2chain.get(rb.head); tikhomirov@178: if (chainElement == null) { tikhomirov@178: chainElement = new BranchChain(rb.head); tikhomirov@178: // record this unknown branch to download later tikhomirov@178: branches2load.add(chainElement); tikhomirov@178: } tikhomirov@178: if (pwLocal.knownNode(rb.root)) { tikhomirov@178: // we known branch start, common head is somewhere in its descendants line tikhomirov@178: checkUp2Head.add(rb); tikhomirov@178: } else { tikhomirov@178: chainElement.branchRoot = rb.root; tikhomirov@178: // dig deeper in the history, if necessary tikhomirov@178: if (!NULL.equals(rb.p1) && !pwLocal.knownNode(rb.p1)) { tikhomirov@178: toQuery.add(rb.p1); tikhomirov@178: head2chain.put(rb.p1, chainElement.p1 = new BranchChain(rb.p1)); tikhomirov@178: } tikhomirov@178: if (!NULL.equals(rb.p2) && !pwLocal.knownNode(rb.p2)) { tikhomirov@178: toQuery.add(rb.p2); tikhomirov@178: head2chain.put(rb.p2, chainElement.p2 = new BranchChain(rb.p2)); tikhomirov@178: } tikhomirov@178: } tikhomirov@178: } tikhomirov@178: } tikhomirov@178: for (RemoteBranch rb : checkUp2Head) { tikhomirov@178: Nodeid h = rb.head; tikhomirov@178: Nodeid r = rb.root; tikhomirov@178: int watchdog = 1000; tikhomirov@178: BranchChain bc = head2chain.get(h); tikhomirov@178: assert bc != null; tikhomirov@178: // if we know branch root locally, there could be no parent branch chain elements. tikhomirov@178: assert bc.p1 == null; tikhomirov@178: assert bc.p2 == null; tikhomirov@178: do { tikhomirov@178: List between = hgRemote.between(h, r); tikhomirov@178: if (between.isEmpty()) { tikhomirov@178: bc.branchRoot = r; tikhomirov@178: break; tikhomirov@178: } else { tikhomirov@178: Collections.reverse(between); tikhomirov@178: for (Nodeid n : between) { tikhomirov@178: if (pwLocal.knownNode(n)) { tikhomirov@178: r = n; tikhomirov@178: } else { tikhomirov@178: h = n; tikhomirov@178: break; tikhomirov@178: } tikhomirov@178: } tikhomirov@178: Nodeid lastInBetween = between.get(between.size() - 1); tikhomirov@178: if (r.equals(lastInBetween)) { tikhomirov@178: bc.branchRoot = r; tikhomirov@178: break; tikhomirov@178: } else if (h.equals(lastInBetween)) { // the only chance for current head pointer to point to the sequence tail tikhomirov@178: // is when r is second from the between list end (iow, head,1,[2],4,8...,root) tikhomirov@178: bc.branchRoot = r; tikhomirov@178: break; tikhomirov@178: } tikhomirov@178: } tikhomirov@178: } while(--watchdog > 0); tikhomirov@178: if (watchdog == 0) { tikhomirov@178: throw new HgBadStateException(String.format("Can't narrow down branch [%s, %s]", rb.head.shortNotation(), rb.root.shortNotation())); tikhomirov@178: } tikhomirov@178: } tikhomirov@178: return branches2load; tikhomirov@31: } tikhomirov@31: tikhomirov@178: /** tikhomirov@178: * @return list of nodeids from branchRoot to branchHead, inclusive. IOW, first element of the list is always root of the branch tikhomirov@178: */ tikhomirov@178: private static List completeBranch(HgRemoteRepository hgRemote, final Nodeid branchRoot, final Nodeid branchHead) throws HgException { tikhomirov@176: class DataEntry { tikhomirov@176: public final Nodeid queryHead; tikhomirov@176: public final int headIndex; tikhomirov@176: public List entries; tikhomirov@31: tikhomirov@176: public DataEntry(Nodeid head, int index, List data) { tikhomirov@176: queryHead = head; tikhomirov@176: headIndex = index; tikhomirov@176: entries = data; tikhomirov@176: } tikhomirov@176: }; tikhomirov@176: tikhomirov@178: List initial = hgRemote.between(branchHead, branchRoot); tikhomirov@178: Nodeid[] result = new Nodeid[1 + (1 << initial.size())]; tikhomirov@178: result[0] = branchHead; tikhomirov@176: int rootIndex = -1; // index in the result, where to place branche's root. tikhomirov@178: if (initial.isEmpty()) { tikhomirov@178: rootIndex = 1; tikhomirov@178: } else if (initial.size() == 1) { tikhomirov@178: rootIndex = 2; tikhomirov@178: } tikhomirov@176: LinkedList datas = new LinkedList(); tikhomirov@176: // DataEntry in datas has entries list filled with 'between' data, whereas tikhomirov@176: // DataEntry in toQuery keeps only nodeid and its index, with entries to be initialized before tikhomirov@176: // moving to datas. tikhomirov@176: LinkedList toQuery = new LinkedList(); tikhomirov@176: // tikhomirov@178: datas.add(new DataEntry(branchHead, 0, initial)); tikhomirov@176: int totalQueries = 1; tikhomirov@176: HashSet queried = new HashSet(); tikhomirov@176: while(!datas.isEmpty()) { tikhomirov@177: // keep record of those planned to be queried next time we call between() tikhomirov@177: // although may keep these in queried, if really don't want separate collection tikhomirov@177: HashSet scheduled = new HashSet(); tikhomirov@176: do { tikhomirov@176: DataEntry de = datas.removeFirst(); tikhomirov@176: // populate result with discovered elements between de.qiueryRoot and branch's head tikhomirov@176: for (int i = 1, j = 0; j < de.entries.size(); i = i << 1, j++) { tikhomirov@176: int idx = de.headIndex + i; tikhomirov@176: result[idx] = de.entries.get(j); tikhomirov@176: } tikhomirov@176: // form next query entries from new unknown elements tikhomirov@176: if (de.entries.size() > 1) { tikhomirov@176: /* when entries has only one element, it means de.queryRoot was at head-2 position, and thus tikhomirov@176: * no new information can be obtained. E.g. when it's 2, it might be case of [0..4] query with tikhomirov@176: * [1,2] result, and we need one more query to get element 3. tikhomirov@176: */ tikhomirov@176: for (int i =1, j = 0; j < de.entries.size(); i = i<<1, j++) { tikhomirov@176: int idx = de.headIndex + i; tikhomirov@176: Nodeid x = de.entries.get(j); tikhomirov@177: if (!queried.contains(x) && !scheduled.contains(x) && (rootIndex == -1 || rootIndex - de.headIndex > 1)) { tikhomirov@176: /*queries for elements right before head is senseless, but unless we know head's index, do it anyway*/ tikhomirov@176: toQuery.add(new DataEntry(x, idx, null)); tikhomirov@177: scheduled.add(x); tikhomirov@176: } tikhomirov@176: } tikhomirov@176: } tikhomirov@176: } while (!datas.isEmpty()); tikhomirov@176: if (!toQuery.isEmpty()) { tikhomirov@176: totalQueries++; tikhomirov@176: } tikhomirov@177: // for each query, create an between request range, keep record Range->DataEntry to know range's start index tikhomirov@177: LinkedList betweenBatch = new LinkedList(); tikhomirov@177: HashMap rangeToEntry = new HashMap(); tikhomirov@176: for (DataEntry de : toQuery) { tikhomirov@177: queried.add(de.queryHead); tikhomirov@178: HgRemoteRepository.Range r = new HgRemoteRepository.Range(branchRoot, de.queryHead); tikhomirov@177: betweenBatch.add(r); tikhomirov@177: rangeToEntry.put(r, de); tikhomirov@177: } tikhomirov@177: if (!betweenBatch.isEmpty()) { tikhomirov@177: Map> between = hgRemote.between(betweenBatch); tikhomirov@177: for (Entry> e : between.entrySet()) { tikhomirov@177: DataEntry de = rangeToEntry.get(e.getKey()); tikhomirov@177: assert de != null; tikhomirov@177: de.entries = e.getValue(); tikhomirov@177: if (rootIndex == -1 && de.entries.size() == 1) { tikhomirov@176: // returned sequence of length 1 means we used element from [head-2] as root tikhomirov@176: int numberOfElementsExcludingRootAndHead = de.headIndex + 1; tikhomirov@176: rootIndex = numberOfElementsExcludingRootAndHead + 1; tikhomirov@176: System.out.printf("On query %d found out exact number of missing elements: %d\n", totalQueries, numberOfElementsExcludingRootAndHead); tikhomirov@176: } tikhomirov@176: datas.add(de); // queue up to record result and construct further requests tikhomirov@176: } tikhomirov@177: betweenBatch.clear(); tikhomirov@177: rangeToEntry.clear(); tikhomirov@176: } tikhomirov@176: toQuery.clear(); tikhomirov@31: } tikhomirov@176: if (rootIndex == -1) { tikhomirov@176: throw new HgBadStateException("Shall not happen, provided between output is correct"); // FIXME tikhomirov@31: } tikhomirov@178: result[rootIndex] = branchRoot; tikhomirov@176: boolean resultOk = true; tikhomirov@176: LinkedList fromRootToHead = new LinkedList(); tikhomirov@176: for (int i = 0; i <= rootIndex; i++) { tikhomirov@176: Nodeid n = result[i]; tikhomirov@176: if (n == null) { tikhomirov@176: System.out.printf("ERROR: element %d wasn't found\n",i); tikhomirov@176: resultOk = false; tikhomirov@176: } tikhomirov@176: fromRootToHead.addFirst(n); // reverse order tikhomirov@31: } tikhomirov@177: System.out.println("Total queries:" + totalQueries); tikhomirov@176: if (!resultOk) { tikhomirov@176: throw new HgBadStateException("See console for details"); // FIXME tikhomirov@176: } tikhomirov@176: return fromRootToHead; tikhomirov@31: } tikhomirov@31: tikhomirov@173: private static class SequenceConstructor { tikhomirov@173: tikhomirov@173: private int[] between(int root, int head) { tikhomirov@173: if (head <= (root+1)) { tikhomirov@173: return new int[0]; tikhomirov@173: } tikhomirov@173: System.out.printf("[%d, %d]\t\t", root, head); tikhomirov@173: int size = 1 + (int) Math.floor(Math.log(head-root - 1) / Math.log(2)); tikhomirov@173: int[] rv = new int[size]; tikhomirov@173: for (int v = 1, i = 0; i < rv.length; i++) { tikhomirov@173: rv[i] = root + v; tikhomirov@173: v = v << 1; tikhomirov@173: } tikhomirov@173: System.out.println(Arrays.toString(rv)); tikhomirov@173: return rv; tikhomirov@173: } tikhomirov@173: tikhomirov@173: public void test() { tikhomirov@176: int root = 0, head = 126; tikhomirov@176: int[] data = between(root, head); // max number of elements to recover is 2**data.length-1, when head is exactly tikhomirov@176: // 2**data.length element of the branch. tikhomirov@176: // In such case, total number of elements in the branch (including head and root, would be 2**data.length+1 tikhomirov@176: int[] finalSequence = new int[1 + (1 << data.length >>> 5)]; // div 32 - total bits to integers, +1 for possible modulus tikhomirov@173: int exactNumberOfElements = -1; // exact number of meaningful bits in finalSequence tikhomirov@173: LinkedHashMap datas = new LinkedHashMap(); tikhomirov@173: datas.put(root, data); tikhomirov@173: int totalQueries = 1; tikhomirov@173: HashSet queried = new HashSet(); tikhomirov@173: int[] checkSequence = null; tikhomirov@173: while(!datas.isEmpty()) { tikhomirov@173: LinkedList toQuery = new LinkedList(); tikhomirov@173: do { tikhomirov@173: Iterator> it = datas.entrySet().iterator(); tikhomirov@173: Entry next = it.next(); tikhomirov@173: int r = next.getKey(); tikhomirov@173: data = next.getValue(); tikhomirov@173: it.remove(); tikhomirov@173: populate(r, head, data, finalSequence); tikhomirov@173: if (checkSequence != null) { tikhomirov@173: boolean match = true; tikhomirov@173: // System.out.println("Try to match:"); tikhomirov@173: for (int i = 0; i < checkSequence.length; i++) { tikhomirov@173: // System.out.println(i); tikhomirov@173: // System.out.println("control:" + toBinaryString(checkSequence[i], ' ')); tikhomirov@173: // System.out.println("present:" + toBinaryString(finalSequence[i], ' ')); tikhomirov@173: if (checkSequence[i] != finalSequence[i]) { tikhomirov@173: match = false; tikhomirov@173: } else { tikhomirov@173: match &= true; tikhomirov@173: } tikhomirov@173: } tikhomirov@173: System.out.println(match ? "Match, on query:" + totalQueries : "Didn't match"); tikhomirov@173: } tikhomirov@176: if (data.length > 1) { tikhomirov@176: /*queries for elements next to head is senseless, hence data.length check above and head-x below*/ tikhomirov@173: for (int x : data) { tikhomirov@176: if (!queried.contains(x) && head - x > 1) { tikhomirov@173: toQuery.add(new int[] {x, head}); tikhomirov@173: } tikhomirov@173: } tikhomirov@173: } tikhomirov@173: } while (!datas.isEmpty()) ; tikhomirov@173: if (!toQuery.isEmpty()) { tikhomirov@173: System.out.println(); tikhomirov@173: totalQueries++; tikhomirov@173: } tikhomirov@173: Collections.sort(toQuery, new Comparator() { tikhomirov@173: tikhomirov@173: public int compare(int[] o1, int[] o2) { tikhomirov@173: return o1[0] < o2[0] ? -1 : (o1[0] == o2[0] ? 0 : 1); tikhomirov@173: } tikhomirov@173: }); tikhomirov@173: for (int[] x : toQuery) { tikhomirov@173: if (!queried.contains(x[0])) { tikhomirov@173: queried.add(x[0]); tikhomirov@173: data = between(x[0], x[1]); tikhomirov@173: if (exactNumberOfElements == -1 && data.length == 1) { tikhomirov@173: exactNumberOfElements = x[0] + 1; tikhomirov@173: System.out.printf("On query %d found out exact number of missing elements: %d\n", totalQueries, exactNumberOfElements); tikhomirov@173: // get a bit sequence of exactNumberOfElements, 0111..110 tikhomirov@173: // to 'and' it with finalSequence later tikhomirov@173: int totalInts = (exactNumberOfElements + 2 /*heading and tailing zero bits*/) >>> 5; tikhomirov@173: int trailingBits = (exactNumberOfElements + 2) & 0x1f; tikhomirov@173: if (trailingBits != 0) { tikhomirov@173: totalInts++; tikhomirov@173: } tikhomirov@173: checkSequence = new int[totalInts]; tikhomirov@173: Arrays.fill(checkSequence, 0xffffffff); tikhomirov@173: checkSequence[0] &= 0x7FFFFFFF; tikhomirov@173: if (trailingBits == 0) { tikhomirov@173: checkSequence[totalInts-1] &= 0xFFFFFFFE; tikhomirov@173: } else if (trailingBits == 1) { tikhomirov@173: checkSequence[totalInts-1] = 0; tikhomirov@173: } else { tikhomirov@173: // trailingBits include heading and trailing zero bits tikhomirov@173: int mask = 0x80000000 >> trailingBits-2; // with sign! tikhomirov@173: checkSequence[totalInts - 1] &= mask; tikhomirov@173: } tikhomirov@173: for (int e : checkSequence) { tikhomirov@173: System.out.print(toBinaryString(e, ' ')); tikhomirov@173: } tikhomirov@173: System.out.println(); tikhomirov@173: } tikhomirov@173: datas.put(x[0], data); tikhomirov@173: } tikhomirov@173: } tikhomirov@173: } tikhomirov@173: tikhomirov@173: System.out.println("Total queries:" + totalQueries); tikhomirov@173: for (int x : finalSequence) { tikhomirov@173: System.out.print(toBinaryString(x, ' ')); tikhomirov@173: } tikhomirov@173: } tikhomirov@173: tikhomirov@173: private void populate(int root, int head, int[] data, int[] finalSequence) { tikhomirov@173: for (int i = 1, x = 0; root+i < head; i = i << 1, x++) { tikhomirov@173: int value = data[x]; tikhomirov@173: int value_check = root+i; tikhomirov@174: if (value != value_check) { tikhomirov@174: throw new IllegalStateException(); tikhomirov@174: } tikhomirov@173: int wordIx = (root + i) >>> 5; tikhomirov@173: int bitIx = (root + i) & 0x1f; tikhomirov@173: finalSequence[wordIx] |= 1 << (31-bitIx); tikhomirov@173: } tikhomirov@173: } tikhomirov@173: tikhomirov@173: private static String toBinaryString(int x, char byteSeparator) { tikhomirov@173: StringBuilder sb = new StringBuilder(4*8+4); tikhomirov@173: sb.append(toBinaryString((byte) (x >>> 24))); tikhomirov@173: sb.append(byteSeparator); tikhomirov@173: sb.append(toBinaryString((byte) ((x & 0x00ff0000) >>> 16))); tikhomirov@173: sb.append(byteSeparator); tikhomirov@173: sb.append(toBinaryString((byte) ((x & 0x00ff00) >>> 8))); tikhomirov@173: sb.append(byteSeparator); tikhomirov@173: sb.append(toBinaryString((byte) (x & 0x00ff))); tikhomirov@173: sb.append(byteSeparator); tikhomirov@173: return sb.toString(); tikhomirov@173: } tikhomirov@173: tikhomirov@173: private static String toBinaryString(byte b) { tikhomirov@173: final String nibbles = "0000000100100011010001010110011110001001101010111100110111101111"; tikhomirov@173: assert nibbles.length() == 16*4; tikhomirov@173: int x1 = (b >>> 4) & 0x0f, x2 = b & 0x0f; tikhomirov@173: x1 *= 4; x2 *= 4; // 4 characters per nibble tikhomirov@173: return nibbles.substring(x1, x1+4).concat(nibbles.substring(x2, x2+4)); tikhomirov@173: } tikhomirov@173: } tikhomirov@31: }