/*+
−
 * Copyright 1997 Sun Microsystems, Inc.  All Rights Reserved.+
−
 * 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,+
−
 * CA 95054 USA or visit www.sun.com if you need additional information or+
−
 * have any questions.+
−
 *+
−
 */+
−
+
−
#ifndef _SET_+
−
#define _SET_+
−
// Sets - An Abstract Data Type+
−
+
−
// Should not manually include these in AVM framework. %%%%% - Ungar+
−
// #ifndef _PORT_+
−
// #include "port.hpp"+
−
// #endif // _PORT_+
−
//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(); }+
−
};+
−
+
−
#endif // _SET_+
−