// 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
// 

template <class Item>
Set<SubSet<Item> > 
SetFuncs<Item>::aux_choose(SubSet<Item>& subset, int k)
{
        long flag;
        Set<SubSet<Item> > result;
        SubSet<Item> s2(subset), s3(subset);
	s2.clear(); s3.clear();

        if ((subset.rank() ==0) || (k==0)) {
                if (k==0) {
                        SubSet<Item> empty(subset);
			empty.clear();
                        result.insert(empty);
                }
                return result;
        }
        int r = subset.rank();
        int hpower = (int) floor(log10((double) r)/log10(2.0));
        r -= (int) pow(2.0, (double) hpower);
        s2.unrank(r);
        Set<SubSet<Item> > tmp_res = aux_choose(s2, k-1);
        Iterator<SubSet<Item> > get_subset(&tmp_res);
        while (get_subset(s3)) {
                r = s3.rank();
                r += (int) pow(2.0, (double) hpower);
                s3.unrank(r);
                result.insert(s3);
        }
        tmp_res = aux_choose(s2, k);
        Iterator<SubSet<Item> > get_subset2(&tmp_res);
        while (get_subset2(s3))
                result.insert(s3);
        return result;
}


template <class Item>
Set<Set<Item> > 
SetFuncs<Item>::choose(const Set<Item>& m, int k)
{
        Set<Set<Item> > result;
	SubSet<Item> orig(m);
        orig.fill();
        Set<SubSet<Item> > mss = aux_choose(orig, k);
        Iterator<SubSet<Item> > get_next(&mss);
        SubSet<Item> ss;
        while (get_next(ss))
                result.insert(ss.makeSet());
        return result;
}


template <class Item>
Set<Sequence<Item> > 
SetFuncs<Item>::cartesianProduct(const Set<Item>& s1, const Set<Item>& s2)
{
	Iterator<Item> get_s1(&s1), get_s2(&s2);
	Item e1, e2;
	Set<Sequence<Item> > result;
	Sequence<Item> new_seq;

	while (get_s1(e1)) {
		while (get_s2(e2)) {
			new_seq.append(e1);
			new_seq.append(e2);
			result.insert(new_seq);
			new_seq.clear();
		}
		get_s2.reset();
	}
        return result;
}

template <class Item>
Set<Set<Item> > 
SetFuncs<Item>::powerSet(const Set<Item>& m)
{
        SubSet<Item> ss(m);
        return ss.powerSet();
}

template <class Item>
Sequence<Item>
SetFuncs<Item>::permutation(const Set<Item>& s, const Permutation& p)
{
   int i, psize = p.size();
   Sequence<Item> result;
   if (psize != s.size()) {
	warning("Sequence::permutation(): wrong size input");
	return result;
   }
   Array<Item> elements;
   Iterator<Item> get_next(&s);
   Item e;
   while (get_next(e))
	elements.append(e);

   for (i=0; i<psize; i++)
	result.append(elements[p[i]-1]);
   //cout << "SetFuncs::permutation(" << p << "): " << result << endl;
   return result;
}

template <class Item>
Sequence<Item>
SetFuncs<Item>::permutation(const Array<Item>& elements, const Permutation& p)
{
   int i, psize = p.size();
   Sequence<Item> result;
   if (psize != elements.size()) {
	warning("Sequence::permutation(): wrong size input");
	return result;
   }
   for (i=0; i<psize; i++)
	result.append(elements[p[i]-1]);
   //cout << "SetFuncs::permutation(" << p << "): " << result << endl;
   return result;
}

template <class Item>
Set<Sequence<Item> > 
SetFuncs<Item>::permutations(const Set<Item>& s)
{
	Set<Sequence<Item> > result;
        Permutation p(s.size()), last = p.last();
	p.first();
	while (p != last) {
		result.append(permutation(s, p));
		p.next();
	}
	return result;
}



template <class Item> 
ostream& operator<<(ostream& os, const SetFuncs<Item>& s)
{
	return os;
}