// JavaListMerge.java SJ
// Example on using java.util.LinkedList (list merge)

import java.util.*;



public class JavaListMerge {

	public static void main(String[] args) {

		int N = 10;
		if (args.length > 0)
			N = Integer.valueOf(args[0]);

		boolean print = false;
		if (args.length > 1)
			print = true;

		long start;

		LinkedList<Integer> L1 = new LinkedList<Integer>();
		LinkedList<Integer> L2 = new LinkedList<Integer>();

		start = (new Date()).getTime();
		System.out.println("Generate two increasing Java list");
		for (int i = 0; i < N; i++) {
			L1.add(i*2);
			L2.add(i*3);
		}
		System.out.println("Generation: " + ((new Date()).getTime()-start) + " ms");

		if (print) {
			System.out.println("Originals");
			System.out.println(L1);
			System.out.println(L2);
		}

		start = (new Date()).getTime();
		System.out.println("Merge");
		merge(L1, L2);
		System.out.println("Time: " + ((new Date()).getTime()-start) + " ms");

		if (print) {
			System.out.println("Merged");
			System.out.println(L1);
		}


		System.out.println("");
		L1 = new LinkedList<Integer>();
		L2 = new LinkedList<Integer>();

		start = (new Date()).getTime();
		System.out.println("Create two sorted lists");
		for (int i = 0; i < N; i++) {
			L1.add(i*2);
			L2.add(i*3);
		}
		System.out.println("Create: " + ((new Date()).getTime()-start) + " ms");

		if (print) {
			System.out.println("Originals");
			System.out.println(L1);
			System.out.println(L2);
		}

		start = (new Date()).getTime();
		System.out.println("Merge22");
		merge2(L1, L2);
		System.out.println("Time: " + ((new Date()).getTime()-start) + " ms");

		if (print) {
			System.out.println("Merged");
			System.out.println(L1);
		}

	} // main()

    // merges list L2 into L1
    // both in ascending order
    // using iterators
    // O(n+m)
	public static void merge(LinkedList L1, LinkedList L2) {
		
		ListIterator i1 = L1.listIterator(0);
		Comparable x1 = null;

		boolean end1 = false;
		if (i1.hasNext())
			x1 = (Comparable)(i1.next());
		else
			end1 = true;

		for(Object x2 : L2) {

			if (end1) {
				L1.add(x2);
			} else {
				while (x1.compareTo(x2) < 0) {
					if (i1.hasNext())
						x1 = (Comparable)(i1.next());
					else {
						end1 = true;
                        L1.add(x2);
						break;
					}
				}
                if (! end1) {
                    i1.previous(); // insert in front of i1
                    i1.add(x2);
                    i1.next();
                }
			}

		} // for

	} // merge()

    // parametrized version
	public static <E extends Comparable<? super E>>
        void mergee(LinkedList<E> L1, LinkedList<E> L2) {
		
		ListIterator<E> i1 = L1.listIterator(0);
		Comparable<? super E> x1 = null;

		boolean end1 = false;
		if (i1.hasNext())
			x1 = i1.next();
		else
			end1 = true;

		for(E x2 : L2) {

			if (end1) {
				L1.add(x2);
			} else {
				while (x1.compareTo(x2) < 0) {
					if (i1.hasNext())
						x1 = i1.next();
					else {
						end1 = true;
                        L1.add(x2);
						break;
					}
				}
                if (! end1) {
                    i1.previous(); // insert in fron of i1
                    i1.add(x2);
                    i1.next();
                }
			}

		} // for

	} // merge()

    // merges list L2 into L1
    // both in ascending order
    // using indexes
    // O(n*m) (i.e.: slow!)
	public static void merge2(LinkedList L1, LinkedList L2) {
	
		int i1 = 0;
		for(Object x2 : L2) {

			while (i1 < L1.size() && ((Comparable)(x2)).compareTo(L1.get(i1)) > 0)
				i1++;

			L1.add(i1, x2);

		} // for

	} // merge2()

			
} // class JavaListMerge