public static PredictionContext mergeArrays(
		ArrayPredictionContext a,
		ArrayPredictionContext b,
		boolean rootIsWildcard,
		DoubleKeyMap<PredictionContext,PredictionContext,PredictionContext> mergeCache)
	{
		if ( mergeCache!=null ) {
			PredictionContext previous = mergeCache.get(a,b);
			if ( previous!=null ) {
				if ( ParserATNSimulator.trace_atn_sim ) System.out.println("mergeArrays a="+a+",b="+b+" -> previous");
				return previous;
			}
			previous = mergeCache.get(b,a);
			if ( previous!=null ) {
				if ( ParserATNSimulator.trace_atn_sim ) System.out.println("mergeArrays a="+a+",b="+b+" -> previous");
				return previous;
			}
		}

		// merge sorted payloads a + b => M
		int i = 0; // walks a
		int j = 0; // walks b
		int k = 0; // walks target M array

		int[] mergedReturnStates =
			new int[a.returnStates.length + b.returnStates.length];
		PredictionContext[] mergedParents =
			new PredictionContext[a.returnStates.length + b.returnStates.length];
		// walk and merge to yield mergedParents, mergedReturnStates
		while ( i<a.returnStates.length && j<b.returnStates.length ) {
			PredictionContext a_parent = a.parents[i];
			PredictionContext b_parent = b.parents[j];
			if ( a.returnStates[i]==b.returnStates[j] ) {
				// same payload (stack tops are equal), must yield merged singleton
				int payload = a.returnStates[i];
				// $+$ = $
				boolean both$ = payload == EMPTY_RETURN_STATE &&
								a_parent == null && b_parent == null;
				boolean ax_ax = (a_parent!=null && b_parent!=null) &&
								a_parent.equals(b_parent); // ax+ax -> ax
				if ( both$ || ax_ax ) {
					mergedParents[k] = a_parent; // choose left
					mergedReturnStates[k] = payload;
				}
				else { // ax+ay -> a'[x,y]
					PredictionContext mergedParent =
						merge(a_parent, b_parent, rootIsWildcard, mergeCache);
					mergedParents[k] = mergedParent;
					mergedReturnStates[k] = payload;
				}
				i++; // hop over left one as usual
				j++; // but also skip one in right side since we merge
			}
			else if ( a.returnStates[i]<b.returnStates[j] ) { // copy a[i] to M
				mergedParents[k] = a_parent;
				mergedReturnStates[k] = a.returnStates[i];
				i++;
			}
			else { // b > a, copy b[j] to M
				mergedParents[k] = b_parent;
				mergedReturnStates[k] = b.returnStates[j];
				j++;
			}
			k++;
		}

		// copy over any payloads remaining in either array
		if (i < a.returnStates.length) {
			for (int p = i; p < a.returnStates.length; p++) {
				mergedParents[k] = a.parents[p];
				mergedReturnStates[k] = a.returnStates[p];
				k++;
			}
		}
		else {
			for (int p = j; p < b.returnStates.length; p++) {
				mergedParents[k] = b.parents[p];
				mergedReturnStates[k] = b.returnStates[p];
				k++;
			}
		}

		// trim merged if we combined a few that had same stack tops
		if ( k < mergedParents.length ) { // write index < last position; trim
			if ( k == 1 ) { // for just one merged element, return singleton top
				PredictionContext a_ =
					SingletonPredictionContext.create(mergedParents[0],
													  mergedReturnStates[0]);
				if ( mergeCache!=null ) mergeCache.put(a,b,a_);
				return a_;
			}
			mergedParents = Arrays.copyOf(mergedParents, k);
			mergedReturnStates = Arrays.copyOf(mergedReturnStates, k);
		}

		PredictionContext M =
			new ArrayPredictionContext(mergedParents, mergedReturnStates);

		// if we created same array as a or b, return that instead
		// TODO: track whether this is possible above during merge sort for speed
		if ( M.equals(a) ) {
			if ( mergeCache!=null ) mergeCache.put(a,b,a);
			if ( ParserATNSimulator.trace_atn_sim ) System.out.println("mergeArrays a="+a+",b="+b+" -> a");
			return a;
		}
		if ( M.equals(b) ) {
			if ( mergeCache!=null ) mergeCache.put(a,b,b);
			if ( ParserATNSimulator.trace_atn_sim ) System.out.println("mergeArrays a="+a+",b="+b+" -> b");
			return b;
		}

		combineCommonParents(mergedParents);

		if ( mergeCache!=null ) mergeCache.put(a,b,M);

		if ( ParserATNSimulator.trace_atn_sim ) {
			System.out.println("mergeArrays a="+a+",b="+b+" -> "+M);
		}

		return M;
	}
Merge two {@link ArrayPredictionContext} instances.

<p>Different tops, different parents.<br>
<embed src="images/ArrayMerge_DiffTopDiffPar.svg" type="image/svg+xml"/></p>

<p>Shared top, same parents.<br>
<embed src="images/ArrayMerge_ShareTopSamePar.svg" type="image/svg+xml"/></p>

<p>Shared top, different parents.<br>
<embed src="images/ArrayMerge_ShareTopDiffPar.svg" type="image/svg+xml"/></p>

<p>Shared top, all shared parents.<br>
<embed src="images/ArrayMerge_ShareTopSharePar.svg" type="image/svg+xml"/></p>

<p>Equal tops, merge parents and reduce top to
{@link SingletonPredictionContext}.<br>
<embed src="images/ArrayMerge_EqualTop.svg" type="image/svg+xml"/></p>
runtime/Java/src/org/antlr/v4/runtime/atn/PredictionContext.java