arrayeddictuos.java

国外的数据结构与算法分析用书

/* ArrayedDictUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */
 
package dslib.dictionary.arrayed;

import dslib.exception.*;
import dslib.dictionary.*;
import dslib.base.*;

/**	A Dictionary implemented via an unordered sequence of 
	items in an array.  There is a method to insert an item,
	and the usual dictionary methods: has, obtain, and delete.  
	It includes the linear iterator capabilities. Items are not ordered 
	in the dictionary. */
public class ArrayedDictUos extends ArrayedBasicDictUos implements DictUos
{
	/**	The current position in the array. */
	protected int pos;

	/**	Default constructor which makes a bag. <br> 
		Analysis: Time = O(size) 
		@param size capacity of the dictionary*/
	public ArrayedDictUos(int size)
	{
		super(size);
		pos = -1;
	}
 
	/**	Is there a current item?. <br> 
		Analysis: Time = O(1) */
	public boolean itemExists()
	{ 
		return ((!before()) && (!after()));
	}
   
	/**	The current item in the dictionary. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists() 
		</ul> */
	public Object item() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist.");  
		
		return rep[pos];
	}

	/**	Is the current position before the start of the structure?. <br> 
		Analysis: Time = O(1) */
	public boolean before()
	{
		return pos<0;
	} 

	/**	Is the current position after the end of the structure?. <br> 
		Analysis: Time = O(1) */
	public boolean after()
	{
	   return pos>=count;
	} 

	/**	Should next search continue from current item or start at the beginning. */
	protected boolean searchesContinue = false;
  
	/**	Subsequent searches start at the first item. <br> 
		Analysis: Time = O(1) */
	public void restartSearches()
	{
		searchesContinue = false;
	}
  
	/**	Subsequent searches continue from the next position. <br> 
		Analysis: Time = O(1) */
	public void resumeSearches()
	{
		searchesContinue = true;
	}
   
	/**	Move the current position to next item that equals i. <br> 
		Analysis: Time = O(n) 
		@param i item being sought in dictionary */
	public void search(Object i)
	{
		if (!searchesContinue)
			goFirst();
		else if (!after())
			goForth();

		while (!after() && !membershipEquals(i, item()))
			goForth();
	}

	/**	Advance one item in the data structure. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			!after() 
		</ul> */ 
	public void goForth() throws AfterTheEndUosException
	{
		if (after())
			throw new AfterTheEndUosException("Cannot advance to next item since already after");

		pos++;
	}

	/**	Go to the first item of the dictionary (if it exists). <br> 
		Analysis: Time = O(1) */
	public void goFirst()
	{ 
		pos = 0;
	}

	/**	Move prior to the first item. <br> 
		Analysis: Time = O(1) */
	public void goBefore()
	{
		pos = -1;
	}
	
	/**	Move after the last item. <br> 
		Analysis: Time = O(1) */
	public void goAfter()
	{
		pos = count;
	}
   
	/**	Change the current item to another item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists() 
		</ul> 
		@param x item to replace the current item */
	public void setItem(Object x) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot set an item that does not exist.");  
	  
	  	rep[pos] = x;
	}

	/**	Delete the item x. <br> 
		Analysis: Time = O(n), where n = number of items in the array <br>
		PRECONDITION:  <br>
		<ul>
			itemExists() 
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot perform deletion since no current item.");  
	
		deleteItemAt(pos);
	}

	/**	Remove all items from the data structure. <br> 
		Analysis: Time = O(1) */ 
	public void wipeOut()
	{
		super.wipeOut();
		goBefore();
	}

	/**	Delete the item in the position specified by position. <br> 
		Analysis: Time = O(count) 
		@param position the location of the item to be deleted */
	protected void deleteItemAt(int position)
	{      
		for (int index = position + 1; index<=count-1; index++)
			rep[index-1] = rep[index]; 
		count--;
	   
		if (pos>position)
			pos--;
	}

	/**	A cursor at the current position. <br> 
		Analysis: Time = O(1) */
	public CursorUos currentPosition()
	{
		ArrayedIteratorUos iter = new ArrayedIteratorUos(rep, count);
		iter.setPos(pos);
		return iter;
  	}

	/**	Go to the position specified by c. <br> 
		Analysis: Time = O(1) 
		@param c position to which to go */
	public void goPosition(CursorUos c)
	{
		ArrayedIteratorUos iter =  (ArrayedIteratorUos)c;
		pos = iter.pos();
	}
   
	/**	The number of times item x occurs within the dictionary. <br> 
		Analysis: Time = O(count) 
		@param x item to check how often it occurs in the dictionary */
	public int frequency(Object x)
	{
		int result = 0;
		CursorUos saveCurrentPos = currentPosition();
		boolean saveSearchMode = searchesContinue;
		restartSearches();
		search(x);
		resumeSearches();
		while (itemExists())
		{
			result++;
			search(x);
		}
		goPosition(saveCurrentPos);
		searchesContinue = saveSearchMode;
		return result;
	}
}