/**
* @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;index<contents.length;index++)
{
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 removeRandom()throws 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<count&&search==NOT_FOUND;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;index<count;index++)
{
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<count&&search==NOT_FOUND;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;index<count;index++)
{
result=result+contents[index].toString()+"\n";
}
return result;
}
}
