tikhomirov@648: /* tikhomirov@648: * Copyright (c) 2013 TMate Software Ltd tikhomirov@648: * tikhomirov@648: * This program is free software; you can redistribute it and/or modify tikhomirov@648: * it under the terms of the GNU General Public License as published by tikhomirov@648: * the Free Software Foundation; version 2 of the License. tikhomirov@648: * tikhomirov@648: * This program is distributed in the hope that it will be useful, tikhomirov@648: * but WITHOUT ANY WARRANTY; without even the implied warranty of tikhomirov@648: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the tikhomirov@648: * GNU General Public License for more details. tikhomirov@648: * tikhomirov@648: * For information on how to redistribute this software under tikhomirov@648: * the terms of a license other than GNU General Public License tikhomirov@648: * contact TMate Software at support@hg4j.com tikhomirov@648: */ tikhomirov@648: package org.tmatesoft.hg.internal; tikhomirov@648: tikhomirov@649: import java.util.ArrayList; tikhomirov@648: import java.util.Collection; tikhomirov@648: import java.util.Collections; tikhomirov@648: import java.util.HashSet; tikhomirov@649: import java.util.Iterator; tikhomirov@649: import java.util.List; tikhomirov@648: import java.util.Set; tikhomirov@648: tikhomirov@648: import org.tmatesoft.hg.core.Nodeid; tikhomirov@649: import org.tmatesoft.hg.repo.HgChangelog; tikhomirov@649: import org.tmatesoft.hg.repo.HgParentChildMap; tikhomirov@648: tikhomirov@648: /** tikhomirov@648: * Unmodifiable collection of revisions with handy set operations tikhomirov@648: * tikhomirov@648: * @author Artem Tikhomirov tikhomirov@648: * @author TMate Software Ltd. tikhomirov@648: */ tikhomirov@649: public final class RevisionSet implements Iterable { tikhomirov@648: tikhomirov@648: private final Set elements; tikhomirov@648: tikhomirov@648: public RevisionSet(Collection revisions) { tikhomirov@648: this(revisions == null ? new HashSet() : new HashSet(revisions)); tikhomirov@648: } tikhomirov@648: tikhomirov@648: private RevisionSet(HashSet revisions) { tikhomirov@648: if (revisions.isEmpty()) { tikhomirov@648: elements = Collections.emptySet(); tikhomirov@648: } else { tikhomirov@648: elements = revisions; tikhomirov@648: } tikhomirov@648: } tikhomirov@648: tikhomirov@649: /** tikhomirov@649: * elements of the set with no parents or parents not from the same set tikhomirov@649: */ tikhomirov@649: public RevisionSet roots(HgParentChildMap ph) { tikhomirov@649: HashSet copy = new HashSet(elements); tikhomirov@649: for (Nodeid n : elements) { tikhomirov@649: assert ph.knownNode(n); tikhomirov@649: Nodeid p1 = ph.firstParent(n); tikhomirov@649: if (p1 != null && elements.contains(p1)) { tikhomirov@649: copy.remove(n); tikhomirov@649: continue; tikhomirov@649: } tikhomirov@649: Nodeid p2 = ph.secondParent(n); tikhomirov@649: if (p2 != null && elements.contains(p2)) { tikhomirov@649: copy.remove(n); tikhomirov@649: continue; tikhomirov@649: } tikhomirov@649: } tikhomirov@649: return copy.size() == elements.size() ? this : new RevisionSet(copy); tikhomirov@648: } tikhomirov@648: tikhomirov@649: /** tikhomirov@649: * elements of the set that has no children in this set tikhomirov@649: */ tikhomirov@649: public RevisionSet heads(HgParentChildMap ph) { tikhomirov@649: HashSet copy = new HashSet(elements); tikhomirov@649: // can't do copy.removeAll(ph.childrenOf(asList())); as actual heads are indeed children of some other node tikhomirov@649: for (Nodeid n : elements) { tikhomirov@649: assert ph.knownNode(n); tikhomirov@649: Nodeid p1 = ph.firstParent(n); tikhomirov@649: Nodeid p2 = ph.secondParent(n); tikhomirov@649: if (p1 != null && elements.contains(p1)) { tikhomirov@649: copy.remove(p1); tikhomirov@649: } tikhomirov@649: if (p2 != null && elements.contains(p2)) { tikhomirov@649: copy.remove(p2); tikhomirov@649: } tikhomirov@649: } tikhomirov@649: return copy.size() == elements.size() ? this : new RevisionSet(copy); tikhomirov@649: } tikhomirov@649: tikhomirov@649: /** tikhomirov@651: * Any ancestor of an element from the supplied child set found in this one. tikhomirov@651: * Elements of the supplied child set are not part of return value. tikhomirov@649: */ tikhomirov@650: public RevisionSet ancestors(RevisionSet children, HgParentChildMap parentHelper) { tikhomirov@649: if (isEmpty()) { tikhomirov@649: return this; tikhomirov@649: } tikhomirov@649: if (children.isEmpty()) { tikhomirov@649: return children; tikhomirov@649: } tikhomirov@649: RevisionSet chRoots = children.roots(parentHelper); tikhomirov@650: HashSet ancestors = new HashSet(); tikhomirov@650: Set childrenToCheck = chRoots.elements; tikhomirov@650: while (!childrenToCheck.isEmpty()) { tikhomirov@650: HashSet nextRound = new HashSet(); tikhomirov@650: for (Nodeid n : childrenToCheck) { tikhomirov@650: Nodeid p1 = parentHelper.firstParent(n); tikhomirov@650: Nodeid p2 = parentHelper.secondParent(n); tikhomirov@650: if (p1 != null && elements.contains(p1)) { tikhomirov@650: nextRound.add(p1); tikhomirov@650: } tikhomirov@650: if (p2 != null && elements.contains(p2)) { tikhomirov@650: nextRound.add(p2); tikhomirov@650: } tikhomirov@649: } tikhomirov@650: ancestors.addAll(nextRound); tikhomirov@650: childrenToCheck = nextRound; tikhomirov@650: } tikhomirov@650: return new RevisionSet(ancestors); tikhomirov@650: } tikhomirov@650: tikhomirov@650: /** tikhomirov@650: * Revisions that are both direct and indirect children of elements of this revision set tikhomirov@650: * as known in supplied parent-child map tikhomirov@650: */ tikhomirov@650: public RevisionSet children(HgParentChildMap parentHelper) { tikhomirov@650: if (isEmpty()) { tikhomirov@650: return this; tikhomirov@649: } tikhomirov@650: List children = parentHelper.childrenOf(elements); tikhomirov@650: return new RevisionSet(new HashSet(children)); tikhomirov@648: } tikhomirov@648: tikhomirov@648: public RevisionSet intersect(RevisionSet other) { tikhomirov@648: if (isEmpty()) { tikhomirov@648: return this; tikhomirov@648: } tikhomirov@648: if (other.isEmpty()) { tikhomirov@648: return other; tikhomirov@648: } tikhomirov@648: HashSet copy = new HashSet(elements); tikhomirov@648: copy.retainAll(other.elements); tikhomirov@648: return copy.size() == elements.size() ? this : new RevisionSet(copy); tikhomirov@648: } tikhomirov@648: tikhomirov@648: public RevisionSet subtract(RevisionSet other) { tikhomirov@648: if (isEmpty() || other.isEmpty()) { tikhomirov@648: return this; tikhomirov@648: } tikhomirov@648: HashSet copy = new HashSet(elements); tikhomirov@648: copy.removeAll(other.elements); tikhomirov@648: return copy.size() == elements.size() ? this : new RevisionSet(copy); tikhomirov@648: } tikhomirov@648: tikhomirov@648: public RevisionSet union(RevisionSet other) { tikhomirov@648: if (isEmpty()) { tikhomirov@648: return other; tikhomirov@648: } tikhomirov@648: if (other.isEmpty()) { tikhomirov@648: return this; tikhomirov@648: } tikhomirov@648: HashSet copy = new HashSet(elements); tikhomirov@648: copy.addAll(other.elements); tikhomirov@648: return new RevisionSet(copy); tikhomirov@648: } tikhomirov@648: tikhomirov@648: /** tikhomirov@648: * A ^ B := (A\B).union(B\A) tikhomirov@648: * A ^ B := A.union(B) \ A.intersect(B) tikhomirov@648: */ tikhomirov@648: public RevisionSet symmetricDifference(RevisionSet other) { tikhomirov@648: if (isEmpty()) { tikhomirov@648: return this; tikhomirov@648: } tikhomirov@648: if (other.isEmpty()) { tikhomirov@648: return other; tikhomirov@648: } tikhomirov@648: HashSet copyA = new HashSet(elements); tikhomirov@648: HashSet copyB = new HashSet(other.elements); tikhomirov@648: copyA.removeAll(other.elements); tikhomirov@648: copyB.removeAll(elements); tikhomirov@648: copyA.addAll(copyB); tikhomirov@648: return new RevisionSet(copyA); tikhomirov@648: } tikhomirov@648: tikhomirov@648: public boolean isEmpty() { tikhomirov@648: return elements.isEmpty(); tikhomirov@648: } tikhomirov@648: tikhomirov@651: public int size() { tikhomirov@651: return elements.size(); tikhomirov@651: } tikhomirov@649: tikhomirov@649: public List asList() { tikhomirov@649: return new ArrayList(elements); tikhomirov@649: } tikhomirov@649: tikhomirov@649: public Iterator iterator() { tikhomirov@649: return elements.iterator(); tikhomirov@649: } tikhomirov@649: tikhomirov@648: @Override tikhomirov@648: public String toString() { tikhomirov@648: StringBuilder sb = new StringBuilder(); tikhomirov@648: sb.append('<'); tikhomirov@648: if (!isEmpty()) { tikhomirov@648: sb.append(elements.size()); tikhomirov@648: sb.append(':'); tikhomirov@648: } tikhomirov@648: for (Nodeid n : elements) { tikhomirov@648: sb.append(n.shortNotation()); tikhomirov@648: sb.append(','); tikhomirov@648: } tikhomirov@648: if (sb.length() > 1) { tikhomirov@648: sb.setCharAt(sb.length() - 1, '>'); tikhomirov@648: } else { tikhomirov@648: sb.append('>'); tikhomirov@648: } tikhomirov@648: return sb.toString(); tikhomirov@648: } tikhomirov@648: tikhomirov@648: @Override tikhomirov@648: public boolean equals(Object obj) { tikhomirov@648: if (false == obj instanceof RevisionSet) { tikhomirov@648: return false; tikhomirov@648: } tikhomirov@648: return elements.equals(((RevisionSet) obj).elements); tikhomirov@648: } tikhomirov@648: tikhomirov@648: @Override tikhomirov@648: public int hashCode() { tikhomirov@648: return elements.hashCode(); tikhomirov@648: } tikhomirov@648: }