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

// 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 MSet_CC
#define MSet_CC
#include <iostream.h>


template <class Item, class Impl>
MSetBase<Item,Impl>::MSetBase(const MSetBase<Item, Impl>& m)
{
    if (&m == this)
	return;

    store = m.store;
    ((Container<Item>*)store)->incrRefCount(); //ref_count++;
}

template <class Item, class Impl>
MSetBase<Item,Impl>::MSetBase(const Collection<Item> &col)
{
    Iterator<Item> get_next(&col);
    Item item; 

    store = new Impl;
    ((Container<Item>*)store)->initRefCount();  //ref_count = 1;
    while (get_next(item))
	insert(item);
}

template <class Item, class Impl>
MSetBase<Item,Impl>::MSetBase(const Container<Item> &con)
{
    Iterator<Item> get_next(&con);
    Item item; 

    store = new Impl;
    ((Container<Item>*)store)->initRefCount();  //ref_count = 1;
    while (get_next(item))
	insert(item);
}

template <class Item, class Impl>
MSetBase<Item,Impl>::MSetBase() : Collection<Item>()
{ 
    store = new Impl;
    ((Container<Item>*)store)->initRefCount();  //ref_count = 1;
}


//
// destructor for an implementation of SetBase uses reference counting
//
template <class Item, class Impl>
MSetBase<Item,Impl>::~MSetBase() 
{ 
    ((Container<Item>*)store)->decrRefCount(); 
    if (((Container<Item>*)store)->getRefCount() == 0)
	delete store;
}

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

template <class Item, class Impl>
MSetBase<Item, Impl>&
MSetBase<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);
}

////
//// return TRUE if two multi-sets are equal according to lexicographic order
////
//template <class Item, class Impl>
//Bool
//MSetBase<Item, Impl>::operator==(const Collection<Item>& m)
//{
//    Iterator<Item> get_next1(this);
//    Iterator<Item> get_next2(&m);
//    Item item1;
//    Item item2;
//
//    while (get_next1(item1) && get_next2(item2))
//    {
//	    if (!ElementOps<Item>::compareItems(item1,item2))
//	        return(FALSE);
//    }
//    return(TRUE);
//}
//
////
//// return TRUE if one multi-set is greater than the other 
//// according to lexicographic order
////
//template <class Item, class Impl>
//Bool
//MSetBase<Item, Impl>::operator>(Collection<Item>& m)
//{
//    Iterator<Item> get_next1(this);
//    Iterator<Item> get_next2(&m);
//    Item item1;
//    Item item2;
//
//    while (get_next1(item1))
//    {
//	if (get_next2(item2))
//	{
//	    if (ElementOps<Item>::compareItems(item1, item2)>0)
//	   	 return(TRUE);
//	    if (ElementOps<Item>::compareItems(item1, item2)<0)
//	       	 return(FALSE);
//	}
//	else return(TRUE);
//    }
//    return(FALSE);
//}
//
////
//// return TRUE if one multi-set is greater than or equal to the other 
//// according to lexicographic order
////
//template <class Item, class Impl>
//Bool
//MSetBase<Item, Impl>::operator>=(Collection<Item>& m)
//{
//    return !operator<(m);
//}
//
////
//// return TRUE if one multi-set is less than the other according to
//// lexicographic order
////
//template <class Item, class Impl>
//Bool
//MSetBase<Item, Impl>::operator<(Collection<Item>& m)
//{
//    Iterator<Item> get_next1(this);
//    Iterator<Item> get_next2(&m);
//    Item item1;
//    Item item2;
//
//    while (get_next1(item1))
//    {
//        if (get_next2(item2))
//	{
//	    if (ElementOps<Item>::compareItems(item1, item2)<0)
//                return(TRUE);
//	    if (ElementOps<Item>::compareItems(item1, item2)>0)
//	        return(FALSE);
//	}
//	else return(FALSE);
//    }
//    return(TRUE);
//}
//
////
//// return TRUE if one multi-set is less than or equal to the other 
//// according to lexicographic order
////
//template <class Item, class Impl>
//Bool
//MSetBase<Item, Impl>::operator<=(Collection<Item>& m)
//{
//    return !operator>(m);
//}
//
////
//// return TRUE if two multi-sets are not equal acording to lexicographic order
////
//template <class Item, class Impl>
//Bool
//MSetBase<Item, Impl>::operator!=(Collection<Item>& m)
//{
//    return !operator==(m);
//}
   
//
// create a new store
//
template <class Item, class Impl>
void
MSetBase<Item,Impl>::newStore()
{
    Impl* nstore = new Impl();
    ((Container<Item>*)nstore)->initRefCount(); 

    ((Container<Item>*)store)->decrRefCount(); 
    if (((Container<Item>*)store)->getRefCount() == 0)
	delete store; 
    store = nstore;
}

//
// create a new multi-set
//
template <class Item, class Impl>
void
MSetBase<Item,Impl>::newMSet(MSetBase<Item,Impl>* m)
{
    Item item; 
    Impl* x = m->store;
    Iterator<Item> get_next(x);

    if (((Container<Item>*)store)->getRefCount() > 1) {
    //if (store->ref_count > 1) {
	newStore();
	while (get_next(item))
	    insert(item);
    }
}

template <class Item, class Impl>
Item
MSetBase<Item,Impl>::numOccurrences(Iterator<Item>& it, Item& cur_val, 
                                    int& count, int &not_done) const
{
	Item next_val;
	count = 1;
	while ((not_done=it(next_val)) && 
		(ElementOps<Item>::compareItems(cur_val,next_val)==0))
		count++;
	return next_val;
}

template <class Item, class Impl>
MSetBase<Item,DEFAULT_SET_IMPL<Item> >
MSetBase<Item,Impl>::sortedUnions(const Collection<Item>& col)
{
    MSetBase<Item,DEFAULT_SET_IMPL<Item> > result;
    int s1, s2;
    Item e1, e2;
    Iterator<Item> get_next1(this), get_next2(&col);

    s1 = get_next1(e1); s2 = get_next2(e2);
    while (s1 || s2) {
	while (s1 && (!s2 || (ElementOps<Item>::compareItems(e1,e2)<0))) {
		result.append(e1);
   		s1 = get_next1(e1);
	}
	while (s2 && (!s1 || (ElementOps<Item>::compareItems(e2, e1)<0))) {
		result.append(e2);
   		s2 = get_next2(e2);
	}
	if (s1 && s2 && ElementOps<Item>::compareItems(e1, e2)==0) {
		result.append(e1);
		result.append(e2);
   		s1 = get_next1(e1);
   		s2 = get_next2(e2);
	}
    }
    return result;
}

template <class Item, class Impl>
MSetBase<Item,DEFAULT_SET_IMPL<Item> >
MSetBase<Item,Impl>::unsortedUnions(const Collection<Item>& col)
{
    MSetBase<Item,DEFAULT_SET_IMPL<Item> > result;
    Iterator<Item> get_next1(this);
    Iterator<Item> get_next2(&col);
    Item item; 
    while (get_next1(item))  
      result.insert(item);
    while (get_next2(item))  
      result.insert(item);
    return result;
}

template <class Item, class Impl>
MSetBase<Item,DEFAULT_SET_IMPL<Item> >
MSetBase<Item,Impl>::unions(const Collection<Item>& col)
{
    if (sortedQ() && col.sortedQ())
    	return sortedUnions(col);
    else
    	return unsortedUnions(col);
}

//
// create a new multi-set which is the union of the two multi-sets
//
template <class Item, class Impl>
MSetBase<Item,DEFAULT_SET_IMPL<Item> >
MSetBase<Item,Impl>::operator+(const Collection<Item>& col)
{
    return unions(col);
}

template <class Item, class Impl>
MSetBase<Item,DEFAULT_SET_IMPL<Item> >
MSetBase<Item,Impl>::sortedIntersection(const Collection<Item>& col)
{
    MSetBase<Item,DEFAULT_SET_IMPL<Item> > result;
    int s1, s2, count1, count2;
    Item e1, e2, next_e1, next_e2;
    Iterator<Item> get_next1(this), get_next2(&col);

    s1 = get_next1(e1); s2 = get_next2(e2);
    while (s1 && s2) {
	while (s1 && s2 && (ElementOps<Item>::compareItems(e1,e2)<0)) {
   		s1 = get_next1(e1);
	}
	while (s1 && s2 && (ElementOps<Item>::compareItems(e2,e1)<0)) {
   		s2 = get_next2(e2);
	}
	if (s1 && s2 && ElementOps<Item>::compareItems(e1,e2)==0) {
		next_e1 = e1;  
		next_e2 = e2;
		next_e1 = numOccurrences(get_next1, e1, count1, s1);
		next_e2 = numOccurrences(get_next2, e1, count2, s2);
		count1 = (count1 > count2) ? count2 : count1;
		for (int i=0; i< count1; i++)
			result.append(e1);
		e1 = next_e1;
		e2 = next_e2;
	}
	//if ((!s2&&(ElementOps<Item>::compareItems(e2,e1)<0)) || 
	//    (!s1&&(ElementOps<Item>::compareItems(e1,e2)<0)))
	//	return result;
    }
    return result;
}

//
// This could be implemented much more efficiently by building a 
// frequency table.
//
template <class Item, class Impl>
MSetBase<Item,DEFAULT_SET_IMPL<Item> >
MSetBase<Item,Impl>::unsortedIntersection(const Collection<Item>& col)
{
    MSetBase<Item,DEFAULT_SET_IMPL<Item> > result;
    Iterator<Item> get_next(this);
    Item item;
    int count, minFreq, temp;

    while (get_next(item)) 
       if (!result.memberQ(item)) {
          minFreq = occurrences(item);
          temp = col.occurrences(item);
          if (minFreq > temp)
            minFreq = temp;
          for (count = 0; count < minFreq; count++)
            result.insert(item);
       }
    return result;
}

template <class Item, class Impl>
MSetBase<Item,DEFAULT_SET_IMPL<Item> >
MSetBase<Item,Impl>::intersection(const Collection<Item>& col)
{
    if (sortedQ() && col.sortedQ())
    	return sortedIntersection(col);
    else
    	return unsortedIntersection(col);
}

//
// create a new multi-set which is the intersection of the two multi-sets
//
template <class Item, class Impl>
MSetBase<Item,DEFAULT_SET_IMPL<Item> >
MSetBase<Item,Impl>::operator^(const Collection<Item>& col)
{
    return intersection(col);
}


template <class Item, class Impl>
MSetBase<Item,DEFAULT_SET_IMPL<Item> >
MSetBase<Item,Impl>::sortedDifference(const Collection<Item>& col)
{
    MSetBase<Item,DEFAULT_SET_IMPL<Item> > result;
    int s1, s2, count1, count2, diff;
    Item e1, e2;
    Iterator<Item> get_next1(this), get_next2(&col);

    s1 = get_next1(e1); s2 = get_next2(e2);
    while (s1) {
	while (s1 && (!s2 || (ElementOps<Item>::compareItems(e1,e2)<0))) {
		result.append(e1);
   		s1 = get_next1(e1);
	}
	if (s1) {
		while (s2 && (ElementOps<Item>::compareItems(e2,e1)<0)) 
   			s2 = get_next2(e2);
	}
	if (s1 && s2 && (ElementOps<Item>::compareItems(e1,e2)==0)) {
		Item cur = e1;
		e1 = numOccurrences(get_next1, e1, count1, s1);
		e2 = numOccurrences(get_next2, e2, count2, s2);
		count1 = ((diff=(count1 - count2))>=0) ? diff : 0;
		for (int i=0; i< diff; i++)
			result.append(cur);
	}
    }
    return result;
}

template <class Item, class Impl>
MSetBase<Item,DEFAULT_SET_IMPL<Item> >
MSetBase<Item,Impl>::unsortedDifference(const Collection<Item>& col)
{
    MSetBase<Item,DEFAULT_SET_IMPL<Item> > result;
    Iterator<Item> get_next(this);
    Item item;
    int count, monFreq;

    while (get_next(item))
      if (!result.memberQ(item))
        {
          monFreq = occurrences(item) - col.occurrences(item);
          for (count = 1; count <= monFreq; count++)
            result.insert(item);
        };
    return result;
}

template <class Item, class Impl>
MSetBase<Item,DEFAULT_SET_IMPL<Item> >
MSetBase<Item,Impl>::difference(const Collection<Item>& col)
{
    if (sortedQ() && col.sortedQ())
    	return sortedDifference(col);
    else
    	return unsortedDifference(col);
}
//{
//    MSetBase<Item,Impl> result;
//    Iterator<Item> get_next(this);
//    Item item; 
//    int count, monFreq;
//
//    while (get_next(item))  
//      if (!col.memberQ(item))
//        {
//            result.insert(item);
//        }
//    return result;
//}

//
// create a new multi-set which is the original minus the collection argument
//
template <class Item, class Impl>
MSetBase<Item,DEFAULT_SET_IMPL<Item> >
MSetBase<Item,Impl>::operator-(const Collection<Item>& col)
{
    return difference(col);
}

//template <class Item, class Impl>
//Bool
//MSetBase<Item,Impl>::unsortedSubsetQ(const Collection<Item>& col)
//{
//    Iterator<Item> get_next(this);
//    Item item; 
//
//    if (store->size() > col.size())
//	return(FALSE);
//    while (get_next(item))  
//	if (col.memberQ(item) == 0)
//	    return(FALSE);
//    return TRUE;
//}


template <class Item, class Impl>
Bool
MSetBase<Item,Impl>::subsetQ(const Collection<Item>& col)
{
    return difference(col).emptyQ();
}

//
// return the number of occurrences of item in the collection. 
//
template <class Item, class Impl>
int
MSetBase<Item, Impl>::occurrences(Item item) const
{
    Iterator<Item> get_next(this);
    Item it; 
    int freq = 0;

    while (get_next(it))
      if (ElementOps<Item>::compareItems(item, it) == 0)
        freq++;
    return freq;
}

template <class Item, class Impl>
int
MSetBase<Item, Impl>::rank(Item item) const
{
    Iterator<Item> get_next(this);
    Item it; 
    int pos = 0;

    while (get_next(it)) {
      if (ElementOps<Item>::compareItems(item, it) == 0)
        return pos;
      pos++;
    }
    return -1;
}

template <class Item, class Impl>
Item
MSetBase<Item, Impl>::ref(int k) const
{
    if ((k < 0) || (k >= size())) {
	static Item i;
	return i;
    }
    int pos=0;
    Iterator<Item> get_next(this);
    Item it; 
    while (get_next(it)) {
      
      if (pos == k)
        return it;
      pos++;
    }
}

template <class Item, class Impl>
Bool
MSetBase<Item, Impl>::permutationQ() const
{
    Iterator<Item> get_next(this);
    Item it;
    if (sortedQ()) {
    	Item prev=first(); 
    	if (get_next(it)) {
    		while (get_next(it)) {
			if (ElementOps<Item>::compareItems(it, prev) == 0)
				return FALSE;
			prev = it;
		}
	}
	return TRUE;
    } else {
	while (get_next(it))
		if (occurrences(it) > 1)
			return FALSE;
	return TRUE;
    }
}

template <class Item, class Impl>
Bool
MSetBase<Item,Impl>::properSubsetQ(const Collection<Item>& col)
{
    if (store->size() < col.size())
        return subsetQ(col);
    else return FALSE;
}

//
// display a human-readable representation of the multi-set
//
template <class Item, class Impl>
ostream&
MSetBase<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;
}

template <class Item>
MSet<Item>::MSet(const MSet<Item>& m)
{
    if (&m == this)
	return;

    delete store; 
    store = m.store;
    ((Container<Item>*)store)->incrRefCount(); //ref_count++;
}

template <class Item>
MSet<Item>::MSet(const Collection<Item> &col)
{
    Iterator<Item> get_next(&col);
    Item item; 

    while (get_next(item))
	insert(item);
}

template <class Item>
MSet<Item>::MSet(const Container<Item> &con)
{
    Iterator<Item> get_next(&con);
    Item item; 

    while (get_next(item))
	insert(item);
}


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


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

template <class Item>
MSet<Item>&
MSet<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