/*
 * LIST.java
 *
 * Created on March 24, 2008, 1:04 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package list_purge;

/**
 *
 * @author suchenek
 */
//Copyright Dr. Marek A. Suchenek, 2005, 2006, 2007, 2008 - 2015
//All rights reserved

// SLL implementation

// See class POSITION for interpretation of position.

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


// Object of class LIST is implemented as a pair of objects of 
// type POSITION: (first, end).

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

// End position needs to be updated after insertion on the end position and
// after deletion from the last position.

// If the list is empty then first == end.


public class LIST<E>
{
	private POSITION<E> first; // points to header
	private POSITION<E> end; // points to the last element
	
	public LIST() //constructs the empty LIST
	{
		cnt.incr();
                POSITION<E> temp = new POSITION<E>();
		temp.head = null; //never used
		temp.tail = null;
		first = temp;
		end = temp;
	}
	
	public void Insert(POSITION<E> p, E x)
	{
		cnt.incr();
                POSITION<E> temp = new POSITION<E>();
		temp.head = x;
		temp.tail = p.tail;
		p.tail = temp;
                if (p.isEqual(end)) end = temp; // if insert to end position, new temp becomes end position
//		if (p == end) end = temp; //a faster alternative
	}

	public boolean Delete(POSITION<E> p)
// Returns true if delete was allowed and false otherwise
	{
		cnt.incr();
                if((first == end) || (p == end)) return false;
                if(p.tail.isEqual(this.End())) end = p; // if delete from last position, p becomes end position
//                if(this.Next(p).isEqual(this.End())) end = p; // if delete from last position, p becomes end position
//                if (p.tail == end) end = p; // a faster alternative; if delete from last position, p becomes end position
		p.tail = p.tail.tail;
                return true;
	}
	
	public E Select(POSITION<E> p)
	{
		cnt.incr();
                return p.tail.head;
	}
	
	public void Replace(POSITION<E> p, E x)
	{
		cnt.incr();
                p.tail.head = x;
	}

	public POSITION<E> First()
	{
		cnt.incr();
                cnt3.incr(); // counting cost of reverse printing
                return first;
	}
	
	public POSITION<E> Next(POSITION<E> p)
	{
		cnt.incr();
                cnt3.incr(); // counting cost of reverse printing
                if(p == end) return null;
                return p.tail;
	}
	
	public POSITION<E> Previous(POSITION<E> p)
	{
            cnt.incr();
            cnt3.incr(); // counting cost of reverse printing
            if(p == first) return null;
            POSITION<E> q;
            for (q = First(); !Next(q).isEqual(p); q = Next(q))
            cnt.incr(); 	           
            return q;
	}
	
	public POSITION<E> Last() //Previous(End())
	{
            cnt.incr();
            POSITION<E> q;
            for (q = First(); !Next(q).isEqual(End()); q = Next(q))
            cnt.incr(); 	           
            return q;
	}
	
	public POSITION<E> End()
	{
            cnt.incr();
            return end;
	}

        public Boolean isEmpty()
    {
            return first == end;
        }

        public boolean hasPosition(POSITION<E> p)
	{
            cnt.incr();
            if (p.isEqual(End())) return true;
            for (POSITION<E> q = First(); !q.isEqual(End()); q = Next(q))
            {
                cnt.incr();
                if (p.isEqual(q)) return true;
            }
            return false;
	}

        public LIST<E> cloneAbstract()
//      Deep clone
	{
            LIST<E> toReturn = new LIST<E>();
            for (POSITION<E> p = First(); !p.isEqual(End()); p = Next(p))
            {
                toReturn.Insert(toReturn.End(), Select(p));
            }
            return toReturn;
        }

        public LIST<E> clone()
//      Deep clone
	{
            LIST<E> toReturn = new LIST<E>();
            for (POSITION<E> p = first; p != end; p = p.tail)
            {
                cnt.incr();
                POSITION<E> temp = new POSITION<E> ();
                temp.head = p.tail.head;
                temp.tail = null;
                toReturn.end.tail = temp;
                toReturn.end = temp;
            }
            return toReturn;
        }


//        public LIST<E> clone()
//	{
//            LIST<E> toReturn = new LIST<E>();
//            for (POSITION<E> p = first; p != end; p = p.tail)
//            {
//                toReturn.Insert(toReturn.End(), this.Select(p));
//            }
//            return toReturn;
//        }


}