package caida.list;
import java.awt.*;

/************************************************************************
By accessing this software, MYLIST, you are duly informed of and 
agree to be bound by the conditions described below in this notice:
 
This software product, MYLIST, is developed by Bradley Huffaker, and
copyrighted(C) 1998 by the University of California, San Diego (UCSD),
with all rights reserved.  UCSD administers the NSF grant to CAIDA,
number NCR-9711092, under which this code was developed.
 
There is no charge for MYLIST software. You can redistribute it and/or
modify it under the terms of the GNU General Public License, v. 2 dated
June 1991 which is incorporated by reference herein.  MYLIST is
distributed WITHOUT ANY WARRANTY, IMPLIED OR EXPRESS, OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE or that the use of
it will not infringe on any third party's intellectual property
rights.
 
You should have received a copy of the GNU GPL along with the MYLIST
program.  Copies can also be obtained from
http://www.gnu.org/copyleft/gpl.html or by writing to
 
                        University of California, San Diego
                        SDSC/CAIDA
                        9500 Gilman Dr., MS-0505
                        La Jolla, CA 92093 - 0505  USA
 
  Or contact INFO@CAIDA.ORG
***********************************************************************/


        /*****************************************************
        *  MyNode                       written 7/05/97
        *  by Bradley Huffaker
        *  Cooperative Association for Internet Data Analysis
        *  version 1.0
        ******************************************************/


	/** MyNode *******************************************
	 *	Helper class to MyList. Used to store the data
	 *****************************************************/
	class MyNode extends Object
	{
		public Object value;
		public MyNode next;
		
		public MyNode(Object val)
		{
			value = val;
			next = null;
		}
	}

	/** MyList *******************************************
	*	A linked list that has many of the standard
	*	linked list member functions clear, enqueue, 
	*	push, pop, and empty.  But also have a few of
	*	my own creation: where, reset, next, insert,
	*	and end.  Which allow the user to edit/view 
	*	list with out destory it.
	*****************************************************/
public class MyList extends Object
{
	
	MyNode first;	
	MyNode tail;
	
	MyNode before;
	MyNode where;
		
	/** MyNode() *******************************************
	*	Default Constructor.
	*****************************************************/
	public MyList()
	{
		where=before=tail = first = null;
	}

	/** MyList(MyList list) *****************************
	*	Copy constructor.  Create new list with same
	*	values.
	*****************************************************/
	public MyList(MyList list)
	{
		if (list.first == null)
		{
			tail = first = null;
			return;
		}
		tail = first =new MyNode(list.first.value); 
		tail.next = null;
	
		MyNode his = list.first.next;
		tail = first;
		while (his != null)
		{
			tail.next = new MyNode(his.value);
			tail = tail.next;
			his = his.next;
		}
 
                reset();

	}

	/** clear() *****************************************
	*	Removes all nodes from the list.  Notes that
	*	because java does all the garabage collection
	*	Simple making is so all nodes point to null 
	*	is same thing.
	*****************************************************/
 	public void clear()
	{
		where = before= tail = first = null;
	}
		
	/** push(Object value) ********************************
	 *	Adds the value to the front of the list.
	 *****************************************************/
	public void push(Object value)
	{
		MyNode temp = new MyNode(value);
		if (first == null)
		{
			tail = first = temp;
			first.next = null;
			return;
		}
		
		temp.next = first;
		first = temp;
		temp = null;
	}
	
	/** enqueue(Object value) ****************************
	*	Stores value in a node at the end of the link
	*	list.
	*****************************************************/
	public void enqueue(Object value)
	{
		MyNode temp = new MyNode(value);
		if (first == null)
		{
			tail = first = temp;
			first.next = null;
			return;
		}
		tail.next = temp;
		tail = tail.next;
		tail.next = null;
	}

	/** top() *******************************************
	*	Returns the value of the top node or null
	*	if there are no nodes.
	*****************************************************/
	public Object top ()
	{
		if (first != null)
			return first.value;
		else
			return null;	
	}
		
	/** pop() *******************************************
	*	Removes the top node and then returns 
	*	the value it contrained.
	*****************************************************/
	public Object pop ()
	{
		if (first == null)
			return null;
		if (first == where)
			where = first.next;
		Object value = first.value;
		first = first.next;
		return value;
	}

	/** empty() *****************************************
	*	Checks to see if the list has any nodes. Returns
	*	true if it does else false.
	*****************************************************/
	public boolean empty()
	{
		return (first == null);
	}

	/** exists(Object value) *****************************
	*	Returns true if value is contained in the link
	*	list and false if it is not found.
	*****************************************************/
	public boolean exists(Object value)
	{
		MyNode current = first;
		while (current != null)
		{
			if (current.value == value)
				return true;
			current = current.next;
		}

		return false;
	} 
	
	/** drop(Object value) ******************************
	*	Drop the first node in the list that contains
	*	the passed value.
	*****************************************************/
	public boolean drop(Object value) 
	{
		MyNode previous = first;
		MyNode current = first;
		while (current != null)
		{
			if (current.value == value)
			{
				if (current == first)
				{
					previous = first = first.next;
				}
				else 
					previous.next = current.next;

				if (before == current)
					before = previous;
				else if (where == current)
					where = current.next;
				if (current == tail)
					tail = previous;

				return true;
			}
			previous = current;
			current = current.next;
		}
		return false;
	}
	
	/** count() *******************************************
	*	Returns the number of nodes currently in linked 
	*	list.	
	*****************************************************/
	public int count()
	{
		int count = 0;
		MyNode current = first;
		while(current != null)
		{
			count++;
			current = current.next;
		}
		return count;
		
	}
	
	/** where() *******************************************
	*	Returns the value stored in the where pointer.
	*	returns null if the where pointer is null.
	*****************************************************/
	public Object where()
	{
		if (where != null)
			return where.value;
		else
			return null;
	}
	
	/** next() ******************************************
	*	Moves the where pointer to the next node in the 
	* 	link and returns the value that was stored in the 
	* 	current node, before the move.	
	*****************************************************/
	public Object next()
	{
		if (where == null)
			return null;
		Object temp = where.value;
		before = where;
		where = where.next;
		return temp;
	}

	/** remove() ****************************************
	*	Removes the node that where is pointing to.	
	*	Then returns the value that was stored in the 
	*	where pointer.
	*****************************************************/
	public Object remove()
	{
		if (where == null)
			return null; 
		
		if (before == null)
		 	first = first.next;
			
		MyNode temp = where;
		before.next = where.next;
		where = where.next;
	
		return temp.value;
	}

	/** insert(Object value) ****************************
	*	Inserts a value into the linked list just ahead
	*	of the location of the where pointer.
	*****************************************************/
        public void insert(Object value)
        {
                MyNode node = new MyNode (value);
                if (before == null)
                {
                        node.next = first;
                        first = node;
                }
                else
                {
                        node.next = before.next;
                        before.next = node;
                }
                where = node;
        }
	
	/** reset() *****************************************
	*	Reset the where pointer to the beginnen of 
	*	Of the linked list.  Used to start a next 
 	*	Loop	
	*****************************************************/
	public void reset()
	{
		before = null;
		where = first;
	}
	
	/** end() *******************************************
	*	Notes where the where pointer reaches the end
	*	of the list.  Used as the boolean statment
	*	when interating throught the loop with next
	*****************************************************/
	public boolean end()
	{
		return (where == null);
	} 

 	/** String print() **********************************
 	* 	Returns a string which is a close representaion
	*	of where the major nodes are
	*	f= first
	*	t = tail
	*	b = before
	*	w = where
	******************************************************/
	public String print()
	{
		MyNode current = first;
		String answer = "[";
		while (current != null)
		{
			if (current == first)
				answer = answer + "f";
			if (current == before)
				answer = answer + "b";
			if (current == where)
				answer = answer + "w";
			if (current == tail)
				answer = answer + "t";
			answer = answer + ",";
			current = current.next;
		}
			if (where == null)
				answer = answer + "w";
		answer = answer + "]";
		return answer;
	}
}