/*
 * POSITION_DLL.java
 *
 * Created on February 6, 2008, 1:51 PM
 *
 *
 * MORE UP TO DATE VERSION IS IN LIST_DLL_purge with classname POSITION
 *
 * 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

// DLL implementation

// POSITION_DLL is a list of the form (head, tail, nose).

// It extends POSITION (in SLL implementation - see a copy below) with an instance variable nose
// defined by the following constrain:

//               operation .nose is the inverse of operation .tail 

// In other words, for any position p, 

//               p.tail.nose == p and p.nose.tail == p.

// (Property: nose of subtail N of list L is the position of the head of N in L.)
// (Definition of subtail of list L is given in a copy below.)

// In order to make both operations .tail and .nose total (never having a null value, that is), 
// and to avoid having both header and trailer in a list, a DLL is circular, that is:

// 				first.nose == end

// and 

// 				end.tail == first

// This makes the instance variable end in DLL superflous.

// It saves updating end after deleting the last element and after inserting on the end position.

// Instance variable first never changes, so it does not require to be updated.


// THE DESCRIPTION BELOW IS A COPY FROM SLL IMPLEMENTATION OF POSITION

// 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. (It exists for every element; in particular, use of the header
// ensures the existence of first position.)

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

// Interpretation: Position always points to the previous element (for an extra level of
// indirection), which is also needed to accomodate "end" position (next after last).

// This makes the trailer (an element the represents the end position) superflous, but
// requires introduction of an element (the header) that is pointed to by the first position.


public class POSITION_DLL
{
	public Object head;
	public POSITION_DLL tail;
	public POSITION_DLL nose; // .nose is the inverse operation to .tail

	public boolean isEqual(POSITION_DLL p)
	{
		return (this == p); // don't be deceived by the simplicity of this - it's not as obvious as it seems! 	

					// test (this.tail == p.tail) doesn't work
					// for the case of this and p being end positions on
					// different lists ((this.tail == p.tail)returns true,
					// while false is correct)
	}

        public boolean isValidPosition(LIST_DLL L)
	{
            if (this.isEqual(L.End())) return true;
            for (POSITION_DLL q = L.First(); q != L.End(); q = L.Next(q))
		if (this.isEqual(q)) return true;
            return false;
	}

}