// 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_h
#define MSet_h

#include <LINK/basic/Collection.h>
#include <LINK/basic/List.h>

#ifndef DEFAULT_SET_IMPL
#define DEFAULT_SET_IMPL SortedList
#endif 

template <class Item, class Impl> 
class MSetBase : public Collection<Item> {

public:
    MSetBase(); 
    MSetBase(const MSetBase<Item,Impl>& m);
    MSetBase(const Collection<Item>&c);
    MSetBase(const Container<Item>&c);
    ~MSetBase(); 

    MSetBase<Item,Impl>&	operator=(const MSetBase<Item,Impl>& m);
    MSetBase<Item,Impl>&	operator=(const Collection<Item>& c);
    //MSetBase<Item,Impl>&	copy(const MSetBase<Item,Impl>& m)
    //					{ *this = m; return *this; }

    int		size() const		{ return store->size(); }
    Bool	emptyQ() const		{ return store->emptyQ(); }
    Bool	fullQ() const		{ return store->fullQ(); }
    Bool	memberQ(const Item& e) const
					{ return store->memberQ(e); }
    Bool	sortedQ() const		{ return store->sortedQ();  }
    DataType	type() const		{ return MSETCOL; }

    Item	first() const		{ return store->first(); }
    Item	last() const		{ return store->last(); }

    void	insert(Item e)		{ newMSet(this); store->insert(e); }
    void	append(Item e)		{ newMSet(this); store->append(e); }

    void	remove(Item e)		{ newMSet(this); store->remove(e); }
    void	clear()			{ newMSet(this); store->clear();   }

    int         iterate(Iterator<Item>& i, Item& e) const
                           {return ((Container<Item>*)store)->iterate(i, e); }

    Bool	operator==(const Collection<Item>& m) const 
					{ return store->operator==(m); }
    Bool    	operator>=(const Collection<Item>& m) const
					{ return store->operator>=(m); }
    Bool    	operator>(const Collection<Item>& m) const
					{ return store->operator>(m); }
    Bool    	operator<(const Collection<Item>& m) const
					{ return store->operator<(m); }
    Bool    	operator<=(const Collection<Item>& m) const
					{ return store->operator<=(m); }
    Bool    	operator!=(const Collection<Item>& m) const
					{ return store->operator!=(m); }


    Bool	operator==(const Container<Item>& m) const 
					{ return store->operator==(m); }
    Bool    	operator>=(const Container<Item>& m) const
					{ return store->operator>=(m); }
    Bool    	operator>(const Container<Item>& m) const
					{ return store->operator>(m); }
    Bool    	operator<(const Container<Item>& m) const
					{ return store->operator<(m); }
    Bool    	operator<=(const Container<Item>& m) const
					{ return store->operator<=(m); }
    Bool    	operator!=(const Container<Item>& m) const
					{ return store->operator!=(m); }

    Bool        eq(MSetBase<Item, Impl>& s) {return *this == s;}
    Bool        neq(MSetBase<Item, Impl>& s) {return *this != s;}

    MSetBase<Item,DEFAULT_SET_IMPL<Item> >unions(const Collection<Item>& c);
    MSetBase<Item,DEFAULT_SET_IMPL<Item> >operator+(const Collection<Item>& c);
    MSetBase<Item,DEFAULT_SET_IMPL<Item> >intersection
						    (const Collection<Item>&c);
    MSetBase<Item,DEFAULT_SET_IMPL<Item> >operator^(const Collection<Item>& c);
    MSetBase<Item,DEFAULT_SET_IMPL<Item> >difference(const Collection<Item>& c);
    MSetBase<Item,DEFAULT_SET_IMPL<Item> >operator-(const Collection<Item>& c);
    
    Bool		subsetQ(const Collection<Item>& c);
    Bool		properSubsetQ(const Collection<Item>& c);
    Bool		permutationQ() const;
    int			occurrences(Item item) const;
    int			rank(Item item) const;
    Item		ref(int k) const;

    ostream&    	display(ostream& os) const;
    Collection<Item>*   newEmpty() const 
				{ return new MSetBase<Item,Impl>; }


protected:
    Impl*	store;
    void	newStore();
    void	newMSet(MSetBase<Item,Impl>* m);

    Item	numOccurrences(Iterator<Item>& it, Item& cur_item, 
			       int& count, int &not_done) const;

 MSetBase<Item,DEFAULT_SET_IMPL<Item> >
				unsortedUnions(const Collection<Item>& c);
 MSetBase<Item,DEFAULT_SET_IMPL<Item> >
				unsortedIntersection(const Collection<Item>&c);
 MSetBase<Item,DEFAULT_SET_IMPL<Item> >
				unsortedDifference(const Collection<Item>& c);

 MSetBase<Item,DEFAULT_SET_IMPL<Item> >
				sortedUnions(const Collection<Item>& c);
 MSetBase<Item,DEFAULT_SET_IMPL<Item> >
				sortedIntersection(const Collection<Item>& c);
 MSetBase<Item,DEFAULT_SET_IMPL<Item> >
				sortedDifference(const Collection<Item>& c);

 //friend class CollectionWrapper<Item>;
};


template <class Item>
class MSet : public MSetBase<Item, DEFAULT_SET_IMPL<Item> > {
public:
    MSet() {}
    MSet(const MSet<Item>& c);
    MSet(const Collection<Item>& c);
    MSet(const Container<Item>& c);

    MSet<Item>&         operator=(const MSet<Item>& m);
    MSet<Item>&         operator=(const Collection<Item>& m);
    //friend class CollectionWrapper<Item>;
};

//////template <class Item>
//////MSet<MSet<Item> > choose(const MSet<Item>&, int);
//////
//////template <class Item>
//////MSet<MSet<Item> > powerSet(const MSet<Item>&);



#define MSET(etype, itype) MSetBase<etype, itype<etype> >


#ifdef DEFINE_TEMPLATE
#include <LINK/basic/MSet.cc>
#endif

#endif