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@652: import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION;
tikhomirov@652: 
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@652: import org.tmatesoft.hg.repo.HgRepository;
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<Nodeid> {
tikhomirov@648: 	
tikhomirov@648: 	private final Set<Nodeid> elements;
tikhomirov@648: 	
tikhomirov@648: 	public RevisionSet(Collection<Nodeid> revisions) {
tikhomirov@648: 		this(revisions == null ? new HashSet<Nodeid>() : new HashSet<Nodeid>(revisions));
tikhomirov@648: 	}
tikhomirov@648: 	
tikhomirov@648: 	private RevisionSet(HashSet<Nodeid> revisions) {
tikhomirov@648: 		if (revisions.isEmpty()) {
tikhomirov@648: 			elements = Collections.<Nodeid>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<HgChangelog> ph) {
tikhomirov@649: 		HashSet<Nodeid> copy = new HashSet<Nodeid>(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@652: 	 * Same as {@link #roots(HgParentChildMap)}, but doesn't require a parent-child map
tikhomirov@652: 	 */
tikhomirov@652: 	public RevisionSet roots(HgRepository repo) {
tikhomirov@652: 		// TODO introduce parent access interface, use it here, provide implementations 
tikhomirov@652: 		// that delegate to HgParentChildMap or HgRepository
tikhomirov@652: 		HashSet<Nodeid> copy = new HashSet<Nodeid>(elements);
tikhomirov@652: 		final HgChangelog clog = repo.getChangelog();
tikhomirov@652: 		byte[] parent1 = new byte[Nodeid.SIZE], parent2 = new byte[Nodeid.SIZE];
tikhomirov@652: 		int[] parentRevs = new int[2];
tikhomirov@652: 		for (Nodeid n : elements) {
tikhomirov@652: 			assert clog.isKnown(n);
tikhomirov@652: 			clog.parents(clog.getRevisionIndex(n), parentRevs, parent1, parent2);
tikhomirov@652: 			if (parentRevs[0] != NO_REVISION && elements.contains(new Nodeid(parent1, false))) {
tikhomirov@652: 				copy.remove(n);
tikhomirov@652: 				continue;
tikhomirov@652: 			}
tikhomirov@652: 			if (parentRevs[1] != NO_REVISION && elements.contains(new Nodeid(parent2, false))) {
tikhomirov@652: 				copy.remove(n);
tikhomirov@652: 				continue;
tikhomirov@652: 			}
tikhomirov@652: 		}
tikhomirov@652: 		return copy.size() == elements.size() ? this : new RevisionSet(copy);
tikhomirov@652: 	}
tikhomirov@652: 	
tikhomirov@652: 	/**
tikhomirov@649: 	 * elements of the set that has no children in this set 
tikhomirov@649: 	 */
tikhomirov@649: 	public RevisionSet heads(HgParentChildMap<HgChangelog> ph) {
tikhomirov@649: 		HashSet<Nodeid> copy = new HashSet<Nodeid>(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<HgChangelog> 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<Nodeid> ancestors = new HashSet<Nodeid>();
tikhomirov@650: 		Set<Nodeid> childrenToCheck = chRoots.elements;
tikhomirov@650: 		while (!childrenToCheck.isEmpty()) {
tikhomirov@650: 			HashSet<Nodeid> nextRound = new HashSet<Nodeid>();
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<HgChangelog> parentHelper) {
tikhomirov@650: 		if (isEmpty()) {
tikhomirov@650: 			return this;
tikhomirov@649: 		}
tikhomirov@650: 		List<Nodeid> children = parentHelper.childrenOf(elements);
tikhomirov@650: 		return new RevisionSet(new HashSet<Nodeid>(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<Nodeid> copy = new HashSet<Nodeid>(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<Nodeid> copy = new HashSet<Nodeid>(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<Nodeid> copy = new HashSet<Nodeid>(elements);
tikhomirov@648: 		copy.addAll(other.elements);
tikhomirov@652: 		return copy.size() == elements.size() ? this : 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<Nodeid> copyA = new HashSet<Nodeid>(elements);
tikhomirov@648: 		HashSet<Nodeid> copyB = new HashSet<Nodeid>(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<Nodeid> asList() {
tikhomirov@649: 		return new ArrayList<Nodeid>(elements);
tikhomirov@649: 	}
tikhomirov@649: 	
tikhomirov@649: 	public Iterator<Nodeid> 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: }