arrayedkeyeddictuos.java

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

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

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

/**	A Keyed Dictionary implemented via an ordered sequence of 
	keyed items in an array.  There is a method to insert keyed items.
	The usual dictionary methods: has, obtain, and delete 
	access items by their key.  It includes the linear iterator 
   	capabilities. Items are ordered in the dictionary by key. */
public class ArrayedKeyedDictUos extends ArrayedKeyedBasicDictUos implements KeyedDictUos
{
	/**	The current position in the array. */
	protected int pos;

	/**	Default constructor which makes a set with duplicates disallowed. <br>
		Analysis: Time = O(size) <br>
		@param size capacity of the dictionary */
	public ArrayedKeyedDictUos(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];
	}

	/**	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 rep[pos].key();
   	}

	/**	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 new PairUos(rep[pos].key(), 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 of the item 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 the 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;
   	}
   
	/**	Change the item to another item with the same key. <br> 
	   	Analysis: Time = O(1) <br>
	   	PRECONDITION: <br>
		<ul>
	   		itemExists() <br>
	   		!(x.key().compareTo(itemKey())!=0)
		</ul> 
		@param x item to replace another item with the same key value */
   	public void setItem(KeyedUos x) throws NoCurrentItemUosException, InvalidArgumentUosException
	{
		if (!itemExists())
		 	throw new NoCurrentItemUosException("No current item to set.");  
	   	if (x.key().compareTo(itemKey())!=0)
		  	throw new InvalidArgumentUosException("Current item must have same key as new item.");  
	  	
	  	rep[pos] = x;
 	}

	/**	Delete the current item. <br> 
	   	Analysis: Time = O(count) <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 dictionary. <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 from which to delete an item */
 	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) <br>
	 	@param c position to which to go */
   	public void  goPosition(CursorUos c)
   	{
		ArrayedIteratorUos iter = (ArrayedIteratorUos)c;
	 	pos = iter.pos();
   	}
   
	/**	The number of times key i occurs within the Dictionary. <br>
	  	Analysis: Time = O(log(count)) 
	  	@param k key to check how often it occurs in the dictionary */
   	public int frequency(Comparable k)
   	{
		if (has(k))
			return 1;
		else
			return 0;
  	}
}