tikhomirov@558: /*
tikhomirov@558:  * Copyright (c) 2013 TMate Software Ltd
tikhomirov@558:  *  
tikhomirov@558:  * This program is free software; you can redistribute it and/or modify
tikhomirov@558:  * it under the terms of the GNU General Public License as published by
tikhomirov@558:  * the Free Software Foundation; version 2 of the License.
tikhomirov@558:  *
tikhomirov@558:  * This program is distributed in the hope that it will be useful,
tikhomirov@558:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@558:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@558:  * GNU General Public License for more details.
tikhomirov@558:  *
tikhomirov@558:  * For information on how to redistribute this software under
tikhomirov@558:  * the terms of a license other than GNU General Public License
tikhomirov@558:  * contact TMate Software at support@hg4j.com
tikhomirov@558:  */
tikhomirov@558: package org.tmatesoft.hg.internal;
tikhomirov@558: 
tikhomirov@558: import java.util.Formatter;
tikhomirov@558: 
tikhomirov@558: /**
tikhomirov@558:  * Sequence of range pairs (denoted origin and target), {originStart, targetStart, length}, tailored for diff/annotate
tikhomirov@558:  * 
tikhomirov@558:  * @author Artem Tikhomirov
tikhomirov@558:  * @author TMate Software Ltd.
tikhomirov@558:  */
tikhomirov@674: public final class RangePairSeq {
tikhomirov@674: 	private final IntSliceSeq ranges = new IntSliceSeq(3);
tikhomirov@558: 	
tikhomirov@558: 	public void add(int start1, int start2, int length) {
tikhomirov@674: 		int count = ranges.size();
tikhomirov@558: 		if (count > 0) {
tikhomirov@674: 			int lastS1 = ranges.get(--count, 0);
tikhomirov@674: 			int lastS2 = ranges.get(count, 1);
tikhomirov@674: 			int lastLen = ranges.get(count, 2);
tikhomirov@558: 			if (start1 == lastS1 + lastLen && start2 == lastS2 + lastLen) {
tikhomirov@558: 				// new range continues the previous one - just increase the length
tikhomirov@674: 				ranges.set(count, lastS1, lastS2, lastLen + length);
tikhomirov@558: 				return;
tikhomirov@558: 			}
tikhomirov@558: 		}
tikhomirov@558: 		ranges.add(start1, start2, length);
tikhomirov@558: 	}
tikhomirov@558: 	
tikhomirov@558: 	public void clear() {
tikhomirov@558: 		ranges.clear();
tikhomirov@558: 	}
tikhomirov@558: 
tikhomirov@558: 	public int size() {
tikhomirov@674: 		return ranges.size();
tikhomirov@558: 	}
tikhomirov@558: 
tikhomirov@558: 	/**
tikhomirov@558: 	 * find out line index in the target that matches specified origin line
tikhomirov@558: 	 */
tikhomirov@558: 	public int mapLineIndex(int ln) {
tikhomirov@674: 		for (IntTuple t : ranges) {
tikhomirov@674: 			int s1 = t.at(0);
tikhomirov@558: 			if (s1 > ln) {
tikhomirov@558: 				return -1;
tikhomirov@558: 			}
tikhomirov@674: 			int l = t.at(2);
tikhomirov@558: 			if (s1 + l > ln) {
tikhomirov@674: 				int s2 = t.at(1);
tikhomirov@558: 				return s2 + (ln - s1);
tikhomirov@558: 			}
tikhomirov@558: 		}
tikhomirov@558: 		return -1;
tikhomirov@558: 	}
tikhomirov@558: 	
tikhomirov@558: 	/**
tikhomirov@558: 	 * find out line index in origin that matches specified target line
tikhomirov@558: 	 */
tikhomirov@558: 	public int reverseMapLine(int targetLine) {
tikhomirov@674: 		for (IntTuple t : ranges) {
tikhomirov@674: 			int ts = t.at(1);
tikhomirov@558: 			if (ts > targetLine) {
tikhomirov@558: 				return -1;
tikhomirov@558: 			}
tikhomirov@674: 			int l = t.at(2);
tikhomirov@558: 			if (ts + l > targetLine) {
tikhomirov@674: 				int os = t.at(0);
tikhomirov@558: 				return os + (targetLine - ts);
tikhomirov@558: 			}
tikhomirov@558: 		}
tikhomirov@558: 		return -1;
tikhomirov@558: 	}
tikhomirov@558: 	
tikhomirov@674: 	public RangePairSeq intersect(RangePairSeq target) {
tikhomirov@674: 		RangePairSeq v = new RangePairSeq();
tikhomirov@674: 		for (IntTuple t : ranges) {
tikhomirov@674: 			int originLine = t.at(0);
tikhomirov@674: 			int targetLine = t.at(1);
tikhomirov@674: 			int length = t.at(2);
tikhomirov@558: 			int startTargetLine = -1, startOriginLine = -1, c = 0;
tikhomirov@558: 			for (int j = 0; j < length; j++) {
tikhomirov@558: 				int lnInFinal = target.mapLineIndex(targetLine + j);
tikhomirov@558: 				if (lnInFinal == -1 || (startTargetLine != -1 && lnInFinal != startTargetLine + c)) {
tikhomirov@558: 					// the line is not among "same" in ultimate origin
tikhomirov@558: 					// or belongs to another/next "same" chunk 
tikhomirov@558: 					if (startOriginLine == -1) {
tikhomirov@558: 						continue;
tikhomirov@558: 					}
tikhomirov@558: 					v.add(startOriginLine, startTargetLine, c);
tikhomirov@558: 					c = 0;
tikhomirov@558: 					startOriginLine = startTargetLine = -1;
tikhomirov@558: 					// fall-through to check if it's not complete miss but a next chunk
tikhomirov@558: 				}
tikhomirov@558: 				if (lnInFinal != -1) {
tikhomirov@558: 					if (startOriginLine == -1) {
tikhomirov@558: 						startOriginLine = originLine + j;
tikhomirov@558: 						startTargetLine = lnInFinal;
tikhomirov@558: 						c = 1;
tikhomirov@558: 					} else {
tikhomirov@558: 						// lnInFinal != startTargetLine + s is covered above
tikhomirov@558: 						assert lnInFinal == startTargetLine + c;
tikhomirov@558: 						c++;
tikhomirov@558: 					}
tikhomirov@558: 				}
tikhomirov@558: 			}
tikhomirov@558: 			if (startOriginLine != -1) {
tikhomirov@558: 				assert c > 0;
tikhomirov@558: 				v.add(startOriginLine, startTargetLine, c);
tikhomirov@558: 			}
tikhomirov@558: 		}
tikhomirov@558: 		return v;
tikhomirov@558: 	}
tikhomirov@558: 	
tikhomirov@558: 	// true when specified line in origin is equal to a line in target
tikhomirov@558: 	public boolean includesOriginLine(int ln) {
tikhomirov@558: 		return includes(ln, 0);
tikhomirov@558: 	}
tikhomirov@558: 	
tikhomirov@558: 	// true when specified line in target is equal to a line in origin
tikhomirov@558: 	public boolean includesTargetLine(int ln) {
tikhomirov@558: 		return includes(ln, 1);
tikhomirov@558: 	}
tikhomirov@558: 
tikhomirov@558: 	private boolean includes(int ln, int o) {
tikhomirov@674: 		for (IntTuple t : ranges) {
tikhomirov@674: 			int rangeStart = t.at(o);
tikhomirov@558: 			if (rangeStart > ln) {
tikhomirov@558: 				return false;
tikhomirov@558: 			}
tikhomirov@674: 			int rangeLen = t.at(2);
tikhomirov@558: 			if (rangeStart + rangeLen > ln) {
tikhomirov@558: 				return true;
tikhomirov@558: 			}
tikhomirov@558: 		}
tikhomirov@558: 		return false;
tikhomirov@558: 	}
tikhomirov@558: 
tikhomirov@558: 	public CharSequence dump() {
tikhomirov@558: 		StringBuilder sb = new StringBuilder();
tikhomirov@558: 		Formatter f = new Formatter(sb);
tikhomirov@674: 		for (IntTuple t : ranges) {
tikhomirov@674: 			int s1 = t.at(0);
tikhomirov@674: 			int s2 = t.at(1);
tikhomirov@674: 			int len = t.at(2);
tikhomirov@558: 			f.format("[%d..%d) == [%d..%d);  ", s1, s1 + len, s2, s2 + len);
tikhomirov@558: 		}
tikhomirov@558: 		return sb;
tikhomirov@558: 	}
tikhomirov@558: 	
tikhomirov@558: 	@Override
tikhomirov@558: 	public String toString() {
tikhomirov@674: 		return String.format("RangeSeq[%d]:%s", size(), dump());
tikhomirov@558: 	}
tikhomirov@558: }