// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): SUNY Stony Brook students, 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 Subset_h
#define Subset_h

#include <LINK/basic/Set.h>
#include <LINK/basic/SetFuncs.h>

#include <math.h>
#include <iostream.h>
//#define Bool short

#define DEFAULT_SUBSET_SIZE 100

template <class Item>
class SubSet {				// : public Set<Item>  {
public: 
      SubSet();      
      //SubSet(int);      
      SubSet(const SubSet<Item>&);
      SubSet(const Set<Item>& );
      ~SubSet();

      SubSet&             random();
      int                 rank() const;
      SubSet&             unrank(int);
      void                clear();
      void                fill();
      SubSet&             next();
      SubSet&             previous();
      SubSet<Item>        unions( SubSet&) const;
      SubSet<Item>        intersection( SubSet& ) const;
      SubSet<Item>        difference( SubSet& ) const;
      Bool                subsetQ(SubSet& );
      Bool                properSubsetQ(SubSet& ); 
      int                 size() const;
      int                 order() const;
      //SubSet&             copy( const SubSet& );
      Set<Item>           makeSet() const;
      ostream&            display(ostream& os) const;

      Bool              operator==(const SubSet&) const;
      Bool              operator!=(const SubSet&) const;
      Bool              operator>(const SubSet&) const;
      Bool              operator<(const SubSet&) const;
      Bool              operator>=(const SubSet&) const;
      Bool              operator<=(const SubSet&) const;
      SubSet&           operator =(const SubSet& );
      Bool&             operator[] (int index) const;
      SubSet<Item>      operator+(SubSet&  ) const;
      SubSet<Item>      operator^(SubSet& ) const;
      SubSet<Item>      operator-(SubSet& ) const;


      Set<Set<Item> > powerSet();
      Set<Set<Item> > choose(int);
      
      friend ostream&   operator<<(ostream& os, const SubSet<Item>& ss);
       
private:
      Bool*                subset;
      Set<Item>*           original;
};

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

#endif