// SortedList.java
// implementation
//

public class SortedList
{
	private int length;
	private ListNode listData;
	private ListNode currentPos;
	public SortedList()
	{
		length = 0;
		listData = null;
		currentPos = null;
	}
	public boolean isEmpty()
	{	return length==0;	}
	public void insert(String item)
	{	ListNode newNode, preLoc, location;
		length ++;
		boolean moreToSearch;

		location = listData;
		preLoc = null;
		moreToSearch = (location != null);
		while(moreToSearch)
		{	if(item.compareToIgnoreCase(location.getData())>0)
			{	preLoc = location;
				location = location.getLink();
				moreToSearch = (location != null);
			}
			else	moreToSearch = false;
		}
		newNode = new ListNode(item, null);
		// insert as the first node
		if(preLoc == null)
		{	newNode.setLink(listData);
			listData = newNode;
		}
		else
		{	newNode.setLink(location);
			preLoc.setLink(newNode);
		}
		currentPos = newNode;
	}
	public void remove(String item)
	{
		ListNode location = listData;	// temp pointer
		// for the first node
		if(location.getData().equalsIgnoreCase(item))
			listData = listData.getLink();
		else
		// not the first one
		{
			while(!location.getLink().getData().equalsIgnoreCase(item))
				location = location.getLink();
			ListNode temp = location.getLink();
			// the current node points the node that
			//		temp's next points to
			location.setLink(temp.getLink());
		}
		length --;
	}
	public void Print()
	{	reset();
		printFromCurrent();
	}
	public void printFromCurrent()
	{
		ListNode temp = currentPos;
		System.out.println("The list is: ");
		while(temp != null)
		{	System.out.print(temp.getData() + " ");
			temp = temp.getLink();
		}
		System.out.println();
	}
	private void reversePrint(ListNode ptr)
	{
		if(ptr!=null)
		{
			reversePrint(ptr.getLink());
			System.out.print(ptr.getData() + " ");
		}
	}
	public void revPrint()
	{
		reversePrint(listData);
		System.out.println();
	}
	public void reset()
	{	currentPos = listData;	}
	public String getCurentItem()
	{
		return currentPos.getData();
	}
	public String getNextItem()
	{	ListNode temp = currentPos;
		temp = temp.getLink();
		return temp.getData();
	}
	public String getCurrentItem()
	{	return currentPos.getData();	}
	public boolean search(String item)
	{
		boolean find = false;
		ListNode temp = listData;
		while(temp != null)
		{	if(temp.getData().equalsIgnoreCase(item))
			{	find = true;
				currentPos = temp;
			}
			// move one node forward
			temp = temp.getLink();
		}
		return find;
	}
/*
	public void deleteItem(String item);
*/
	public static void main(String[] args)
	{
		SortedList sl = new SortedList();
		sl.insert("Yon");
		sl.revPrint();
		sl.insert("Lee");
		sl.revPrint();
		sl.insert("Tom");
		sl.revPrint();
		if(sl.search("Tom"))
		{
			System.out.println("We got it.");
			sl.remove("Tom");
		}
		else
			System.out.println("The code has error.");
		sl.revPrint();
	}
}