arrayedpkeyeddictuos.java

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

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

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


/**	A Keyed Dictionary implemented via an ordered sequence of (key, item)
	pairs in an array.  There is a method to insert an item with its
	key.  The usual dictionary methods: has, obtain, and delete 
	acccess items by their associated key.  It includes the linear 
	iterator capabilities. Items are ordered in the dictionary by key. */
public class ArrayedPKeyedDictUos extends ArrayedPKeyedBasicDictUos implements PKeyedDictUos
{
	/**	The current position in the array. */
	protected int pos;

	/**	Default constructor which makes a set with duplicates disallowed. 
		Time: O(size) */
	public ArrayedPKeyedDictUos(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 array. <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].secondItem();
	}

	/**	The key of the current item. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists() 
		</ul> */
	public Comparable itemKey() throws NoCurrentItemUosException
   	{     
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist");  
		
		return (Comparable)rep[pos].firstItem();
	} 

	/**	The current key-item pair. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION:  <br>
		<ul>
			itemExists() 
		</ul> */
	public PairUos keyItemPair() 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;
	} 

   	/**	Move the current position to next item with key k or else set to !ItemExists. <br> 
		Analysis: Time = O(log(count)) 
		@param k key being sought in the dictionary */
	public void search(Comparable k) 
	{
		pos = location(k);
	}

	/**	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 data structure (if it exists). <br> 
		Analysis: Time = O(1) */
	public void goFirst()
	{ 
		pos = 0;
	}

	/**	Move to prior to the first item. <br> 
		Analysis: Time = O(1) */
	public void goBefore()
	{
		pos = -1;
	}
	
	/**	Move to after the last item. <br> 
		Analysis: Time = O(1) */
	public void goAfter()
	{
		pos = count;
	}
   
	/**	Set the current item to x. <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("No current item to set.");  
		
		rep[pos].setSecondItem(x);
	}
   
	/**	Delete the current item. <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 delete an item that does not exist.");  

		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 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 go to */
	public void  goPosition(CursorUos c)
	{
		ArrayedIteratorUos iter = (ArrayedIteratorUos)c;
		pos = iter.pos();
	}
   
	/**	The number of times key k occurs within the  Dictionary. <br> 
		Analysis: Time = O(log(count)) 
		@param k key being counted in the dictionary */
	public int frequency(Comparable k)
	{
		if (has(k))
			return 1;
		else
			return 0;
	}
}