/*
 * LIST.java
 *
 * Created on December 8, 2008, 6:26 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package graph2;

/**
 *
 * @author suchenek
 */
//Copyright Dr. Marek A. Suchenek, 2005, 2006, 2007, 2008

// Interpretation: Object of class POSITION always points 
// to the previous element (for an extra level of indirection);
// needed to accomodate "end" position (next after last).

// Definition of position of an element x in a list L: 
// a subtail N of list L such that
// x is the head of tail of N.

// Subtail of a list L is either L itself or (if L is non-empty) 
// a subtail of tail of L

// Object of class LIST is implemented as a pair of objects of 
// type POSITION: (front, rear), just like in QUEUE


//Copyright Dr. Marek A. Suchenek, 2005, 2006, 2007, 2008

// Interpretation: Object of class POSITION always points 
// to the previous element (for an extra level of indirection);
// needed to accomodate "end" position (next after last).

// Definition of position of an element x in a list L: 
// a subtail N of list L such that
// x is the head of tail of N.

// Subtail of a list L is either L itself or (if L is non-empty) 
// a subtail of tail of L

// Object of class LIST is implemented as a pair of objects of 
// type POSITION: (front, rear), just like in QUEUE


public class LIST
{
	private POSITION first; //implements front, points to header
	private POSITION end; //implements rear, points to the last element
	
	public LIST()
	{
		cnt.incr();
                POSITION temp = new POSITION();	
		temp.head = null;
		temp.tail = null;
		first = temp;
		end = temp;
	}
	
	public void Insert(POSITION p, Object x)
	{
		cnt.incr();
                POSITION temp = new POSITION();
		temp.head = x;
		temp.tail = p.tail;
		p.tail = temp;
		if (p == end) end = temp;
	}
	
	public void Delete(POSITION p)
	{
		cnt.incr();
                if (p.tail == end) end = p; // if delete from last position, p becomes end position
		p.tail = p.tail.tail;
	}
	
	public Object Select(POSITION p)
	{
		cnt.incr();
                return p.tail.head;
	}
	
	public POSITION First()
	{
		cnt.incr();
                return first;
	}
	
	public POSITION Next(POSITION p)
	{
		cnt.incr();
                return p.tail;
	}
	
	public POSITION Previous(POSITION p)
	{
            POSITION q;
            for (q = First(); !Next(q).isEqual(p); q = Next(q))
                cnt.incr(); 	           
                return q;
	}
	
	public POSITION Last()
	{
            POSITION q;
            for (q = First(); !Next(q).isEqual(End()); q = Next(q))
                cnt.incr(); 	           
                return q;
	}
	
	public POSITION End()
	{
		cnt.incr();
                return end;
	}
}