/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

// Sets - An Abstract Data Type

//INTERFACE

class SparseSet;

class VectorSet;

class ListSet;

class CoSet;

class ostream;

class SetI_;

// These sets can grow or shrink, based on the initial size and the largest

// element currently in them.  Basically, they allow a bunch of bits to be

// grouped together, tested, set & cleared, intersected, etc.  The basic

// Set class is an abstract class, and cannot be constructed.  Instead,

// one of VectorSet, SparseSet, or ListSet is created.  Each variation has

// different asymptotic running times for different operations, and different

// constants of proportionality as well.

// {n = number of elements, N = largest element}

//              VectorSet       SparseSet       ListSet

// Create       O(N)            O(1)            O(1)

// Clear        O(N)            O(1)            O(1)

// Insert       O(1)            O(1)            O(log n)

// Delete       O(1)            O(1)            O(log n)

// Member       O(1)            O(1)            O(log n)

// Size         O(N)            O(1)            O(1)

// Copy         O(N)            O(n)            O(n)

// Union        O(N)            O(n)            O(n log n)

// Intersect    O(N)            O(n)            O(n log n)

// Difference   O(N)            O(n)            O(n log n)

// Equal        O(N)            O(n)            O(n log n)

// ChooseMember O(N)            O(1)            O(1)

// Sort         O(1)            O(n log n)      O(1)

// Forall       O(N)            O(n)            O(n)

// Complement   O(1)            O(1)            O(1)

// TIME:        N/32            n               8*n     Accesses

// SPACE:       N/8             4*N+4*n         8*n     Bytes

// Create:      Make an empty set

// Clear:       Remove all the elements of a Set

// Insert:      Insert an element into a Set; duplicates are ignored

// Delete:      Removes an element from a Set

// Member:      Tests for membership in a Set

// Size:        Returns the number of members of a Set

// Copy:        Copy or assign one Set to another

// Union:       Union 2 sets together

// Intersect:   Intersect 2 sets together

// Difference:  Compute A & !B; remove from set A those elements in set B

// Equal:       Test for equality between 2 sets

// ChooseMember Pick a random member

// Sort:        If no other operation changes the set membership, a following

//              Forall will iterate the members in ascending order.

// Forall:      Iterate over the elements of a Set.  Operations that modify

//              the set membership during iteration work, but the iterator may

//              skip any member or duplicate any member.

// Complement:  Only supported in the Co-Set variations.  It adds a small

//              constant-time test to every Set operation.

//

// PERFORMANCE ISSUES:

// If you "cast away" the specific set variation you are using, and then do

// operations on the basic "Set" object you will pay a virtual function call

// to get back the specific set variation.  On the other hand, using the

// generic Set means you can change underlying implementations by just

// changing the initial declaration.  Examples:

//      void foo(VectorSet vs1, VectorSet vs2) { vs1 |= vs2; }

// "foo" must be called with a VectorSet.  The vector set union operation

// is called directly.

//      void foo(Set vs1, Set vs2) { vs1 |= vs2; }

// "foo" may be called with *any* kind of sets; suppose it is called with

// VectorSets.  Two virtual function calls are used to figure out the that vs1

// and vs2 are VectorSets.  In addition, if vs2 is not a VectorSet then a

// temporary VectorSet copy of vs2 will be made before the union proceeds.

//

// VectorSets have a small constant.  Time and space are proportional to the

//   largest element.  Fine for dense sets and largest element < 10,000.

// SparseSets have a medium constant.  Time is proportional to the number of

//   elements, space is proportional to the largest element.

//   Fine (but big) with the largest element < 100,000.

// ListSets have a big constant.  Time *and space* are proportional to the

//   number of elements.  They work well for a few elements of *any* size

//   (i.e. sets of pointers)!

//------------------------------Set--------------------------------------------

class Set : public ResourceObj {

 public:

  // Creates a new, empty set.

  // DO NOT CONSTRUCT A Set.  THIS IS AN ABSTRACT CLASS, FOR INHERITENCE ONLY

  Set(Arena *arena) : _set_arena(arena) {};

  // Creates a new set from an existing set

  // DO NOT CONSTRUCT A Set.  THIS IS AN ABSTRACT CLASS, FOR INHERITENCE ONLY

  Set(const Set &) {};

  // Set assignment; deep-copy guts

  virtual Set &operator =(const Set &s)=0;

  virtual Set &clone(void) const=0;

  // Virtual destructor

  virtual ~Set() {};

  // Add member to set

  virtual Set &operator <<=(uint elem)=0;

  // virtual Set  operator << (uint elem);

  // Delete member from set

  virtual Set &operator >>=(uint elem)=0;

  // virtual Set  operator >> (uint elem);

  // Membership test.  Result is Zero (absent)/ Non-Zero (present)

  virtual int operator [](uint elem) const=0;

  // Intersect sets

  virtual Set &operator &=(const Set &s)=0;

  // virtual Set  operator & (const Set &s) const;

  // Union sets

  virtual Set &operator |=(const Set &s)=0;

  // virtual Set  operator | (const Set &s) const;

  // Difference sets

  virtual Set &operator -=(const Set &s)=0;

  // virtual Set  operator - (const Set &s) const;

  // Tests for equality.  Result is Zero (false)/ Non-Zero (true)

  virtual int operator ==(const Set &s) const=0;

  int operator !=(const Set &s) const { return !(*this == s); }

  virtual int disjoint(const Set &s) const=0;

  // Tests for strict subset.  Result is Zero (false)/ Non-Zero (true)

  virtual int operator < (const Set &s) const=0;

  int operator > (const Set &s) const { return s < *this; }

  // Tests for subset.  Result is Zero (false)/ Non-Zero (true)

  virtual int operator <=(const Set &s) const=0;

  int operator >=(const Set &s) const { return s <= *this; }

  // Return any member of the Set.  Undefined if the Set is empty.

  virtual uint getelem(void) const=0;

  // Clear all the elements in the Set

  virtual void Clear(void)=0;

  // Return the number of members in the Set

  virtual uint Size(void) const=0;

  // If an iterator follows a "Sort()" without any Set-modifying operations

  // inbetween then the iterator will visit the elements in ascending order.

  virtual void Sort(void)=0;

  // Convert a set to printable string in an allocated buffer.

  // The caller must deallocate the string.

  virtual char *setstr(void) const;

  // Print the Set on "stdout".  Can be conveniently called in the debugger

  void print() const;

  // Parse text from the string into the Set.  Return length parsed.

  virtual int parse(const char *s);

  // Convert a generic Set to a specific Set

  /* Removed for MCC BUG

     virtual operator const SparseSet* (void) const;

     virtual operator const VectorSet* (void) const;

     virtual operator const ListSet  * (void) const;

     virtual operator const CoSet    * (void) const; */

  virtual const SparseSet *asSparseSet(void) const;

  virtual const VectorSet *asVectorSet(void) const;

  virtual const ListSet   *asListSet  (void) const;

  virtual const CoSet     *asCoSet    (void) const;

  // Hash the set.  Sets of different types but identical elements will NOT

  // hash the same.  Same set type, same elements WILL hash the same.

  virtual int hash() const = 0;

protected:

  friend class SetI;

  friend class CoSet;

  virtual class SetI_ *iterate(uint&) const=0;

  // Need storeage for the set

  Arena *_set_arena;

};

typedef Set&((*Set_Constructor)(Arena *arena));

extern Set &ListSet_Construct(Arena *arena);

extern Set &VectorSet_Construct(Arena *arena);

extern Set &SparseSet_Construct(Arena *arena);

//------------------------------Iteration--------------------------------------

// Loop thru all elements of the set, setting "elem" to the element numbers

// in random order.  Inserted or deleted elements during this operation may

// or may not be iterated over; untouched elements will be affected once.

// Usage:  for( SetI  i(s); i.test(); i++ ) { body = i.elem; }   ...OR...

//         for( i.reset(s); i.test(); i++ ) { body = i.elem; }

class SetI_ : public ResourceObj {

protected:

  friend class SetI;

  virtual ~SetI_();

  virtual uint next(void)=0;

  virtual int test(void)=0;

};

class SetI {

protected:

  SetI_ *impl;

public:

  uint elem;                    // The publically accessible element

  SetI( const Set *s ) { impl = s->iterate(elem); }

  ~SetI() { delete impl; }

  void reset( const Set *s ) { delete impl; impl = s->iterate(elem); }

  void operator ++(void) { elem = impl->next(); }

  int test(void) { return impl->test(); }

};