tikhomirov@329: /*
tikhomirov@533:  * Copyright (c) 2011-2013 TMate Software Ltd
tikhomirov@329:  *  
tikhomirov@329:  * This program is free software; you can redistribute it and/or modify
tikhomirov@329:  * it under the terms of the GNU General Public License as published by
tikhomirov@329:  * the Free Software Foundation; version 2 of the License.
tikhomirov@329:  *
tikhomirov@329:  * This program is distributed in the hope that it will be useful,
tikhomirov@329:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@329:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@329:  * GNU General Public License for more details.
tikhomirov@329:  *
tikhomirov@329:  * For information on how to redistribute this software under
tikhomirov@329:  * the terms of a license other than GNU General Public License
tikhomirov@329:  * contact TMate Software at support@hg4j.com
tikhomirov@329:  */
tikhomirov@329: package org.tmatesoft.hg.internal;
tikhomirov@329: 
tikhomirov@329: import java.io.IOException;
tikhomirov@329: import java.util.ArrayList;
tikhomirov@330: import java.util.Formatter;
tikhomirov@329: 
tikhomirov@329: /**
tikhomirov@419:  * @see http://mercurial.selenic.com/wiki/BundleFormat
tikhomirov@419:  * in Changelog group description
tikhomirov@329:  * 
tikhomirov@533:  * range [start..end) in original source gets replaced with data of length (do not keep, use data.length instead)
tikhomirov@533:  * range [end(i)..start(i+1)) is copied from the source
tikhomirov@329:  * 
tikhomirov@329:  * @author Artem Tikhomirov
tikhomirov@329:  * @author TMate Software Ltd.
tikhomirov@329:  */
tikhomirov@329: public final class Patch {
tikhomirov@329: 	private final IntVector starts, ends;
tikhomirov@329: 	private final ArrayList<byte[]> data;
tikhomirov@584: 	private final boolean shallNormalize;
tikhomirov@330: 
tikhomirov@330: 	private static byte[] generate(int c) {
tikhomirov@330: 		byte[] rv = new byte[c];
tikhomirov@330: 		for (int i = 0; i < c; i++) {
tikhomirov@330: 			byte x = (byte) ('a' + i);
tikhomirov@330: 			rv[i] = x;
tikhomirov@330: 		}
tikhomirov@330: 		return rv;
tikhomirov@330: 	}
tikhomirov@330: 
tikhomirov@330: 	public static void main(String[] args) {
tikhomirov@330: 		Patch p1 = new Patch(), p2 = new Patch();
tikhomirov@330: 		// simple cases (one element in either patch)
tikhomirov@330: 		// III: (1,10 20) & (5,15,15) p2End from [p1End..p1AppliedEnd] (i.e. within p1 range but index is past p2 end index) 
tikhomirov@330: 		//  II: (1,10,7) & (3,15,15) insideP2 = true and no more p1 entries
tikhomirov@330: 		//  II: (1,1,10) & (3,11,15)
tikhomirov@330: 		// independent: (1,10,10) & (15,25,10);  (15, 25, 10) & (1, 10, 10) 
tikhomirov@330: 		//   I: (15, 25, 10) & (10, 20, 10). result: [10, 20, 10] [20, 25, 5]
tikhomirov@330: 		//  IV: (15, 25, 10) & (10, 30, 20)
tikhomirov@330: 		// 
tikhomirov@330: 		// cycle with insideP2
tikhomirov@330: 		//
tikhomirov@330: 		// cycle with insideP1
tikhomirov@330: 		//
tikhomirov@330: 		// multiple elements in patches (offsets)
tikhomirov@330: 		p1.add(15, 25, generate(10));
tikhomirov@330: 		p2.add(10, 30, generate(20));
tikhomirov@330: 		System.out.println("p1: " + p1);
tikhomirov@330: 		System.out.println("p2: " + p2);
tikhomirov@330: 		Patch r = p1.apply(p2);
tikhomirov@330: 		System.out.println("r: " + r);
tikhomirov@330: 	}
tikhomirov@584: 	
tikhomirov@584: 	public Patch() {
tikhomirov@587: 		this(16, false);
tikhomirov@587: 	}
tikhomirov@587: 	
tikhomirov@587: 	public Patch(boolean normalizeOnChange) {
tikhomirov@587: 		this(16, normalizeOnChange);
tikhomirov@584: 	}
tikhomirov@330: 
tikhomirov@587: 	public Patch(int sizeHint, boolean normalizeOnChange) {
tikhomirov@584: 		shallNormalize = normalizeOnChange;
tikhomirov@587: 		starts = new IntVector(sizeHint, -1);
tikhomirov@587: 		ends = new IntVector(sizeHint, -1);
tikhomirov@587: 		data = new ArrayList<byte[]>(sizeHint);
tikhomirov@329: 	}
tikhomirov@329: 	
tikhomirov@330: 	public String toString() {
tikhomirov@330: 		StringBuilder sb = new StringBuilder();
tikhomirov@330: 		Formatter f = new Formatter(sb);
tikhomirov@330: 		for (int i = 0; i < count(); i++) {
tikhomirov@330: 			f.format("[%d, %d, %d] ", starts.get(i), ends.get(i), data.get(i).length);
tikhomirov@330: 		}
tikhomirov@330: 		return sb.toString();
tikhomirov@330: 	}
tikhomirov@330: 	
tikhomirov@329: 	public int count() {
tikhomirov@329: 		return data.size();
tikhomirov@329: 	}
tikhomirov@329: 
tikhomirov@329: 	// number of bytes this patch will add (or remove, if negative) from the base revision
tikhomirov@583: 	public int patchSizeDelta() {
tikhomirov@329: 		int rv = 0;
tikhomirov@329: 		int prevEnd = 0;
tikhomirov@329: 		for (int i = 0, x = data.size(); i < x; i++) {
tikhomirov@329: 			final int start = starts.get(i);
tikhomirov@329: 			final int len = data.get(i).length;
tikhomirov@329: 			rv += start - prevEnd; // would copy from original
tikhomirov@329: 			rv += len; // and add new
tikhomirov@329: 			prevEnd = ends.get(i);
tikhomirov@329: 		}
tikhomirov@329: 		rv -= prevEnd;
tikhomirov@329: 		return rv;
tikhomirov@329: 	}
tikhomirov@329: 	
tikhomirov@329: 	public byte[] apply(DataAccess baseRevisionContent, int outcomeLen) throws IOException {
tikhomirov@329: 		if (outcomeLen == -1) {
tikhomirov@329: 			outcomeLen = baseRevisionContent.length() + patchSizeDelta();
tikhomirov@329: 		}
tikhomirov@329: 		int prevEnd = 0, destIndex = 0;
tikhomirov@329: 		byte[] rv = new byte[outcomeLen];
tikhomirov@329: 		for (int i = 0, x = data.size(); i < x; i++) {
tikhomirov@329: 			final int start = starts.get(i);
tikhomirov@329: 			baseRevisionContent.seek(prevEnd);
tikhomirov@329: 			// copy source bytes that were not modified (up to start of the record)
tikhomirov@329: 			baseRevisionContent.readBytes(rv, destIndex, start - prevEnd);
tikhomirov@329: 			destIndex += start - prevEnd;
tikhomirov@329: 			// insert new data from the patch, if any
tikhomirov@329: 			byte[] d = data.get(i);
tikhomirov@532: 			System.arraycopy(d, 0, rv, destIndex, d.length);
tikhomirov@329: 			destIndex += d.length;
tikhomirov@329: 			prevEnd = ends.get(i);
tikhomirov@329: 		}
tikhomirov@329: 		baseRevisionContent.seek(prevEnd);
tikhomirov@329: 		// copy everything in the source past last record's end
tikhomirov@420: 		baseRevisionContent.readBytes(rv, destIndex, (baseRevisionContent.length() - prevEnd));
tikhomirov@329: 		return rv;
tikhomirov@329: 	}
tikhomirov@329: 	
tikhomirov@329: 	public void clear() {
tikhomirov@329: 		starts.clear();
tikhomirov@329: 		ends.clear();
tikhomirov@329: 		data.clear();
tikhomirov@329: 	}
tikhomirov@329: 	
tikhomirov@329: 	/**
tikhomirov@329: 	 * Initialize instance from stream. Any previous patch information (i.e. if instance if reused) is cleared first.
tikhomirov@329: 	 * Read up to the end of DataAccess and interpret data as patch records.
tikhomirov@329: 	 */
tikhomirov@329: 	public void read(DataAccess da) throws IOException {
tikhomirov@329: 		clear();
tikhomirov@329: 		while (!da.isEmpty()) {
tikhomirov@329: 			readOne(da);
tikhomirov@329: 		}
tikhomirov@329: 	}
tikhomirov@329: 
tikhomirov@329: 	/**
tikhomirov@329: 	 * Caller is responsible to ensure stream got some data to read
tikhomirov@329: 	 */
tikhomirov@329: 	public void readOne(DataAccess da) throws IOException {
tikhomirov@329: 		int s = da.readInt();
tikhomirov@329: 		int e = da.readInt();
tikhomirov@329: 		int len = da.readInt();
tikhomirov@329: 		byte[] src = new byte[len];
tikhomirov@329: 		da.readBytes(src, 0, len);
tikhomirov@329: 		starts.add(s);
tikhomirov@329: 		ends.add(e);
tikhomirov@329: 		data.add(src);
tikhomirov@329: 	}
tikhomirov@534: 	
tikhomirov@534: 	/**
tikhomirov@534: 	 * @return how many bytes the patch would take if written down using BundleFormat structure (start, end, length, data)
tikhomirov@534: 	 */
tikhomirov@534: 	public int serializedLength() {
tikhomirov@534: 		int totalDataLen = 0;
tikhomirov@534: 		for (byte[] d : data) {
tikhomirov@534: 			totalDataLen += d.length;
tikhomirov@534: 		}
tikhomirov@534: 		int prefix = 3 * 4 * count(); // 3 integer fields per entry * sizeof(int) * number of entries
tikhomirov@534: 		return prefix + totalDataLen;
tikhomirov@534: 	}
tikhomirov@534: 	
tikhomirov@534: 	/*package-local*/ void serialize(DataSerializer out) throws IOException {
tikhomirov@534: 		for (int i = 0, x = data.size(); i < x; i++) {
tikhomirov@534: 			final int start = starts.get(i);
tikhomirov@534: 			final int end = ends.get(i);
tikhomirov@534: 			byte[] d = data.get(i);
tikhomirov@534: 			out.writeInt(start, end, d.length);
tikhomirov@534: 			out.write(d, 0, d.length);
tikhomirov@534: 		}
tikhomirov@534: 	}
tikhomirov@534: 	
tikhomirov@330: 	private void add(Patch p, int i) {
tikhomirov@330: 		add(p.starts.get(i), p.ends.get(i), p.data.get(i));
tikhomirov@330: 	}
tikhomirov@330: 
tikhomirov@533: 	/*package-local*/ void add(int start, int end, byte[] d) {
tikhomirov@583: 		if (start == end && d.length == 0) {
tikhomirov@583: 			System.currentTimeMillis();
tikhomirov@583: 			return;
tikhomirov@583: 		}
tikhomirov@584: 		int last;
tikhomirov@584: 		if (shallNormalize && (last = starts.size()) > 0) {
tikhomirov@584: 			last--;
tikhomirov@584: 			if (ends.get(last) == start) {
tikhomirov@584: 				byte[] d1 = data.get(last);
tikhomirov@584: 				byte[] nd;
tikhomirov@584: 				if (d1.length > 0 && d.length > 0) {
tikhomirov@584: 					nd = new byte[d1.length + d.length];
tikhomirov@584: 					System.arraycopy(d1, 0, nd, 0, d1.length);
tikhomirov@584: 					System.arraycopy(d, 0, nd, d1.length, d.length);
tikhomirov@584: 				} else {
tikhomirov@584: 					nd = d1.length == 0 ? d : d1 ;
tikhomirov@584: 				}
tikhomirov@584: 				ends.set(last, end);
tikhomirov@584: 				data.set(last, nd);
tikhomirov@584: 				return;
tikhomirov@584: 			}
tikhomirov@584: 			// fall-through
tikhomirov@584: 		}
tikhomirov@330: 		starts.add(start);
tikhomirov@330: 		ends.add(end);
tikhomirov@330: 		data.add(d);
tikhomirov@330: 	}
tikhomirov@330: 	
tikhomirov@583: 	// copies [start..end) bytes from the d
tikhomirov@330: 	private static byte[] subarray(byte[] d, int start, int end) {
tikhomirov@583: 		byte[] r = new byte[end-start];
tikhomirov@330: 		System.arraycopy(d, start, r, 0, r.length);
tikhomirov@330: 		return r;
tikhomirov@329: 	}
tikhomirov@329: 
tikhomirov@329: 	/**
tikhomirov@329: 	 * Modify this patch with subsequent patch 
tikhomirov@330: 	 */
tikhomirov@583: 	public /*SHALL BE PUBLIC ONCE TESTING ENDS*/ Patch apply(Patch another) {
tikhomirov@587: 		Patch r = new Patch(count() + another.count() * 2, shallNormalize);
tikhomirov@330: 		int p1TotalAppliedDelta = 0; // value to add to start and end indexes of the older patch to get their values as if
tikhomirov@330: 		// in the patched text, iow, directly comparable with respective indexes from the newer patch.
tikhomirov@330: 		int p1EntryStart = 0, p1EntryEnd = 0, p1EntryLen = 0;
tikhomirov@330: 		byte[] p1Data = null;
tikhomirov@330: 		boolean insideP1entry = false;
tikhomirov@330: 		int p2 = 0, p1 = 0;
tikhomirov@330: 		final int p2Max = another.count(), p1Max = this.count();
tikhomirov@330: L0:		for (; p2 < p2Max; p2++) {
tikhomirov@330: 			int p2EntryStart = another.starts.get(p2);
tikhomirov@330: 			int p2EntryEnd = another.ends.get(p2);
tikhomirov@330: 			final int p2EntryRange = p2EntryEnd - p2EntryStart;
tikhomirov@330: 			final byte[] p2Data = another.data.get(p2);
tikhomirov@330: 			boolean insideP2entry = false;
tikhomirov@583: 			// when we iterate p1 elements within single p2, we need to remember where p2
tikhomirov@583: 			// shall ultimately start in terms of p1
tikhomirov@583: 			int p2EntrySavedStart = -1;
tikhomirov@330: 			///
tikhomirov@329: 			
tikhomirov@330: L1:			while (p1 < p1Max) {
tikhomirov@330: 				if (!insideP1entry) {
tikhomirov@330: 					p1EntryStart = starts.get(p1);
tikhomirov@330: 					p1EntryEnd = ends.get(p1);
tikhomirov@330: 					p1Data = data.get(p1);
tikhomirov@330: 					p1EntryLen = p1Data.length;
tikhomirov@330: 				}// else keep values
tikhomirov@330: 
tikhomirov@330: 				final int p1EntryDelta = p1EntryLen - (p1EntryEnd - p1EntryStart); // number of actually inserted(+) or deleted(-) chars
tikhomirov@330: 				final int p1EntryAppliedStart = p1TotalAppliedDelta + p1EntryStart;
tikhomirov@330: 				final int p1EntryAppliedEnd = p1EntryAppliedStart + p1EntryLen; // end of j'th patch entry in the text which is source for p2
tikhomirov@330: 				
tikhomirov@330: 				if (insideP2entry) {
tikhomirov@583: 					if (p2EntryEnd <= p1EntryAppliedStart) {
tikhomirov@583: 						r.add(p2EntrySavedStart, p2EntryEnd - p1TotalAppliedDelta, p2Data);
tikhomirov@330: 						insideP2entry = false;
tikhomirov@330: 						continue L0; 
tikhomirov@330: 					}
tikhomirov@330: 					if (p2EntryEnd >= p1EntryAppliedEnd) {
tikhomirov@330: 						// when p2EntryEnd == p1EntryAppliedEnd, I assume p1TotalAppliedDelta can't be used for p2EntryEnd to get it to p1 range, but rather shall be
tikhomirov@330: 						// augmented with current p1 entry and at the next p1 entry (likely to hit p1EntryAppliedStart > p2EntryEnd above) would do the rest 
tikhomirov@330: 						insideP1entry = false;
tikhomirov@330: 						p1++;
tikhomirov@330: 						p1TotalAppliedDelta += p1EntryDelta;
tikhomirov@330: 						continue L1;
tikhomirov@330: 					}
tikhomirov@583: 					// p1EntryAppliedStart < p2EntryEnd < p1EntryAppliedEnd
tikhomirov@583: 					// can add up to p1EntryEnd here (not only to p1EntryStart), but decided
tikhomirov@583: 					// to leave p1 intact here, to avoid delta/range recalculation 
tikhomirov@583: 					r.add(p2EntrySavedStart, p1EntryStart, p2Data);
tikhomirov@583: 					// consume part of p1 overlapped by current p2
tikhomirov@583: 					final int p1DataPartShift = p2EntryEnd - p1EntryAppliedStart;
tikhomirov@583: 					// p2EntryEnd < p1EntryAppliedEnd		==> p2EntryEnd < p1EntryAppliedStart + p1EntryLen
tikhomirov@583: 					//										==> p2EntryEnd - p1EntryAppliedStart < p1EntryLen
tikhomirov@583: 					assert p1DataPartShift < p1EntryLen;
tikhomirov@583: 					p1EntryLen -= p1DataPartShift;
tikhomirov@583: 					p1Data = subarray(p1Data, p1DataPartShift, p1Data.length);
tikhomirov@583: 					p1TotalAppliedDelta += p1DataPartShift;
tikhomirov@330: 					insideP1entry = true;
tikhomirov@330: 					insideP2entry = false;
tikhomirov@330: 					continue L0;
tikhomirov@330: 				}
tikhomirov@330: 
tikhomirov@330: 				if (p1EntryAppliedStart < p2EntryStart) {
tikhomirov@330: 					if (p1EntryAppliedEnd <= p2EntryStart) { // p1EntryAppliedEnd in fact index of the first char *after* patch
tikhomirov@330: 						// completely independent, copy and continue
tikhomirov@330: 						r.add(p1EntryStart, p1EntryEnd, p1Data);
tikhomirov@330: 						insideP1entry = false;
tikhomirov@330: 						p1++;
tikhomirov@330: 						// fall-through to get p1TotalAppliedDelta incremented
tikhomirov@583: 					} else { // SKETCH: II or III - p2 start inside p1 range
tikhomirov@330: 						// remember, p1EntryDelta may be negative
tikhomirov@330: 						// shall break j'th entry into few 
tikhomirov@330: 						// fix p1's end/length
tikhomirov@583: 						// p1EntryAppliedStart < p2EntryStart < p1EntryAppliedEnd, or, alternatively
tikhomirov@583: 						// p2EntryStart is from (p1EntryAppliedStart .. p1EntryAppliedStart + p1EntryLen)
tikhomirov@583: 						int p1DataPartEnd = p2EntryStart - p1EntryAppliedStart;
tikhomirov@583: 						assert p1DataPartEnd < p1EntryLen;
tikhomirov@583: 						r.add(p1EntryStart, p1EntryEnd, subarray(p1Data, 0, p1DataPartEnd));
tikhomirov@583: 						if (p2EntryEnd <= p1EntryAppliedEnd) { // p2 fits completely into p1
tikhomirov@583: 							r.add(p1EntryEnd, p1EntryEnd, p2Data);
tikhomirov@583: 							// p2 consumed, p1 has p1EntryLen - p1DataPartEnd - p2EntryRange bytes left to *insert*
tikhomirov@330: 							insideP1entry = true;
tikhomirov@583: 							p1EntryStart = p1EntryEnd;
tikhomirov@583: 							p1EntryLen -= p1DataPartEnd;
tikhomirov@583: 							p1EntryLen -= p2EntryRange;
tikhomirov@583: 							// p2EntryEnd <= p1EntryAppliedEnd						==> p2EntryEnd <= p1EntryAppliedStart + p1EntryLen
tikhomirov@583: 							// -p2EntryStart    									==> p2EntryRange <= p1EntryAppliedStart-p2EntryStart + p1EntryLen
tikhomirov@583: 							// p1EntryAppliedStart-p2EntryStart = -p1DataPartEnd	==> p2EntryRange <= p1EntryLen - p1DataEndPart
tikhomirov@583: 							//	+p1DataEndPart										==> p2EntryRange + p1DataEndPart <= p1EntryLen
tikhomirov@583: 							assert p1EntryLen >= 0;
tikhomirov@583: 							// p1EntryLen==0 with insideP1entry == true is nor really good here (gives empty patch elements x;x;0), 
tikhomirov@583: 							// however changing <= to < in p2EntryEnd <= p1EntryAppliedEnd above leads to errors
tikhomirov@583: 							p1Data = subarray(p1Data, p1DataPartEnd+p2EntryRange, p1Data.length);
tikhomirov@583: 							// augment total delta with p1EntryDelta part already consumed (p1EntryLen is pure insertion left for the next step) 
tikhomirov@583: 							p1TotalAppliedDelta += (p1EntryDelta - p1EntryLen);
tikhomirov@330: 							continue L0;
tikhomirov@583: 						} else {
tikhomirov@583: 							// p1 is consumed, take next
tikhomirov@330: 							insideP1entry = false;
tikhomirov@330: 							p1++;
tikhomirov@583: 							insideP2entry = true;
tikhomirov@583: 							p2EntrySavedStart = p1EntryEnd; // this is how far we've progressed in p1
tikhomirov@583: 							// fall-through to get p1TotalAppliedDelta updated with consumed p1
tikhomirov@330: 						}
tikhomirov@330: 					}
tikhomirov@330: 				} else { // p1EntryAppliedStart >= p2EntryStart
tikhomirov@330: 					if (p2EntryEnd < p1EntryAppliedStart) {
tikhomirov@330: 						// newer patch completely fits between two older patches 
tikhomirov@330: 						r.add(p2EntryStart - p1TotalAppliedDelta, p2EntryEnd - p1TotalAppliedDelta, p2Data);
tikhomirov@330: 						// SHALL NOT increment p1TotalAppliedDelta as we didn't use any of p1
tikhomirov@330: 						continue L0; // next p2 
tikhomirov@330: 					} else { // p2EntryEnd >= p1EntryAppliedStart
tikhomirov@583: 						// SKETCH: I or IV:
tikhomirov@583: 						// p2 start is outside of p1 range.
tikhomirov@583: 						//
tikhomirov@583: 						// p2DataPartEnd: this is how many bytes prior to p1EntryStart is replaced by p2Data
tikhomirov@583: 						int p2DataPartEnd = p1EntryAppliedStart - p2EntryStart;
tikhomirov@583: 						if (p2EntryEnd < p1EntryAppliedEnd) {
tikhomirov@330: 							// SKETCH: I: copy p2, strip p1 to start from p2EntryEnd, next i (p2)
tikhomirov@330: 							insideP1entry = true;
tikhomirov@583: 							// replace whole p1 (extended to the left by (p2 \ p1) front bytes)
tikhomirov@583: 							r.add(p1EntryStart - p2DataPartEnd, p1EntryEnd, p2Data);
tikhomirov@583: 							p1EntryStart = p1EntryEnd;
tikhomirov@583: 							// see how much of p1 is left for insertion
tikhomirov@583: 							int p1DataPartEnd = p2EntryEnd - p1EntryAppliedStart; // #1
tikhomirov@583: 							// Similar, although incorrect: p1DataPartEnd == p2Data.length - p2DataPartEnd; // #2
tikhomirov@583: 							// #1(p2EntryStart + p2DataLen) - p1EntryAppliedStart
tikhomirov@583: 							// #2 p2DataLen - (p1EntryAppliedStart - p2EntryStart)
tikhomirov@583: 							// but this works only in assumption that p2EntryEnd-p2EntryStart == p2Data.length
tikhomirov@583: 							//
tikhomirov@583: 							// p1EntryAppliedStart <= p2EntryEnd < p1EntryAppliedStart + p1EntryLen
tikhomirov@583: 							// -p1EntryAppliedStart (to compare against p1DataPartEnd)  ==> 	0 <= p1DataPartEnd < p1EntryLen
tikhomirov@583: 							assert p1DataPartEnd < p1EntryLen;
tikhomirov@583: 							assert p1DataPartEnd >= 0;
tikhomirov@583: 							p1EntryLen -= p1DataPartEnd;
tikhomirov@583: 							p1Data = subarray(p1Data, p1DataPartEnd, p1Data.length);
tikhomirov@583: 
tikhomirov@583: 							// p1TotalAppliedDelta XXX
tikhomirov@583: 							p1TotalAppliedDelta += (p1EntryDelta - p1EntryLen);
tikhomirov@330: 							continue L0; // next p2;
tikhomirov@330: 						} else {
tikhomirov@583: 							// p2EntryEnd >= p1EntryAppliedEnd
tikhomirov@330: 							// SKETCH IV: skip (rest of) p1 completely, continue the same unless  found p1 with start or end past p2EntryEnd.
tikhomirov@330: 							insideP1entry = false;
tikhomirov@583: 							// p1 consumed
tikhomirov@330: 							p1++;
tikhomirov@330: 							insideP2entry = true;
tikhomirov@583: 							// extend to the left of p1 by p2 \ p1 front bytes
tikhomirov@583: 							p2EntrySavedStart = p1EntryStart - p2DataPartEnd;
tikhomirov@330: 							// fall-through to get p1TotalAppliedDelta incremented
tikhomirov@330: 						}
tikhomirov@329: 					}
tikhomirov@329: 				}
tikhomirov@330: 				p1TotalAppliedDelta += p1EntryDelta;
tikhomirov@330: 			} // while (p1 < p1Max)
tikhomirov@330: 			{
tikhomirov@330: 				// no more p1 entries, shall close p2 (if it's handled, code above jumps directly to L0)
tikhomirov@330: 				// regardless of whether insideP2 is .t
tikhomirov@583: 				int s = p2EntrySavedStart != -1 ? p2EntrySavedStart : p2EntryStart - p1TotalAppliedDelta;
tikhomirov@583: 				// p2EntrySavedStart != -1 when we started p2 entry processing, but not completed
tikhomirov@330: 				// if we handled last p1 entry but didn't start with p2 entry processing, it's -1 and regular p1 delta shall be used
tikhomirov@330: 				r.add(s, p2EntryEnd - p1TotalAppliedDelta, p2Data);
tikhomirov@329: 			}
tikhomirov@329: 		}
tikhomirov@330: 		if (p1 < p1Max && insideP1entry) {
tikhomirov@330: 			r.add(p1EntryStart, p1EntryEnd, p1Data);
tikhomirov@330: 			p1++;
tikhomirov@330: 		}
tikhomirov@330: 		while (p1 < p1Max) {
tikhomirov@330: 			r.add(this, p1);
tikhomirov@330: 			p1++;
tikhomirov@330: 		};
tikhomirov@330: 		return r;
tikhomirov@329: 	}
tikhomirov@534: 
tikhomirov@583: 	/**
tikhomirov@583: 	 * Combine consecutive regions into one.
tikhomirov@583: 	 * XXX NOW only combines two subsequent regions, seems enough for quick test
tikhomirov@583: 	 * @return <code>this</code> or new instance of consecutive regions found
tikhomirov@583: 	 */
tikhomirov@583: 	public Patch normalize() {
tikhomirov@583: 		Patch rv = null;
tikhomirov@583: 		for (int i = 1, x = data.size(); i < x; i++) {
tikhomirov@583: 			if (starts.get(i) == ends.get(i-1)) {
tikhomirov@583: 				if (rv == null) {
tikhomirov@583: 					rv = new Patch();
tikhomirov@583: 					rv.copyOf(this, 0, i-1);
tikhomirov@583: //				} else if (ends.get(i-1) == rv.ends.get(rv.ends.size()-1)) {
tikhomirov@583: //					// "JUST IN CASE" code, i++ below prevents us from getting here
tikhomirov@583: //					// if the last region is the one already merged,
tikhomirov@583: //					// ignore this occurrence (otherwise data(i-1) would get copied again) 
tikhomirov@583: //					continue;
tikhomirov@583: 				}
tikhomirov@583: 				byte[] d1 = data.get(i-1);
tikhomirov@583: 				byte[] d = data.get(i);
tikhomirov@583: 				byte[] nd;
tikhomirov@583: 				if (d1.length > 0 && d.length > 0) {
tikhomirov@583: 					nd = new byte[d1.length + d.length];
tikhomirov@583: 					System.arraycopy(d1, 0, nd, 0, d1.length);
tikhomirov@583: 					System.arraycopy(d, 0, nd, d1.length, d.length);
tikhomirov@583: 				} else {
tikhomirov@583: 					nd = d1.length == 0 ? d : d1 ;
tikhomirov@583: 				}
tikhomirov@583: 				rv.add(starts.get(i-1), ends.get(i), nd);
tikhomirov@583: 				i++; // skip i-th element (effectively means we detect only pairs)
tikhomirov@583: 				// without this ++, element(i-1) is added to rv once "else" below is hit on the next step
tikhomirov@583: 			} else {
tikhomirov@583: 				if (rv != null) {
tikhomirov@583: 					rv.add(this, i-1);
tikhomirov@583: 				}
tikhomirov@583: 			}
tikhomirov@583: 		}
tikhomirov@583: 		if (rv == null) {
tikhomirov@583: 			return this;
tikhomirov@583: 		} else {
tikhomirov@583: 			int last = count() - 1;
tikhomirov@583: 			if (starts.get(last) != ends.get(last-1)) {
tikhomirov@583: 				rv.add(this, last);
tikhomirov@583: 			}
tikhomirov@583: 		}
tikhomirov@583: 		return rv;
tikhomirov@583: 	}
tikhomirov@583: 	
tikhomirov@583: 	private void copyOf(Patch another, int fromIndex, int upToIndex) {
tikhomirov@583: 		while(fromIndex < upToIndex) {
tikhomirov@583: 			add(another, fromIndex++);
tikhomirov@583: 		}
tikhomirov@583: 	}
tikhomirov@583: 
tikhomirov@534: 	public class PatchDataSource implements DataSerializer.DataSource {
tikhomirov@534: 
tikhomirov@534: 		public void serialize(DataSerializer out) throws IOException {
tikhomirov@534: 			Patch.this.serialize(out);
tikhomirov@534: 		}
tikhomirov@534: 
tikhomirov@534: 		public int serializeLength() {
tikhomirov@534: 			return Patch.this.serializedLength();
tikhomirov@534: 		}
tikhomirov@534: 	}
tikhomirov@329: }