// see apset.h

const int SDEFAULT_SIZE = 10;        // default initial set size

template <class itemType>
apset<itemType>::apset()
    : myList(SDEFAULT_SIZE),
      myCount(0)
{
    
}

template <class itemType>
bool apset<itemType>::contains(const itemType & item) const
{
    int loc = find(item);
    return loc != -1;
}

template <class itemType>
int apset<itemType>::size() const
{
    return myCount;
}

template <class itemType>
void apset<itemType>::print(ostream & output) const
{
    int k;
    output << "(" << endl;
    for(k=0; k < myCount; k++)
    {
	    output << "\t" << myList[k] << endl;
    }
    output << ")" << endl;
}

template <class itemType>
void apset<itemType>::add(const itemType & item)
{
    int loc = find(item);
    if (loc == -1)
    {
		if (myCount >= myList.length())
		{
		    myList.resize(myCount * 2);
		}
        loc = myCount - 1;         
        while (0 <= loc && item < myList[loc])
        {
            myList[loc+1] = myList[loc];
            loc--;
        }
		myList[loc+1] = item;
		myCount++;
    }
}

template <class itemType>
void apset<itemType>::remove(const itemType & item)
{
    int loc = find(item);
    if (loc != -1)
    {
        int k;
        for(k=loc; k < myCount-1; k++)
        {
        	myList[k] = myList[k+1];
        }
		myCount--;
    }
}

template <class itemType>
void apset<itemType>::makeEmpty()
{
    myCount = 0;
}

template <class itemType>
int apset<itemType>::find(const itemType & item) const
{
    int low = 0;
    int high = myCount-1;
    int mid;                          // middle of current range
    while (low <= high)
    {
        mid = (low + high)/2;
        if (myList[mid] == item)       // found key, exit
        {
            return mid;
        }
        else if (myList[mid] < item)   // key in upper half
        {
            low = mid + 1;
        }
        else                          // key in lower half
        {
            high = mid - 1;
        }
    }
    return -1;
}

template <class itemType>
const apset<itemType>&
apset<itemType>::operator *= (const apset<itemType> & rhs)
{
    apset<itemType> result;
    int k;
    int length;
    
    if (size() < rhs.size())
    {
		length = size();
		for(k=0; k < length; k++)
		{
		    if (rhs.contains(myList[k]))
		    {
			    result.add(myList[k]);
		    }
		}
    }
    else
    {
		length = rhs.size();
		for(k=0; k < length; k++)
		{
		    if (contains(rhs.myList[k]))
		    {
			    result.add(myList[k]);
		    }
		}
    }
    
    *this = result;
    return *this;
}

template <class itemType>
const apset<itemType>&
apset<itemType>::operator += (const apset<itemType> & rhs)
{
    int k;
    int length = rhs.size();

    for(k=0; k < length; k++)
    {
		if (! contains(rhs.myList[k]))
		{
		    add(rhs.myList[k]);
		}
    }
    return *this;
}