集合基于数组的实现:ArrayBag.java
/**
* @Author 陈伟兵
* @MSN:cwbnig1982@hotmail.com
* @E-mail:chenweibing1982@sohu.com
* @CreateTime 2004-11-30
* @Version:1.0
*/
package com.cwbnig.util;
import Java.util.Random;
import java.util.Iterator;
public class ArrayBag implements BagADT
{
private static Random rand=new Random;
private final int DEFAULT_CAPACITY =100;
private final int NOT_FOUND=-1;
private int count;
private Object contents;
/**
* Create an empty bag using the default capacity
*/
public ArrayBag
{
count=0;
contents=new Object[DEFAULT_CAPACITY];
}
/**
* Create an empty bag using the specified capacity
*/
public ArrayBag(int initialCapacity)
{
count=0;
contents=new Object[initialCapacity];
}
/**
* Returns the number of elements currentl in this bag
*/
public int size
{
return count;
}
/**
* Returns true if this bag is empty and false otherwise
*/
public boolean isEmpty
{
return(count==0);
}
/**
* Adds the speacified element to the bag,expanding the capacity of the array if necessary.
*/
public void add(Object element)
{
if(size==contents.length)
{
expandCapacity;
}
contents[count]=element;
count++;
}
/**
* Creates a new array to store the contents of the bag with twice the capcity of the old one.
*/
public void expandCapacity
{
Object larger=new Object[contents.length*2];
for(int index=0;indexbr /> {
larger[index]=contents[index];
}
contents=larger;
}
/**
* Adds the contents of the parameter to this bag.
*/
public void addAll(BagADT bag)
{
Iterator scan=bag.iterator;
while(scan.hasNext)
{
add(scan.next);
}
}
/**
* Remove a random element from the bag and returns it.Throws and EmptyBagException if the bag is empty
*/
public Object removeRandomthrows EmptyBagException
{
if(isEmpty)
{
throw new EmptyBagException;
}
int choice=rand.nextInt(count);
Object result=contents[choice];
contents[choice]=contents[count-1];
contents[count-1]=null;
count--;
return result;
}
/**
* Removes one occurance of the specified element from the bag and returns it.
* Throws and EmptyBagException if the bag is empty and a NoSuchElementException if the target is not in the bag.
*/
public Object remove(Object target)throws EmptyBagException,NoSuchElementException
{
int search=NOT_FOUND;
if(isEmpty)
{
throw new EmptyBagException;
}
for(int index=0;index {
search=index;
}
if(search==NOT_FOUND)
{
throw new NoSuchElementException;
}
Object result=contents[count-1];
contents[search]=contents[count-1];
contents[count-1]=null;
return result;
}
/**
* Returns a new bag that is the union of this bag and the parameter.
*/
public BagADT union(BagADT bag)
{
ArrayBag both=new ArrayBag;
for(int index=0;indexbr /> {
both.add(contents[index]);
}
Iterator scan=bag.iterator;
while(scan.hasNext)
{
both.add(scan.next);
}
return both;
}
/**
* Returns true if this bag contains the specified target element.
*/
public boolean contains(Object target)
{
int search=NOT_FOUND;
for(int index=0;index {
if(contents[index].equals(target))
{
search=index;
}
}
return(search!=NOT_FOUND);
}
/**
* Returns true if this bag contains exactly the same elements as the parameter.
*/
public boolean equals(BagADT bag)
{
boolean result=false;
ArrayBag temp1=new ArrayBag;
ArrayBag temp2=new ArrayBag;
Object obj;
if(size==bag.size)
{
temp1.addAll(this);
temp2.addAll(bag);
Iterator scan=bag.iterator;
while(scan.hasNext)
{
obj=scan.next;
if(temp1.contains(obj))
{
try
{
temp1.remove(obj);
temp2.remove(obj);
}
catch(EmptyBagException emptyE)
{
System.out.println("The current Bag is Empty!");
}
catch(NoSuchElementException nosuchE)
{
System.out.println("The current Bag has no such element!");
}
}
}
result=(temp1.isEmpty&&temp2.isEmpty);
}
return result;
}
/**
* Returns an iterator for the elements currently in this bag
*/
public Iterator iterator
{
return new ArrayIterator(contents,count);
}
/**
* Returns a string representation of this bag.
*/
public String toString
{
String result="";
for(int index=0;indexbr /> {
result=result+contents[index].toString+"n";
}
return result;
}
}
查看评论 回复