//
//  MergeList.java
//  
//
//  Created by Herbert J. Bernstein on 2/24/11.
//  Copyright 2011 All rights reserved.
//

import java.io.*;
import java.util.Scanner;

public class MergeList {
    
    public static void main(String[] args) {
        ListNode a, b, c;
        int ka, kb, kc, i, value;
        ListNode cn;
        a = new ListNode();
        b = new ListNode();
        c = new ListNode();
        Scanner scanner = new Scanner(System.in);
        
        // First assume pre-sorted lists 
        
        // Read in list a
        
        System.out.print(" number of items list a: ");
        ka = scanner.nextInt();
        System.out.println(ka);
        for(i = 0; i < ka; i++) {
            System.out.print("a element "+ i + ": ");
            value = scanner.nextInt();
            System.out.println(value);
            ListNode.listappend(a,value);
        }
        
        System.out.println("list a:");
        ListNode.printl(a);

        // Read in list b 
        System.out.print(" number of items list b: ");
        kb = scanner.nextInt();
        System.out.println(kb);
        for(i = 0; i < kb; i++) {
            System.out.print("b element "+ i + ": ");
            value = scanner.nextInt();
            System.out.println(value);
            ListNode.listappend(b,value);
        }

        System.out.println("list b:");
        ListNode.printl(b);

        
        // Create merged list c 
        
        ListNode.mergel(a,b,c);
        System.out.println("merged ist c:");
        ListNode.printl(c);
        
        // Now get rid of all three lists and do it again with unsorted
        //  data by merging in each element as we get it 
        
        a = new ListNode();
        b = new ListNode();
        c = new ListNode();
        
        // Read in list a
        
        System.out.print("number of items list a: ");
        ka = scanner.nextInt();
        System.out.println(ka);
        
        // Put the element onto list a via cn using mergel to do the sort 
        
        for(i = 0; i < ka; i++) {
            System.out.print("a element " + i + ": ");
            value = scanner.nextInt();
            System.out.println(value);
            cn = new ListNode();
            ListNode.listappend(cn,value);
            ListNode.mergel(a,cn,c);
            a = c;
            c = new ListNode();
        }
        
        System.out.println("list a:");
        ListNode.printl(a);
        
        // Read in list b
        
        
        System.out.print("number of items list b: ");
        kb = scanner.nextInt();
        System.out.println(kb);
        
        // Put the element onto list a via cn using mergel to do the sort 
        
        for(i = 0; i < kb; i++) {
            System.out.print("b element "+ i + ": ");
            value = scanner.nextInt();
            System.out.println(value);
            cn = new ListNode();
            ListNode.listappend(cn,value);
            ListNode.mergel(b,cn,c);
            b = c;
            c = new ListNode();
        }
        
        System.out.println("list a:");
        ListNode.printl(a);

        // Create merged list c 
        
        ListNode.mergel(a,b,c);
        System.out.println("merged list a:");
        ListNode.printl(a);
        System.out.println("merged list b:");
        ListNode.printl(b);
        System.out.println("merged list c");
        ListNode.printl(c);
        
        // test the insert operations 
        
        ListNode.listinsert(c,0,0);
        ListNode.listinsert(c,4,1);
        ListNode.listinsert(c,1,1);
        ListNode.listinsert(c,5,3);
        ListNode.listinsert(c,2,2);
        ListNode.listinsert(c,6,5);
        ListNode.listinsert(c,3,3);
        System.out.println("updated list c:");
        ListNode.printl(c);
        ListNode.listinsert(c,22,22);
        System.out.println("reupdated list c:");
        ListNode.printl(c);
        
        return;
    }    

}