// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Jonathan Berry

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

#ifndef Set_CC
#define Set_CC



template <class Item, class Impl>
SetBase<Item,Impl>::SetBase(const SetBase<Item, Impl>& s)
{
    delete store;  // it just got created in MSetBase()
    store = s.store;
    ((Container<Item>*)store)->incrRefCount();
}

template <class Item, class Impl>
SetBase<Item,Impl>::SetBase(const Collection<Item> &col)
{
    Iterator<Item> get_next(&col);
    Item item; 
    while (get_next(item))
	insert(item);
}

template <class Item, class Impl>
SetBase<Item,Impl>::SetBase(const Container<Item> &con)
{
    Iterator<Item> get_next(&con);
    Item item; 
    while (get_next(item))
	insert(item);
}

//
// copy one SetBase Class instance to another
//
template <class Item, class Impl>
SetBase<Item, Impl>&
SetBase<Item,Impl>::operator=(const SetBase<Item,Impl>& s)
{
    if (&s == this)
        return *this;
    ((Container<Item>*)store)->decrRefCount(); 
    if (((Container<Item>*)store)->getRefCount() == 0)
	delete store;
    store = s.store;
    ((Container<Item>*)store)->incrRefCount();
    return *this;
}

template <class Item, class Impl>
SetBase<Item, Impl>&
SetBase<Item,Impl>::operator=(const Collection<Item>& c)
{
    if (&c == this)
        return *this;
    newStore();

    Iterator<Item> get_next(&c);
    Item item;
    while (get_next(item))
        insert(item);
}
//
// insert an item to a set if it is not in it yet
//
template <class Item, class Impl>
void
SetBase<Item, Impl>::insert(Item e)
{
    if (this->memberQ(e))
    {
	//warning("Item is in the set, can't insert");
	return;
    }
    else
    {
 	newSet(this);
	store->insert(e);
    }
}

//
// insert an item at the end of a set if it is not a member and the 
// order permits this (if not the container's append() method decides
// what is done - typically the element is simply inserted to
// maintain sorted order
//
template <class Item, class Impl>
void
SetBase<Item, Impl>::append(Item e)
{
    if (this->memberQ(e))
    {
	//warning("Item is in the set, can't insert");
	return;
    }
    else
    {
 	newSet(this);
	store->append(e);
    }
}

//
// create a new set
//
template <class Item, class Impl>
void
SetBase<Item,Impl>::newSet(SetBase<Item,Impl>* s)
{
    Item item; 
    Impl* x = s->store;
    Iterator<Item> get_next(x);

    //if (store->ref_count > 1)  {
    if (((Container<Item>*)store)->getRefCount() > 1)  {
    	newStore();
    	while (get_next(item))
            MSetBase<Item,Impl>::append(item); //avoid membership tests
	    //insert(item);
    }
}

////
//// create a new set which is the union of the two sets
////
//template <class Item, class Impl>
//MSetBase<Item,Impl>
//SetBase<Item,Impl>::unions(Collection<Item>& col)
//{
//    return MSetBase<Item,Impl>::unions(col);
//}
//
////
//// create a new set which is the union of the two sets
////
//template <class Item, class Impl>
//MSetBase<Item,Impl>
//SetBase<Item,Impl>::operator+(Collection<Item>& col)
//{
//    return MSetBase<Item,Impl>::unions(col);
//}
//
////
//// create a new set which is the intersection of the two sets
////
//template <class Item, class Impl>
//MSetBase<Item, Impl>
//SetBase<Item,Impl>::intersection(Collection<Item>& col)
//{
//    return MSetBase<Item,Impl>::intersection(col);
//}
//
////
//// create a new set which is the intersection of the two sets
////
//template <class Item, class Impl>
//MSetBase<Item,Impl>
//SetBase<Item,Impl>::operator^(Collection<Item>& col)
//{
//    return MSetBase<Item,Impl>::intersection(col);
//}
//
//// 
//// create a new set which is the original minus the collection argument
////
//template <class Item, class Impl>
//MSetBase<Item, Impl>
//SetBase<Item,Impl>::difference(Collection<Item>& col)
//{
//    return MSetBase<Item,Impl>::difference(col);
//}
//
////
//// create a new set which is the original minus the collection argument
////
//template <class Item, class Impl>
//MSetBase<Item,Impl>
//SetBase<Item,Impl>::operator-(Collection<Item>& col)
//{
//    return MSetBase<Item,Impl>::difference(col);
//}

////
//// create a new set which is the union of the two sets
////
//template <class Item, class Impl>
//MSetBase<Item,Impl>
//SetBase<Item,Impl>::unions(SetBase<Item,Impl>& s)
//{
//    SetBase<Item,Impl> result;
//    Iterator<Item> get_next1(this);
//    Iterator<Item> get_next2(&s);
//    Item item; 
//    while (get_next1(item))  
//	result.insert(item);
//    while (get_next2(item))  
//	result.insert(item);
//    return result;
//}
//
////
//// create a new set which is the union of the two sets
////
//template <class Item, class Impl>
//MSetBase<Item,Impl>
//SetBase<Item,Impl>::operator+(SetBase<Item,Impl>& s)
//{
//    return unions(s);
//}
//
////
//// create a new set which is the intersection of the two sets
////
//template <class Item, class Impl>
//MSetBase<Item, Impl>
//SetBase<Item,Impl>::intersection(SetBase<Item,Impl>& s)
//{
//    SetBase<Item,Impl> result;
//    Iterator<Item> get_next(this);
//    Item item; 
//    while (get_next(item))  
//	if (s.memberQ(item))
//	    result.insert(item);
//    return result;
//}
//
////
//// create a new set which is the intersection of the two sets
////
//template <class Item, class Impl>
//MSetBase<Item,Impl>
//SetBase<Item,Impl>::operator^(SetBase<Item,Impl>& s)
//{
//    return intersection(s);
//}
//
//// 
//// create a new set which is the original minus the collection argument
////
//template <class Item, class Impl>
//MSetBase<Item, Impl>
//SetBase<Item,Impl>::difference(SetBase<Item,Impl>& s)
//{
//    SetBase<Item,Impl> result;
//    Iterator<Item> get_next(this);
//    Item item; 
//    while (get_next(item))  
//	if (s.memberQ(item) == 0)
//	    result.insert(item);
//    return result;
//}
//
////
//// create a new set which is the original minus the collection argument
////
//template <class Item, class Impl>
//MSetBase<Item,Impl>
//SetBase<Item,Impl>::operator-(SetBase<Item,Impl>& s)
//{
//    return difference(s);
//}

//
// return the number of occurrences of item in the collection. 
//
template <class Item, class Impl>
int
SetBase<Item, Impl>::occurrences(Item item) const
{
    if (this->memberQ(item))
	return(1);
    else return(0);
}

template <class Item, class Impl>
Bool
SetBase<Item, Impl>::permutationQ() const
{
	return 1;
}

//
// display a human-readable representation of the set
//
template <class Item, class Impl>
ostream&
SetBase<Item,Impl>::display(ostream& os) const
{
    os << "{";    
    Iterator<Item> get_next(this);
    Item i;
    Bool start = FALSE;
    while (get_next(i))
         if (!start) {
                ElementOps<Item>::displayItem(os, i);
                start = TRUE;
         } else {
                os << " ";
                ElementOps<Item>::displayItem(os, i);
	}
    os << "}";    
    return os;
}

//******************************************************************

//
// Copy one multi-set to another
//


template <class Item>
Set<Item>&
Set<Item>::operator=(const Set<Item>& s)
{
    if (&s == this)
	return *this;
    ((Container<Item>*)store)->decrRefCount(); 
    if (((Container<Item>*)store)->getRefCount() == 0)
	delete store;
    store = s.store;
    ((Container<Item>*)store)->incrRefCount();
    return *this;
}

template <class Item>
Set<Item>&
Set<Item>::operator=(const Collection<Item>& c)
{
    if (&c == this)
        return *this;
    newStore();

    Iterator<Item> get_next(&c);
    Item item;
    while (get_next(item))
        insert(item);
}

#endif