/*
 * Main.java
 *
 * Created on February 6, 2008, 1:48 PM
 *
 *
 * MORE UP TO DATE VERSION IS IN LIST_DLL_purge with classname LIST_purge
 * WELL, THAT FILE CONTAINS SLL IMPLEMENTATION
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package list_dll_purge;

/**
 *
 * @author suchenek
 */
//Copyright Dr. Marek A. Suchenek, 2005, 2006, 2007, 2008 ,2009, 2010, 2011 - 2025

public class LIST_DLL_purge
{
	public static void main (String[] args)
	{
		LIST_DLL L = new LIST_DLL();
//Exercise: use Integer instead of Object and simplify this class
		Integer x;
                
                // The code below creates a list 
                // of N consecutive numbers
                // with duplicity W repeated M times
                
                long length = 0;
                int K = 10; //number of values
                int M = 10; //degree of duplicity - macro
                int W = 10; //degree of duplicity - micro

                for (int k=0;k<M;k++)
                {
                for (int i=0; i<K;i++)
                {
                x = new Integer(i);
                for (int u=0;u<W;u++)
                {
		L.Insert(L.End(), x);
                length++;
                }
                }
                }
                
                // End of The code below ...

                long N=length;
		System.out.println("N = "+ N);
                System.out.println("Original list:");

		for (POSITION_DLL p = L.First(); !p.isEqual(L.End()); p = L.Next(p)) 
				System.out.print(((Integer)L.Select(p)) + " ");
                System.out.println();

                cnt.clr();
                LIST_DLL C = L.clone();
                cnt.out("Clonning toook ", " steps");
                System.out.println(" N + 2 = " + (N+2));

                LIST_DLL D = L;
                
                
                System.out.println("Purge it!");
                cnt.clr();
		LIST_DLL_purge.Purge(L);

		for (POSITION_DLL p = L.First(); !p.isEqual(L.End()); p = L.Next(p))
				System.out.print((L.Select(p)) + " ");
                System.out.println();

                cnt3.clr();
                System.out.println("Same, in the reverse order");
		for (POSITION_DLL p = L.Last(); !p.isEqual(L.First()); p = L.Previous(p))
				System.out.print((L.Select(p)) + " ");
                System.out.print((L.Select(L.First())) + " ");
                System.out.println();
                cnt3.out(">>> Reverse printing of K = " + K + " elements toook ", " steps; 2*K + 1 = " + (2*K + 1));
                System.out.println();

                System.out.print("N = " + N);
                cnt.out(" cnt = ");
        long cntval = cnt.get(); // cost of purging and forward and backward traversal
        System.out.print(" cnt/N = " + (1.0*cntval/(N)));
        System.out.print(" cnt/N^2 = " + (1.0*cntval/(N * N)));
		System.out.print(" 4*N + 18 = "+ ((N)*4+18));
		System.out.println(" 4.5*N^2 + 11.5*N + 6 = "+ (6 + ((N)*23 + (N)*(N)*9)/2));

        System.out.println("Copied list:");
		for (POSITION_DLL p = D.First(); !p.isEqual(D.End()); p = D.Next(p))
				System.out.print((D.Select(p)) + " ");
        System.out.println();
        System.out.println("Cloned list:");
		for (POSITION_DLL p = C.First(); !p.isEqual(C.End()); p = C.Next(p))
				System.out.print((C.Select(p)) + " ");
        System.out.println();

                cnt3.clr();
                System.out.println("Same, in the reverse order");
		for (POSITION_DLL p = C.Last(); !p.isEqual(C.First()); p = C.Previous(p))
				System.out.print((C.Select(p)) + " ");
                System.out.print((C.Select(C.First())) + " ");
                System.out.println();
                cnt3.out(">>> Reverse printing of N = " + N + " elements toook ", " steps; 2*N + 1 = " + (2*N + 1));
                System.out.println();

        Purge(C);
        System.out.println("Purged cloned list:");
		for (POSITION_DLL p = C.First(); !p.isEqual(C.End()); p = C.Next(p))
				System.out.print((C.Select(p)) + " ");
        System.out.println();

	}
	
	
	public static void Purge(LIST_DLL L)
	{

		for (POSITION_DLL p = L.First(); !p.isEqual(L.End()); p = L.Next(p))
		{
			Object x = L.Select(p);
			POSITION_DLL q = L.Next(p);
			while (!q.isEqual(L.End())) 
			{
				Object y = L.Select(q);
				if (LIST_DLL_purge.isEqual(x, y)) L.Delete(q);
				else q = L.Next(q);
			}
		}
	}

	public static boolean isEqual(Object x, Object y) 
	{
        return (((Integer)x).equals((Integer)y));
	}
	
}