/*
 * LIST_DLL.java
 *
 * Created on February 6, 2008, 1:52 PM
 *
 *
 * 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

// See class POSITION_DLL for interpretation of position.

// Object of class LIST_DLL is implemented as POSITION_DLL: (first).

// First position never changes during the lifetime of the list in question.



public class LIST_DLL
{
	private POSITION_DLL first; //never changes because it is a reference to the header of the list
	
	public LIST_DLL() //constructor of the empty list
	{
                cnt.incr();
		first = new POSITION_DLL();	
		first.head = null; //not necessary
		first.tail = first; //self-reference
		first.nose = first; //self-reference
//	System.out.println("List created");

	}
	
	public void Insert(POSITION_DLL p, Object x)
	{
// Optimal method because one new position, assignment of x, 
// and update of 4 references (2 tails and 2 noses) are necessary to carry it on.
                cnt.incr();
		POSITION_DLL temp = new POSITION_DLL();
		temp.head = x;
		temp.tail = p.tail;
		temp.nose = p; 
		temp.tail.nose = temp; //same as: p.tail.nose = temp;
		temp.nose.tail = temp; //same as: p.tail = temp;
// System.out.println("Insert completed");

	}
	
	public void Delete(POSITION_DLL p)
	{
// Optimal method because update of 2 references (1 tail and 1 nose) are necessary to carry it on.
		p.tail = p.tail.tail; //promoting the tail after the deleted element
		p.tail.nose = p; //fixing nose after the deleted element (must be the inverse of tail)
                cnt.incr();
        }
	
	public Object Select(POSITION_DLL p)
	{
            cnt.incr();
            return p.tail.head;
	}
	
	public POSITION_DLL First()
	{
                cnt.incr();
                cnt3.incr(); // counting cost of reverse printing
		return first;
	}
	
	public POSITION_DLL Next(POSITION_DLL p)
	{
                cnt.incr();
                cnt3.incr(); // counting cost of reverse printing
		return p.tail;
	}
	
	public POSITION_DLL Previous(POSITION_DLL p)
	{
                cnt.incr();
                cnt3.incr(); // counting cost of reverse printing
		return p.nose;
	}
	
	public POSITION_DLL End()
	{
                cnt.incr();
                cnt3.incr(); // counting cost of reverse printing
		return first.nose;
	}

	public POSITION_DLL Last() //Previous(End())
	{
                cnt.incr();
                cnt3.incr(); // counting cost of reverse printing
		return first.nose.nose;
	}

        public boolean isEmpty()
	{
                cnt.incr();
		return first.isEqual(first.nose);
//		return (this.First()).isEqual(this.End());
	}

        public LIST_DLL abstractClone()
        {
            POSITION_DLL p;
            LIST_DLL toReturn = new LIST_DLL();
//            POSITION_DLL q = toReturn.First();
            for (p = First(); !p.isEqual(End()); p = Next(p))
            {
                toReturn.Insert(toReturn.End(), Select(p));
//                q = toReturn.Next(q);
            }
            return toReturn;
        }

        public LIST_DLL clone()
// Deep clone
        {
            cnt.incr();
            LIST_DLL toReturn = new LIST_DLL();
            POSITION_DLL temp;
            for (POSITION_DLL p = first; p != first.nose; p = p.tail)
            {
                cnt.incr();
		temp = new POSITION_DLL();
		temp.head = p.tail.head;
		temp.tail = toReturn.first.nose.tail;
		temp.nose = toReturn.first.nose;
		temp.tail.nose = temp; 
		temp.nose.tail = temp; 
            }
            return toReturn;
        }

        public boolean hasPosition(POSITION_DLL p)
	{
            if (p.isEqual(End())) return true;
            for (POSITION_DLL q = First(); !q.isEqual(End()); q = Next(q))
		if (p.isEqual(q)) return true;
            return false;
	}
}