// h4_t1.java SJ

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

public class h4_t1 {

	public static void main(String[] args) {

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

		TraLinkedList<Integer> omalista = randomList(N, N, N);

		System.out.println("Alkuperainen");
		printList(omalista);

		for (int i = 1; i < N; i++) {
			System.out.println("Kasvavat " + i + " "); 
			tulostaKasvavat(omalista, i);
		}


	} // main()


	// returns a new TraLinkedList<Integer>
	public static TraLinkedList<Integer> randomList(int N, int M, int seed) {

		TraLinkedList<Integer> L = new TraLinkedList<Integer>();

		Random r = new Random(seed);
		Integer x = new Integer(0);
		for (int i = 0; i < N; i++) {
            x = r.nextInt(M);
            L.insert(L.EOL, x);
        }

		return L;
	} // randomList()


	// 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()


	/* Kirjoita algoritmi joka tulostaa annetusta listasta kaikki vahintaan
		   k alkion mittaiset kasvavat osajaksot. Jos siis kukin k:sta alkiosta
		   on edeltajaansa suurempi, tulostetaan ko. alkioita kunnes jokin
		   alkio on pienempi (tai yhtasuuri) kuin edellinen tai lista loppuu.
                   Vihje: keraa kasvavaa sarjaa jonoon. */

	public static void tulostaKasvavat(TraLinkedList<? extends Comparable> L,
									   int k) {
		LinkedDeque<Comparable> Q = new LinkedDeque<Comparable>();

		ListNode<? extends Comparable> p = L.first();

		if (p == L.EOL)
			return;

		// 1. alkio jonoon
		Q.addLast((Comparable)(p.getElement()));
		// Q.addLast(p.getElement());
		int i = 1;

		p = p.next();
		while (p != L.EOL) {
			if (Q.getLast().compareTo(p.getElement()) < 0) {
				// suurempi kuin edellinen
				Q.addLast(p.getElement());
				i++;
			} else {
				// pienempi kuin edellinen
				tyhjennaJaEhkaTulosta(Q, i >= k);
				Q.addLast(p.getElement());
				i = 1;
			}
			p = p.next();
		} // while p
		tyhjennaJaEhkaTulosta(Q, i >= k);

	} // tulostaKasvavat()


	public static void tyhjennaJaEhkaTulosta(LinkedDeque Q, boolean tulosta) {
		while (! Q.isEmpty()) {
			if (tulosta)
				System.out.print(Q.getFirst() + " ");
			Q.removeFirst();
		}
		if (tulosta)
			System.out.println();
	} // tyhjennaJaEhkaTulosta()



}

====================================================

// h4_t2.java SJ

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

public class h4_t2 {

	public static void main(String[] args) {

		int N1 = 4;
        if (args.length > 0)
            N1 = Integer.valueOf(args[0]);

		int N2 = 4;
        if (args.length > 0)
            N2 = Integer.valueOf(args[1]);

		TraLinkedList<Integer> omalista1 = randomList(N1, 9, N1+N2+1);
		TraLinkedList<Integer> omalista2 = randomList(N2, 9, N1+N2+1);

		System.out.println("Alkuperaiset");
		printList(omalista1);
		printList(omalista2);

		System.out.println("Summa");
		printList(summa(omalista1, omalista2));

	} // main()


	// returns a new TraLinkedList<Integer>
	public static TraLinkedList<Integer> randomList(int N, int M, int seed) {

		TraLinkedList<Integer> L = new TraLinkedList<Integer>();

		Random r = new Random(seed);
		Integer x = new Integer(0);
		for (int i = 0; i < N; i++) {
            x = r.nextInt(M);
            L.insert(L.EOL, x);
        }

		return L;
	} // randomList()


	// 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()


	/* 22)  Kirjoita algoritmi joka saa parametrinaan kaksi kokonaislukulistaa
			(kukin luku valilta 0..9) ja joka laskee listojen summan, eli siis
			uuden listan jonka alkiot esittavat kokonaislukua, joka saadaan
			alkuperaisten listojen summasta. Huomaa ylivuodot (siirrot). Esim.
			listoista (5 2 3 4 5) ja (6 7 8 9 0) tulee lista (1 2 0 2 3 5).
			Huomaa, etteivat listat valttamatta ole saman mittaisia.
			Aikavaativuus? Voit kayttaa joko TraLinkedList:ia tai
			java.util.LinkedList:a. */

	public static TraLinkedList<Integer> summa(TraLinkedList<Integer> L1,
											   TraLinkedList<Integer> L2) {

		TraLinkedList<Integer> L = new TraLinkedList<Integer>();

		int sum = 0, v1, v2, carry;

		ListNode<Integer> p1 = L1.last();
		ListNode<Integer> p2 = L2.last();

		while ((p1 != L1.EOL) || (p2 != L2.EOL)) {

			// otetaan kokonaisluvut listoista
			if (p1 != L1.EOL) {
				v1 = p1.getElement().intValue();
				if (p1 != L1.first())		// tama on tarpeeton jos/kun
					p1 = p1.previous();	// L.EOL == null
				else
					p1 = L1.EOL;
			} else
				v1 = 0;
		
			if (p2 != L2.EOL) {
				v2 = p2.getElement().intValue();
				if (p2 != L2.first())		// tama on tarpeeton jos/kun
					p2 = p2.previous();	// L.EOL == null
				else
					p2 = L2.EOL;
			} else
				v2 = 0;

			sum = sum + v1 + v2;

			L.insert(L.first(), sum % 10);

			sum = sum / 10;

		} // while

		if (sum > 0)
			L.insert(L.first(), sum);

		return L;

	} // summa()


} 

=============================================

// Queue.java

import fi.joensuu.cs.tra.*;

public class Queue<E> extends TraLinkedList<E> {
   public Queue() {
        super();
   }
   public void enqueue(E x) {
        super.insert(super.EOL, x);
   }
   public E dequeue() {
        return super.remove(super.first());
   }
   public E getFirst() {
        return super.first().getElement();
   }
   public boolean isEmpty() {
        return super.isEmpty();
   }

   // testaus:

   public static void main(String[] args) {

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

       Queue<Integer> Q = new Queue<Integer>();
       for (int i = 0; i < N; i++)
           Q.enqueue(i*10);

       for (int i = 0; i < N; i++) {
           Integer x = Q.dequeue();
           System.out.print(x + " ");
           Q.enqueue(x);
       }
       System.out.println();

       reverse(Q);

       for (int i = 0; i < N; i++) {
           Integer x = Q.dequeue();
           System.out.print(x + " ");
           Q.enqueue(x);
       }
       System.out.println();
   }

   public static void reverse(Queue Q) {
       LinkedStack S = new LinkedStack();
       while (! Q.isEmpty())
           S.push(Q.dequeue());
       while (! S.isEmpty())
           Q.enqueue(S.pop());


   }

}