// TraListMerge.java SJ
// List merge using TraLinkedList

import fi.joensuu.cs.tra.*;
import java.util.Date;

public class TraListMerge {

	public static void main(String[] args) {

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

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

		long start;

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

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

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

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


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

	} // main()


	// prints a TraLinkedList
	public static void printList(TraLinkedList L) {

		ListNode p = L.first();
		System.out.print("(");
		while (p != L.EOL) {
			System.out.print(p.getElement());
			p = p.next();
			if (p != L.EOL)
				System.out.print(",");
		}
		System.out.println(")");

	} // printList()


	// adds elements of L2 to L1, both in ascending order
	public static <E extends Comparable<? super E>> void merge(TraLinkedList<E> L1,
							 TraLinkedList<E> L2) {
		ListNode<E> p1 = L1.first();
		ListNode<E> p2 = L2.first();
		while (p2 != L2.EOL)  {
			if ((p1 == L1.EOL) ||
				(p2.getElement().compareTo(p1.getElement()) < 0)) {
				L1.insert(p1, p2.getElement());
				p2 = p2.next();
			} else
				p1 = p1.next();
		}
	} // merge()

} // class TraListMerge